C++ 中的 Zobrist 散列

2025年5月15日 | 阅读 13 分钟

Zobrist Hashing 简介

Zobrist Hashing 是一种哈希函数方法，用于快速生成棋盘游戏状态的唯一数字，主要用于国际象棋、围棋和跳棋等游戏。它由 Albert Zobrist 在 20 世纪 60 年代开发，为每个可能的棋子和每个棋盘位置分配一个随机位串。通过对这些位串进行 XOR（异或）运算，可以快速为任何游戏配置生成哈希号。

该算法的一个主要优点是，移动一个棋子时只需要很少的重新计算，因此非常适合用于高速游戏引擎。如果棋子被放置、移动或删除，可以使用 XOR 运算来重新计算哈希值，而不是重新计算棋盘的每一个位置。由于这种高效的更新过程以及低冲突率，Zobrist Hashing 是 AI 决策过程中的一个有用工具，尤其是在需要评估数百万个棋盘位置的情况下。

为什么 Zobrist Hashing 对国际象棋和围棋等棋盘游戏如此有效？

Zobrist Hashing 对国际象棋和围棋等棋盘游戏非常有效，因为它速度快、效率高且具有增量特性。它允许在发生微小变化（例如移动、放置或移除棋子）时快速更新棋盘位置的哈希值。这对于国际象棋或围棋等游戏至关重要，因为每一步棋只会改变棋盘的一小部分。Zobrist Hashing 可以通过 XOR 运算实现增量更新，而不是从头开始重新计算整个棋盘的哈希值。这最大限度地减少了计算量，并加快了游戏评估速度。
此外，Zobrist Hashing 还为棋盘状态提供了紧凑且唯一的表示，可以存储在哈希表（称为置换表）中，以避免冗余的重新计算。在国际象棋等游戏中尤其如此，因为可以通过不同的走法序列到达相同的棋盘位置。通过比较 Zobrist 哈希值，引擎可以轻松找出该位置是否已被评估过，并使用之前的评估结果。
为每个棋子-位置组合使用随机位串可确保低冲突率，这意味着不同的棋盘配置不太可能产生相同的哈希值。这种准确性与其效率相结合，使 Zobrist Hashing 成为棋盘游戏 AI 的理想选择，因为 AI 需要快速评估数百万个位置以做出最佳决策。

Zobrist Hashing 如何工作？

1. Zobrist Hashing 基本概念

Zobrist Hashing 是一种技术，通过为棋盘上的每个棋子在每个位置随机分配一个新值来创建与当前游戏状态对应的全新哈希值。目的是设计一个数据结构，使其在游戏进行中易于重组，并且速度够快。Zobrist Hashing 计算整个棋盘的哈希值。这可以通过微小的移动来充分替代，只需最少的计算。
每个棋子和位置也可以通过分配的特定随机位串数字来表征（例如，在国际象棋中，某个特定方格上的每个白兵）。目标是有一个优化的棋盘表示，可以在游戏进行中轻松地动态更新新值。而传统的棋盘哈希需要计算棋子从一个单元格移动到另一个单元格的全新哈希值，Zobrist Hashing 则只需要进行小的增量计算，从而大大减少了计算时间。

2. XOR 运算及其在哈希中的作用

XOR（异或）运算对 Zobrist Hashing 至关重要。它具有一些特性，使其非常适合高效地更新哈希值：

交换性： 操作顺序无关紧要。
自逆性： 用相同的值对 XOR 应用两次可以恢复原始值。

例如，如果一个棋子从一个方格移动到另一个方格，您可以 XOR 掉原始位置的位串，然后 XOR 进新位置的位串来更新哈希值。

3. 为哈希棋盘状态生成随机位串

为了生成随机位串，Zobrist Hashing 为棋盘上的每种可能的棋子-位置组合分配一个唯一的随机位串。例如，如果国际象棋有 64 个方格和 12 种黑白棋子，那么将有 64 x 12 = 个随机位串。这些位串的长度为 64 位，这使得实现唯一性并降低不同棋盘状态产生相同哈希值的可能性成为可能。
在为所有棋子分配完位串后，第一个棋盘状态的哈希值可以通过对起始位置方格或棋盘上棋子的所有位串进行按位异或来计算。目标是创建一个紧凑且高效的棋盘表示，该表示可以在游戏进行中快速更新。Zobrist Hashing 不是在每次移动时重新计算整个棋盘的哈希值，而是允许进行小的增量更新，计算量极少。

