每日算法 — 使用java实现五子棋：迭代深化与历史启发式着法排序

五子棋的规则简单到三句话就能说清，但它的搜索树宽得可怕。15×15 的棋盘上有 225 个交叉点，中盘阶段每层可能有 60–100 个合法着点。假设平均分支因子 b = 40、搜索深度 d = 6，朴素 Minimax 需要评估 40⁶ ≈ 4×10⁹ 个叶子——按每秒评估一千万个算，要跑 7 分钟。

Alpha-Beta 剪枝在着法顺序完美时能把有效分支因子降到 √b ≈ 6.3，同样深度只需 6.3⁶ ≈ 6×10⁴ 个叶子——快了 6 万倍。但”完美顺序”要求先搜最好的着法，而这正是我们不知道的答案。

本文讲的就是如何用三个工程手段把”猜测最优着法”这件事做得足够好：迭代深化（Iterative Deepening）、历史启发（History Heuristic）、杀手着法（Killer Moves），再配上一张置换表（Transposition Table）。这四件东西组合起来，就是所有现代棋类引擎（包括 Stockfish）的搜索骨架。

一、Alpha-Beta 为什么依赖着法顺序

1.1 剪枝的条件

Alpha-Beta 的剪枝发生在某个节点满足：

β ≤ α

即”对手已经有一个更好的选择，我这条分支不用再看了”。关键是这个条件什么时候被满足：

• 如果第一个子节点就给出 β（一个很强的上界），那么后续子节点里只要有一个值超过它，立刻剪掉。
• 如果第一个子节点是最差的，β 一开始就很低，后面的好着法一出现就剪——但剪的是好着法所在的整棵子树，而它们本可以继续改善 β。

一句话：先搜好着法，能剪掉的子树最多。

1.2 有效分支因子

Knuth 与 Moore（1975）证明了 Alpha-Beta 的节点数处于：

最好情况：b^⌈d/2⌉ + b^⌊d/2⌋ - 1     （完美排序）
最坏情况：b^d                          （完全逆序，等价于 Minimax）

定义有效分支因子 b_eff = (节点数)^(1/d)。五子棋实测：无排序 b_eff ≈ 35，用简单估值排序 b_eff ≈ 12，加上历史启发 + 杀手着法 b_eff ≈ 7，加上置换表 b_eff ≈ 5.5。这意味着同样 6 层搜索的节点数相差 5000 倍以上。

二、四个武器逐一拆解

2.1 迭代深化：用浅层结果指导深层

不做迭代深化时，你必须事先决定搜几层。搜太浅棋力弱，搜太深超时。

迭代深化的做法极其简单：从深度 1 开始搜，逐层加深，直到时间用完。

for d = 1, 2, 3, ... :
    score = alphaBeta(root, d, -INF, +INF)
    if timeout: break
    bestMove = root's best move at depth d

表面上看这浪费了大量重复工作（深度 1、2、3 的结果都重算了一遍）。但实际上：

• 深度 d-1 的总节点数约为深度 d 的 1/b_eff，累加几何级数只多花 1/(1-1/b_eff) ≈ 1.2 倍的代价，只多 20%。
• 收益是：每一层都能拿到上一层的 bestMove，把它排到最前面，从而在深度 d 的第一个子节点就得到强上界，剪枝效率剧增。实测迭代深化反而比固定深度更快（因为排序更好）。
• 附带好处：任何时候超时，你手上都有一个”完整搜过的浅层最优解”，而不是半棵被剪坏的树。

2.2 历史启发：记住”在别处剪过枝的着法”

历史启发维护一张表：

history[player][from][to] += depth * depth

每当某个着法在深度 d 处引起剪枝（即产生 beta cutoff），就把它的历史分加上 d²（用平方是因为深层剪枝更可信）。

在着法排序时，把历史分作为次要关键字。它捕捉的是”这类走法在相似局面中往往很有效”这种跨局面的模式——注意它和局面无关，纯靠统计。

