Skip to content

黑白棋 AI 算法深入

这篇文档解释本项目的 AI 怎样从一个棋盘数组算出下一步。它从棋盘表示开始，一直讲到搜索、剪枝、评估函数、终局搜索和统计数据。读完后，读者应该能把右侧搜索评分表里的数字和代码里的步骤对应起来。

先看一次完整输入输出

浏览器传给 Rust 的入口是 search_best_move()。它不是直接看网页上的棋子，而是接收四个值：

pub fn search_best_move(
    cells: &[i8],
    is_black_turn: bool,
    think_time_ms: u32,
    allowed_moves: &[u8],
) -> String

cells 是长度 64 的数组。黑棋是 -1，白棋是 1，空格是 0。数组下标就是棋盘格编号：

index = row * 8 + col

左上角是 0，右上角是 7，左下角是 56，右下角是 63。例如 row = 2, col = 3 时，编号是 19。

allowed_moves 是当前 Worker 分到的候选步，按 [row, col, row, col] 编码。假设某个 Worker 只负责两个候选步 (2, 3) 和 (4, 5)，它收到的数组就是：

[2, 3, 4, 5]

Rust 返回 CSV 字符串：

row,col,score,depth,nodes,elapsed_ms,nps

例如：

2,3,18,8,125000,3970,31486

含义是：AI 选择 (2, 3)，评分是 18，完成到 8 层，访问了 125000 个节点，用时 3970 毫秒，速度约 31486 节点每秒。正常结果里，row,col 必须是合法步，depth 和 nodes 应该大于 0。

从初始局面走一遍

标准黑白棋开局只有中间四个格子有棋。按本项目坐标，常见初始局面可以写成：

row 3, col 3: white
row 3, col 4: black
row 4, col 3: black
row 4, col 4: white

换成一维编号：

3 * 8 + 3 = 27  white
3 * 8 + 4 = 28  black
4 * 8 + 3 = 35  black
4 * 8 + 4 = 36  white

如果黑棋先走，合法步通常是：

(2, 3), (3, 2), (4, 5), (5, 4)

以 (2, 3) 为例，它的一维编号是 19。从 19 向下看，会先看到 27 的白棋，再看到 35 的黑棋，所以 27 会被翻成黑棋。这一步的翻子 mask 里包含 1 << 27。

落子后的变化是：

19 从空格变成黑棋
27 从白棋变成黑棋
28 和 35 仍是黑棋
36 仍是白棋

这时搜索不会立刻说“这步一定最好”。它会把这个新局面交给下一层，让白棋选择回应。白棋每个回应又会产生新局面。搜索深度越深，AI 越能看到“眼前翻子多但后面送角”这类问题。

这个例子可以用来检查三个函数是否连起来了：

  • flips_for_move() 对 (2, 3) 应该返回包含 27 的 mask。
  • apply_move() 应该让 19 和 27 都属于黑棋。
  • negamax() 后续应该站在白棋行动方继续搜索，而不是继续让黑棋连下。

棋盘为什么转成 Bitboard

网页和 JavaScript 用二维数组更直观，但搜索引擎需要反复复制局面、找合法步、翻棋子。如果每次都操作 8x8 数组，代码容易写，但每个节点都要遍历和复制更多数据。

本项目把棋盘转成两个 u64：

struct Board {
    black: u64,
    white: u64,
}

一个 u64 有 64 个 bit，刚好对应 64 个格子。某个 bit 是 1，表示这个颜色占了这个格子。黑白各一个 u64，就能表示完整棋盘。

举个例子，如果黑棋在左上角 (0, 0)，编号是 0，那么：

black |= 1 << 0

如果白棋在 (3, 4)，编号是 28，那么：

white |= 1 << 28

判断某格是否被占也很直接：

occupied = black | white
occupied & (1 << idx) != 0

这个表示法的输入是 cells 数组，输出是 Board { black, white }。判断正常的方式是：棋盘上每个非空格都应该只出现在一个颜色的 bitboard 中，不能同时出现在黑白两个 bitboard 中。

合法步怎样生成

黑白棋的合法步必须满足一个条件：落子后，至少在一个方向上夹住对方棋子。方向有 8 个：

