谜题 / 井字棋 · 一个被完全解出的游戏 / 这棋到底有多大:数一数 待审核 5 / 6
count · 状态空间

这棋到底有多大:数一数

「井字棋只有 9!=3628809! = 362880 种」是常见的误算——那是把九格填满的全排列,既忽略了连成线就立即结束,也把大量殊途同归的局面重复计了。下面这些数全部在浏览器里现场穷举得到(页面加载时即时计算),而不是抄来的常量。

1 · 局面与对局的数量

图 1-1 · 三档量级的对比条:全排列上界、完整对局数、可达局面数。

注 · 这三档各有所指。9!9! 是忽略提前获胜、强行填满的上界;完整对局 (games) 是不同走子顺序的对局总数,一局走到分胜负或填满即止;可达局面 (positions) 则把「不同顺序走到同一盘面」合并后的不同盘面数——所以它远小于对局数。

2 · 958 个终局的胜负分布

图 2-1 · 958 个终局按结果拆分:X 胜 626、O 胜 316、和 16。

警示 · X 胜的终局 (626) 明显多于 O 胜 (316),这是先手的结构性优势在终局计数上的体现。但它不等于「X 该赢」:统计的是有多少种盘面以 X 连线收场,不含双方是否最优。一旦双方都不犯错,结果仍是平局——计数优势与博弈论结果是两回事。

3 · 对称归约

棋盘有 8 种对称(4 个旋转 × 镜像,即二面体群 D4D_4)。把彼此互为旋转或镜像的局面看成同一个,可达局面就从 5478 压到 765 个本质局面

图 3-1 · 一个局面的 8 个对称像与它的规范代表(字典序最小,绿框)。可点格子在空、X、O 之间切换。

建议 · 对称归约是把状态空间变小的通用手段——同样的思路用在更大的棋类与搜索里(置换表把对称局面归并),能成倍减少要存、要搜的状态。井字棋因为小,归约后 765 个本质局面可以直接全部列举出来。