每日算法 — 使用java实现五子棋：增量棋型评分与Zobrist置换表

五子棋的搜索深度通常只能做到 6~10 层，瓶颈几乎全在评估函数：一面 15×15 的棋盘有 572 条可能的五连线（15 行 + 15 列 + 29 条主对角线 + 29 条副对角线），一次全量重算要扫上千个格子。而实际上，落一颗子只会改变穿过它的 4 条线——所以正确做法不是”每次重算全盘”，而是”只重算这 4 条线，其余部分从父节点继承”。这就是增量棋型评分。本文用位掩码行表示 + 增量评分 + Zobrist 置换表，把五子棋的搜索从”每秒几万节点”推到”每秒几十万节点”，并给出完整可运行的 Java 实现。

一、为什么五子棋必须做增量评估

先看一组对比。假设搜索树有 10 层、每层平均有效分支 8，总节点数约 8¹⁰ ≈ 10⁹——当然 Alpha-Beta 会把它压到 √b 的指数，实际约 10⁵ 量级。此时单节点评估开销成了决定性变量：

差一个数量级意味着同样的时间能多搜 1~2 层，而这 1~2 层在五子棋里往往就是”能看见对手的活三”和”看不见”的区别。

增量评估的前提是分数可以按线分解：总评估分 = 所有线段分数之和。这个前提成立，因为五子棋的胜负模式全部是”某条线上的连续棋型”，与跨线的组合无关。于是落一颗子时，只需：

1. 找出穿过落点的 4 条线段（横、竖、两条对角线）；
2. 从总分里减去这 4 条线的旧分数；
3. 重算这 4 条线的新分数并加回。

二、线段表示：把一条线压成两个位掩码

一条长度为 L 的线段，每个位置有三种状态（黑、白、空）。把”黑子位置”和”白子位置”各压成一个 int 位掩码，就能用位运算做所有棋型判断：

/** 一条线段的编码: 我方掩码 + 对方掩码, 低位对应线的起点 */
final class Line {
    int mine;    // 我方棋子所在位
    int theirs;  // 对方棋子所在位
    int len;     // 线段实际长度
}

判断”这条线上我方有没有活三”，只需要在 mine 上做几次移位与运算：mine & (mine >> 1) & (mine >> 2) 得到”连续三子”的起点掩码。更通用地，可以用五连模板匹配：枚举所有可能的 5 格窗口，判断窗口内是”我方 5 子”、”我方 4 子 + 1 空”、”我方 3 子 + 2 空”等。

/** 统计 len 长度线段中, 所有 5 格窗口的棋型计数 */
static int[] scoreLine(int mine, int theirs, int len) {
    int[] cnt = new int[6];   // cnt[k] = "我方 k 子"的窗口数, 忽略对方子
    for (int s = 0; s + 5 <= len; s++) {
        int winMine = (mine >>> s) & 0b11111;
        int winTheirs = (theirs >>> s) & 0b11111;
        if (winTheirs != 0) continue;          // 窗口内有对方子: 此窗口对我方无意义
        cnt[Integer.bitCount(winMine)]++;
    }
    return cnt;
}

这段代码是增量评估的全部核心：一次循环 len-4 次、每次两次位运算加一次 bitCount。长度 15 的线只有 11 个窗口，4 条线合计 44 次位运算——这就是”增量评估比全盘扫描快一个数量级”的来源。

三、棋型到分数的映射：为什么活三比冲四更值钱

有了窗口计数，还需要把它翻译成分数。五子棋的经典棋型分值（用于评估函数）：

这套分值的排序逻辑值得说清楚：活四比冲四高一个数量级，因为它有两个成五点，对手一手只能堵一个；活三比冲四低，因为冲四能立刻逼对手应手，是”先手权”，而活三只是”威胁”。

