알파 베타 전정이있는 전이 테이블

Question

전치 테이블을 사용하여 알파 베타 전정을 구현하려는 중, 위키 백과에서 알고리즘의 의사 코드를 찾았습니다. 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

사용할 전위 테이블과 가지 치기 알파 베타에 대한 다른 구현이 있습니다. 예를 들어 Marsland에서 하나 A REVIEW OF GAME-TREE PRUNING, Breuker : Memory versus Search in Games과의 Carolus는 : 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 기사의 토론 페이지에서 더 많은 논의가 있습니다.