python 国际象棋引擎的换位表

Question

这是我上次 post 的后续。该代码没有任何错误，可以计算出下一个最佳着法。我一直在研究如何合并转置表并将排序移动到我的 negamax 函数中以使其运行更快更准确，但对于像我这样的初学者来说似乎有些困难和高级。

你可以找到我的代码here。

在研究国际象棋编程维基时，我发现了一些换位表的示例代码：

def negamax(node, depth, alpha, beta, color):
alphaOrig = alpha

## Transposition Table Lookup; node is the lookup key for ttEntry
ttEntry = transpositionTableLookup(node)
if ttEntry.is_valid is True and ttEntry.depth >= depth:
    if ttEntry.flag == EXACT :
        return ttEntry.value
    if ttEntry.flag == LOWERBOUND:
        alpha = max(alpha, ttEntry.value)
    if ttEntry.flag == UPPERBOUND:
        beta = min(beta, ttEntry.value)

    if alpha >= beta:
        return ttEntry.value

if depth == 0 or node is terminal_node:
    return color* heuristic_value_of_node

childNodes = domove(node)
childNodes = orderMoves(childNodes)
bestValue = -99999

for child in childNodes:
    bestValue = max(bestValue, -negamax(child, depth - 1, -beta, -alpha, -color))
    alpha = max(alpha, bestValue)
    if alpha >= beta:
        break

##Transposition Table Store; node is the lookup key for ttEntry 
    ttEntry.value = bestValue
    if bestValue <= alphaOrig:
        ttEntry.flag = UPPERBOUND
    if bestValue >= beta:
        ttEntry.flag = LOWERBOUND
    else:
        ttEntry.flag = EXACT
        ttEntry.depth = depth   
        transpositionTableStore(node, ttEntry)
        return bestValue

我尝试进行一些修改以将其集成到我的代码中，但我没有从中得到任何结果。我还看到了一些关于使用 Zobrist 键存储散列键的信息，但我不太了解它是如何工作的，所以我放弃了这个想法。目前有点卡在这些问题上，不知道下一步是什么。

Answer 1

要使用转置 table，您“需要”使用 Zorbrist 哈希。散列为每个位置提供一个（几乎）唯一的代码，您将其存储在转置 table 及其评估中。然后，为了简单解释，如果你正在搜索的当前位置在你的换位中找到 table 你将不必再次评估它，你只需使用存储的值。

Zorbrist 密钥是一个噩梦，很难调试。如果对您有帮助，您可以在 Endamat Chess Engine 中查看我的实现，但由于您可能采用不同的方法，因此阅读 Zorbrist 键的工作原理并尝试使其适合您的实现可能会更容易。

python 国际象棋引擎的换位表

Transposition tables for python chess engine

python

chess

alpha-beta-pruning

negamax