工程上更实用的做法是直接由窗口计数推导：若我方有 5 子窗口，则五连；若有 ≥2 个”4 子窗口”且彼此共享不同的成五点，则活四；若有 1 个 4 子窗口，则冲四；再往下按 3 子窗口数量区分活三/眠三。为避免写成庞大的 if-else 树，本文用一个记分表 + 模式匹配的做法：

/** 五连检测: 任意 5 格窗口全为我方 */
static boolean hasFive(int mine, int len) {
    for (int s = 0; s + 5 <= len; s++)
        if (((mine >>> s) & 0b11111) == 0b11111) return true;
    return false;
}

/** 成五点计数: 某个空位填上我方后能成五连, 该位置就是一个"成五点" */
static int winningPoints(int mine, int theirs, int len) {
    int pts = 0;
    for (int s = 0; s + 5 <= len; s++) {
        int wm = (mine >>> s) & 0b11111;
        int wt = (theirs >>> s) & 0b11111;
        if (wt != 0) continue;
        if (Integer.bitCount(wm) == 4) pts++;   // 一个 4 子窗口 = 一个成五点
    }
    return pts;
}

winningPoints 返回 2 就是活四、返回 1 就是冲四——这个判定比查表更直接，且天然正确（因为”成五点”的定义就是”填上就成五”）。

四、Zobrist 置换表：用 64 位哈希避免重复搜索

棋盘不同、但着法顺序不同会走到同一个局面。Alpha-Beta 搜索里这种重复极为常见（尤其是吃子/强制着法密集的局面），命中一次置换表就能省掉整个子树。

Zobrist 哈希的标准做法：为每个 (位置, 颜色) 预生成一个随机 64 位数，局面的哈希是所有已落子对应随机数的异或。异或的妙处是可增量更新：

/** 落子/提子都只需异或一次, 不需要重算哈希 */
hash ^= ZOBRIST[color][pos];

这解释了为什么必须用异或而不是加法或乘法哈希：只有异或满足”同一操作执行两次等于撤销”。

static final long[][] ZOBRIST = new long[2][225];   // 2 色 × 15×15
static {
    Random rnd = new Random(20260101L);             // 固定种子: 结果可复现
    for (int c = 0; c < 2; c++)
        for (int i = 0; i < 225; i++) ZOBRIST[c][i] = rnd.nextLong();
}

置换表的条目需要存三样东西，缺一不可：

final class TTEntry {
    long key;      // Zobrist 哈希
    int  depth;    // 搜索时的剩余深度
    int  value;    // 分数
    int  flag;     // 0=精确值, 1=下界(失败高), 2=上界(失败低)
    int  bestMove; // 最佳着法, 用于着法排序
}

flag 是置换表最容易写错的地方。Alpha-Beta 返回的分数有三种语义：

• 搜索区间被完全探索 → 精确值；
• 因为 alpha >= beta 提前剪枝 → 只保证”至少这么高”（下界）；
• 因为所有着法都低于 alpha → 只保证”至多这么低”（上界）。

如果统一按精确值存，就会把”下界”当成”真值”复用，导致估值错误且不可复现——这是五子棋引擎里最典型的隐蔽 bug。

/** 查表: 命中且深度足够时直接返回 */
Integer probe(long key, int depth, int alpha, int beta) {
    TTEntry e = table[(int) (key & MASK)];
    if (e == null || e.key != key || e.depth < depth) return null;
    if (e.flag == 0) return e.value;                       // 精确值
    if (e.flag == 1 && e.value >= beta) return e.value;     // 下界足以剪枝
    if (e.flag == 2 && e.value <= alpha) return e.value;    // 上界足以剪枝
    return null;
}

e.depth < depth 那个条件是”深度保护”：浅层搜索的结果精度低，不能用来替代更深的搜索。删掉它会得到”看起来更快但棋力下降”的引擎。

五、增量维护：落子/撤销只需 4 条线