2.3 杀手着法：同一层里剪过枝的兄弟着法

杀手着法比历史启发更”局部”：它对每一层深度单独维护 2 个着法槽位，记录在该深度上最近一次引起剪枝的着法。

原理是：如果某个着法在深度 d 的兄弟节点里剪掉了枝，那么在同一深度的其他兄弟节点里它也很可能有效——因为这一层的局面结构相似（都是”对手刚走完某步”的应答）。

排序优先级典型设置为：

1. 置换表给出的 bestMove（如果有）
2. 吃子/威胁着法，按 MVV-LVA 或估值分排序
3. 杀手着法（killer[0] > killer[1]）
4. 历史启发分降序
5. 其余按估值

2.4 置换表：不同路径到达同一局面

五子棋的着法顺序可以交换（”先下 A 再下 B”与”先下 B 再下 A”到达同一局面），这导致大量重复搜索。置换表用 Zobrist 哈希把局面压成 64 位整数，存下”搜索深度 + 分数 + 界限类型 + 最佳着法”。

界限类型有三种，必须区分，否则会给出错误分数：

三、Java 实现

3.1 项目结构

gomoku-search/
└── src/main/java/com/example/gomoku/
    ├── Board.java            棋盘 + Zobrist 哈希增量维护
    ├── PatternEvaluator.java 棋型识别与局面估值
    ├── Move.java             着法（含排序键）
    ├── TranspositionTable.java
    ├── SearchEngine.java     迭代深化 + Alpha-Beta + 历史/杀手
    └── Main.java             自对弈演示

3.2 棋盘与 Zobrist 哈希

package com.example.gomoku;

import java.util.Random;

/**
 * 15x15 棋盘。Zobrist 哈希用增量维护：
 * 落子/撤子时只 XOR 对应随机数，O(1)，无需每次重算。
 */
public class Board {

    public static final int SIZE = 15;
    public static final int EMPTY = 0, BLACK = 1, WHITE = 2;

    private final int[][] grid = new int[SIZE][SIZE];
    private long hash = 0L;
    private int movesMade = 0;

    /** ZOBRIST[color][row][col] */
    private static final long[][][] ZOBRIST = new long[3][SIZE][SIZE];
    /** 轮到哪一方也是局面的一部分，必须进哈希 */
    private static final long ZOBRIST_SIDE;

    static {
        Random r = new Random(0x5EEDL);
        for (int c = 0; c < 3; c++)
            for (int i = 0; i < SIZE; i++)
                for (int j = 0; j < SIZE; j++) ZOBRIST[c][i][j] = r.nextLong();
        ZOBRIST_SIDE = r.nextLong();
    }

    public int get(int r, int c) { return grid[r][c]; }
    public boolean isEmpty(int r, int c) { return grid[r][c] == EMPTY; }
    public int movesMade() { return movesMade; }
    public long hash() { return hash; }

    public void make(int r, int c, int color) {
        grid[r][c] = color;
        hash ^= ZOBRIST[color][r][c];
        hash ^= ZOBRIST_SIDE;      // 换边
        movesMade++;
    }

    public void unmake(int r, int c) {
        int color = grid[r][c];
        grid[r][c] = EMPTY;
        hash ^= ZOBRIST[color][r][c];
        hash ^= ZOBRIST_SIDE;
        movesMade--;
    }

    /** 判断 (r,c) 落子 color 后是否连成五子 */
    public boolean isWin(int r, int c, int color) {
        int[][] DIRS = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
        for (int[] d : DIRS) {
            int cnt = 1;
            for (int s = 1; s <= 4; s++) {
                int nr = r + d[0] * s, nc = c + d[1] * s;
                if (inBounds(nr, nc) && grid[nr][nc] == color) cnt++; else break;
            }
            for (int s = 1; s <= 4; s++) {
                int nr = r - d[0] * s, nc = c - d[1] * s;
                if (inBounds(nr, nc) && grid[nr][nc] == color) cnt++; else break;
            }
            if (cnt >= 5) return true;
        }
        return false;
    }

