3

転置テーブルを使用してアルファ ベータ プルーニングを実装しようとしています。ウィキペディアでアルゴリズムの疑似コードを見つけました: 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