每日算法 — 使用java实现Zobrist哈希：博弈状态高效编码与重复局面检测

引言

在博弈类游戏中，AI需要频繁评估和记忆大量的棋盘状态。例如在国际象棋、围棋或五子棋的搜索过程中，同一个局面可能通过不同的行棋顺序多次出现。如果不做优化，程序会重复计算相同的局面，造成巨大的性能浪费。Zobrist哈希正是为解决这一问题而生的高效哈希技术，它能够在O(1)时间内完成局面的哈希计算，并支持O(1)的增量更新，是 modern game AI 的核心组件之一。

本文将用 Java 完整实现 Zobrist 哈希算法，并结合置换表（Transposition Table）演示如何在博弈搜索中检测重复局面、避免循环以及加速评估。

算法原理

核心思想

Zobrist 哈希由 Albert Zobrist 于 1970 年提出，其核心思想非常简洁：

1. 为棋盘上每一个位置的每一种棋子类型预生成一个随机 64 位整数
2. 一个局面的哈希值等于所有存在棋子的位置所对应随机数的异或（XOR）之和
3. 移动一个棋子时，只需 XOR 掉旧位置的随机数，再 XOR 上新位置的随机数，即可在 O(1) 时间内更新哈希值

为什么用异或？

异或运算具有完美的可逆性和交换律：
– a ^ a = 0（同一位置同一棋子异或两次等于没异或）
– a ^ b = b ^ a（交换律，棋子顺序不影响结果）

这意味着：
– 添加一个棋子：hash ^= randomTable[piece][position]
– 移除一个棋子：hash ^= randomTable[piece][position]（同一操作）
– 移动一个棋子：hash ^= randomTable[piece][oldPos] ^ randomTable[piece][newPos]

碰撞概率

使用 64 位随机数时，两个不同局面产生相同哈希值的概率约为 1 / 2^64，在实际应用中几乎可以忽略不计。

Java 实现

1. Zobrist 哈希表生成器

import java.util.Random;

/**
 * Zobrist哈希表生成器
 * 为每个棋子类型的每个棋盘位置预生成随机64位哈希值
 */
public class ZobristHasher {
    // 棋盘尺寸（以8x8国际象棋为例，可调整）
    public static final int BOARD_SIZE = 8;
    // 棋子类型数：空、白兵、白马、白象、白车、白后、白王、黑兵、黑马、黑象、黑车、黑后、黑王
    public static final int PIECE_TYPES = 13;

    // 三维数组：[pieceType][row][col]
    private final long[][][] zobristTable;
    // 当前局面的哈希值
    private long currentHash;

    public ZobristHasher() {
        this.zobristTable = new long[PIECE_TYPES][BOARD_SIZE][BOARD_SIZE];
        initializeRandomTable();
        this.currentHash = 0L;
    }

    /**
     * 使用固定种子初始化随机表，确保可复现性
     * 实际应用中可使用更复杂的随机数生成策略
     */
    private void initializeRandomTable() {
        Random random = new Random(42); // 固定种子便于调试和测试
        for (int piece = 0; piece < PIECE_TYPES; piece++) {
            for (int row = 0; row < BOARD_SIZE; row++) {
                for (int col = 0; col < BOARD_SIZE; col++) {
                    zobristTable[piece][row][col] = random.nextLong();
                }
            }
        }
    }

    /**
     * 从完整棋盘状态计算初始哈希值
     * @param board 二维数组表示棋盘，每个元素为棋子类型索引
     */
    public void computeHashFromBoard(int[][] board) {
        currentHash = 0L;
        for (int row = 0; row < BOARD_SIZE; row++) {
            for (int col = 0; col < BOARD_SIZE; col++) {
                int piece = board[row][col];
                if (piece != 0) { // 0表示空位
                    currentHash ^= zobristTable[piece][row][col];
                }
            }
        }
    }

    /**
     * 在指定位置放置棋子，增量更新哈希值
     * @param piece 棋子类型
     * @param row 行坐标
     * @param col 列坐标
     */
    public void placePiece(int piece, int row, int col) {
        if (piece != 0) {
            currentHash ^= zobristTable[piece][row][col];
        }
    }

    /**
     * 移除指定位置的棋子，增量更新哈希值
     * @param piece 棋子类型
     * @param row 行坐标
     * @param col 列坐标
     */
    public void removePiece(int piece, int row, int col) {
        if (piece != 0) {
            currentHash ^= zobristTable[piece][row][col];
        }
    }

    /**
     * 移动棋子：从旧位置移除，在新位置放置
     * @param piece 棋子类型
     * @param oldRow 原行坐标
     * @param oldCol 原列坐标
     * @param newRow 新行坐标
     * @param newCol 新列坐标
     */
    public void movePiece(int piece, int oldRow, int oldCol, int newRow, int newCol) {
        removePiece(piece, oldRow, oldCol);
        placePiece(piece, newRow, newCol);
    }

    /**
     * 获取当前局面的哈希值
     */
    public long getHash() {
        return currentHash;
    }

