如何使用 alpha beta 修剪实现迭代深化

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我希望这对你有所帮助。