算法说明¶

本页解释引擎如何选择一步棋。内容从棋盘编码开始，一直到浏览器里显示出来的搜索结果。

阅读时可以把每一节都当成同一个问题的不同层次：

输入是什么：浏览器、Worker 或 Rust 具体收到什么数据。
处理什么：这一层负责减少哪些搜索浪费，或识别哪类棋形。
输出是什么：下一层会拿到什么结果继续计算。
怎么判断正常：界面上的分数、节点数、深度和落子是否符合预期。

如果只想确认引擎有没有认真工作，重点看候选点生成、落子排序、五格窗口威胁、NegaMax 和 Alpha-Beta。它们决定 AI 是在算棋，还是只是在做表面评分。

实际工程算法¶

这一节只写项目当前代码真实使用的流程和数值。Wasm 导出入口在 rust-ai/src/lib.rs 的 search_best_move()，实际搜索在 rust-ai/src/search.rs，棋盘和胜负判断在 rust-ai/src/board.rs，评估和排序在 rust-ai/src/evaluate.rs，候选点生成在 rust-ai/src/movegen.rs。

一步棋的真实流程¶

AI 每次行动时，浏览器不会把整棵树交给 Rust。JavaScript 先维护 UI、棋盘数组和 Worker 池，再把当前局面发给 Wasm。

search_best_move() 的输入是：

cells             225 格棋盘，1 黑棋，-1 白棋，0 空点
is_black_turn     当前是否黑棋行动；人机模式下 AI 通常是白棋，所以这里多为 false
think_time_ms     默认 5000 毫秒
allowed_moves     当前 Worker 分到的候选点，编码为 row * 15 + col

Rust 收到后按这个顺序处理：

Board::from_cells() 把 225 格数组转成 cells、black_bits 和 white_bits。
root_moves() 解码 allowed_moves，并重新验证坐标是否在棋盘内、该点是否为空。
如果 allowed_moves 为空，generate_candidates() 自己生成根候选。
如果 think_time_ms <= 2，只返回候选热力图，不启动递归搜索；这是 JavaScript 拆分 Worker 任务前用的快速请求。
正常搜索从深度 1 开始迭代加深，最大深度是 12。
每个根候选先 place() 到克隆棋盘上，再调用 negamax() 搜索对手回应。
深度到 0、棋盘满了或采样发现超时时，用 relative_score() 返回当前行动方视角的估分。
根节点先用 root_forcing_score() 检查立即五连、必须堵、我方 VCF 和对手 VCF。
只有当前深度的全部根候选都完整搜完，才更新本层最佳结果；如果中途超时，丢弃这一层半成品。
返回 r、c、score、depth、nodes、time_ms、nps 和 heatmap。

判断结果是否正常，可以看几项：

r,c       应该是空点，并且来自该 Worker 的 allowed_moves，除非这是未分片的根搜索。
depth     正常思考时应该大于 0；只拿热力图时允许是 0。
nodes     正常搜索时应该大于 0。
time_ms   通常接近 5000 毫秒；如果很短，可能是强制战术已经提前确定。
heatmap   应该只覆盖候选空点，不应该画到已有棋子上。

当前搜索宽度和时间¶

当前搜索常量在 rust-ai/src/search.rs：

ROOT_LIMIT   = 36
CHILD_LIMIT  = 22
MAX_DEPTH    = 12
TT_SIZE      = 1 << 18

含义是：

根节点最多保留 36 个候选点，避免主动进攻点在 Worker 分片前被截掉。
子节点最多保留 22 个候选点，让 Alpha-Beta 能验证进攻后的反击。
迭代加深最多搜到 12 层；时间先到就返回上一层完整结果。
置换表使用固定大小槽位，避免搜索过程中反复扩容。

时间控制没有额外扣掉固定余量。Rust 在入口处直接设置：

deadline = Date.now() + think_time_ms

递归中不会每个节点都调用时间函数，而是按节点数采样。这样可以减少 Wasm 调 JavaScript 时间函数的开销。正常情况下，右侧表格里的耗时会接近 5 秒；如果出现几十毫秒就返回，通常是根节点发现立即胜、必须堵或强制四。

候选点生成¶

自由五子棋所有空点都合法，但搜索 225 个点会让分支爆炸。当前 generate_candidates() 的工程规则是：

