写一个会下中国象棋的 AI（上）：搜索、剪枝与 8 秒预算

上篇讲了架构，这篇进入重头戏：AI 引擎。先泼一盆冷水——"让电脑下象棋"在原理上早就不是难题，难的是在有限的算力预算里尽量下得不像臭棋篓子。我的引擎全部跑在 PHP（Webman 常驻进程）里，每步思考预算是 8 秒（self::$aiTimeBudget = 8.0，Events.php:39）。下面把所有关键机制对照真实代码拆开讲。

一、核心思路：极大极小 + Alpha-Beta 剪枝

象棋是零和博弈。AI 想最大化自己的分，对手想最小化——这就是"极大极小"（minimax）。但裸 minimax 要把整棵博弈树搜到底，象棋平均分叉 30 步、搜 6 层就是 30^6 ≈ 7 亿个节点，8 秒根本不可能。

Alpha-Beta 剪枝是唯一能救命的招：维护一个 [alpha, beta] 窗口，一旦某条支路证明"再算下去也不可能比已知最优更好"，直接砍掉整棵子树。代码在 alphaBetaSearch（Events.php:830），入口的时间预算检查在 :869：

// Events.php:869 —— 每进一个节点先看时间够不够
if (self::$searchDeadline > 0.0 && microtime(true) > self::$searchDeadline) {
    throw new \Exception('timeup'); // 超时：抛出，由上层沿用上一层结果
}
// Events.php:875 —— 深度到底转静态搜索，消除"水平线效应"
if ($depth === 0) {
    return self::quiescence($boardState, $alpha, $beta, $isMaximizingPlayer, $aiColor, 0, $ply);
}

二、迭代加深：深度是上限，时间是老板

我不会预先定死"搜 6 层"。self::$depth = 6（Events.php:28）只是深度上限，真正搜多深由 8 秒预算说了算。做法叫迭代加深（makeAIMove，Events.php:621 起）：

self::$searchDeadline = microtime(true) + self::$aiTimeBudget; // :617
for ($d = 1; $d <= self::$depth; $d++) {
    try {
        $move = self::alphaBetaSearch($boardState, $d, -PHP_INT_MAX, PHP_INT_MAX, true, $aiColor, true);
    } catch (\Exception $e) {
        break; // 这一层超时，沿用上一层已确定的着法
    }
    if (is_array($move) && isset($move['from'], $move['to'])) {
        $bestMove = $move;
        $completedDepth = $d;
    }
}

好处很明显：浅层先出结果，时间够就加深，超时立刻停，总耗时恒被预算兜住。实战里往往只搜到 3~5 层就被时间截断——这点后面讲评估函数时很关键。

三、静态搜索（quiescence）：别在"炮口下的马"上停手

如果一到底就返回评估分，会出现经典 bug：AI 刚把车送到对方炮口下，因为"深度到底了"就当作安全局面——下一步对方吃车它才发现亏大了。这叫水平线效应。

解法：深度到底后，继续把"吃子链"算到底，直到局面安静。quiescence（Events.php:1126）只展开吃子着，把战术陷阱暴露出来。代价是它也会被时间预算检查（:1129），不会无限递归。

四、走法排序：让剪枝砍得更多

Alpha-Beta 的剪枝效率极度依赖"好着法先算"。如果最优着总被排最后，剪枝几乎失效；排最前，大半子树直接被砍。我用三级排序（sortMoves，Events.php:1244 起）：

MVV-LVA（吃大子优先、用小子吃大子更优先），基数 1000000 保证吃子着永远排在最前（:1266）；
Killer 着：同一层（ply）曾经触发剪枝的安静着，下一节点复用（:1109）；
History 历史分：跨层累计"历史上好用"的安静着（:1118，上限 $historyMax 保证不盖过杀棋）。

五、空着裁剪（Null Move）：跳过"明显没威胁"的局面

一个直觉：如果我方走完，对方竟然"走一步空着（不走动任何子）"都拦不住我方优势，那当前局面已经大优，没必要细算。这就是空着裁剪，减深量 R=2（Events.php:939）：

if (self::$enableNullMove && !$isRoot && !$currentInCheck
    && self::hasEnoughMaterialForNullMove($currentPlayerColor, $boardState)) {
    $nullDepth = max(0, $depth - 1 - 2); // R=2
    // 走一步"空着"后递归，若该空着都足够好则直接剪枝
}

hasEnoughMaterialForNullMove 是安全阀：残局子少时不开空着裁剪，避免把"兑子求和"误判成大优（象棋里有"逼和"陷阱，空着裁剪的 zugzwang 风险在残局尤为真实）。

六、置换表：搜过的局面别再搜

同一局棋，不同走法顺序会反复到达相同局面。把"局面哈希 → 已知评分/边界"存进置换表（$transpositionTable，Events.php:898 查、:1079 存），命中就直接复用。这里有个细节：存边界时必须带着原始的 beta（$originalBeta，:886、:1074），否则复用来的 alpha/beta 窗口错位会污染结果。

七、将军延伸与重复判负

将军延伸：被将军时多探一层（:998），确保"将杀序列"不被深度截断漏掉；
重复 / 长将判负：detectRepetition（Events.php:1550）用"局面哈希 + 轮走方指纹"，同一局面第 3 次出现，若单方一直在将则判长将负、否则判和。recordPositionHistory（Events.php:1628）吃子时清零计数——这是后来专门补的规则正确性特性。

八、小结

到这一层，引擎已经"会下棋"了：8 秒内尽量深搜 + 剪枝 + 不漏战术。但光有搜索还不够——怎么给一个局面打分，才是棋力的天花板。下篇就讲评估函数，以及一段我自己的"翻车"故事：几个看起来很合理的评估改进，最后被我自己写的 A/B 对弈测试一一证伪。