在 C++ 中实现 Zobrist Hashing

以下是为像国际象棋这样的棋盘游戏在 C++ 中实现 Zobrist Hashing 的分步指南。

Zobrist Hashing 是一种用于对围棋和其他回合制双人游戏等非国际象棋棋盘游戏进行高效哈希处理的技术。它允许在游戏状态转换时快速增量更新哈希值。

实现 Zobrist Hashing 的步骤

1. 初始化

Zobrist Hashing 依赖于为棋盘上的每个棋子和每个位置预先计算的随机位串。您需要一个二维数组，其中每个条目代表特定位置上特定棋子的随机位串。

const int BOARD_SIZE = 64; // Example: chessboard has 64 squares
const int PIECE_TYPES = 12; // 6 pieces for each player in chess
unsigned long long zobristTable[PIECE_TYPES][BOARD_SIZE];

void initializeZobristTable() {
    srand(time(NULL)); // Seed for randomness
    for (int i = 0; i < PIECE_TYPES; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            zobristTable[i][j] = ((unsigned long long)rand() << 32) | rand();
        }
    }
}   

2. 哈希计算

对于棋盘上的每个棋子，将其相应的位串 XOR 到总体哈希值中。

unsigned long long computeZobristHash(const int board[BOARD_SIZE], const int pieceMapping[BOARD_SIZE]) {
    unsigned long long hash = 0;
    for (int i = 0; i < BOARD_SIZE; ++i) {
        if (board[i] != -1) { // -1 indicates an empty square
            hash ^= zobristTable[pieceMapping[board[i]]][i];
        }
    }
    return hash;
}   

3. 增量更新

当发生移动时（即添加、删除或移动棋子），通过 XOR 涉及的棋子的位串来增量更新哈希值。

void updateZobristHash(unsigned long long &hash, int piece, int from, int to) {
    hash ^= zobristTable[piece][from]; // Remove piece from old position
    hash ^= zobristTable[piece][to];   // Add piece to new position
}   

示例 1

以下是一个在类似国际象棋的游戏中使用 Zobrist Hashing 的简单示例。

#include <iostream>
#include <cstdlib>
#include <ctime>

const int BOARD_SIZE = 64;
const int PIECE_TYPES = 12;

unsigned long long zobristTable[PIECE_TYPES][BOARD_SIZE];

void initializeZobristTable() {
    srand(time(NULL));
    for (int i = 0; i < PIECE_TYPES; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            zobristTable[i][j] = ((unsigned long long)rand() << 32) | rand();
        }
    }
}

unsigned long long computeZobristHash(const int board[BOARD_SIZE], const int pieceMapping[BOARD_SIZE]) {
    unsigned long long hash = 0;
    for (int i = 0; i < BOARD_SIZE; ++i) {
        if (board[i] != -1) {
            hash ^= zobristTable[pieceMapping[board[i]]][i];
        }
    }
    return hash;
}

void updateZobristHash(unsigned long long &hash, int piece, int from, int to) {
    hash ^= zobristTable[piece][from];
    hash ^= zobristTable[piece][to];
}

int main() {
    initializeZobristTable();
    
    int board[BOARD_SIZE] = { /* Initialize with piece positions */ };
    int pieceMapping[BOARD_SIZE] = { /* Piece type mappings */ };

    unsigned long long zobristHash = computeZobristHash(board, pieceMapping);
    std::cout << "Initial Zobrist Hash: " << zobristHash << std::endl;
    
    return 0;
}   

输出

Initial Zobrist Hash: 4443322467265810049

示例 2

#include <iostream>
#include <cstdlib>
#include <ctime>

const int BOARD_SIZE = 64;
const int PIECE_TYPES = 12;

unsigned long long zobristTable[PIECE_TYPES][BOARD_SIZE];

