棋类游戏AI设计:选择STL数据容器

Question

我正在为一个简单的棋盘游戏编写一个AI引擎。我现在的简单实现是遍历所有可选的棋盘状态，根据游戏规则和我的简单算法对每个状态进行加权，并根据该分数选择最佳走法。

由于评分算法是完全无状态的，我想通过创建一个哈希表来节省计算时间。板配置，并从那里获得分数，而不是计算它的飞行。

我的问题是：

1. 我的方法合乎逻辑吗？(如果不是，你能给我一些改进的技巧吗？：)
2. 什么是最适合我需要的线程安全的容器？我正在考虑使用字符数组(板配置)作为键，分数作为值。
3. 你能给出一些让我的AI成为杀手级AI的技巧吗？:)

编辑:更多信息：

棋盘是10x10，有两个玩家，每个玩家都有10个棋子。规则很像跳棋。

Answer 1

是的，将评估板存储到哈希表中是很常见的，这就是所谓的转置表。STL容器可以是std::vector。一般来说，你必须创建一个散列函数(例如，zobrist散列)。散列函数计算特定板的散列值。hash_value modulo HASH_TABLE_SIZE的结果将是std::vector的索引。

转置表格条目可以包含更多的信息，而不仅仅是棋盘得分和最佳移动，您还可以存储棋盘被评估的深度，以及评估得分(如果您正在进行alpha-beta搜索)是

• exact
• a上限
• 或下限

我可以推荐chessprogramming站点，在那里我学到了很多。查找术语alpha-beta、转置表、zobrist散列、迭代加深。还有一些很好的论文可以进一步阅读：

• TA Marsland - Computer Chess and Search
• TA Marsland - A Review of Game Tree Pruning
• AL Zobrist - A New Hashing Method with Application for Game Playing
• J Schaeffer - The games Computers (and People) Play

Answer 2

你的逻辑方法是好的，你应该阅读，也许可以尝试使用Minimax算法：

http://en.wikipedia.org/wiki/Minimax

我认为除了tic tac toe游戏的状态数量太多之外，你应该努力让计数变得更快。

Answer 3

国际象棋和跳棋可以用这种方法来完成，但我不推荐使用这种方法。

如果你走这条路，我会用某种形式的树。如果你仔细想想，每一次移动都会减少在移动之前存在的总的可能性。此外，这允许难度级别。不要总是选择最好的，有时选择第二好的。

我不会走这条路的原因是它通常不好玩。人们凭直觉发现这一点，他们觉得这是不公平的。我写了一个连接4游戏，它是无与伦比的，但它是基于规则而不是基于游戏板状态的。太无聊了。每一个举动都得到了相同的回应。我认为这也是这种方法所发生的事情。另外，这取决于你为什么要这样做。如果要学习AI，很少有AI是这样做的。如果它是为了玩一款有趣的游戏，那么它通常不是。如果它是出于制作“深蓝”的原因，为了拓展计算机所能做的事情的极限，那么当然。

我要么使用一个基于个人的人工智能，然后选择一个最有说服力的，要么我会使用爬山的变体，并在棋盘上放置一种策略高度。这取决于各个部件之间相互支持的程度。对于个人人工智能，我会使用神经网络。

战略高度系统对于士兵想要知道哪条路径有最多掩护的FPS来说是很好的。神经网络赋予每个实体更多的个性。您甚至可以使用级联神经网络，其中一个是策略，第二个是个性。