如何通过 alpha beta 剪枝实现迭代加深

Question

我正在编写一个玩 Dots and Boxes 的程序，我想通过在迭代深化方案中根据它们的启发值对我在 alphaBeta 中考虑的动作进行排序来提高我的时间效率。本质上，我想进入搜索树，在每次迭代中增加深度，并使用 alphaBeta 评估每个节点。在每次连续迭代中，我考虑节点的顺序将由前一次迭代中节点的启发式值决定。但是，我无法理解这将如何实施。有人可以提供关于标准 alphaBeta 程序如何适应使用迭代加深进行搜索的伪代码吗？谢谢！

Answer 1

嗯，Iterative Deepening实施起来并不难。如果你已经有一个执行搜索的函数，我们称它为alphaBetaAtRoot，它执行固定距离的搜索，你只需重复调用它，从距离1开始：

for(int distance = 1; distance < MAX_DISTANCE && !outOfTime(); distance++) {
  bestmove = alphaBetaAtRoot(position, distance);
}
play(bestmove);

不过，重要的是您实施 Transposition Table。否则，您将无法从更好的移动顺序中获益，因为每次搜索都是从零知识开始的。

Answer 2

我找到了以下 link：https://github.com/nealyoung/CS171/blob/master/AI.java 希望对你有帮助。