左上、上、右上、右、右下、下、左下、左

代码先遍历 64 个格子。已经有棋子的格子跳过。空格会调用 flips_for_move()，检查这一步会翻哪些棋子。

以黑棋行动为例，某个方向的检查过程是：

  1. 从落子点往这个方向走一格。
  2. 如果先看到白棋，就把这些白棋记入临时集合。
  3. 继续走，直到看到黑棋、空格或棋盘边界。
  4. 如果最后看到黑棋，而且中间至少有一个白棋，这条线上的白棋可以翻。
  5. 如果最后看到空格或边界，这个方向不成立。

flips_for_move() 的输出是一个 bit mask。mask 中为 1 的格子就是会被翻的棋子。如果 mask 是 0，这一步不是合法步。

小例子：

行内片段：黑 白 白 空
位置编号：10 11 12 13

如果黑棋下在 13，向左看会先看到 12 和 11 两个白棋，再看到 10 的黑棋，所以 11 和 12 会被翻。输出 mask 包含 1 << 11 和 1 << 12。

落子怎样更新局面

找到翻子 mask 后，apply_move() 会生成新棋盘。黑棋落子时：

new_black = old_black | flips | move_bit
new_white = old_white & !flips

也就是把落子位置和翻到的棋子加入黑棋，同时从白棋中移除这些被翻的棋子。白棋落子时反过来。

这个函数的输入是旧 Board、落子编号和行动方。输出是新 Board。正常结果应该满足：

  • 落子位置从空格变成当前颜色。
  • flips 中的棋子全部换色。
  • 其他棋子不变。
  • 黑白 bitboard 没有重叠 bit。

搜索树是什么

AI 不是只看下一步翻几个子。它会假设双方之后都尽量下好棋，然后评估某个候选步的长期结果。

如果当前黑棋有 4 个合法步，搜索树第一层有 4 个分支。黑棋选其中一步后，轮到白棋。白棋可能也有若干合法步，于是每个黑棋分支下面又展开白棋分支。这样继续下去，就形成一棵树。

搜索深度 depth = 1 表示只看当前 AI 的一步。depth = 2 表示看 AI 一步和对手一步。depth = 8 表示向后看 8 个半回合。

搜索树的输入是当前局面和行动方。输出不是整棵树，而是根节点某个候选步的分数。右侧面板里的 nodes 表示搜索实际访问了多少个树节点。

NegaMax 为什么能简化 Minimax

传统 Minimax 会写两套逻辑：轮到自己时选最大分，轮到对手时选最小分。NegaMax 利用一个事实：对手眼里的好分数，就是我眼里的坏分数。

所以递归可以统一写成：

当前局面分数 = - 对手行动后能拿到的最好分数

代码里这一行就是核心：

let score = -negamax(next, next_depth, -beta, -alpha, !black_turn, ply + 1, ctx);

进入下一层时，行动方变成对手，alpha 和 beta 也取负并交换。返回后再取负，就回到当前行动方视角。

为什么要区分 root_black 和 black_turn？因为最终评分要站在本次 AI 的视角。root_black 表示这次搜索的 AI 是不是黑棋，整个搜索过程中固定不变。black_turn 表示当前递归层轮到谁，会每层变化。

判断正常的方式是：同一个终局，如果根节点 AI 胜，terminal_score() 应该是大正数；如果根节点 AI 败，应该是大负数。换边搜索时，NegaMax 通过取负保持这个方向一致。

Alpha-Beta 剪枝剪掉什么

Alpha-Beta 不改变 Minimax 的结果，只是不搜索已经不可能影响答案的分支。

可以把 alpha 理解成“当前这一方已经能保证的最好下限”，把 beta 理解成“对手允许你达到的上限”。如果搜索到某一步时发现：

alpha >= beta

说明这条线已经好到或坏到对手不会让它发生，后面的兄弟分支不需要继续看。

一个简化例子：

黑棋有 A、B 两步。
A 搜完后，黑棋知道自己至少能得到 20 分。
现在看 B。白棋在 B 后有三个回应：B1、B2、B3。
只看完 B1，就发现白棋能把黑棋压到 5 分。