    private static boolean inBounds(int r, int c) { return r >= 0 && r < SIZE && c >= 0 && c < SIZE; }
}

为什么轮到哪一方也要进哈希？ 因为同一颗子布局、不同轮次是完全不同的局面（该走的人不同，胜负判断也不同）。漏掉这一项是置换表 bug 的头号来源。

3.3 棋型识别与估值

五子棋的棋型按威胁等级从高到低：

package com.example.gomoku;

/**
 * 局面估值：对每条过 (r,c) 的四个方向做"线扫描"，把棋型映射成分值。
 * 这里用简化实现（只统计落子点周围的连续段与开放端），
 * 真实引擎会用"模板匹配 + 位运算"，但算法骨架完全一样。
 */
public class PatternEvaluator {

    public static final int FIVE      = 10_000_000;
    public static final int OPEN_FOUR = 1_000_000;
    public static final int FOUR      = 100_000;
    public static final int OPEN_THREE= 50_000;
    public static final int THREE     = 5_000;
    public static final int OPEN_TWO  = 1_000;
    public static final int TWO       = 100;

    private static final int[][] DIRS = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};

    /** 单点增量估值：只算过 (r,c) 的四条线，用于着法排序的快速打分 */
    public static int pointScore(Board b, int r, int c, int color) {
        int total = 0;
        for (int[] d : DIRS) total += lineScore(b, r, c, d[0], d[1], color);
        return total;
    }

    private static int lineScore(Board b, int r, int c, int dr, int dc, int color) {
        int count = 1;          // 含落子点自身
        int openEnds = 0;       // 两端有多少端是"空点"（可直接延伸）

        // 沿正方向扫描最近 4 格：统计连续己方数，判断该端是否开放
        int run = 0;
        boolean openPos = false;
        for (int s = 1; s <= 4; s++) {
            int nr = r + dr * s, nc = c + dc * s;
            if (!inB(nr, nc)) break;                 // 出界 = 被封死
            int v = b.get(nr, nc);
            if (v == color) { run++; }
            else if (v == Board.EMPTY) { openPos = true; break; }
            else break;                              // 对方子 = 被封死
        }
        count += run;
        if (openPos) openEnds++;

        // 沿负方向做同样的事
        run = 0;
        boolean openNeg = false;
        for (int s = 1; s <= 4; s++) {
            int nr = r - dr * s, nc = c - dc * s;
            if (!inB(nr, nc)) break;
            int v = b.get(nr, nc);
            if (v == color) { run++; }
            else if (v == Board.EMPTY) { openNeg = true; break; }
            else break;
        }
        count += run;
        if (openNeg) openEnds++;

        if (count >= 5) return FIVE;

        // 用 count*10 + openEnds 编码 8 种具体棋型，穷举映射比分段 if 更不易出错
        return switch (count * 10 + openEnds) {
            case 42 -> OPEN_FOUR;                 // 四子两开放端 = 活四，必胜
            case 41 -> FOUR;                      // 四子一开放端 = 冲四
            case 32 -> OPEN_THREE;                // 三子两开放端 = 活三
            case 31 -> THREE;                     // 三子一开放端 = 眠三
            case 22 -> OPEN_TWO;                  // 二子两开放端 = 活二
            case 21 -> TWO;
            case 40, 30, 20 -> 10;                // 两端全封：价值极低
            default -> 10;
        };
    }

    private static boolean inB(int r, int c) {
        return r >= 0 && r < Board.SIZE && c >= 0 && c < Board.SIZE;
    }

    /** 全盘估值（增量式引擎不会用它，这里用于演示与终局判断） */
    public static int evaluate(Board b, int color, int opponent) {
        int mine = 0, theirs = 0;
        for (int r = 0; r < Board.SIZE; r++)
            for (int c = 0; c < Board.SIZE; c++) {
                int v = b.get(r, c);
                if (v == color) mine += pointScore(b, r, c, color) / 4;
                else if (v == opponent) theirs += pointScore(b, r, c, opponent) / 4;
            }
        return mine - theirs;
    }
}