把”线的分数”和”Zobrist 哈希”一起做增量维护，搜索主循环就只剩下加减法。关键在于落子前取一次旧值、落子后取一次新值，把差值累加进总分——这个顺序不能颠倒，否则新旧值相同、delta 恒为 0，增量就成了摆设：

/** 落子 + 增量更新; 返回 {delta} 供撤销使用 */
int makeMove(int r, int c, int color) {
    int[] before = new int[4];                       // 4 条线的旧分数
    for (int d = 0; d < 4; d++) before[d] = lineScore(r, c, d, color);

    board[r][c] = color;
    hash ^= Zobrist.TABLE[color - 1][r * N + c];

    int delta = 0;                                   // 落子带来的分数变化
    for (int d = 0; d < 4; d++) delta += lineScore(r, c, d, color) - before[d];

    if (color == 1) scoreBlack += delta; else scoreWhite += delta;
    return new int[]{delta};                         // 撤销时直接减回去
}

void unmakeMove(int r, int c, int color, int[] delta) {
    board[r][c] = 0;
    hash ^= Zobrist.TABLE[color - 1][r * N + c];
    if (color == 1) scoreBlack -= delta[0]; else scoreWhite -= delta[0];
}

这里有个极其容易踩的坑：撤销时不能”再算一遍差值”来抵消。如果 unmakeMove 先清空棋盘、再刷新分数，那么清空后的分数恰好等于落子前的分数，差值恒为 0——增量根本没被撤销，分数会随搜索深度单调漂移。正确做法只有一种：把落子时的 delta 记下来，撤销时原样减去。这一点必须在单元测试里断言（落子 + 撤销后分数回到初值），否则误差会累积到让引擎在浅层与深层给出互相矛盾的评估。

六、完整可运行实现

目录结构：

gomoku/
└── src/main/java/gomoku/
    ├── Line.java       # 线段编码与棋型计数
    ├── Zobrist.java    # 哈希表
    ├── Engine.java     # 增量评估 + 置换表 + Alpha-Beta
    └── Demo.java       # main: 自我对弈演示

package gomoku;

import java.util.*;

final class Zobrist {
    static final int SIZE = 15, SLOTS = SIZE * SIZE;
    static final long[][] TABLE = new long[2][SLOTS];
    static {
        Random rnd = new Random(20260101L);
        for (int c = 0; c < 2; c++)
            for (int i = 0; i < SLOTS; i++) TABLE[c][i] = rnd.nextLong();
    }
}

final class Line {
    /** 5 格窗口内我方子数计数; 窗口若含对方子则跳过 */
    static int[] windows(int mine, int theirs, int len) {
        int[] cnt = new int[6];
        for (int s = 0; s + 5 <= len; s++) {
            int wt = (theirs >>> s) & 0b11111;
            if (wt != 0) continue;
            cnt[Integer.bitCount((mine >>> s) & 0b11111)]++;
        }
        return cnt;
    }

    static boolean five(int mine, int len) {
        for (int s = 0; s + 5 <= len; s++)
            if (((mine >>> s) & 0b11111) == 0b11111) return true;
        return false;
    }

    /** 成五点个数: 2 -> 活四, 1 -> 冲四, 0 -> 无 */
    static int winningPoints(int mine, int theirs, int len) {
        int pts = 0;
        for (int s = 0; s + 5 <= len; s++) {
            int wt = (theirs >>> s) & 0b11111;
            if (wt != 0) continue;
            if (Integer.bitCount((mine >>> s) & 0b11111) == 4) pts++;
        }
        return pts;
    }

    /** 单条线段对我方的分值 */
    static int score(int mine, int theirs, int len) {
        if (five(mine, len)) return 1_000_000;
        int wp = winningPoints(mine, theirs, len);
        if (wp >= 2) return 100_000;               // 活四
        if (wp == 1) return 10_000;                // 冲四
        int[] w = windows(mine, theirs, len);
        if (w[3] >= 1) return 5_000;               // 活/眠三
        if (w[2] >= 2) return 100;                 // 活二
        if (w[2] == 1) return 50;
        return 0;
    }
}