void initializeZobristTable() {
    srand(time(NULL));
    for (int i = 0; i < PIECE_TYPES; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            zobristTable[i][j] = ((unsigned long long)rand() << 32) | rand();
        }
    }
}

unsigned long long computeZobristHash(const int board[BOARD_SIZE], const int pieceMapping[BOARD_SIZE]) {
    unsigned long long hash = 0;
    for (int i = 0; i < BOARD_SIZE; ++i) {
        if (board[i] != -1) {
            hash ^= zobristTable[pieceMapping[board[i]]][i];
        }
    }
    return hash;
}

void updateZobristHash(unsigned long long &hash, int piece, int from, int to) {
    hash ^= zobristTable[piece][from];
    hash ^= zobristTable[piece][to];
}

int main() {
    //Initialize the Zobrist table
    initializeZobristTable();
    
    // Example board configuration (using -1 for empty squares)
    int board[BOARD_SIZE] = {
        0, 1, 2, 3, 4, 2, 1, 0, // Row 0 (Black pieces)
        -1, -1, -1, -1, -1, -1, -1, -1, // Row 1
        -1, -1, -1, -1, -1, -1, -1, -1, // Row 2
        -1, -1, -1, -1, -1, -1, -1, -1, // Row 3
        -1, -1, -1, -1, -1, -1, -1, -1, // Row 4
        -1, -1, -1, -1, -1, -1, -1, -1, // Row 5
        5, 6, 7, 8, 9, 7, 6, 5  // Row 6 (White pieces)
    };

    // Piece mapping: Example mapping for piece types (0: King, 1: Queen, 2: Rook, 3: Bishop, 4: Knight, 5: Pawn)
    int pieceMapping[BOARD_SIZE] = {
        2, 1, 0, 3, 4, 0, 1, 2, // Black pieces
        -1, -1, -1, -1, -1, -1, -1, -1, // Empty squares
        -1, -1, -1, -1, -1, -1, -1, -1, // Empty squares
        -1, -1, -1, -1, -1, -1, -1, -1, // Empty squares
        -1, -1, -1, -1, -1, -1, -1, -1, // Empty squares
        -1, -1, -1, -1, -1, -1, -1, -1, // Empty squares
        5, 6, 7, 8, 9, 7, 6, 5  // White pieces
    };

    // Compute the initial Zobrist hash
    unsigned long long zobristHash = computeZobristHash(board, pieceMapping);
    std::cout << "Initial Zobrist Hash: " << zobristHash << std::endl;

    return 0;
}   

输出

Initial Zobrist Hash: 8714018581147955026

优化 C++ 中的 Zobrist Hashing

1. 减少 Zobrist Hashing 中的冲突

然而，由于任何哈希表都源于哈希空间是有限的事实，因此会发生冲突，Zobrist Hashing 也不例外。为了进一步减少冲突，可以采取以下措施：

使用更大的哈希大小：将哈希的位大小从 64 位扩展到 128 位，可以极大地呈指数级减少冲突的程度。随着哈希大小的增加，需要更多的内存，但可能的哈希值数量也更多。
随机位串：生成高质量的随机数，以创建每个棋子-方格对的相应位串。这确保了哈希值的分布是分散的，没有可能导致冲突的重复。
双重哈希：应使用多个不同的 Zobrist 哈希函数。就像您保留两个不同的哈希值（例如，Zobrist 和另一个加密哈希）一样，您可以大大减少出现假阳性的几率。

2. 性能优化技术

为了提高 Zobrist Hashing 的性能，可以应用以下技术：

增量更新：在移动中，只需更新哈希中相关的部分，这可以通过 XOR 运算完成。这是 Zobrist Hashing 的主要优势，避免了计算延迟。
置换表：所使用的一种技术是通过置换表缓存先前的状态评估。这消除了重复计算给定位置的需要，并加快了对相似位置的评估。
并行处理：如果您的应用程序支持多线程，您应该并行化评估过程的各个片段。Zobrist Hashing 可以跨线程并行更新，以更新不同的位置。

3. 内存管理和效率考虑