空棋盘：只返回天元 (7, 7)
非空棋盘：只看已有棋子两格范围内的空点
排序：每个候选只计算一次 quick_move_score()
截断：按 order_score 从高到低保留 limit 个

这里有一个重要性能约束：排序比较函数只比较缓存好的 order_score，不会在比较过程中落子、不会递归搜索、不会生成子局面。这能避免排序阶段反复做昂贵计算。

快速排序的真实数值¶

当前 rust-ai/src/evaluate.rs 使用这些战术阈值：

WIN_NOW          = 40_000_000
BLOCK_WIN_NOW    = 35_000_000
FORCE_FOUR       = 8_000_000
OPEN_THREE       = 1_500_000
DOUBLE_THREAT    = 4_500_000

quick_move_score() 的真实分层是：

自己下一手成五：        WIN_NOW
对手下一手成五：        BLOCK_WIN_NOW
自己的强制四：          34_000_000 + attack_threat + attack_fork
防守对手强制四：        30_000_000 + defend_threat + defend_fork
自己的双威胁：          22_000_000 + attack_threat + attack_fork
防守对手双威胁：        18_000_000 + defend_threat + defend_fork
自己的活三：            11_000_000 + attack_threat + attack_fork
防守对手活三：           7_000_000 + defend_threat + defend_fork
普通局面：center_bonus + attack * 8 + defend * 4 + attack_threat * 3 + defend_threat * 2 + attack_fork + defend_fork / 2

这组数值表达的是当前攻防策略：

自己能赢，直接最高。
对手马上能赢，必须堵。
双方都有强制威胁时，AI 更愿意主动制造自己的强制四。
没有直接杀棋时，普通局面的进攻权重高于防守权重，避免满盘只补防。
防守仍然存在，但主要处理会立刻输或会进入强制线的点。

根节点战术短路¶

根节点有两层战术短路。第一层是 root_forcing_score()，它来自 rust-ai/src/threat.rs，专门处理立即胜、防立即胜和 VCF 连续冲四。

VCF 的输入是当前棋盘、候选落子和行动方。输出是一个可选分数：

自己立即五连：                 620_000_000
堵住对手立即五连：             580_000_000
自己进入 VCF 强制胜：           540_000_000
落子后让对手立即胜或 VCF 胜：  -540_000_000 或更低
没有证明强制线：               None，回到普通搜索

VCF 只展开“落子后产生下一手直接成五点”的冲四招法。防守方也只需要尝试堵这些直接成五点。如果某个进攻招法让防守方所有堵法之后仍然回到攻击方 VCF，才算证明强制胜。这个限制很重要：它让 AI 更会进攻，但不会把普通活三直接当成已经赢。

第二层是 root_tactical_score()，它只对确定性很强的局部情况提前返回：

自己立即五连：500_000_000
对手立即五连：450_000_000
落子后产生至少两个直接成五点：380_000_000 + 成五点数量 * 10_000_000
自己的强制四：300_000_000 + attack_threat + attack_fork
防守对手强制四：270_000_000 + defend_threat + defend_fork

“落子后产生至少两个直接成五点”用于处理乘胜追击。比如白棋已经形成双三，下一手如果能让自己同时拥有两个成五落点，对手通常只能堵一个，白棋就应该继续压迫。

普通活三不会在这里直接短路。它会提高排序分，让 Alpha-Beta 优先搜索，但仍然要继续算对手回应。这样做是为了避免 AI 只看到进攻形状，却没看到对手下一手的偷袭。

五格窗口和双威胁¶

window_threat_stats() 会枚举所有包含候选点的五格窗口。每个窗口用 score_window() 评分：

5 颗己方棋：              50_000_000
4 颗己方棋，1 空，两端开： 12_000_000
4 颗己方棋，1 空，一端开：  8_000_000
4 颗己方棋，1 空，两端堵：  4_000_000
3 颗己方棋，2 空，两端开：  1_500_000
3 颗己方棋，2 空，一端开：    450_000
2 颗己方棋，3 空，两端开：     45_000
其他：                         0

同时它还会统计：

force_count       分数达到 FORCE_FOUR 的窗口数量
open_three_count  分数达到 OPEN_THREE 的窗口数量

fork_bonus() 用这两个计数识别多威胁：

两个以上强制四：          18_000_000
一个强制四 + 一个活三：    9_000_000
两个以上活三：             4_500_000

