带记忆化的极小化极大算法？

Question

6

我正在尝试使用JavaScript中的minimax算法实现连接四个人工智能，但目前速度非常慢。除了我将要实现的alpha-beta剪枝之外，我想知道是否值得对游戏状态进行哈希处理：

我可以立即看出为什么2会很有用，因为有许多方法可以到达相同的游戏状态，但我想知道我是否还必须对当前深度进行哈希处理才能使其正常工作。

例如，如果我以深度3到达此状态（所以只需要再看4个移动），而不是深度2并且需要再看5个移动，我可能会得出不同的答案。这是否意味着我应该在哈希时考虑深度？

我的第二个问题是，将棋盘哈希到它们的评估值是否值得。构建我的哈希需要O(n)时间，并且评估棋盘需要O(n)时间（尽管实际上更像是O(2或3n)）。游戏状态通常被哈希到它们的评估值吗？还是这太过于复杂了？感谢任何帮助。

- Jared

1

棋盘位置中的深度不是固有的吗？如果棋盘上有10个棋子，则您可以说已经走了五步。 - Michael Lorton

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Salvador Dali · Accepted Answer

每当您使用启发式算法对状态的值进行哈希时，都需要了解此状态评估的深度信息。这是因为“在深度1处值为0.1”和“在深度20处值为0.1”之间存在很大差异。在第一种情况下，我们几乎没有探索空间，所以我们不太确定会发生什么。在第二种情况下，我们已经完成了大量的工作，所以我们有点知道我们在谈论什么。

问题是，对于某些游戏，我们不知道某个位置的深度是多少。例如国际象棋。但是在连四中，查看一个位置，您知道深度是多少。

对于连四游戏，这里的深度为14（只放了14个圆）。因此你不需要存储深度。

至于是否必须哈希状态或重新评估状态。显然，在这个游戏中可以通过许多游戏路径到达某个位置，因此你期望哈希会有所帮助。重要问题是创建/查看哈希的权衡以及你的评估函数有多么密集。如果它看起来做了很多工作-就哈希它并进行基准测试。

最后一个建议。你提到了alpha-beta，这比在你的阶段使用哈希更有帮助（而且实现也不难）。你可以进一步实现移动排序move ordering来优化alpha-beta。如果我是你，我会先这样做，然后才会实现哈希。