注意 pointScore 会把每颗子周围的同一条线重复计入（同一连段里的每颗子都会各自算一次），所以全盘估值里用 /4 粗略抵消。真实引擎用增量估值：落子时只更新受影响的 4 条线，撤销时反向恢复，做到 O(1) 更新。

3.4 着法生成与排序键

package com.example.gomoku;

/** 着法：坐标 + 排序用的复合键 */
public final class Move implements Comparable<Move> {
    public final int r, c;
    public int orderScore;   // 排序键，越大越优先

    public Move(int r, int c, int orderScore) {
        this.r = r; this.c = c; this.orderScore = orderScore;
    }

    @Override
    public int compareTo(Move o) { return Integer.compare(o.orderScore, this.orderScore); }
}

着法生成的裁剪：五子棋不需要枚举全部 225 个空点。只考虑”已有棋子周围 R=2 的邻域”即可——离已有棋子太远的点没有战术价值。这一条就把中盘的分支因子从 200+ 降到 40–60。

    /** 只生成已有棋子 2 格范围内的空点 */
    public static void generateMoves(Board b, int color, List<Move> out) {
        boolean[][] near = new boolean[Board.SIZE][Board.SIZE];
        for (int r = 0; r < Board.SIZE; r++)
            for (int c = 0; c < Board.SIZE; c++) {
                if (b.get(r, c) == Board.EMPTY) continue;
                for (int dr = -2; dr <= 2; dr++)
                    for (int dc = -2; dc <= 2; dc++) {
                        int nr = r + dr, nc = c + dc;
                        if (nr < 0 || nr >= Board.SIZE || nc < 0 || nc >= Board.SIZE) continue;
                        if (b.isEmpty(nr, nc)) near[nr][nc] = true;
                    }
            }
        for (int r = 0; r < Board.SIZE; r++)
            for (int c = 0; c < Board.SIZE; c++)
                if (near[r][c]) {
                    // 快速点分作为基础排序键
                    int s = PatternEvaluator.pointScore(b, r, c, color);
                    out.add(new Move(r, c, s));
                }
    }

3.5 置换表

package com.example.gomoku;

/**
 * 置换表：Zobrist 哈希 -> 条目。
 * 用固定大小数组 + 直接映射（index = hash & mask），冲突时新条目覆盖旧条目。
 * 这是所有真实引擎的做法——比 HashMap 快一个数量级，且内存可控。
 */
public class TranspositionTable {

    public static final byte EXACT = 1, LOWER = 2, UPPER = 3;

    public static final class Entry {
        long key;
        int depth;
        int score;
        byte flag;
        int bestR = -1, bestC = -1;
        boolean valid = false;
    }

    private final Entry[] table;
    private final int mask;

    public TranspositionTable(int log2Size) {
        int size = 1 << log2Size;
        table = new Entry[size];
        for (int i = 0; i < size; i++) table[i] = new Entry();
        mask = size - 1;
    }

    public Entry probe(long key) {
        Entry e = table[index(key)];
        return e.valid && e.key == key ? e : null;
    }

    public void store(long key, int depth, int score, byte flag, int br, int bc) {
        int idx = index(key);
        Entry e = table[idx];
        // 替换策略：深度优先（浅层结果价值低），同深度则总是替换
        if (e.valid && e.key == key && e.depth > depth) return;
        e.key = key; e.depth = depth; e.score = score;
        e.flag = flag; e.bestR = br; e.bestC = bc; e.valid = true;
    }

    private int index(long key) {
        // 高低位混合，避免某些位模式导致的聚集
        long h = key ^ (key >>> 32);
        return (int) (h & mask);
    }

    public void clear() { for (Entry e : table) e.valid = false; }
}

3.6 搜索核心

package com.example.gomoku;

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

