这棋到底有多大:数一数
「井字棋只有 种」是常见的误算——那是把九格填满的全排列,既忽略了连成线就立即结束,也把大量殊途同归的局面重复计了。下面这些数全部在浏览器里现场穷举得到(页面加载时即时计算),而不是抄来的常量。
1 · 局面与对局的数量
注 · 这三档各有所指。 是忽略提前获胜、强行填满的上界;完整对局 (games) 是不同走子顺序的对局总数,一局走到分胜负或填满即止;可达局面 (positions) 则把「不同顺序走到同一盘面」合并后的不同盘面数——所以它远小于对局数。
2 · 958 个终局的胜负分布
警示 · X 胜的终局 (626) 明显多于 O 胜 (316),这是先手的结构性优势在终局计数上的体现。但它不等于「X 该赢」:统计的是有多少种盘面以 X 连线收场,不含双方是否最优。一旦双方都不犯错,结果仍是平局——计数优势与博弈论结果是两回事。
3 · 对称归约
棋盘有 8 种对称(4 个旋转 × 镜像,即二面体群 )。把彼此互为旋转或镜像的局面看成同一个,可达局面就从 5478 压到 765 个本质局面。
建议 · 对称归约是把状态空间变小的通用手段——同样的思路用在更大的棋类与搜索里(置换表把对称局面归并),能成倍减少要存、要搜的状态。井字棋因为小,归约后 765 个本质局面可以直接全部列举出来。