    /**
     * 获取指定位置的预生成随机值（用于特殊处理，如置换表索引）
     */
    public long getTableValue(int piece, int row, int col) {
        return zobristTable[piece][row][col];
    }
}

2. 置换表（Transposition Table）

import java.util.concurrent.atomic.AtomicInteger;

/**
 * 置换表条目：存储已搜索局面的评估结果
 * 用于避免重复计算和检测循环局面
 */
public class TTEntry {
    // 存储的哈希值（用于验证碰撞）
    public long hash;
    // 搜索深度
    public int depth;
    // 评估分数
    public int score;
    // 节点类型：EXACT(精确值)、LOWERBOUND(下界)、UPPERBOUND(上界)
    public int flag;
    // 最佳走法（用于走法排序优化）
    public int bestMove;
    // 年龄标记（用于替换策略）
    public int age;

    public static final int EXACT = 0;
    public static final int LOWERBOUND = 1;
    public static final int UPPERBOUND = 2;

    public TTEntry() {
        this.hash = 0L;
        this.depth = 0;
        this.score = 0;
        this.flag = EXACT;
        this.bestMove = -1;
        this.age = 0;
    }
}

/**
 * 置换表实现
 * 使用固定大小的数组 + 线性探测处理冲突
 */
public class TranspositionTable {
    // 表大小：2^20 约 100 万条目，每个条目约 40 字节，总内存约 40MB
    private static final int TABLE_SIZE = 1 << 20;
    private static final int MASK = TABLE_SIZE - 1;

    private final TTEntry[] table;
    private final AtomicInteger hits;
    private final AtomicInteger collisions;
    private int currentAge;

    public TranspositionTable() {
        this.table = new TTEntry[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++) {
            table[i] = new TTEntry();
        }
        this.hits = new AtomicInteger(0);
        this.collisions = new AtomicInteger(0);
        this.currentAge = 0;
    }

    /**
     * 计算索引：取哈希值的低20位
     */
    private int getIndex(long hash) {
        return (int) (hash & MASK);
    }

    /**
     * 查询置换表
     * @param hash 当前局面的Zobrist哈希值
     * @param depth 当前搜索深度
     * @return 若找到有效条目则返回，否则返回null
     */
    public TTEntry probe(long hash, int depth) {
        int index = getIndex(hash);
        TTEntry entry = table[index];

        // 验证哈希值是否匹配（防止哈希碰撞）
        if (entry.hash == hash && entry.depth >= depth) {
            hits.incrementAndGet();
            return entry;
        }
        return null;
    }

    /**
     * 存储条目到置换表
     * 使用替换策略：更深的搜索结果优先保留
     */
    public void store(long hash, int depth, int score, int flag, int bestMove) {
        int index = getIndex(hash);
        TTEntry entry = table[index];

        // 替换策略：如果新结果更深，或条目是旧轮次的，则替换
        if (entry.hash == 0 || entry.depth <= depth || entry.age != currentAge) {
            if (entry.hash != 0 && entry.hash != hash) {
                collisions.incrementAndGet();
            }
            entry.hash = hash;
            entry.depth = depth;
            entry.score = score;
            entry.flag = flag;
            entry.bestMove = bestMove;
            entry.age = currentAge;
        }
    }

    /**
     * 开始新一轮搜索，更新年龄标记
     */
    public void newSearch() {
        currentAge++;
    }

    /**
     * 清空置换表
     */
    public void clear() {
        for (TTEntry entry : table) {
            entry.hash = 0L;
        }
        hits.set(0);
        collisions.set(0);
    }

    public int getHits() { return hits.get(); }
    public int getCollisions() { return collisions.get(); }
}

3. 完整示例：五子棋中的 Zobrist 哈希应用

/**
 * 简化版五子棋AI，演示Zobrist哈希与置换表的实战应用
 */
public class GomokuAI {
    private static final int BOARD_SIZE = 15;
    private static final int EMPTY = 0;
    private static final int BLACK = 1;
    private static final int WHITE = 2;

    // Zobrist哈希器：只需3种棋子类型（空、黑、白）
    private final ZobristHasher hasher;
    private final TranspositionTable tt;
    private final int[][] board;

    public GomokuAI() {
        this.hasher = new ZobristHasher();
        this.tt = new TranspositionTable();
        this.board = new int[BOARD_SIZE][BOARD_SIZE];
        // 初始化哈希值（空棋盘）
        hasher.computeHashFromBoard(board);
    }

    /**
     * 在指定位置落子，同时更新Zobrist哈希
     */
    public void makeMove(int row, int col, int player) {
        board[row][col] = player;
        hasher.placePiece(player, row, col);
    }

    /**
     * 撤销落子，同时更新Zobrist哈希
     */
    public void undoMove(int row, int col, int player) {
        board[row][col] = EMPTY;
        hasher.removePiece(player, row, col);
    }

