基于博弈树的开源五子棋AI教程[2 Zobrist散列]

1 Zobrist Hashing

Zobrist Hashing由阿尔伯特·Zobrist于1970年提出，是一种用于棋类游戏的哈希技术。它通过为棋盘上的每一个可能状态分配一个唯一的哈希值，来有效地识别和储存不同的游戏状态。

2 优点

2.1 散列值快速计算：通常情况下散列函数需要有一定的复杂度和避免hash冲突，而Zobrist散列仅仅只要一次位运算。
2.2 状态快速识别： 博弈树搜索过程中可以通过对比一组uint64准确识别。同时散列值是无下棋顺序无关的，只和叶子状态相关。
2.3 方便存储棋盘信息：博弈树搜索过程中需要保存一些信息避免重复搜索，都需要一个唯一的标识码。例如置换表，还有文后实现的杀手表，历史表等等

3 实现

初始化： 为棋盘上所有的棋子位置生成一个随机数，这些随机数构成了Zobrist表。

// 初始化Zobrist哈希数组，为每个元素生成随机哈希值
void ZobristHash::initializeZobristHash() {
    for (int row = 0; row < boardSize; ++row) {
        for (int col = 0; col < boardSize; ++col) {
            m_zobristHashTable[row][col][PLAYER_BLACK] = m_randomGenerator64.generate();
            m_zobristHashTable[row][col][PLAYER_WHITE] = m_randomGenerator64.generate();
        }
    }
}

计算哈希值： 每当棋子在棋盘上移动时，在Zobrist表中查找相应的随机数，并通过异或操作（XOR）更新当前的哈希值。

// 在棋盘上进行一步移动并更新Zobrist哈希值
void ZobristHash::updateHash(const MPoint &point, MPlayerType oldPiece, MPlayerType newPiece)
{
    if(oldPiece != PLAYER_NONE){
        m_hash ^= m_zobristHashTable[point.x() - 1][point.y() - 1][oldPiece];
    }
    if(newPiece != PLAYER_NONE)
        m_hash ^= m_zobristHashTable[point.x() - 1][point.y() - 1][newPiece];
}

quint64 ZobristHash::generateHash(const quint64& oldKey, const MPoint &point, MPlayerType oldPiece, MPlayerType newPiece) const
{
    quint64 key = oldKey;
    if(newPiece == oldPiece) return key;
    if(oldPiece != PLAYER_NONE)
        key ^= m_zobristHashTable[point.x() - 1][point.y() - 1][oldPiece];
    if(newPiece != PLAYER_NONE)
        key ^= m_zobristHashTable[point.x() - 1][point.y() - 1][newPiece];
    return key;
}