如何使用 alpha beta 修剪实现转置表

Question

我试图在我的negamax中实现转置表。但首先我想理解伪代码中的所有思想:

' 函数 negamax（节点， 深度， α， β， 颜色） 是 alphaOrig ：= α

(* Transposition Table Lookup; node is the lookup key for ttEntry *)
ttEntry := transpositionTableLookup(node)
if ttEntry is valid and ttEntry.depth ≥ depth then
    if ttEntry.flag = EXACT then
        return ttEntry.value
    else if ttEntry.flag = LOWERBOUND then
        α := max(α, ttEntry.value)
    else if ttEntry.flag = UPPERBOUND then
        β := min(β, ttEntry.value)

    if α ≥ β then
        return ttEntry.value

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

childNodes := generateMoves(node)
childNodes := orderMoves(childNodes)
value := −∞
for each child in childNodes do
    value := max(value, −negamax(child, depth − 1, −β, −α, −color))
    α := max(α, value)
    if α ≥ β then
        break

(* Transposition Table Store; node is the lookup key for ttEntry *)
ttEntry.value := value
if value ≤ alphaOrig then
    ttEntry.flag := UPPERBOUND
else if value ≥ β then
    ttEntry.flag := LOWERBOUND
else
    ttEntry.flag := EXACT
ttEntry.depth := depth  
transpositionTableStore(node, ttEntry)

return value

但我想知道的一件事是旗帜是什么？喜欢精确、上限和下限？

Answer 1

在使用alpha beta的Nagamax搜索中，您通常从无限窗口（alpha=-inf，beta=inf）开始。然后在搜索过程中，由于截止值，此窗口变窄，这导致要么提高alpha，要么降低beta。

这些标志指示您找到的节点类型。如果您在搜索窗口中找到了一个节点（alpha

你可以在这里阅读更多关于它的信息，这也是一个很好的页面，可以找到国际象棋编程所需的一切。