3

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

if bestValue ≤ alphaOrig
        ttEntry.Flag := UPPERBOUND

它应该是：

if bestValue ≤ α
        ttEntry.Flag := UPPERBOUND

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

这里的伪代码：

function negamax(node, depth, α, β, color)

alphaOrig := α

// Transposition Table Lookup; node is the lookup key for ttEntry
ttEntry := TranspositionTableLookup( node )
if ttEntry is valid and ttEntry.depth ≥ depth
    if ttEntry.Flag = EXACT
        return ttEntry.Value
    else if ttEntry.Flag = LOWERBOUND
        α := max( α, ttEntry.Value)
    else if ttEntry.Flag = UPPERBOUND
        β := min( β, ttEntry.Value)
    endif
    if α ≥ β
        return ttEntry.Value
endif

if depth = 0 or node is a terminal node
    return color * the heuristic value of node

bestValue := -∞
childNodes := GenerateMoves(node)
childNodes := OrderMoves(childNodes)
foreach child in childNodes
    v := -negamax(child, depth - 1, -β, -α, -color)
    bestValue := max( bestValue, v )
    α := max( α, v )
    if α ≥ β
        break

// Transposition Table Store; node is the lookup key for ttEntry
ttEntry.Value := bestValue
if bestValue ≤ alphaOrig
    ttEntry.Flag := UPPERBOUND
else if bestValue ≥ β
    ttEntry.Flag := LOWERBOUND
else
    ttEntry.Flag := EXACT
endif
ttEntry.depth := depth 
TranspositionTableStore( node, ttEntry )

return bestValue
4

1 回答 1

3

alpha beta 修剪有不同的实现，可以使用转置表。例如来自 Marsland: A REVIEW OF GAME-TREE PRUNING 、Breuker: Memory vs Search in Games和 Carolus: Alpha-Beta with Sibling Prediction Pruning in Chess

对于我的回答，我将引用Talk:Negamax页面的片段：

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

  • 转置表查找更新 α 因为它是“下限”（Breuker：alphaOrig < αMarsland alphaOrig = α：）
  • 移动评估返回与 bestValue 不变的相同α（分数）
  • 使用相同的 bestValue（分数）更新节点的转置表条目

在 Breuker 的逻辑中，节点的转置表条目将更新为“精确”标志（因为alphaOrig < bestValue < β）。在 Marsland，更新将具有“上限”标志（自score ≤ α）。理想情况下，分数的标志应该是“精确的”，而不是在上限和下限之间交替。所以我认为布鲁克的版本更好？在 Carolus 中，没有 alphaOrig 和等价物。移动评估期间的 alpha 更新。在这种情况下，在移动评估之后，best 永远不会大于 alpha，并且为转置表条目设置“精确”标志是不可能的。

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

于 2017-11-04T08:28:59.460 回答