黑棋已经有 A 的 20 分，不会选择只能保证 5 分的 B。于是 B2 和 B3 不再需要搜索。剪掉它们不会影响根节点选择。

剪枝效果强不强，取决于好走法是否排在前面。如果先搜索强分支，alpha 和 beta 会更快收紧，后面能剪掉更多节点。

走法排序怎样帮助剪枝

order_moves() 只改变搜索顺序，不直接改变评分。本项目给每个候选步一个排序分：

TT 最佳步 + killer move + history 分数 + 角奖励 + 位置权重 + 翻子数量

这些信号含义如下：

  • TT 最佳步：置换表里记录过这个局面的最好走法，优先试。
  • killer move：同一搜索层曾经造成剪枝的走法，可能在相似分支里继续强。
  • history 分数：某个走法多次造成剪枝，就长期提高它的排序。
  • 角奖励：角通常不会再被翻，是黑白棋里最强的位置。
  • 位置权重：浅层搜索时用静态棋盘权重提供基本方向。
  • 翻子数量：只作为排序参考，不等同于最终评估。

正常情况下，排序越有效，同样深度下 nodes 越少，或者同样时间内 depth 更高。

置换表缓存什么

搜索中，同一个局面可能通过不同落子顺序到达。置换表用一个 key 表示搜索状态：

black bitboard + white bitboard + side to move

值里保存：

depth, score, flag, best_move

depth 表示这个缓存结果至少搜索到了多深。score 是分数。best_move 用于下次排序。flag 有三种：

  • TT_EXACT：这个分数就是准确窗口内的结果。
  • TT_LOWER：真实分数至少不低于这个值。
  • TT_UPPER：真实分数最多不高于这个值。

为什么有上下界？因为 Alpha-Beta 有时会提前剪枝，没有完整搜完所有兄弟分支。这样的结果仍然有用，可以收紧下一次搜索的 alpha 或 beta。

置换表的输入是局面和行动方。输出可能是直接返回分数，也可能只是提供一个优先搜索的 best_move。正常结果是：开启置换表后，重复局面越多，节点数越少。

评估函数算什么

中盘不能每次都搜到终局，所以深度到 0 时需要估算局面好坏。项目的 evaluate() 把多个分数组合起来：

positional
+ mobility
+ corners
- frontier
+ material
+ parity
- danger
+ stable

每一项都有明确含义。

位置权重 positional 来自 64 格静态表。角是高正分，角旁的 X 位和 C 位在角未占时通常是负分。它的作用是让浅层搜索不要只看翻子数量。

机动性 mobility 比较双方合法步数量。合法步越多，下一步选择越多，也越容易逼对方走坏棋。

角 corners 单独加高权重。角一旦占住不会被翻，所以它比普通边子更可靠。

前沿子 frontier 指周围接触空格的棋子。前沿子容易被对手利用和翻掉，所以自己的前沿子多通常是风险。

子数 material 是当前棋子数量差。它有用，但中盘不能过重，因为黑白棋经常先少后多。

奇偶性 parity 只在空格较少时启用。终盘常常由谁拿到最后一手影响局部收益。

角旁危险 danger 惩罚空角附近的 X 位和 C 位。如果角还没人占，提前贴着角下，可能把角送给对手。

稳定子 stable 估计不会再被翻的棋子。它比当前子数更接近长期优势。

判断评估是否正常，不能只看某一项。比如某步翻了很多子，但同时给了对手角，综合分就应该下降。

稳定子怎样估计

完整稳定子判断很复杂。本项目用了一个保守近似，宁可少算，也不把明显会被翻的中腹棋算成稳定。

第一层是边稳定子。从已占角开始，沿边连续同色的棋子都算稳定。例如左上角是黑棋，第一行从左往右连续三个黑棋，那么这三个边子都稳定。只要中间断开，后面的棋子不算。

第二层是角区域扩张。从四个角向内看，如果某个同色棋子被角方向上的稳定棋支撑，就加入稳定集合。支撑条件要求行、列、斜向都被已有稳定棋或边界支撑。

输入是当前 Board。输出是稳定棋 bit mask。最后统计 mask 里黑白各有多少棋，得到稳定子差。

