棋盘游戏AI设计：选择STL数据容器

Question

我正在为一个简单的棋盘游戏编写一个AI引擎。现在我的简单实现是遍历所有可选的棋盘状态，根据游戏规则和我的简单算法对每个状态进行加权，然后根据该得分选择最佳棋步。由于评分算法是完全无状态的，因此我希望通过创建一些（所有？）棋盘配置的哈希表来节省计算时间，并从那里获得得分而不是实时计算得分。

我的问题是：
1.我的方法是否合乎逻辑？ （如果没有，你能给我一些提示，以便更好吗？:)）
2.什么是最适合我的需求的线程安全的STL容器？我正在考虑使用char数组（板配置）作为关键字，并将得分作为值。
3.你可以给我一些提示让我的AI成为一个杀手锏？ :)

编辑：更多信息：
董事会是10x10，有两个玩家，每个有10个兵。规则很像跳棋。

Answer 1

是的，通常会将评估板存储到散列表中，它被称为换位表。一个STL容器可能是std::vector。一般来说，你必须创建一个哈希函数（例如zobrist hashing）。散列函数计算特定板的散列值。 hash_value modulo HASH_TABLE_SIZE的结果将是std::vector的索引。

换位表项可不仅仅是板得分和最佳移动存储更多的信息，你也可以存储深度董事会评估其如果评价分数（如果你是做α-β搜索）是

• 确切
• 一个上界
• 或下界

我可以推荐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

你符合逻辑的做法是好的，你应该阅读，也许尝试使用极小的算法：

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

我认为，除了从井字游戏状态的数量将是太大了，你应该尽快地进行计数。

Answer 3

国际象棋和跳棋可以用这种方法来实现，但它不是一个我d推荐。

如果你走这条路线，那么我会使用某种形式的树。如果你仔细想想，一举一动都会减少移动之前存在的全部可能性。另外，这允许难度等级。不要总是挑选最好的，有时会选择第二好的。

我不会走这条路的原因是它一般不好玩。人们直觉地认识到这一点，他们认为这是不公平的。我写了一个无与伦比的连接4游戏，但是基于规则而不是基于游戏棋盘状态。它很无聊。一举一动都得到了同样的回应。我认为这也是这种方法所发生的。另外，这取决于你为什么这样做。如果是为了学习人工智能，那么很少人工智能就是这样完成的。如果它有一个有趣的游戏，它通常不是。如果是因为Deep Blue的原因，为了扩展计算机可以执行的限制，那么确定。

我会使用一个基于个人AI的片段，然后选择一个最引人注目的论据，或者我会使用爬山的变体，并将一种策略的高度放入董事会。这取决于多少支持件给对方。对于个人AI我会使用神经网络。

战略身高系统对于FPS来说很好，因为士兵们想知道哪条路线最有效。神经网络给每个实体更多的个性。你甚至可以使用级联神经网络，其中一个是策略，第二个是个性。