带 alpha beta 修剪的转置表

Question

我正在尝试用转置表实现 alpha beta 剪枝，我在维基百科中找到了该算法的伪代码：https://en.wikipedia.org/wiki/Negamax#cite_note-Breuker-1 但是我相信这个 psudocode 是错误的，我认为 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

Answer 1

alpha beta 剪枝有不同的实现方式，可以使用转置表。例如来自 Marsland 的那个：A REVIEW OF GAME-TREE PRUNING, Breuker: Memory versus Search in Games and Carolus: Alpha-Beta with Sibling Prediction Pruning in Chess

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

Marsland transposition table logic is equivalent when alphaOrig in Breuker stores α after the transposition table lookup (rather than before). But consider the following case during a negamax function call:

transposition table lookup updates α because it's a "lower bound" (Breuker: alphaOrig < α Marsland: alphaOrig = α)

the move evaluation returns the same as unchanged α for bestValue (score)

update the node's transposition table entry with the same bestValue (score)

In Breuker's logic, the node's transposition table entry will update with "exact" flag (since alphaOrig < bestValue < β). In Marsland, the update will have "upper bound" flag (since score ≤ α). Optimally, the flag for the score should be "exact" rather than alternating between upper and lower bound. So I think Breuker's version is better? In Carolus, there's no alphaOrig and no equivalent. alpha updates during move evaluation. In this case, after move evaluation, best can never be greater than alpha, and setting "exact" flag for the transposition table entry is impossible.

Negamax 文章的讨论页上对此有更多讨论。

带 alpha beta 修剪的转置表

Transpositional tables with alpha beta pruning

pseudocode

alpha-beta-pruning

negamax