Python棋类引擎中的置换表

Question

这是我上一篇文章的进展。代码没有任何错误，能够计算出下一个最佳步骤。我一直在研究如何将置换表和移动排序融入到我的负极大值搜索函数中，以使其运行更快、更准确，但这似乎对像我这样的初学者来说有些困难和高级。

你可以在这里找到我的代码。

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

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键存储哈希键的内容，但我并不太明白它是如何工作的，所以我放弃了这个想法。目前在这些问题上有些困惑，不知道下一步该怎么做。

- Bruno

Answer 1

要使用置换表，您“需要”使用Zorbrist哈希。哈希为每个位置提供一个（几乎）唯一的代码，并将其与其评估一起存储在置换表中。然后，简单地解释一下，如果您正在搜索的当前位置在置换表中找到，则无需再次评估它，只需使用存储的值即可。

Zorbrist键很难正确获取并且很难调试。如果有帮助的话，您可以查看我的实现Endamat Chess Engine，但由于您可能有不同的方法，因此阅读有关Zorbrist键的工作原理并尝试为您的实现做正确可能更容易。

- eligolf

---

谢谢。我一定会查看你的代码。我会对这个主题进行更多的研究，看看能找到什么。 - Bruno