有效的内存管理对 Zobrist Hashing 至关重要。

紧凑的数据结构：为了节省内存信息，请将 Zobrist 位串和置换表存储在小型数据结构中。因此，建议使用能够轻松存储和检索数据的结构。
固定大小的数组：不要使用动态内存分配来存储 Zobrist 表和棋盘表示，而是使用固定大小的数组。这使得分配不那么碎片化，并提高了缓存效率。
内存池：为置换表开发内存池。这种方法降低了分配和释放对象的开销，并且内存空间更少碎片化，效率更高。

Zobrist Hashing 的用例

Zobrist Hashing 因其高效的状态表示处理和冲突管理，在棋盘游戏和各种人工智能应用中特别有用。以下是一些关键用例：

1. 国际象棋引擎

国际象棋引擎使用 Zobrist Hashing 在相对较短的时间内评估大量棋盘位置。引擎可以：

存储先前状态：通过使用 Zobrist 哈希创建的置换表来完成，该表由引擎读取并包含先前分析过的位置。
处理增量更新：每当发生移动时，只有与移动相关的哈希部分会通过异或运算进行修改。这使得从游戏的一个状态快速切换到另一个状态成为可能。
识别重复位置：因此，Zobrist Hashing 用作检查重复位置的方法，这对于检测平局和最大化引擎获胜机会至关重要。

2. 围棋 AI

在围棋中，Zobrist Hashing 用于更大的游戏棋盘，通常是 19x19。在围棋引擎中使用 Zobrist Hashing 具有多种优势：

状态评估效率：Zobrist Hashing 也使 AI 更容易评估棋盘状态，从而可以更有效地探索走法。
内存优化：棋盘状态的简洁描述有助于节省内存，考虑到围棋中状态的数量，这一点至关重要。

3. 跳棋和 Othello

跳棋和 Othello 等其他双人棋盘游戏也利用 Zobrist Hashing 来有效管理游戏状态。

置换表：这两种游戏都使用置换表来记录和搜索高效的棋盘位置，以防止 AI 为同一位置进行重复计算。
快速走法评估：Zobrist Hashing 使得在放置或移动棋子时可以快速更新，从而更容易分析游戏。

4. 游戏模拟器和训练环境

Zobrist Hashing 用于各种游戏模拟器和 AI 训练环境，以有效管理状态表示。

模拟游戏场景：当一次运行更多游戏场景时，Zobrist Hashing 使得存储和检索实际游戏状态成为可能。
强化学习：Zobrist Hashing 可以确保对状态进行记录，以便评估训练模型中多种策略的表现。

5. 计算机视觉和图像识别

虽然 Zobrist Hashing 主要与游戏相关，但也可以将其改编用于计算机视觉应用。

对象识别：Zobrist Hashing 可用于哈希对象特征或模式，从而能够高效地比较和识别图像中的相似对象。

Zobrist Hashing 与其他哈希技术的比较

Zobrist Hashing 是一种专门的哈希技术，主要用于游戏 AI，尤其是在国际象棋和围棋等棋盘游戏中。虽然 MD5 和 SHA（安全哈希算法）等传统加密哈希函数被广泛用于通用目的，但 Zobrist Hashing 在游戏 AI 场景中提供了独特的优势。

Zobrist 与其他哈希函数（例如 MD5、SHA）的比较

目的和速度：Zobrist Hashing 设计用于需要使用游戏状态的游戏，并且当棋子移动或改变时，可以轻松更新结果。它使用 XOR 运算来增量更新此哈希值，这比加密哈希函数快，后者通常针对性能而非速度进行优化。
冲突管理：尽管 MD5 和 SHA 在用于最大化唯一性时可能会发生许多冲突，但使用这两种类型的哈希存在权衡，即由于算法的复杂性，它们的计算速度较慢。另一方面，Zobrist Hashing 的冲突概率较低，因为位串机制是使用随机数创建的，因此，游戏状态评估可以更快地进行，而不会给安全上下文中的哈希带来适当的冲突抵抗负担。
内存效率：与标准加密哈希函数的输出相比，Zobrist Hashing 采用特定于游戏棋盘的小型表示，因此内存开销更少。正是这种效率使得在最常见的游戏环境中能够实时处理许多游戏状态。

