数据集连接4评估算法

Question

我的工作是一个连接4人工智能，并看到许多人使用这数据集，包含所有的法律立场8层，以及他们的最终结果。

我使用一个标准的minimax和alpha/beta剪枝作为我的搜索算法。似乎这个数据集可能真的会对我的人工智能有用。然而，我正试图找到实现它的最佳方法。我认为最好的方法可能是处理列表，并使用董事会状态作为最终结果的散列(赢、输、平局)。

设计一个AI来使用这样的数据集的最好方法是什么？是我的想法，哈希董事会状态，并使用它在传统的搜索算法(例如。在正确的轨道上吗？还是有更好的方法？

Update：我最终将大移动数据库转换成普通的测试格式，其中1表示X和-1。然后我使用了董事会状态的字符串，一个代表最终结果的整数，并将其放入std::unsorted_map中(关于遇到的问题，请参见带有无序映射的堆栈溢出 )。这张地图的性能很好。它建造得很快，查找速度也很快。然而，我从来没有完全正确的搜索。当游戏中的回合数小于8，然后切换到一个普通的α-β时，这是解决问题的正确方法吗？

Answer 1

你的方法似乎是正确的。。

对于前8个移动，使用alpha-beta算法，并使用查找表来评估每个节点在深度8处的值。

一旦你“筋疲力尽”的表(超过8移动在游戏中)-你应该切换到常规的α-β算法，以终端状态(在游戏树中的叶子)结束。

这是非常有用的，因为：

请记住，搜索树的复杂性是O(B^d)，其中B是分支因子(每个状态可能移动的次数)，d是结束前所需的深度。

通过使用这种方法，可以有效地减少最大等待时间的B和d (需要计算最长的移动)，因为：

1. 您的最大深度缩小了显着地缩小到d-8 (仅对最后的移动)，有效地减少了d！
2. 分支因素本身倾向于在这个游戏中经过几次移动后收缩(许多动作变得不可能或导致失败，不应该被探索)，这减少了B。
3. 在第一步中，您还将开发节点的数量减少到B^8而不是B^d。

因此，由于这些-最大等待时间显着减少了使用这种方法。

注意:如果您发现优化不够-您可以随时展开您的查找表( 9,10，.当然，它将以指数方式增加所需的空间--这是一种权衡，您需要检查并选择哪些最适合您的需要(如果内存不够，甚至可以将整个游戏存储在文件系统中)。