修改 Minimax 为 Alpha-Beta 剪枝伪代码

Question

我正在学习 Alpha-Beta 伪代码，我想为 Alpha Beta 剪枝.

编写一个最简单的伪代码

我写了Minimax的伪代码:

function minimax(node, depth)
     if node is a terminal node or depth ==0
          return the heuristic value of node
     else 
          best = -99999
     for child in node
          best = max(best, -minimax(child, depth-1))
     return best

但是，我不知道如何将其修改为alpha-beta剪枝。有人可以帮忙吗？

Answer 1

在 Alpha-Beta 中，您会跟踪一个位置的保证分数。如果发现比对手在其先前位置（之前的一手）已经保证的分数更好的着法，您可以立即停止。

从技术上讲，每一方都会跟踪其下界得分（alpha），而您可以访问对手的下界得分（beta）。

以下伪代码未经测试，但思路如下：

function alphabeta(node, depth, alpha, beta)
     if node is a terminal node or depth ==0
          return the heuristic value of node
     else 
          best = -99999
     for child in node
          best = max(best, -alphabeta(child, depth-1, -beta, -alpha))
          if best >= beta
                return best
          if best > alpha
                alpha = best
     return best

在开始搜索时，您可以将 alpha 设置为 -INFINITY，将 beta 设置为 +INFINITY。严格来说，草图算法不是 alpha-beta 而是 Negamax。两者是相同的，所以这只是一个实现细节。

请注意，在 Alpha-Beta 中，移动顺序至关重要。如果大多数时候，你从最好的着法开始，或者至少是非常好的着法，你应该会看到相对于 Minimax 的巨大改进。

从受限的 alpha beta windows（不是 -INFINITY 和 +INFINITY）开始的额外优化。但是，如果你的假设被证明是错误的，你必须以更开放的方式重新开始搜索 search window.

修改 Minimax 为 Alpha-Beta 剪枝伪代码

Modify Minimax to Alpha-Beta pruning pseudo code

algorithm

chess

artificial-intelligence

pseudocode

minimax