/**
 * 迭代深化 + Alpha-Beta + 历史启发 + 杀手着法 + 置换表。
 *
 * 时间控制：checkTime() 每 N 个节点检查一次系统时间，
 * 用抛异常的方式中断递归 —— 比在每个节点 return 特殊值更干净。
 */
public class SearchEngine {

    private static final int INF = 1_000_000_000;
    private static final int MAX_PLY = 32;

    private final Board board;
    private final TranspositionTable tt;

    /** history[color][r][c]，O(1) 查表 */
    private final int[][][] history = new int[3][Board.SIZE][Board.SIZE];
    /** killer[ply] = {r1, c1, r2, c2}，同一层最多记 2 个杀手着法 */
    private final int[][] killer = new int[MAX_PLY][4];

    private long nodes = 0;
    private long deadlineNanos = Long.MAX_VALUE;
    private int bestMoveR = -1, bestMoveC = -1;

    public SearchEngine(Board board, int ttLog2) {
        this.board = board;
        this.tt = new TranspositionTable(ttLog2);
    }

    /** 搜索超时用的轻量异常（不填栈，零开销） */
    private static final class TimeUp extends RuntimeException {
        TimeUp() { super(null, null, false, false); }
    }

    /**
     * 迭代深化入口。
     * @param color 轮到谁走
     * @param timeMs 思考时间（毫秒）
     * @return {r, c, score}
     */
    public int[] think(int color, int timeMs) {
        deadlineNanos = System.nanoTime() + timeMs * 1_000_000L;
        int opponent = 3 - color;
        int[] result = {-1, -1, 0};

        for (int depth = 1; depth <= MAX_PLY; depth++) {
            try {
                int score = alphaBeta(color, opponent, depth, -INF, INF, 0, true);
                if (bestMoveR >= 0) {
                    result = new int[]{bestMoveR, bestMoveC, score};
                    // 找到必胜/必败就不用再搜了
                    if (Math.abs(score) > PatternEvaluator.FIVE) break;
                }
            } catch (TimeUp e) {
                break;     // 保留上一层的结果
            }
            // 时间过半但还没搜完下一层，就提前退出，避免"半层"结果污染
            if (System.nanoTime() > deadlineNanos) break;
        }
        return result;
    }

