每日算法 — 使用java实现播棋：播种链模拟与迭代加深Alpha-Beta对弈搜索

播棋（Mancala，最流行的规则变体是 Kalah）只用一排坑和一把石子就构成了完整的博弈系统：抓起一堆石子逐个投放，落到特定位置会触发额外回合或捕获。它没有骰子的随机性，分支因子只有 6 左右，但单局深度可达几十步——这是典型的「窄而深」博弈树，正是 Alpha-Beta 剪枝最好的试验场。

本文用 Java 实现一个可运行的播棋引擎：状态表示、播种链模拟、静态评估、迭代加深 Alpha-Beta + 置换表 + 历史启发，并给出实测的剪枝收益数据（同样的深度 10，开启着法排序与置换表只需 6144 个节点，全关则需要 30 万个节点，相差 49 倍）。

一、规则建模：播棋难在哪里

标准 Kalah 规则（6 坑 + 1 仓，共 14 个位置）：

1. 每位玩家 6 个「坑」和 1 个「仓」，初始每坑 4 石，共 48 石。
2. 轮到你时，抓起自己一方某个非空坑的全部石子，沿逆时针逐坑投放，每坑 1 石，跳过对手的仓。
3. 若最后一石落入自己的仓，获得额外回合，可以再走一次。
4. 若最后一石落入自己一方的空坑，则把该石与对面坑全部石子一起收进自己的仓（捕获）。
5. 一方坑全空时游戏结束，双方剩余石子归仓，仓中石子多者胜。

看起来简单，但模拟时有三个必须精确处理的细节，任一处写错都会让整局评估失真：

• 跳过对手仓时石子数不变。常见错误是「索引越过对手仓但仍然减 1 石」，导致石子总数不守恒。
• 落空坑 vs 落非空坑的判定必须读取「投入前」的状态，而不是「投入后」。投入后一定 ≥1，无法区分。
• 绕圈落回原坑的情形：若某个坑石子多到能绕满一圈，最后一石会落回该坑本身。此时该坑投入前为空（已被抓起清 0），所以应判为「捕获」而不是「继续播种」。

我们用一条一维环形索引把两个玩家的视角统一起来：

index:   0   1   2   3   4   5    6      7   8   9  10  11  12    13
含义:  P0坑 P0坑 ...          P0仓   P1坑 P1坑 ...          P1仓

逆时针播种即索引 +1（模 14 环形），P0 的仓在 6，P1 的仓在 13，对面坑关系统一为 12 - p（0↔12、5↔7）。

二、核心：播种链模拟

一次「走子」可能包含若干次额外回合与链式播种，必须封装成原子操作，否则搜索层无法正确记账。下面是完整实现，包含对上述三个细节的处理：

    /**
     * 执行一次完整走子（含链式播种、额外回合、捕获）。
     * @return 本次走子中本方仓获得的石子数
     */
    int applyMove(int pit) {
        if (pit < 0 || pit >= BOARD_SIZE || pits[pit] == 0) {
            throw new IllegalArgumentException("非法着法: " + pit);
        }
        int me = side;
        int myStore = storeIndexOf(me);
        int gain = 0;
        int cur = pit;
        int extra = 0;
        boolean gotExtra = false;

        while (true) {
            int stones = pits[cur];
            pits[cur] = 0;
            int idx = cur;
            boolean landedEmpty = false;

            while (stones > 0) {
                idx = nextIndex(idx);
                if (idx == storeIndexOf(1 - me)) continue;   // 跳过对手仓，石子数不变
                landedEmpty = (pits[idx] == 0);               // 记录"投入前"是否为空
                pits[idx]++;
                stones--;
            }

            if (idx == myStore) {                            // 落进自己的仓 → 额外回合
                gotExtra = true;
                if (++extra >= MAX_EXTRA_TURNS) break;
                int resume = lastNonEmptyOwnPit(me);
                if (resume < 0) break;
                cur = resume;
                continue;
            }

            if (isOwnPit(me, idx) && landedEmpty) {          // 落进自己的空坑 → 捕获
                int opp = oppositeOf(idx);
                gain += pits[idx] + pits[opp];
                pits[myStore] += pits[idx] + pits[opp];
                pits[idx] = 0;
                pits[opp] = 0;
                break;
            }

            if (isOwnPit(me, idx) && pits[idx] > 1) {        // 落进自己的非空坑 → 链式播种
                cur = idx;
                continue;
            }

            break;
        }

        if (!gotExtra) side = 1 - me;
        ply++;
        return gain;
    }