    /**
     * 带置换表优化的Minimax搜索
     */
    public int search(int depth, int alpha, int beta, boolean isMaximizing) {
        long hash = hasher.getHash();

        // 查询置换表
        TTEntry entry = tt.probe(hash, depth);
        if (entry != null) {
            switch (entry.flag) {
                case TTEntry.EXACT: return entry.score;
                case TTEntry.LOWERBOUND: 
                    alpha = Math.max(alpha, entry.score);
                    break;
                case TTEntry.UPPERBOUND:
                    beta = Math.min(beta, entry.score);
                    break;
            }
            if (alpha >= beta) {
                return entry.score;
            }
        }

        // 到达叶子节点或游戏结束
        if (depth == 0 || isGameOver()) {
            int score = evaluateBoard();
            tt.store(hash, depth, score, TTEntry.EXACT, -1);
            return score;
        }

        int bestMove = -1;
        int originalAlpha = alpha;

        if (isMaximizing) {
            int maxScore = Integer.MIN_VALUE;
            for (int[] move : generateMoves()) {
                makeMove(move[0], move[1], BLACK);
                int score = search(depth - 1, alpha, beta, false);
                undoMove(move[0], move[1], BLACK);

                if (score > maxScore) {
                    maxScore = score;
                    bestMove = move[0] * BOARD_SIZE + move[1];
                }
                alpha = Math.max(alpha, score);
                if (beta <= alpha) break; // Alpha-Beta剪枝
            }

            // 存储到置换表
            int flag = (maxScore <= originalAlpha) ? TTEntry.UPPERBOUND :
                       (maxScore >= beta) ? TTEntry.LOWERBOUND : TTEntry.EXACT;
            tt.store(hash, depth, maxScore, flag, bestMove);
            return maxScore;
        } else {
            int minScore = Integer.MAX_VALUE;
            for (int[] move : generateMoves()) {
                makeMove(move[0], move[1], WHITE);
                int score = search(depth - 1, alpha, beta, true);
                undoMove(move[0], move[1], WHITE);

                if (score < minScore) {
                    minScore = score;
                    bestMove = move[0] * BOARD_SIZE + move[1];
                }
                beta = Math.min(beta, score);
                if (beta <= alpha) break;
            }

            int flag = (minScore <= originalAlpha) ? TTEntry.UPPERBOUND :
                       (minScore >= beta) ? TTEntry.LOWERBOUND : TTEntry.EXACT;
            tt.store(hash, depth, minScore, flag, bestMove);
            return minScore;
        }
    }

    // 以下为简化版辅助方法，实际应用需完善
    private boolean isGameOver() { return false; }
    private int evaluateBoard() { return 0; }
    private int[][] generateMoves() { return new int[0][0]; }

    public static void main(String[] args) {
        GomokuAI ai = new GomokuAI();

        // 模拟几个落子操作
        ai.makeMove(7, 7, BLACK);
        ai.makeMove(7, 8, WHITE);
        ai.makeMove(8, 7, BLACK);

        System.out.println("Current hash: " + ai.hasher.getHash());

        // 验证异或的可逆性：撤销后哈希应恢复
        long hashBefore = ai.hasher.getHash();
        ai.undoMove(8, 7, BLACK);
        ai.makeMove(8, 7, BLACK);
        System.out.println("Hash reversible: " + (hashBefore == ai.hasher.getHash()));

        // 运行搜索
        ai.tt.newSearch();
        int bestScore = ai.search(4, Integer.MIN_VALUE, Integer.MAX_VALUE, true);
        System.out.println("Best score: " + bestScore);
        System.out.println("TT hits: " + ai.tt.getHits());
    }
}

复杂度分析

其中 P 为棋子类型数，R、C 为棋盘行列数，T 为置换表条目数。

进阶扩展

1. 处理特殊规则

对于需要记录额外状态的游戏（如国际象棋的吃过路兵权利、王车易位权利、逼和规则），可以为每个状态位额外生成随机数：

// 额外状态哈希值
private long castlingRightsHash;  // 四项易位权利
private long enPassantHash;       // 吃过路兵目标格
private long sideToMoveHash;      // 轮到哪方行棋

// 切换行棋方时
public void switchSide() {
    currentHash ^= sideToMoveHash;
}

2. 多线程安全

置换表在多线程环境下可能出现竞争条件。解决方案：
– 每个线程维护独立的置换表（内存换效率）
– 使用原子操作或无锁数据结构（复杂度换内存）
– 采用懒删除策略，允许多个条目共存

3. 哈希碰撞的进一步处理

虽然 64 位哈希的碰撞概率极低，但在关键应用中可采取：
– 双哈希验证：同时存储 64 位和 32 位哈希值
– 完整局面验证：置换表命中后，对比完整棋盘状态确认无误

总结

Zobrist 哈希以其极简的实现和卓越的性能，成为博弈 AI 领域不可替代的基础工具。通过本文的 Java 实现，我们展示了：

1. 预生成随机表：一次计算，永久复用
2. 异或增量更新：O(1) 时间维护局面哈希
3. 置换表集成：避免重复搜索，实现指数级加速
4. 碰撞安全：64 位空间 + 哈希验证双重保障

在实际的 Stockfish、Leela Chess Zero 等顶级引擎中，Zobrist 哈希都是核心基础设施。掌握这一技术，是构建高性能博弈 AI 的必经之路。