带有记忆的Minimax算法？
Minimax algorithm with memoization?
我正在尝试使用 javascript 中的 minimax 算法实现连接四个 AI。目前，它非常慢。除了我将实施的 alpha-beta 修剪之外，我想知道将游戏状态散列到
是否值得
- 他们的启发式评估
- 下一个最佳着法
我可以立即明白为什么 2 会有用，因为有很多方法可以达到相同的游戏状态，但我想知道我是否还必须对当前深度进行哈希处理才能使它起作用。
例如，如果我达到此状态的深度为 3（所以只说再向前看 4 步）与深度为 2 并向前看 5 步，我可能会得出不同的答案。这是否意味着我应该考虑哈希的深度？
我的第二个问题是散列板对他们的评估是否值得。我需要 O(n) 的时间来构建我的散列，而 O(n) 的时间来评估一个板（尽管它实际上更像是 O（2 或 3n））。游戏状态通常是散列到他们的评估中，还是这是矫枉过正？感谢您的帮助
每当您对状态值进行哈希处理（使用启发式算法）时，您都需要了解有关评估该状态的深度的信息。这是因为 the value is 0.1 at depth 1 和 the value is 0.1 at depth 20 之间有很大的区别。在第一种情况下，我们几乎没有调查 space，所以我们不确定会发生什么。在第二种情况下，我们已经做了大量的工作，所以我们知道我们在说什么。
问题是，对于某些游戏，我们不知道位置的深度是多少。例如国际象棋。但是在connect 4中，看一个位置就知道深度是多少。
对于connect 4，这里的深度是14（只放了14个圆圈）。所以你不需要存储深度。
至于你是否真的需要散列状态或重新评估它。很明显，可以通过许多游戏路径到达此游戏中的位置，因此您希望散列会有所帮助。重要的问题是 creating/looking 在散列上的权衡以及您的评估函数的强度。如果看起来它做了很多工作 - 对其进行哈希处理和基准测试。
最后一个建议。您提到了 alpha-beta，它比您所在阶段的散列更有用（而且实施起来并不难）。您可以更进一步，为您的 alpha-beta 实施 move ordering。如果我是你，我会这样做，然后才实现散列。
我正在尝试使用 javascript 中的 minimax 算法实现连接四个 AI。目前，它非常慢。除了我将实施的 alpha-beta 修剪之外，我想知道将游戏状态散列到
是否值得- 他们的启发式评估
- 下一个最佳着法
我可以立即明白为什么 2 会有用，因为有很多方法可以达到相同的游戏状态，但我想知道我是否还必须对当前深度进行哈希处理才能使它起作用。 例如，如果我达到此状态的深度为 3（所以只说再向前看 4 步）与深度为 2 并向前看 5 步，我可能会得出不同的答案。这是否意味着我应该考虑哈希的深度？
我的第二个问题是散列板对他们的评估是否值得。我需要 O(n) 的时间来构建我的散列，而 O(n) 的时间来评估一个板（尽管它实际上更像是 O（2 或 3n））。游戏状态通常是散列到他们的评估中，还是这是矫枉过正？感谢您的帮助
每当您对状态值进行哈希处理（使用启发式算法）时，您都需要了解有关评估该状态的深度的信息。这是因为 the value is 0.1 at depth 1 和 the value is 0.1 at depth 20 之间有很大的区别。在第一种情况下，我们几乎没有调查 space，所以我们不确定会发生什么。在第二种情况下，我们已经做了大量的工作，所以我们知道我们在说什么。
问题是，对于某些游戏，我们不知道位置的深度是多少。例如国际象棋。但是在connect 4中，看一个位置就知道深度是多少。
对于connect 4，这里的深度是14（只放了14个圆圈）。所以你不需要存储深度。
至于你是否真的需要散列状态或重新评估它。很明显，可以通过许多游戏路径到达此游戏中的位置，因此您希望散列会有所帮助。重要的问题是 creating/looking 在散列上的权衡以及您的评估函数的强度。如果看起来它做了很多工作 - 对其进行哈希处理和基准测试。
最后一个建议。您提到了 alpha-beta，它比您所在阶段的散列更有用（而且实施起来并不难）。您可以更进一步，为您的 alpha-beta 实施 move ordering。如果我是你，我会这样做，然后才实现散列。