这就是当前版本比单纯防守更主动的关键。一步棋如果同时制造两个问题，对手通常只能处理一个，AI 下一手就更容易进入必胜线。

全局窗口评估¶

静态评估不只扫描连续棋。score_side() 还会调用全局五格滑动窗口评估，识别当前局面里已经存在的断点四、跳三和活三。

这样做是为了避免启发式不一致：

排序阶段：XX_XX 是强制威胁。
叶子评估：也必须看懂 XX_XX，而不能把它拆成两个普通二连。

窗口分类会检查空位在窗口内的具体位置。XX_XX 是强制四，但不是真活四；X_X_X 是跳三或眠三，也不是真活三。

连续棋形的静态分¶

pattern_score() 用于连续线段和局部形状：

五连或更长：20_000_000
活四：       3_200_000
冲四：         360_000
活三：         110_000
眠三：          12_000
活二：           3_500
眠二：             600
单子双开：          80
其他：              10

这个表不是胜率表。它只是在搜索到叶子节点时给局面一个可比较的整数。真正的决策仍然由 NegaMax 把多层结果回传到根节点。

右侧表格怎么验证¶

右侧“AI 搜索评分”表可以直接观察这些工程参数是否生效：

深度：迭代加深完成到哪一层。局面越复杂，深度可能越低。
节点：实际访问的局面数。候选宽度变大后，节点数通常会上升。
NPS：每秒节点数，主要反映设备性能和 Wasm 执行效率。
耗时：正常搜索通常接近 5 秒；强制战术可能明显更短。
分数：千万级通常表示立即五连、必须堵或强制四；普通整数表示静态评估和浅层搜索结果。
热力图：绿色候选应该集中在成五、堵五、强制四、双威胁和活三点上；红色通常是相关性较低的附近空点。

如果 AI 明明该思考但表格没有新增记录，优先检查 Worker 和 Wasm 是否加载成功。如果表格新增了记录但 depth = 0，通常说明这次只是候选热力图请求，或搜索没有进入正常分片流程。

1. 棋盘状态¶

棋盘是 15x15，一共有 225 个交叉点。引擎用行优先的一维索引表示棋盘：

index = row * 15 + col

例如：

(0, 0) -> 0
(0, 1) -> 1
(1, 0) -> 15
(7, 7) -> 112

JavaScript 发送给 Rust 的是 225 项数组：

1   黑棋
-1  白棋
0   空点

这个格式容易检查，也容易跨 Wasm 边界传递。Rust 收到后会构造 Board 对象。

一次真实传递可以这样理解：

用户点击 (7, 9)
index = 7 * 15 + 9 = 114
如果当前是白棋，JavaScript 把 board[114] 设置为 -1
Worker 把 225 项数组发给 Rust
Rust 重新构造 cells、black_bits 和 white_bits

这里的输入是整盘棋，而不是“只发最后一步”。这样做更稳：Worker 即使重启，也能从完整棋盘恢复状态，不依赖之前缓存的历史。

2. 为什么还要用 Bitboard¶

数组适合读取某个坐标，比如 (7, 7)。但胜负判断用位操作更快。

棋盘有 225 个点，一个 u64 放不下。Rust 给黑白双方各用四个 u64：

black_bits: [u64; 4]
white_bits: [u64; 4]

每一位表示该方是否占有某个点。位索引仍然是 row * 15 + col。

这样引擎同时有两种视图：

cells：方便写坐标评估。
Bitboard：方便快速判断五连。

四个 u64 的分桶方式如下：

bucket = index / 64
offset = index % 64
mask   = 1_u64 << offset

例如 (7, 7) 的 index 是 112：

bucket = 112 / 64 = 1
offset = 112 % 64 = 48
mask   = 1_u64 << 48

如果白棋占了这个点，white_bits[1] 的第 48 位就会被置为 1。判断这个点是否有白棋时，只需要做：

white_bits[1] & (1_u64 << 48) != 0

这个结构的意义不是让代码看起来更复杂，而是把“检查很多格子”的工作变成 CPU 很擅长的按位运算。

3. 用 shift-and 判断五连¶

棋盘上的一条线，在一维索引里就是固定步长：

横向：      +1
纵向：      +15
左上到右下：+16
右上到左下：+14

假设黑棋有横向五连：

(7, 4), (7, 5), (7, 6), (7, 7), (7, 8)

它们的索引是：

109, 110, 111, 112, 113

横向步长是 1，引擎检查：