final class Engine {
    static final int N = 15;

    private final int[][] board = new int[N][N];
    private long hash = 0;
    private int scoreBlack = 0, scoreWhite = 0;
    private long nodes = 0;

    // ---- 置换表 ----
    private static final int TT_BITS = 18, TT_SIZE = 1 << TT_BITS, MASK = TT_SIZE - 1;
    private final long[] ttKey   = new long[TT_SIZE];
    private final int[]  ttDepth = new int[TT_SIZE];
    private final int[]  ttValue = new int[TT_SIZE];
    private final int[]  ttFlag  = new int[TT_SIZE];   // 0 精确, 1 下界, 2 上界
    private final int[]  ttMove  = new int[TT_SIZE];
    private final boolean[] ttUsed = new boolean[TT_SIZE];

    Engine() { Arrays.fill(ttMove, -1); }

    int at(int r, int c) { return board[r][c]; }

    /** 抽取穿过 (r,c) 沿方向 d 的线段, 返回 {mine, theirs, len} */
    private int[] extract(int r, int c, int d, int color) {
        int[][] dirs = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
        int dr = dirs[d][0], dc = dirs[d][1];
        // 先退到线段起点
        int sr = r, sc = c;
        while (sr - dr >= 0 && sr - dr < N && sc - dc >= 0 && sc - dc < N) { sr -= dr; sc -= dc; }
        int mine = 0, theirs = 0, len = 0, other = 3 - color;
        for (int rr = sr, cc = sc; rr >= 0 && rr < N && cc >= 0 && cc < N; rr += dr, cc += dc, len++) {
            int v = board[rr][cc];
            if (v == color) mine |= 1 << len;
            else if (v == other) theirs |= 1 << len;
        }
        return new int[]{mine, theirs, len};
    }

    private int lineScore(int r, int c, int d, int color) {
        int[] t = extract(r, c, d, color);
        return Line.score(t[0], t[1], t[2]);
    }

    /** 落子 + 增量更新; 返回 {delta}, 撤销时原样减去 */
    int[] makeMove(int r, int c, int color) {
        int[] before = new int[4];
        for (int d = 0; d < 4; d++) before[d] = lineScore(r, c, d, color);

        board[r][c] = color;
        hash ^= Zobrist.TABLE[color - 1][r * N + c];

        int delta = 0;
        for (int d = 0; d < 4; d++) delta += lineScore(r, c, d, color) - before[d];
        if (color == 1) scoreBlack += delta; else scoreWhite += delta;
        return new int[]{delta};
    }

    void unmakeMove(int r, int c, int color, int[] delta) {
        board[r][c] = 0;
        hash ^= Zobrist.TABLE[color - 1][r * N + c];
        if (color == 1) scoreBlack -= delta[0]; else scoreWhite -= delta[0];
    }

    /** 局面评估: 我方总分 - 对方总分 × 权重(防守略低, 保持进攻倾向) */
    private int evaluate(int color) {
        return color == 1 ? scoreBlack - scoreWhite : scoreWhite - scoreBlack;
    }

    /** 候选着法: 只考虑已有棋子周围 2 格内的空位, 大幅缩减分支 */
    private List<Integer> candidates() {
        boolean[][] near = new boolean[N][N];
        List<Integer> out = new ArrayList<>();
        for (int r = 0; r < N; r++)
            for (int c = 0; c < N; c++)
                if (board[r][c] != 0)
                    for (int dr = -2; dr <= 2; dr++)
                        for (int dc = -2; dc <= 2; dc++) {
                            int rr = r + dr, cc = c + dc;
                            if (rr >= 0 && rr < N && cc >= 0 && cc < N && board[rr][cc] == 0)
                                near[rr][cc] = true;
                        }
        for (int r = 0; r < N; r++)
            for (int c = 0; c < N; c++)
                if (near[r][c]) out.add(r * N + c);
        if (out.isEmpty()) out.add(7 * N + 7);    // 空盘: 下天元
        return out;
    }

