残局实验室通俗讲解 · 约 9 分钟
MINIMAX · ALPHA–BETA

AI 下棋,
真的会思考吗?

我们用最简单的井字棋,看看电脑怎样提前推演未来、选择最好的一步。不需要公式,也能看懂。

XOXOXOOX
01 / 10
残局实验室01 · 游戏规则
规则只有一句话

轮流落子,
先连成三个就赢。

九个格子,两个人,轮流下一手。如果双方都不犯错,这盘棋一定是平局。

XOXOXOOX和
02 / 10
残局实验室02 · 它怎么思考

AI 不是凭感觉,
它在脑内“演电影”。

AI 的脑内预演
1
我先下这里尝试一个空格
2
对手会怎么回?假设对手也想赢
3
然后我还能怎么下?继续往后推演
4
比较所有结果,选最好的一步走完这场“脑内电影”
我下对手对手对手赢平输赢输平
03 / 10
残局实验室03 · Minimax

一句话理解 Minimax:
先假设对手也很聪明。

AI 的选择

只挑对自己最好的结果

在每一个“AI 的回合”,把所有可能的下一步比较一遍,选收益最大的。

我要最大值
AI 眼中的对手

对手也会挑最麻烦的回应

在每一个“人类的回合”,AI 假设对手会尽量让自己难受,所以先看最坏结果。

对手取最小值
重点不是赌对手会失误,而是先保证:即使对手不失误,我也能拿到当前最好的结果。
04 / 10
残局实验室04 · 一个例子

三步小推演:
结果会替 AI 做选择。

方案 A
对手回应 1
赢
对手回应 2
输
最差结果:输
方案 B
对手回应 1
平
对手回应 2
平
最差结果:平
方案 C
对手回应 1
输
对手回应 2
赢
最差结果:输
AI 的选择方案 A 可能赢,但对手会让它输;方案 B 无论对手怎么回都至少平局。所以 AI 选 B。
05 / 10
残局实验室05 · Alpha-Beta

有些未来,
根本不用继续想。

我对对对??×
像做选择题时排除错误选项
1先看一条路

如果已经找到一个足够好的结果,就记住它。

2再看另一条路

如果它无论怎么发展都不可能更好,就不必继续展开。

3最后答案不变

只是少算了没有用的分支,所以 Alpha-Beta 不是“猜”。

06 / 10
残局实验室06 · 实测结果

同一个答案,
少算了八成多。

节点减少比例85.74%

比较 4,520 个没有结束的井字棋局面

普通 Minimax2,125,535
Alpha-Beta303,179
答案完全一致,最优值没有任何分歧。少掉的 1,822,356 个节点,都是不会影响最终选择的计算。
07 / 10
残局实验室07 · 这说明什么

剪枝最擅长处理
选择最多的阶段。

01

开局收益最大

空格多、分支多,Alpha-Beta 可以更早排除大片不需要搜索的未来。

选择多 → 更容易剪枝
02

尾声差距变小

只剩一两个空格时,本来就没有多少分支,两种算法访问的节点数几乎一样。

选择少 → 剪枝空间小
03

正确性优先

全量比对 4,520 个局面,评分没有一处不同。更快不等于更不准。

结果一致 → 优化有效
08 / 10
残局实验室08 · 换成 4×4
棋盘只多一格,未来多很多

能算完,
不等于能算大。

4×4 有四子连线。搜索越深,可能性不是加法增长,而是一层一层相乘。到了某个程度,就不再适合全部算完。

解决办法:限制搜索深度 + 给局面打分,换取更快的响应速度。
2 层
257
47
3 层
3,617
287
4 层
47,297
3,159
浅色:Minimax 红色:Alpha-Beta
深度每增加一层,未来都会成倍展开。
09 / 10
残局实验室09 · 带走三句话
YOU ONLY NEED THREE IDEAS

先想清结果,
再少想一点。

Minimax 负责找到正确答案,Alpha-Beta 负责更快地得到正确答案;当未来实在太多时,我们再用近似方法做取舍。

01 · 会推演假设对手也聪明,再选择自己的最优一步。
02 · 会排除不可能改变决定的分支,不用继续计算。
03 · 知边界问题变大时,用深度和近似换取速度。
10 / 10