algorithm - 带有内存的Minimax算法？

Question

我正在尝试使用 javascript 中的极小极大算法实现连接四个 AI。目前，它非常慢。除了我将实现的 alpha-beta 修剪之外，我想知道是否值得将游戏状态散列到

1. 他们的启发式评估
2. 下一个最佳行动

我可以立即明白为什么 2 会有用，因为有很多方法可以达到相同的游戏状态，但我想知道我是否还必须对当前深度进行哈希处理才能使它起作用。例如，如果我达到此状态的深度为 3(所以只说再向前看 4 步)与深度为 2 并向前看 5 步，我可能会得出不同的答案。这是否意味着我应该考虑哈希的深度？

我的第二个问题是散列板对他们的评估是否值得。我需要 O(n) 的时间来构建我的散列，而 O(n) 的时间来评估一个板(尽管它实际上更像是 O(2 或 3n))。游戏状态通常是散列到他们的评估中，还是这是矫枉过正？感谢您的帮助

Answer 1

每当您对状态值进行哈希处理(使用启发式算法)时，您都需要了解有关评估该状态的深度的信息。这是因为 the value is 0.1 at depth 1 和 the value is 0.1 at depth 20 之间存在很大差异。在第一种情况下，我们几乎没有调查过这个空间，所以我们非常不确定会发生什么。在第二种情况下，我们已经完成了大量工作，所以我们有点知道我们在说什么。

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

对于连接 4，此处的深度为 14(仅放置了 14 个圆圈)。所以你不需要存储深度。

至于你是否真的需要散列状态或重新评估它。很明显，可以通过许多游戏路径到达此游戏中的位置，因此您希望散列会有所帮助。重要的问题是创建/查看哈希与评估函数的强度之间的权衡。如果看起来它做了很多工作 - 对其进行散列和基准测试。

最后一个建议。您提到了 alpha-beta，它比您所在阶段的散列更有用(而且实现起来并不难)。您可以进一步实现 move ordering为您的 alpha-beta。如果我是你，我会这样做，只有在那之后我才会实现散列。