2

我正在开发一个 connect 4 AI，并且看到很多人都在使用这个数据集，其中包含 8 层的所有法律职位及其最终结果。

我使用带有 alpha/beta 修剪的标准 minimax 作为我的搜索算法。看起来这个数据集可能对我的 AI 非常有用。但是，我正在尝试找到实现它的最佳方法。我认为最好的方法可能是处理列表，并使用棋盘状态作为最终结果（赢、输、平）的哈希值。

设计 AI 以使用这样的数据集的最佳方法是什么？我的想法是散列棋盘状态，并在正确的轨道上在传统的搜索算法（例如极小极大）中使用它吗？还是有更好的方法？

更新：我最终将大型移动数据库转换为简单的测试格式，其中 1 代表 X 和 -1 O。然后我使用了一个棋盘状态字符串，一个代表最终结果的整数，并将其放入std::unsorted_map（见Stack Overflow With Unordered Map来解决我遇到的问题）。地图的表现非常出色。它构建得很快，而且查找速度很快。但是，我从来没有完全正确地进行搜索。当游戏中的回合数少于 8 时，仅搜索数据库，然后切换到常规的 alpha-beta 是解决问题的正确方法吗？

4

1 回答 1

3

你的方法似乎是正确的。

对于前 8 步，使用 alpha-beta 算法，并使用查找表来评估每个节点在深度 8 处的值。
一旦你“用尽”表（在游戏中超过 8 步） - 你应该切换到常规的 alpha-beta 算法，以终止状态（游戏树中的叶子）结束。

这非常有帮助，因为：
请记住，搜索树的复杂性是O(B^d)-B分支因子（每个状态可能移动的数量）在哪里，并且d是直到结束所需的深度。
通过使用这种方法，您可以有效地减少B最大d等待时间（需要计算最长的移动），因为：

  1. 您的最大深度显着缩小到d-8（仅适用于最后一步），有效减少d！
  2. 在这个游戏中，分支因素本身往往会在几个动作后缩小（许多动作变得不可能或导致失败，不应该探索），这会减少B。
  3. 在第一步中，您将开发节点的数量也缩小到B^8而不是B^d.

因此，正因为如此 - 使用这种方法可以显着减少最大等待时间。

另请注意：如果您发现优化不够 - 您可以随时扩展查找表（到 9,10，... 第一步），当然它会以指数方式增加所需空间 - 这是您需要检查的权衡并选择最能满足您需求的东西（如果主内存不够，甚至可以将整个游戏存储在文件系统中）

于 2012-12-04T22:22:45.567 回答