我正在学习 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 剪枝。谁能帮忙？
最佳答案
在 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 窗口(不是 -INFINITY 和 +INFINITY)开始的额外优化。但是，如果您的假设被证明是错误的，您必须使用更开放的 search window 重新开始搜索。 .
关于algorithm - 修改 Minimax 为 Alpha-Beta 剪枝伪代码，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41182117/