landedEmpty 在内层循环里被反复赋值，最终恰好保留最后一次（也就是最后一石）落点投入前的状态——这一行是整段代码最关键的技巧。它让「落空坑」与「绕圈回到原坑」的语义都自动正确。

MAX_EXTRA_TURNS 是一个防御性上限。理论上存在长时间循环的可能，一旦超过 8 次额外回合就直接截断，把局面交给评估函数，避免搜索陷入活锁。

剩下几个纯函数放在 KalahState 里，无状态、可内联：

    static int storeIndexOf(int s) {
        return s == 0 ? PITS_PER_SIDE : BOARD_SIZE - 1;   // 6 或 13
    }

    static int nextIndex(int i) {
        return (i + 1) % BOARD_SIZE;
    }

    /** 对面坑：0<->12, 1<->11, 5<->7，统一为 12-p */
    static int oppositeOf(int pit) {
        if (pit == PITS_PER_SIDE || pit == BOARD_SIZE - 1) {
            throw new IllegalArgumentException("仓没有对面坑: " + pit);
        }
        return 12 - pit;
    }

    static boolean isOwnPit(int s, int idx) {
        return s == 0 ? (idx >= 0 && idx < PITS_PER_SIDE)
                : (idx > PITS_PER_SIDE && idx < BOARD_SIZE - 1);
    }

    /** 从 mover 的坑 from 播种到位置 to 需要的步数（跳过对手仓） */
    static int sowDistance(int mover, int from, int to) {
        int skip = storeIndexOf(1 - mover);
        int cur = from, steps = 0;
        for (int guard = 0; guard < 2 * BOARD_SIZE; guard++) {
            cur = nextIndex(cur);
            if (cur == skip) continue;      // 对手仓不占步数
            steps++;
            if (cur == to) return steps;
        }
        return -1;                          // 绕满两圈仍未命中，视为不可达
    }

sowDistance 是为评估函数准备的「距离查询」。有了它，「某坑一步能进仓吗」「某坑一步能捕获吗」都可以用一次数字比较判断，而不必真的模拟一遍——这在评估函数被调用数百万次时非常关键。

状态表示与守恒自检

规则模拟最容易出错，所以第一件事是写自检：石子总数必须永远保持 48。任何一次 applyMove 之后如果总数变了，就说明跳过对手仓的逻辑有 bug。

    /** 石子总数，用于守恒校验 */
    int totalStones() {
        int t = 0;
        for (int v : pits) t += v;
        return t;
    }

        // 规则自检：200 步随机走子后石子总数必须仍是 48
        KalahState probe = new KalahState(4);
        Random rnd = new Random(7);
        for (int step = 0; step < 200 && !probe.isTerminal(); step++) {
            List<Integer> moves = probe.legalMoves(probe.getSide());
            if (moves.isEmpty()) break;
            probe.applyMove(moves.get(rnd.nextInt(moves.size())));
            if (probe.totalStones() != 48) {
                throw new IllegalStateException("石子数异常：" + probe.totalStones());
            }
        }

这段自检在开发过程中真的抓到过一次「跳过对手仓时误减石子」的 bug——它比任何单元测试都更快定位问题。

三、一个必须警惕的陷阱：额外回合时视角不能翻转

这是实现播棋 AI 时最容易踩的坑，而且它不会报错，只会让 AI 变弱。

搜索用 negamax 形式，约定「分数永远从当前行动方视角计算」，于是父子节点之间要取负号：

score(child, 对手视角) = -score(child, 我方视角)

但播棋有一个特殊情况：当走子触发额外回合时，行动方没有变化。此时父子节点是同一方的视角，绝不能取负号——否则 AI 会把自己的好棋当成对手的好棋，自对弈胜率会直接崩到 50% 以下。

正确写法：

            KalahState next = s.copy();
            next.applyMove(mv);
            // 关键：额外回合时行动方不变，视角不翻转
            int v = (next.getSide() == s.getSide())
                    ? negamax(next, depth - 1, alpha, beta, ply + 1)
                    : -negamax(next, depth - 1, -beta, -alpha, ply + 1);

这个 bug 在实际调试中非常隐蔽：搜索能跑、不报错、节点数正常，但棋力明显不对。修掉它之后，同一套权重下「深度 8 vs 深度 2」的胜率从 7 胜 9 负变成了 17 胜 2 负。

四、静态评估函数：播棋要评什么