这个算法的正常表现是：占角后，沿边连续棋子的稳定分会明显增加；中腹临时多出来的棋子不会轻易增加稳定分。

终局搜索为什么不同

当空格数不超过 EXACT_ENDGAME_EMPTY，当前代码设为 14，搜索会进入终局模式。这个时候引擎尽量直接搜到双方都无棋可走，而不是用评估函数估算。

原因很简单：终局空格少，搜索树变小，真实胜负可以算出来。此时如果还用中盘评估，可能出现“位置看起来好，但最后少一子输棋”的问题。

终局评分使用很大的胜负权重：

diff.signum() * 10_000_000 + diff * 10_000

diff 是根节点 AI 的最终子数差。赢 1 子也会比任何中盘位置分更重要。这样 AI 在终局会优先保证真实胜负，然后才考虑赢多少子。

时间预算怎样控制

浏览器默认给每步 4000 毫秒。Rust 内部会减掉一点余量：

budget = think_time_ms - 30ms

这样可以给消息传递和页面更新留空间，避免刚好压线造成体感卡顿。

迭代加深按深度 1、2、3 继续搜索。每完成一层，就更新当前最佳结果。如果搜索中超时，函数停止展开并返回上一个已经完成的结果。

正常情况下，elapsed_ms 会接近但不明显超过 4000。早期局面分支多，深度可能较低；终局空格少，深度可能更高。

Worker 并行怎样改变搜索

JavaScript 会把根节点合法步分给多个 Worker。每个 Worker 只搜索自己的候选步集合。所有 Worker 返回后，ai-manager.js 选择 score 最高的结果。

这不是把同一棵树拆到多线程共享搜索，而是根节点分片。好处是实现简单，浏览器兼容性好，每个 Worker 都独立加载 Wasm，不需要共享内存。

输入是完整棋盘和该 Worker 的 allowed_moves。输出是这个分片里的最佳走法。主线程再把所有分片结果合并。

判断正常的方式是：workerCount 不应超过合法步数量，所有 Worker 的 nodes 会加总到最终结果里。机器核心数越多，根节点候选步越多时越容易看到收益。

怎样读搜索评分表

右侧表格不是装饰，它能帮助判断算法是否真的在工作。

深度 表示完成的最大搜索层数。深度越高，AI 看得越远，但不同局面的深度不能直接比较。分支少的局面天然更容易搜深。

节点 表示访问过多少局面。节点越多不一定越好。如果走法排序和剪枝更有效，可能用更少节点达到同样深度。

NPS 是每秒节点数。它受设备、浏览器、Wasm 性能和局面复杂度影响。它适合观察同一机器上不同版本的变化。

耗时 应该接近时间预算。若明显很短，可能是合法步很少、终局已被搜完，或 Worker 提前失败。

分数 是相对当前 AI 的分数。正分表示当前搜索认为这步对 AI 有利，负分表示不利。终局附近如果出现千万级分数，通常表示已经搜索到真实胜负。

从代码跟一次搜索

一次 AI 搜索可以按这个路径读代码：

  1. search_best_move() 接收 JS 输入。
  2. board_from_cells() 把 64 格数组转成两个 bitboard。
  3. decode_allowed_moves() 解码并验证 Worker 分到的候选步。
  4. 外层 for depth in 1..=MAX_DEPTH 做迭代加深。
  5. 根节点对每个候选步调用 apply_move()。
  6. negamax() 递归搜索对手回应。
  7. legal_moves() 和 flips_for_move() 生成后续合法步。
  8. order_moves() 用缓存、killer、history、角和位置权重排序。
  9. evaluate() 在中盘叶子节点估分。
  10. terminal_score() 在终局给真实胜负分。
  11. 搜索结束后格式化 row,col,score,depth,nodes,elapsed_ms,nps。

如果要调试一个异常结果，先记录输入棋盘、行动方和合法步，再检查返回的 row,col 是否在合法步内。然后看 depth、nodes、elapsed_ms。这三个数能区分“没有开始搜”、“搜了但很浅”、“搜完太快”和“接近时间预算正常返回”。