    /**
     * Alpha-Beta with fail-soft。
     *
     * @param root true 表示根节点（需要记录 bestMove）
     */
    private int alphaBeta(int color, int opponent, int depth,
                          int alpha, int beta, int ply, boolean root) {
        if ((++nodes & 1023) == 0 && System.nanoTime() > deadlineNanos) throw new TimeUp();

        // ---- 置换表探测 ----
        long key = board.hash();
        TranspositionTable.Entry e = tt.probe(key);
        if (!root && e != null) {
            if (e.depth >= depth) {
                switch (e.flag) {
                    case TranspositionTable.EXACT: return e.score;
                    case TranspositionTable.LOWER: if (e.score > alpha) alpha = e.score; break;
                    case TranspositionTable.UPPER: if (e.score < beta)  beta  = e.score; break;
                    default: break;
                }
                if (alpha >= beta) return e.score;
            }
        }

        // ---- 叶子评估 ----
        if (depth <= 0) return PatternEvaluator.evaluate(board, color, opponent);

        // ---- 生成 + 排序 ----
        List<Move> moves = new ArrayList<>(64);
        generateMoves(color, moves);

        // 1) 先搜置换表里的 bestMove：直接提到最前
        if (e != null && e.bestR >= 0) {
            for (Move m : moves) {
                if (m.r == e.bestR && m.c == e.bestC) { m.orderScore = Integer.MAX_VALUE; break; }
            }
        }
        // 2) 杀手着法：同层最近引起剪枝的两个着法，加一个高额常量分
        int kr1 = killer[ply][0], kc1 = killer[ply][1];
        int kr2 = killer[ply][2], kc2 = killer[ply][3];
        for (Move m : moves) {
            if ((m.r == kr1 && m.c == kc1) || (m.r == kr2 && m.c == kc2)) {
                // 加分要卡在"活四/冲四"与"活三"之间：杀手着法通常也是战术着法，
                // 但不能盖过真正的成五/活四威胁，也不能低于普通估值
                m.orderScore += 60_000;
            }
        }
        // 3) 历史启发：叠加统计分
        for (Move m : moves) m.orderScore += history[color][m.r][m.c];

        Collections.sort(moves);

        // ---- 主循环 ----
        byte flag = TranspositionTable.UPPER;     // 默认：全是上界（可能剪枝）
        int bestScore = -INF;
        int localBestR = -1, localBestC = -1;

        for (Move m : moves) {
            board.make(m.r, m.c, color);

            int score;
            if (board.isWin(m.r, m.c, color)) {
                score = PatternEvaluator.FIVE - ply;    // 越快赢分越高
            } else {
                score = -alphaBeta(opponent, color, depth - 1, -beta, -alpha, ply + 1, false);
            }
            board.unmake(m.r, m.c);

            if (score > bestScore) {
                bestScore = score;
                localBestR = m.r; localBestC = m.c;
            }
            if (score > alpha) {
                alpha = score;
                flag = TranspositionTable.EXACT;      // 落在窗口内 → 精确值

                if (root) { bestMoveR = m.r; bestMoveC = m.c; }

                // ---- 剪枝：记录 killer 与 history ----
                if (alpha >= beta) {
                    flag = TranspositionTable.LOWER;  // fail-high → 下界
                    // 更新杀手着法：新着法插到槽 0，旧槽 0 挪到槽 1
                    if (!(m.r == kr1 && m.c == kc1)) {
                        killer[ply][2] = killer[ply][0];
                        killer[ply][3] = killer[ply][1];
                        killer[ply][0] = m.r;
                        killer[ply][1] = m.c;
                    }
                    // 历史启发：深度平方，深层剪枝更可信
                    history[color][m.r][m.c] += depth * depth;
                    break;
                }
            }
        }

        tt.store(key, depth, bestScore, flag, localBestR, localBestC);
        return bestScore;
    }

    private void generateMoves(int color, List<Move> out) {
        boolean[][] near = new boolean[Board.SIZE][Board.SIZE];
        for (int r = 0; r < Board.SIZE; r++)
            for (int c = 0; c < Board.SIZE; c++) {
                if (board.get(r, c) == Board.EMPTY) continue;
                int lo = Math.max(0, r - 2), hi = Math.min(Board.SIZE - 1, r + 2);
                int lc = Math.max(0, c - 2), hc = Math.min(Board.SIZE - 1, c + 2);
                for (int nr = lo; nr <= hi; nr++)
                    for (int nc = lc; nc <= hc; nc++)
                        if (board.isEmpty(nr, nc)) near[nr][nc] = true;
            }
        for (int r = 0; r < Board.SIZE; r++)
            for (int c = 0; c < Board.SIZE; c++)
                if (near[r][c])
                    out.add(new Move(r, c, PatternEvaluator.pointScore(board, r, c, color)));
    }

    public long nodes() { return nodes; }
    public void clearHistory() {
        for (int c = 0; c < 3; c++) for (int i = 0; i < Board.SIZE; i++)
            java.util.Arrays.fill(history[c][i], 0);
    }
}

3.7 自对弈演示

package com.example.gomoku;

public class Main {

    public static void main(String[] args) {
        Board board = new Board();
        SearchEngine engine = new SearchEngine(board, 18);   // 256K 条目 ≈ 10MB

        int color = Board.BLACK, opponent = Board.WHITE;
        int[] answer = {7, 7, 0};

        for (int step = 0; step < 225; step++) {
            long t0 = System.nanoTime();
            int[] mv = step == 0
                    ? new int[]{7, 7, 0}                        // 首手走天元
                    : engine.think(color, 800);                 // 每步 0.8 秒
            long ms = (System.nanoTime() - t0) / 1_000_000;

            if (mv[0] < 0) { System.out.println("无着可走，结束"); break; }
            board.make(mv[0], mv[1], color);
            System.out.printf("第%3d手 %s 落 (%2d,%2d) 评分=%9d 耗时=%4dms 累计节点=%d%n",
                    step + 1, color == Board.BLACK ? "黑" : "白",
                    mv[0], mv[1], mv[2], ms, engine.nodes());

            if (board.isWin(mv[0], mv[1], color)) {
                System.out.printf("%s 在第 %d 手连成五子，获胜%n",
                        color == Board.BLACK ? "黑方" : "白方", step + 1);
                break;
            }
            int t = color; color = opponent; opponent = t;
        }
    }
}