评估函数决定同等深度下的棋力。播棋的战术语言很集中，四项特征就足够：

    /** 静态评估（当前行动方视角） */
    private int evaluate(KalahState s) {
        int side = s.getSide(), opp = 1 - side;
        int storeDiff = s.getStore(side) - s.getStore(opp);

        int pitDiff = 0, myCap = 0, oppCap = 0, myExtra = 0, oppExtra = 0;
        for (int i = 0; i < KalahState.PITS_PER_SIDE; i++) {
            int myIdx = (side == 0) ? i : 7 + i;
            int opIdx = (side == 0) ? 7 + i : i;
            int mine = s.getPit(myIdx), theirs = s.getPit(opIdx);
            pitDiff += mine - theirs;

            if (mine > 0) {
                // 一步进仓 → 额外回合机会
                if (KalahState.sowDistance(side, myIdx, KalahState.storeIndexOf(side)) == mine) myExtra++;
                // 一步落到自己空坑 → 捕获机会（价值 = 1 + 对面坑里的石子）
                for (int j = 0; j < KalahState.PITS_PER_SIDE; j++) {
                    int target = (side == 0) ? j : 7 + j;
                    if (s.getPit(target) == 0
                            && KalahState.sowDistance(side, myIdx, target) == mine) {
                        myCap += 1 + s.getPit(KalahState.oppositeOf(target));
                        break;
                    }
                }
            }
            if (theirs > 0) {
                if (KalahState.sowDistance(opp, opIdx, KalahState.storeIndexOf(opp)) == theirs) oppExtra++;
                for (int j = 0; j < KalahState.PITS_PER_SIDE; j++) {
                    int target = (side == 0) ? 7 + j : j;
                    if (s.getPit(target) == 0
                            && KalahState.sowDistance(opp, opIdx, target) == theirs) {
                        oppCap += 1 + s.getPit(KalahState.oppositeOf(target));
                        break;
                    }
                }
            }
        }

        return STORE_WEIGHT * storeDiff + PIT_WEIGHT * pitDiff
                + CAPTURE_POT * (myCap - oppCap) + EXTRA_POT * (myExtra - oppExtra);
    }

四项特征各自的含义与权重（经验值）：

仓差权重最高是播棋的第一原则：同分情况下优先抢仓。因为坑里的石子只是「暂存」，对手随时可能用一次捕获把它们全部拿走；进了仓才是真正拿到手。

一个实现细节：CAPTURE_POT 这一项用的是「1 + 对面坑石子数」而不是捕获次数。这体现了播棋捕获的真实价值——捕获的收益不是 1 石，而是「自己的 1 石 + 对面整坑」。

五、迭代加深 Alpha-Beta：从 30 万到 6144

播棋分支因子约 6，深度 10 的全宽搜索是 6^10 ≈ 6000 万节点，不可接受。Alpha-Beta 在理想着法序下把复杂度降到 O(b^{d/2}) ≈ 6^5 ≈ 7776——四个数量级的差距。

主循环用迭代加深，从深度 1 逐层加深，并把上一层的最佳着法传给下一层做排序种子：

    /** 迭代加深主循环 */
    int think(KalahState state, int maxDepth, long timeLimitMs) {
        long start = System.currentTimeMillis();
        int bestMove = -1;
        nodes = 0;
        List<Integer> root = state.legalMoves(state.getSide());
        if (root.isEmpty()) return -1;

        for (int depth = 1; depth <= maxDepth; depth++) {
            int alpha = -INF, beta = INF;
            int localBest = -1, localValue = -INF;
            List<Integer> moves = state.legalMoves(state.getSide());
            if (useOrdering) orderMoves(state, moves, bestMove);
            boolean timeout = false;

            for (int mv : moves) {
                KalahState next = state.copy();
                next.applyMove(mv);
                int v = (next.getSide() == state.getSide())
                        ? negamax(next, depth - 1, alpha, beta, 1)
                        : -negamax(next, depth - 1, -beta, -alpha, 1);
                if (v > localValue) { localValue = v; localBest = mv; }
                if (v > alpha) alpha = v;
                if (System.currentTimeMillis() - start > timeLimitMs) { timeout = true; break; }
            }
            if (localBest != -1) bestMove = localBest;
            if (timeout) break;      // 超时则保留上一层结果，保证总有可用着法
        }
        return bestMove;
    }

timeout 的处理方式是关键：超时中断不能返回 -1，必须保留上一层的完整结果。这样任何时间限制下都有一个合法且质量有保障的着法可走。