bits
& (bits >> 1)
& (bits >> 2)
& (bits >> 3)
& (bits >> 4)

如果五项按位与之后还有某一位是 1，说明这个位置就是五连起点。

引擎还会加方向 mask。没有 mask 时，横向位移可能把一行末尾和下一行开头误连起来。横向五连的起点列只能是 0..10。

一个容易出错的例子是：

(0, 13), (0, 14), (1, 0), (1, 1), (1, 2)

这些 index 在一维数组里是连续的 13..17，但棋盘上不是横向五连。方向 mask 会把这种跨行误判挡掉。

正常结果：has_five() 能识别横、竖、斜五连；如果只是索引跨行造成的假连接，应该返回 false。

4. 候选点生成¶

自由五子棋里所有空点都合法。但搜索所有空点太慢。实际有意义的点大多在已有棋子附近，所以引擎只生成已有棋子两格范围内的空点。

例如：

黑棋在 (7, 7)
白棋在 (7, 8)

引擎会考虑 (6, 7)、(8, 8)、(7, 6) 等附近点。当前战斗在中心时，它不会浪费时间搜很远的角落。

每个候选点只计算一次 order_score。之后排序只比较缓存数字。排序比较函数不会落子、不会生成子局面、不会调用搜索。

正常结果：空棋盘时，引擎应优先天元。局面展开后，候选点应该集中在已有棋子附近。

5. 落子排序¶

Alpha-Beta 剪枝依赖好的排序。强招越早搜索，越容易剪掉弱分支。

引擎的候选优先级大致是：

自己一步能赢。
对手一步能赢，必须堵。
制造自己的强制四或断点四。
防守对手强制四或断点四。
制造自己的活三。
防守对手活三。
普通棋形分和很小的中心偏好。

中心偏好权重很小。它只能帮助安静局面，不能覆盖真实威胁。

防守不是绝对压过一切。对手下一步能赢时必须堵，但如果 AI 自己的强制进攻强于对手普通压力，就应该主动进攻。这样可以避免整盘棋只补防、不抢先手。

排序的输出不是最终答案，只是“先搜谁”。最终答案仍由完整搜索决定。一个候选点的排序分高，表示它值得优先展开；如果展开后发现对手有更强反击，NegaMax 仍然会把它压下去。

判断排序是否正常，可以看三类局面：

AI 自己有五连落点：应该第一优先。
人类下一步能五连：AI 应该优先堵。
双方都没有直接杀棋：AI 应该更偏向扩展自己的活三、活四，而不是只补很远的弱点。

6. 五格窗口威胁¶

只数连续棋子不够。它能识别 XXXX_，但容易漏掉断点威胁：

XX_XX
XXX_X
X_XXX

引擎会枚举所有包含候选点的五格窗口。

对每个窗口，Rust 会判断：

窗口里有没有对手棋？
如果下在候选点，本方有几颗棋？
还剩几个空点？
窗口两端是否开放？

例如：

黑棋：X X _ X X
轮到白棋

如果白棋下在中间空点，黑棋这个五格窗口就不能直接成五。引擎会给这个防守点很高分。

再看两个对比：

X X X _ _

这是三连带两个空位。它有进攻价值，但还不是下一步必胜。

X X _ X X

这是断点四。中间空位如果不处理，黑棋下一手就能补成五连。防守这个点的优先级必须明显高于普通三连。

同一个候选点可能同时参与多个窗口。比如一个点既能堵住对手断点四，又能形成自己的活三，它的综合分会更高。这也是热力图会在某些点显示明显高分的原因。

正常结果：人类有断点四时，AI 应该把中间缺口和相关端点当成紧急防守候选。

7. 静态评估¶

搜索到深度上限时，Rust 会评估局面。分数先按 root 方视角计算，在 NegaMax 需要时再转换成当前行动方视角。

棋形强度大致是：

五连       极高
活四       高
冲四       高
活三       重要
二连       较低

这些数字不是胜率，而是用于比较分支的启发式信号。

可以把静态评估理解成“搜索到这里先估一下谁更有希望”。它的输入是一个完整棋盘，输出是一个整数：

正数：对 root 方更好
负数：对 root 方更差
接近 0：双方暂时接近

分数不是落子概率，也不是“领先多少颗棋”。五子棋里一颗关键点可能比十个普通连接更重要，所以评估函数更重视强制威胁。