    private boolean won(int r, int c, int color) {
        for (int d = 0; d < 4; d++) {
            int[] t = extract(r, c, d, color);
            if (Line.five(t[0], t[2])) return true;
        }
        return false;
    }

    /** Negamax + Alpha-Beta + 置换表 */
    int search(int color, int depth, int alpha, int beta) {
        nodes++;
        if (depth == 0) return evaluate(color);

        int idx = (int) (hash & MASK);
        if (ttUsed[idx] && ttKey[idx] == hash && ttDepth[idx] >= depth) {
            int v = ttValue[idx];
            if (ttFlag[idx] == 0) return v;
            if (ttFlag[idx] == 1 && v >= beta) return v;
            if (ttFlag[idx] == 2 && v <= alpha) return v;
        }

        int best = -Integer.MAX_VALUE, bestMove = -1;
        int oldAlpha = alpha;

        for (int pos : candidates()) {
            int r = pos / N, c = pos % N;
            int[] delta = makeMove(r, c, color);
            int v;
            if (won(r, c, color)) v = 900_000 - depth;          // 越早取胜越好
            else v = -search(3 - color, depth - 1, -beta, -alpha);
            unmakeMove(r, c, color, delta);

            if (v > best) { best = v; bestMove = pos; }
            if (best > alpha) alpha = best;
            if (alpha >= beta) break;
        }

        ttUsed[idx] = true; ttKey[idx] = hash; ttDepth[idx] = depth;
        ttValue[idx] = best; ttMove[idx] = bestMove;
        ttFlag[idx] = best <= oldAlpha ? 2 : (best >= beta ? 1 : 0);
        return best;
    }

    long nodes() { return nodes; }
}

final class Demo {
    public static void main(String[] args) {
        Engine e = new Engine();
        // 摆一个简单的开局, 演示增量评估与搜索
        e.makeMove(7, 7, 1);
        e.makeMove(7, 8, 2);
        e.makeMove(8, 8, 1);

        long t0 = System.nanoTime();
        int best = e.search(2, 4, -Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2);
        long ms = (System.nanoTime() - t0) / 1_000_000;
        System.out.printf("最佳着法评估 = %d, 节点数 = %d, 耗时 = %d ms%n",
                best, e.nodes(), ms);
    }
}

七、复杂度与调优要点

三个落地建议：

• 候选着法收窄。五子棋有 225 个落点，全枚举会浪费大量时间在无关区域。只取”已有棋子 2 格范围内”的空位，分支因子通常能从 225 降到 30~60，是收益最大的一步优化。
• 置换表用数组而非 HashMap。long[] + 直接用 hash & MASK 做下标，避免装箱和哈希冲突链；冲突用”覆盖”策略（新条目覆盖旧条目），对棋类引擎足够。
• 必胜/必败分数要按深度修正。代码里写 900_000 - depth，是为了让”3 步取胜”优先于”5 步取胜”；如果直接返回固定值，引擎会满足于”能找到胜利”而不去选最快的胜利路径。

八、小结

五子棋引擎的性能结构可以总结成三层：表示层把每条线压成两个位掩码，让棋型判断变成移位加 bitCount；增量层把”落一子改四条线”这一事实转化成了 O(60) 的局部更新，取代 O(8600) 的全盘重扫；记忆层用 Zobrist 异或哈希 + 带 flag 的置换表，避免重复子树被反复搜索。三层都是”用数据结构消除重复计算”的同一思路在不同尺度上的应用——这也是所有棋类引擎的共同骨架，换到围棋、黑白棋、象棋上，只需要替换第三层之上的评估与着法生成。