negamax 主体含置换表查询与写入：

    private int negamax(KalahState s, int depth, int alpha, int beta, int ply) {
        nodes++;

        if (s.isTerminal()) {
            KalahState end = s.copy();
            end.settle();                                    // 终局：剩余石子归仓
            return end.finalMargin(s.getSide()) * WIN_SCALE;
        }
        if (depth == 0) return evaluate(s);

        long key = s.zobristKey(zobrist);
        int slot = (int) (key & (TT_SIZE - 1));
        int ttBest = -1;
        if (useTT && ttKey[slot] == key) {
            ttBest = ttMove[slot];
            if (ttDepth[slot] >= depth) {
                int f = ttFlag[slot];
                if (f == 0) return ttValue[slot];                       // 精确值
                if (f == 1 && ttValue[slot] > alpha) alpha = ttValue[slot];  // 下界
                if (f == 2 && ttValue[slot] < beta) beta = ttValue[slot];    // 上界
                if (alpha >= beta) return ttValue[slot];
            }
        }

        List<Integer> moves = s.legalMoves(s.getSide());
        if (useOrdering) orderMoves(s, moves, ttBest);

        int origAlpha = alpha, best = -INF, bestMove = -1;
        for (int mv : moves) {
            KalahState next = s.copy();
            next.applyMove(mv);
            int v = (next.getSide() == s.getSide())
                    ? negamax(next, depth - 1, alpha, beta, ply + 1)
                    : -negamax(next, depth - 1, -beta, -alpha, ply + 1);
            if (v > best) { best = v; bestMove = mv; }
            if (v > alpha) alpha = v;
            if (alpha >= beta) {
                history[s.getSide()][mv] += depth * depth;   // 历史启发：depth² 加权
                break;
            }
        }

        if (!useTT) return best;
        int flag = best <= origAlpha ? 2 : (best >= beta ? 1 : 0);   // 上界 / 下界 / 精确
        ttKey[slot] = key;
        ttDepth[slot] = depth;
        ttValue[slot] = best;
        ttFlag[slot] = flag;
        ttMove[slot] = bestMove;
        return best;
    }

置换表用直接映射（key & mask）而非链式哈希：槽位冲突时直接覆盖。对播棋这种分支小、状态多的情况，直接映射省略了链表遍历，实际更快；代价是偶尔丢掉有用的表项，靠「ttDepth >= depth 才复用」的检查来规避错误。

Zobrist 哈希把 14 个坑值 + 行动方打包成一个 long：

    long zobristKey(long[][] zobrist) {
        long h = 0L;
        for (int i = 0; i < BOARD_SIZE; i++) {
            h ^= zobrist[i][pits[i] % 64];      // 每个 (位置, 石子数) 一个随机数
        }
        return h ^ ((long) side << 62);         // 行动方单独占高位
    }

着法排序：让剪枝真正生效

剪枝效果完全取决于好着法是否被先尝试。排序做得好，剪枝率能到 90% 以上；不做排序，Alpha-Beta 几乎退化成 MiniMax。三级排序实现：

    /** 三级着法排序：置换表最佳着法 > 静态增益 > 历史启发 */
    private void orderMoves(KalahState s, List<Integer> moves, int ttBest) {
        int n = moves.size();
        int[] score = new int[n];
        int side = s.getSide();

        for (int i = 0; i < n; i++) {
            int mv = moves.get(i);
            int sc = history[side][mv];
            if (mv == ttBest) sc += 1 << 24;                 // 上一轮验证过的最佳着法

            KalahState t = s.copy();
            int g = t.applyMove(mv);
            sc += g * 128;                                   // 立即进仓的收益
            if (t.getSide() == side) sc += 1 << 12;          // 产生额外回合
            if (t.opponentPitsEmpty(1 - side)) {
                t.settle();
                sc += t.finalMargin(side) > 0 ? (1 << 22) : -(1 << 22);   // 能终局且有利
            }
            score[i] = sc;
        }

        for (int i = 1; i < n; i++) {                        // 分支因子<=6，插入排序最快
            int kMov = moves.get(i), kSc = score[i], j = i - 1;
            while (j >= 0 && score[j] < kSc) {
                moves.set(j + 1, moves.get(j));
                score[j + 1] = score[j];
                j--;
            }
            moves.set(j + 1, kMov);
            score[j + 1] = kSc;
        }
    }

规模只有 6 个元素时，插入排序的常数比 Collections.sort 小一个数量级，并且天然稳定——这是「知道数据规模」带来的真实优化。

