带记忆的极小极大算法？

Question

我正在尝试使用 JavaScript 中的极小极大算法实现连接四个人工智能。目前，速度非常慢。除了我将实现的 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，这比您所在阶段的散列更有帮助（而且实现起来并不难）。您可以更进一步，为您的 alpha-beta 实施移动排序。如果我是你，我就会这样做，并且只有在那之后我才会实现哈希。