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

Question

我正在尝试在我的 negamax 中实现转置表。但首先我想了解伪代码中的所有想法：

` 函数 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 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

但是我想知道的一件事是标志是什么？喜欢 EXACT、UPPERBOUND 和 LOWERBOUND?

Answer 1

在使用 alpha beta 的 Negamax 搜索中，您通常从无限 window（alpha=-inf，beta=inf）开始。然后在搜索过程中，这个 window 由于截断而变窄，这导致提高 alpha 或降低 beta。

标志表明您找到了哪种类型的节点。如果您在搜索中找到了一个节点 window (alpha < score < beta) 这意味着您有一个精确的节点。下限意味着分数 >= beta，上限意味着分数 <= alpha。

您可以阅读更多相关内容 here，这也是一个很好的页面，可以找到您需要的所有国际象棋编程。

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

How to implement transposition tables with alpha beta pruning

javascript

chess

alpha-beta-pruning