我们用最简单的井字棋,看看电脑怎样提前推演未来、选择最好的一步。不需要公式,也能看懂。
九个格子,两个人,轮流下一手。如果双方都不犯错,这盘棋一定是平局。
在每一个“AI 的回合”,把所有可能的下一步比较一遍,选收益最大的。
我要最大值在每一个“人类的回合”,AI 假设对手会尽量让自己难受,所以先看最坏结果。
对手取最小值如果已经找到一个足够好的结果,就记住它。
如果它无论怎么发展都不可能更好,就不必继续展开。
只是少算了没有用的分支,所以 Alpha-Beta 不是“猜”。
比较 4,520 个没有结束的井字棋局面
空格多、分支多,Alpha-Beta 可以更早排除大片不需要搜索的未来。
选择多 → 更容易剪枝只剩一两个空格时,本来就没有多少分支,两种算法访问的节点数几乎一样。
选择少 → 剪枝空间小全量比对 4,520 个局面,评分没有一处不同。更快不等于更不准。
结果一致 → 优化有效4×4 有四子连线。搜索越深,可能性不是加法增长,而是一层一层相乘。到了某个程度,就不再适合全部算完。
Minimax 负责找到正确答案,Alpha-Beta 负责更快地得到正确答案;当未来实在太多时,我们再用近似方法做取舍。