四、着法排序到底带来了多少收益

在一台普通笔记本上，对同一局中盘局面（黑棋第 20 手）做对照实验，固定搜索深度 6：

从 3100ms 降到 78ms，40 倍加速，而搜索深度和评估函数一字未改。 这就是”工程优化”和”算法改进”的差别——前者不改善棋力上限，但让你在同样时间内搜得更深（多搜 2–3 层，棋力提升巨大）。

值得强调的是：这四项技术互不替代。历史启发捕捉跨局面的统计规律，杀手着法捕捉同层兄弟节点的局部相似性，置换表捕捉不同路径的重复局面，迭代深化则把前三种排序信号”喂”给下一层。四者叠加才有 40 倍，单独用任何一个只有 3–6 倍。

五、复杂度分析

设有效分支因子 b_eff、搜索深度 d、置换表大小 T：

迭代深化的总代价是各层之和的几何级数，约 b_eff^d × b_eff/(b_eff-1)，b_eff = 5 时只多 25%。

六、四个容易踩的坑

第一，置换表分数与 alpha/beta 窗口的关系。 置换表里存的分数是相对于该节点当时的搜索窗口的。如果你把一个在 (α=0, β=100) 窗口下存下的 EXACT 分数，拿到 (α=-INF, β=INF) 窗口下复用，答案是对的；但如果存的是 UPPER（β=100 剪枝得到 score ≤ 100），拿到 α=200 的新窗口下，score ≤ 100 < α 就不能直接返回，只能用作上界调整。搞错这一点会得到”引擎莫名其妙走出漏着的棋”。

第二，Zobrist 哈希必须包含换边信息。 前面代码里 hash ^= ZOBRIST_SIDE 那两行就是干这个的。漏掉它，黑棋局面和白棋局面会哈希到同一个值，置换表直接串味。

第三，depth 在置换表里要按”剩余深度”存。 如果一个局面的剩余深度是 6，另一个是 3，后者不能覆盖前者。代码里 if (e.valid && e.key == key && e.depth > depth) return; 就是这层保护。但反过来，如果新搜索的深度更大，就该覆盖——因为更深的结果更可信。

第四，终止条件的精度。 五子棋在”必胜/必败”处的分数必须随 ply 递减（FIVE - ply），否则引擎会”绕远路取胜”（明明 3 步能赢，却走 5 步）。这个细节在象棋里同样重要，通常叫 mate distance pruning。

七、从五子棋到通用博弈引擎

五子棋是理解搜索工程的最佳载体，因为它同时具备：

1. 大分支因子（比象棋大，比围棋小）——排序优化的收益立刻可见。
2. 强战术性（活四、冲四、双活三）——评估函数必须捕捉组合威胁，而不只是单点连子数。
3. 可交换着法（同色棋子顺序无关）——置换表的收益非常明显。

把这套骨架搬到其他场景，只需替换三样东西：generateMoves（合法着法规则）、isWin（终局判定）、evaluate（局面静态估值）。搜索部分——迭代深化、Alpha-Beta、历史启发、杀手着法、置换表——一个字都不用改。

这也是为什么现代棋类引擎的代码结构几乎是同一个模板：Stockfish 的 search() 里能找到完全对应的一一映射（Iterative deepening → aspiration window → TT probe → move ordering → history/killer/countermove → null move pruning）。理解了五子棋这一百来行，读 Stockfish 就不再是天书。