正常结果：强制威胁应该压过普通棋形收益。一个很小的中心加分不应该胜过必须堵的点。自己的强制进攻应该胜过对非强制威胁的被动补防。

8. NegaMax 搜索¶

Minimax 的意思是：选择一步棋，同时假设对手也会选择强招。

NegaMax 用一个对称公式表达同样的事：

score(position, side) = -score(position_after_move, other_side)

如果白棋搜索一步，下一层就是黑棋视角。黑棋分数返回后，白棋取负号。

这要求叶子分数和超时分数都必须站在当前行动方视角。引擎使用 relative_score() 处理这个问题。

一个两层搜索的例子：

白棋有两个候选：
A：白棋形成活四，但黑棋下一手能堵住，最终估分 +300
B：白棋直接堵住黑棋断点四，最终估分 +800

白棋不会只看第一步像不像进攻。它会把黑棋最强回应也算进去，所以 B 会胜出。

NegaMax 的关键是每层都站在“当前行动方”看分数。递归回来时取负号，相当于把对手眼里的好坏转换回自己眼里的好坏。

正常结果：刚好超时也不应该因为符号错误把好棋和坏棋反过来。

9. Alpha-Beta 剪枝¶

Alpha-Beta 维护两个边界：

alpha：当前方已经能保证的最好分数
beta：对手已经能把我们压到的上界

如果某个分支不可能改善结果，搜索就停止展开这个分支。

例如：

A 走法已经让白棋得到 +500。
B 走法会让黑棋把白棋压到 +100 以下。

白棋不需要把 B 下面所有变化都搜完。A 已经更好。

一个更具体的剪枝过程：

白棋先搜 A，得到 +500，alpha 变成 +500。
再搜 B 时，黑棋找到一个回应，让白棋最多只有 +100。
因为 +100 已经不可能超过 +500，B 后面的变化不用继续搜。

这里没有猜测，也不是随机跳过。剪枝成立的前提是双方都选择对自己最有利的回应。

正常结果：排序越好，弱分支越早被剪掉，浪费节点越少。

10. 迭代加深和时间¶

AI 通常每步有 5 秒预算。Rust 会搜索：

深度 1
深度 2
深度 3
...

每完成一层，就保存当前最佳落子。如果下一层搜索到一半时间到了，引擎返回上一层完整结果。

每个节点都检查时间会很贵，因为 Wasm 需要调用 JavaScript 的时间函数。引擎按节点数采样超时，控制时间的同时减少时间检查开销。

正常结果：AI 应在接近时间限制时返回，并带有完成深度、节点数和耗时。

11. 置换表¶

不同落子顺序可能到达同一个局面。置换表会缓存当前搜索里已经搜过的局面。

key 使用：

黑棋 Bitboard
白棋 Bitboard
当前行动方

缓存内容是：

搜索深度
分数
分数类型：Exact / Upper / Lower

只有缓存深度不低于当前请求深度时，分数才可能被复用。Exact 可以直接返回；Lower 和 Upper 只有在能证明当前 Alpha-Beta 窗口会失败时才会截断。

正常结果：一次搜索内重复到达的局面，不应该每次都完整重搜。

12. Worker 并行¶

浏览器根据 navigator.hardwareConcurrency 创建 Worker 池，默认使用约 90% 的线程数。

JavaScript 先请求 Rust 生成根候选，然后把候选分给 Worker：

Worker 1：候选 1、4、7
Worker 2：候选 2、5、8
Worker 3：候选 3、6、9

每个 Worker 搜索自己的分片并返回最佳结果。JavaScript 从所有 Worker 结果中选最高分，并合并搜索统计。

正常结果：UI 保持响应，右侧评分表显示合并后的节点数和 NPS。

13. 读懂一次 AI 结果¶

搜索结果类似：

{
  "r": 7,
  "c": 9,
  "score": 450000000,
  "depth": 5,
  "nodes": 13758,
  "timeMs": 100,
  "nps": 137580,
  "heatmap": []
}

含义：

r, c：选中的点。
score：引擎的 Minimax 分数。很大的正数通常表示强制战术。
depth：完成的最深迭代层数。
nodes：搜索过的局面数。
timeMs：耗时。
nps：每秒节点数。
heatmap：用于显示的候选点评分。

正常结果：强制堵点可能有非常大的分数，这是评估器把它标记为紧急战术，不是错误。