我正在开发一个连接4的AI，看到很多人都在使用这个数据集，其中包含了8步棋的所有合法位置及其最终结果。

我使用带有alpha/beta剪枝的标准极小化极大算法作为我的搜索算法。看起来这个数据集对我的AI非常有用。然而，我正在寻找实现它的最佳方法。我认为最好的方法可能是处理列表，并使用棋盘状态作为最终结果（胜、负、平）的哈希值。

设计AI使用这样的数据集的最佳方法是什么？我关于哈希棋盘状态，并在传统搜索算法（例如极小化极大）中使用它的想法是否正确？还是有更好的方法？

更新：我最终将大型移动数据库转换为纯文本格式，其中1代表X，-1代表O。然后我使用棋盘状态的字符串和表示最终结果的整数，并将其放入std::unsorted_map中（参见Stack Overflow With Unordered Map了解我遇到的问题）。映射的性能非常出色。它构建得很快，查找速度也很快。然而，我始终没有完全正确地进行搜索。正确的方法是否是在游戏轮数少于8时搜索数据库，然后切换到常规的alpha-beta算法？

回答：

你的方法似乎是正确的。

在前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,…第一步），当然这将指数级增加所需的空间 – 这是一个你需要检查并选择最适合你需求的权衡（如果主内存不够，甚至可以考虑将整个游戏存储在文件系统中）