java - 如何使用 alpha beta pruning 实现迭代加深

Question

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

Answer 1

好吧，迭代深化并不是很难实现。如果你已经有一个函数来执行搜索，我们称之为它alphaBetaAtRoot，它执行一个固定距离的搜索，你只需重复调用它，从距离 1 开始：

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

不过，重要的是您实现了一个转置表。否则，您将不会从更好的移动排序中受益，因为每次搜索都将从零知识开始。

Answer 2

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