アルファベータ刈り込みの転置テーブル

Question

転置テーブルを使ったアルファベータプルーニングを実装しようとしていますが、私はアルゴリズムの擬似コードをwikipediaで見つけました：https://en.wikipedia.org/wiki/Negamax#cite_note-Breuker-1 しかし、私はこのpsudocodeが間違っていると信じています。そして代わりに：

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

利用可能移調テーブルを持つアルファ・ベータ法のための異なる実装があります。例えば、Marslandから1：A REVIEW OF GAME-TREE PRUNING、Breuker：Memory versus Search in Gamesとカロルスは：Alpha-Beta with Sibling Prediction Pruning in Chess

は私の答えのために私はTalk:Negamaxページの抜粋を引用します：

Marsland転置テーブルロジックが同等であるときalphaOrig Breuker店でαを転置テーブルルックアップの後に（以前よりも）使用します。しかしnegamax関数呼び出し中に次のような場合を考えてみましょう。それは「下限」ですので、

• 転置テーブルルックアップの更新がα（Breuker：alphaOrig < α Marslandを：alphaOrig = α）
• 移動評価は用変わらずαと同じ返しますbestValue（スコア）
• 同じbestValue（スコア）Breukerのロジックで

と更新ノードの転置テーブルエントリ、ノードの転置テーブル・エントリはexac」に更新しますtフラグ（alphaOrig < bestValue < β以降）。 Marslandでは、アップデートには "上限"フラグが付きます（score ≤ α以降）。最適には、スコアのフラグは、上限と下限の間で交替するのではなく、「正確」でなければなりません。だから私はBreukerのバージョンが良いと思いますか？ CarolusにはalphaOrigはなく、同等のものはありません。移動評価中のアルファ更新。この場合、移動の評価後、最良の値はアルファより大きくなることはありません。また、転置テーブルのエントリに「正確な」フラグを設定することは不可能です。

Negamaxの記事のトークページでこれに関するさらに議論があります。