将minimax修改为alpha-beta修剪伪代码

Question

我正在学习alpha-beta pseudo代码，我想为 alpha beta beta pruning 编写最简单的伪代码。

我为 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。严格来说，素描的算法不是α-beta，而是Negamax。两者都是相同的，因此这只是一个实现细节。

请注意，在Alpha-Beta中，移动排序至关重要。如果在大多数情况下，您从最佳动作开始，或者至少是一个很好的举动，您应该看到对Minimax的巨大进步。

从限制的alpha beta窗口开始的额外优化（不是-Infinity和 Infinity）。但是，如果您的假设结果错误，则必须使用更开放的搜索窗口重新启动搜索。