具有 alpha beta 剪枝的转置表

Question

我正在尝试使用换位表实现 alpha beta 剪枝，我在维基百科中找到了该算法的伪代码：https: //en.wikipedia.org/wiki/Negamax#cite_note-Breuker-1 \n但是我相信这psudocode 是错误的，我认为 alphaOrig 是无用的，而不是：

\n\n

if bestValue \xe2\x89\xa4 alphaOrig\n        ttEntry.Flag := UPPERBOUND\n

\n\n

它应该是：

\n\n

if bestValue \xe2\x89\xa4 \xce\xb1\n        ttEntry.Flag := UPPERBOUND\n

\n\n

谁能确认我是否正确或向我解释为什么我错了，谢谢！

\n\n

这里是伪代码：

\n\n

function negamax(node, depth, \xce\xb1, \xce\xb2, color)\n\nalphaOrig := \xce\xb1\n\n// Transposition Table Lookup; node is the lookup key for ttEntry\nttEntry := TranspositionTableLookup( node )\nif ttEntry is valid and ttEntry.depth \xe2\x89\xa5 depth\n    if ttEntry.Flag = EXACT\n        return ttEntry.Value\n    else if ttEntry.Flag = LOWERBOUND\n        \xce\xb1 := max( \xce\xb1, ttEntry.Value)\n    else if ttEntry.Flag = UPPERBOUND\n        \xce\xb2 := min( \xce\xb2, ttEntry.Value)\n    endif\n    if \xce\xb1 \xe2\x89\xa5 \xce\xb2\n        return ttEntry.Value\nendif\n\nif depth = 0 or node is a terminal node\n    return color * the heuristic value of node\n\nbestValue := -\xe2\x88\x9e\nchildNodes := GenerateMoves(node)\nchildNodes := OrderMoves(childNodes)\nforeach child in childNodes\n    v := -negamax(child, depth - 1, -\xce\xb2, -\xce\xb1, -color)\n    bestValue := max( bestValue, v )\n    \xce\xb1 := max( \xce\xb1, v )\n    if \xce\xb1 \xe2\x89\xa5 \xce\xb2\n        break\n\n// Transposition Table Store; node is the lookup key for ttEntry\nttEntry.Value := bestValue\nif bestValue \xe2\x89\xa4 alphaOrig\n    ttEntry.Flag := UPPERBOUND\nelse if bestValue \xe2\x89\xa5 \xce\xb2\n    ttEntry.Flag := LOWERBOUND\nelse\n    ttEntry.Flag := EXACT\nendif\nttEntry.depth := depth \nTranspositionTableStore( node, ttEntry )\n\nreturn bestValue\n

\n

Answer 1

alpha beta 剪枝有不同的实现方式，并提供转置表。例如来自 Marsland 的一篇：A REVIEW OF GAME-TREE PRUNING、Breuker：Memory vs Search in Games和 Carolus： Alpha-Beta with Sibling Prediction Pruning in Chess

\n

对于我的回答，我将引用谈话的片段：Negamax：

\n

\n

当 Breuker 中的 alphaOrig 在转置表查找之后（而不是之前）存储 \xce\xb1 时，Marsland 转置表逻辑是等效的。但在 negamax 函数调用期间请考虑以下情况：

\n

\n
• 换位表查找更新 \xce\xb1 因为它是“下限”（Breuker：alphaOrig < \xce\xb1Marsland：alphaOrig = \xce\xb1：）
\n
• 移动评估返回与未更改相同\xce\xb1对于 bestValue（分数），
\n
• 使用相同的 bestValue（分数）更新节点的转置表条目
\n

\n

在 Breuker 的逻辑中，节点的转置表条目将使用“精确”标志进行更新（自 以来alphaOrig < bestValue < \xce\xb2）。在 Marsland，更新将具有“上限”标志（自score \xe2\x89\xa4 \xce\xb1）。最佳情况下，分数的标志应该是“精确的”，而不是在上限和下限之间交替。所以我认为 Breuker 的版本更好？\n在 Carolus 中，没有 alphaOrig，也没有等效的版本。阿尔法在移动评估期间更新。在这种情况下，在移动评估之后，best永远不会大于alpha，并且为换位表条目设置“精确”标志是不可能的。

\n

\n

在 Negamax 文章的讨论页面上还有更多关于此的讨论。

\n