为什么 Zobrist 在游戏 AI 场景中更受青睐？

增量更新：Zobrist Hashing 在更新方面最为有益，因为理想情况下，我们的哈希函数应该为棋盘状态的变化提供更新的哈希值。此功能在棋盘游戏中尤其有用，因为移动频繁发生，而从原始棋盘状态重新计算哈希值将非常耗时。
置换表：Zobrist Hashing 支持使用置换表来帮助人工智能正确缓存评估过的位置，以便人工智能可以轻松区分先前评估过的位置和当前位置，这对于游戏优化至关重要。

结论

尽管如此，Zobrist Hashing 作为一种在国际象棋、围棋、跳棋和 Othello 等人工智能应用中组织和评估棋盘游戏状态的技术，非常出色。通过结合 XOR 运算的特定特性和随机位串，Zobrist Hashing 不需要每次都完全重新计算哈希值——这个问题通常需要巨大的计算资源——这就是为什么它的增量更新令人印象深刻地快速。当需要通过分析数百万种可能的比赛来做出决策时，这种效率至关重要。

该方法的一个优点是冲突率低，通过置换表，AI 引擎可以识别先前定位过的位置。这种能力不仅加快了评估速度，还利用了先前计算的结果来形成更好的游戏玩法。

此外，Zobrist Hashing 的概念可以用于更广泛的场景，从游戏模拟到训练 AI，甚至可以用于计算机视觉等各种领域。通过更好地利用 RAM 而不是 ROM 并使用空间高效的类型，编程开发人员可以创建健全的计算环境，从而很好地处理复杂的游戏状态。

与标准加密哈希函数相比，Zobrist Hashing 专门针对游戏 AI 的使用进行了优化，提供了速度、效率和低内存使用。这使其适用于任何需要执行快速状态评估并为经常发生变化的组织做出最佳决策的应用程序。总之，Zobrist Hashing 所代表的方法至今仍是计算机科学和游戏开发领域的重要贡献，并且在人工智能和游戏玩法方面具有广阔的未来。

下一个主题C++ 中的 Lamport 烘焙机算法

C++ 中的 Zobrist 散列

Zobrist Hashing 简介

为什么 Zobrist Hashing 对国际象棋和围棋等棋盘游戏如此有效？

Zobrist Hashing 如何工作？

1. Zobrist Hashing 基本概念

2. XOR 运算及其在哈希中的作用

3. 为哈希棋盘状态生成随机位串

在 C++ 中实现 Zobrist Hashing

实现 Zobrist Hashing 的步骤

1. 初始化

2. 哈希计算

3. 增量更新

示例 1

示例 2

优化 C++ 中的 Zobrist Hashing

1. 减少 Zobrist Hashing 中的冲突

2. 性能优化技术

3. 内存管理和效率考虑

Zobrist Hashing 的用例

1. 国际象棋引擎

2. 围棋 AI

3. 跳棋和 Othello

4. 游戏模拟器和训练环境

5. 计算机视觉和图像识别

Zobrist Hashing 与其他哈希技术的比较

Zobrist 与其他哈希函数（例如 MD5、SHA）的比较

为什么 Zobrist 在游戏 AI 场景中更受青睐？

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中的 Zobrist 散列

Zobrist Hashing 简介

为什么 Zobrist Hashing 对国际象棋和围棋等棋盘游戏如此有效？

Zobrist Hashing 如何工作？

1. Zobrist Hashing 基本概念

2. XOR 运算及其在哈希中的作用

3. 为哈希棋盘状态生成随机位串

在 C++ 中实现 Zobrist Hashing

实现 Zobrist Hashing 的步骤

1. 初始化

2. 哈希计算

3. 增量更新

示例 1

示例 2

优化 C++ 中的 Zobrist Hashing

1. 减少 Zobrist Hashing 中的冲突

2. 性能优化技术

3. 内存管理和效率考虑

Zobrist Hashing 的用例

1. 国际象棋引擎

2. 围棋 AI

3. 跳棋和 Othello