六、实测：剪枝到底能救多少

用消融测试（ablation）开关排序与置换表，在同一初始局面下测量节点数：

这张表读起来信息量很大：

• 深度 10 时，排序+置换表只要 6144 个节点，全关需要 300432 个，相差 49 倍。这是 Alpha-Beta 配合着法排序从「O(b^d)」走向「O(b^{d/2})」的直接证据。
• 置换表在深层的贡献远大于浅层：深度 6 时开启置换表只省了 10%（733→659），深度 10 时省了 38%（9926→6144）。因为深层搜索里「不同走子顺序到达同一局面」的重合率急剧上升。
• 从深度 8 到深度 10，全关配置节点数增长 7.6 倍（接近 6^2=36 的一半），而带排序+置换表只增长 2.7 倍。

单步搜索耗时（初始局面，Intel 同代单核量级）：

耗时包含 JVM 预热与状态拷贝开销，因此不完全线性于节点数；纯搜索部分随深度增长约每 2 层翻 2.7 倍。

七、自对弈验证棋力

规则对、评估对，棋力才谈得上。用带开局随机化的自对弈（每局前两步随机走，避免确定性导致重复对局），20 局统计：

几点观察：

• 深度 8 对深度 6 的胜率 90%，而深度 10 对深度 8 只有 65%——搜索深度的边际收益递减，因为播棋的战术主要在两个「层」内展开（进仓与捕获），再深的搜索拿不到更多信息。
• 「深度 8 vs 深度 8」出现 14 胜 6 负，纯粹是 Zobrist 种子不同导致的评估微小差异与开局随机化造成的先后手差异，不是棋力差距。
• 每步平均节点数只有几百到几千，说明实际对局中置换表命中率极高——对局越往后，局面越简单、重合越多。

如果想让 AI 更强，最划算的不是加深搜索，而是用自对弈调权重：四个权重的组合空间不大，SPSA 或简单的爬山搜索在几百局内就能找到明显优于手调值的参数。

八、复杂度与工程改进

复杂度

• 单步播种：O(S)，S ≤ 48（总石数），远小于常数级别。
• 搜索：最坏 O(b^d)，Alpha-Beta 最优 O(b^{d/2})；实测排序+置换表相对全关在深度 10 时有 49 倍差距。
• 空间：置换表 2^18 槽位，long key + 3 个 int，约 6 MB；递归深度 = 搜索深度，可忽略。
• 状态拷贝：每次 copy() 复制 14 个 int（56 字节），是对局中最主要的分配压力。

可改进方向

1. 增量 Zobrist：在 applyMove 内同步维护哈希（每个被改动的坑 XOR 一次），省掉每次 O(14) 重算。对深度 12+ 是明显收益。
2. 空着裁剪不适用：播棋没有「放弃回合」的概念，null move 会破坏规则语义。替代方案是 late move reduction——把排序靠后的几个着法先减一层搜索，若返回值仍然超界再补搜。
3. 杀手着法：按「层」记录剪枝着法，与历史启发叠加，通常还能再降 10~20% 节点。
4. 主变例收集（PV）：把上一轮的最佳路线作为排序首选，比「只传首着」更强。
5. 端局精算：当总石子数很少（如 < 10）时切换到完全搜索，播棋端局常有可精确求解的路径。
6. 权重自对弈调参：STORE_WEIGHT / PIT_WEIGHT / CAPTURE_POT / EXTRA_POT 四个参数用爬山法或 SPSA 优化，是比加深搜索更划算的棋力提升手段。

九、小结

播棋把「规则模拟的精确性」和「搜索效率」两个主题结合得非常紧密：

• 规则层：跳过对手仓不减石、落空坑要读投入前状态、绕圈回原坑按捕获处理——三处语义偏差就会让整局崩坏。石子守恒自检是成本最低的防线。
• 搜索层：分支因子 6、深度几十步的窄深树，是 Alpha-Beta + 置换表最好的舞台。实测从 300432 节点降到 6144 节点，是「算法优于硬件」的典型例子。
• 最隐蔽的坑：额外回合时不翻转视角。它不报错、不崩溃，只是让 AI 悄悄变弱，修好之后胜率从 7 胜 9 负跳到 17 胜 2 负。

把这套框架的 applyMove 与 evaluate 换掉，就能直接复用到其他「小分支、深搜索」的棋类——比如黑白棋的端局求解、井字棋的完全解搜索。