为什么井字棋值得再写一次
井字棋只有 3×3 九格，规则三十秒能讲完，几乎所有搜索算法的教程都拿它当第一个例子。正因为如此，它成了一块极好的“标尺”：状态空间小到可以穷尽，又能暴露搜索算法里最本质的两个问题——状态重复和状态冗余。
前者靠置换表（transposition table）解决，后者靠对称性约化解决。本文的重点是后者：用群论里的 Burnside 引理，把 5,478 个可达局面压缩成 765 个本质不同的局面，再用记忆化 Minimax 求解，节点数从 549,946 降到 2,271。
一、先把状态空间数清楚
九格、每格三态（空 / X / O），朴素计数是 3^9 = 19,683 种填法。但绝大多数是不合法的：X 与 O 的落子数最多差 1，且已经成三的一方必须“刚刚”落子才成立。
把规则写成三个判定条件：
- X 的数量等于 O 的数量，或比 O 多 1（X 先手）；
- 若 X 已成三，则 X 数量必须比 O 多 1，且存在某一枚 X 棋子，拿掉它之后 X 不再成三（说明这步棋就是制胜手，之后游戏已结束）；
- 若 O 已成三，同理要求 O 数量等于 X 数量。
对 19,683 种填法逐一筛选，可达局面数为 5,478。
static boolean legal(int[] b) {
int cx = 0, co = 0;
for (int v : b) { if (v == X) cx++; else if (v == O) co++; }
if (cx - co != 0 && cx - co != 1) return false;
int wx = winLines(b, X), wo = winLines(b, O);
if (wx > 0 && wo > 0) return false; // 双方同时成三，不可能
if (wx > 0) return cx == co + 1 && canBeLastMove(b, X);
if (wo > 0) return cx == co && canBeLastMove(b, O);
return true;
}
/** 是否存在某一枚本方棋子，撤掉它之后本方不再成三 */
static boolean canBeLastMove(int[] b, int player) {
for (int i = 0; i < 9; i++) {
if (b[i] != player) continue;
b[i] = EMPTY;
boolean stillWin = winLines(b, player) > 0;
b[i] = player;
if (!stillWin) return true;
}
return false;
}
5,478 已经不大，但 Minimax 的搜索树会反复访问同一局面：首手在角上和在边上，后续的子树在旋转/镜像意义下完全同构。
二、把棋盘放进二面体群 D4
正方形棋盘的对称操作共 8 个：恒等、旋转 90°、180°、270°，以及水平镜像、垂直镜像、主对角镜像、副对角镜像。它们在复合下封闭，构成二面体群 D4，阶为 8。
对 (r, c) 坐标（r 为行，c 为列，取值 0..2），八个变换是：
| 编号 | 变换 | (r, c) → |
|---|---|---|
| T0 | 恒等 | (r, c) |
| T1 | 顺转 90° | (c, 2−r) |
| T2 | 转 180° | (2−r, 2−c) |
| T3 | 转 270° | (2−c, r) |
| T4 | 左右镜像 | (r, 2−c) |
| T5 | 上下镜像 | (2−r, c) |
| T6 | 主对角镜像 | (c, r) |
| T7 | 副对角镜像 | (2−c, 2−r) |
把 (r, c) 映射到线性下标 r*3+c，每个变换就变成一个长度 9 的置换 perm[t]，满足 newBoard[perm[t][i]] = oldBoard[i]。
三、Burnside 引理：数一数究竟有多少“本质不同”的局面
对有限群 G 作用在集合 X 上，轨道（orbit）数等于各群元素不动点数的平均值：
$$|X/G| = \frac{1}{|G|}\sum_{g \in G} |X^g|$$
D4 阶为 8，于是只需数出每种变换下“自己映射到自己”的局面有多少个。对 5,478 个可达局面实测：
| 变换 | 不动点数量 |
|---|---|
| 恒等 | 5,478 |
| 顺转 90° | 6 |
| 转 180° | 42 |
| 转 270° | 6 |
| 左右镜像 | 136 |
| 上下镜像 | 136 |
| 主对角镜像 | 158 |
| 副对角镜像 | 158 |
| 合计 | 6,120 |
6120 / 8 = 765。也就是说，5,478 个可达局面在对称意义下只有 765 个本质不同的形态，约化率 86%。
作为交叉验证，对全部 3^9 = 19,683 种填法做同样的统计，得到 19683 + 27 + 243 + 27 + 729 + 729 + 729 + 729 = 23,856，除以 8 得 2,862，与“所有 3^9 填法在 D4 下的轨道数”完全一致。这说明统计口径没有写错。
注意 Burnside 数出来的是轨道数，不是“代表元个数”。工程上我们不需要真的枚举轨道，只需要一个能选出轨道内唯一代表元的函数，也就是规范形（canonical form）。
四、规范形：把轨道压成一个 long
把棋盘按三进制编码成整数，九个格子分别对应 3^0 到 3^8 的权重。对同一局面的 8 个变换各算一次编码，取最小值作为规范形。同一轨道内所有局面必然得到同一个最小值，不同轨道不可能撞车（编码是单射）。
static final long[] POW3 = new long[9];
static {
POW3[0] = 1;
for (int i = 1; i < 9; i++) POW3[i] = POW3[i - 1] * 3;
}
/** 返回该局面在 D4 下 8 个编码中的最小值 */
static long canonical(int[] b) {
long best = Long.MAX_VALUE;
for (int t = 0; t < 8; t++) {
int[] p = PERM[t];
long code = 0;
for (int i = 0; i < 9; i++) code += b[p[i]] * POW3[i];
if (code < best) best = code;
}
return best;
}
单次调用是 8×9 = 72 次乘加，看起来比一次哈希贵，但它换来的是置换表命中率的大幅提高：原本因为“旋转了一下”而无法命中的局面，现在全部落到同一个表项。
五、记忆化 Minimax：轮到谁走也要进键
井字棋是零和完美信息游戏，用 negamax 形式最省事：
- 若已分出胜负，己方赢返回 +1，输返回 −1；
- 若棋盘填满，返回 0；
- 否则枚举所有空格落子，取
-negamax(对手)的最大值。
置换表的键必须是 (局面, 轮到谁)，因为同一个棋盘在 X 走和 O 走时价值完全不同。实现上把规范形乘 2 再加上 0/1 即可：
static int negamax(int[] b, int player, Map<Long, Integer> memo, int[] nodes) {
nodes[0]++;
int w = winner(b);
if (w != EMPTY) return (w == player) ? 1 : -1;
if (isFull(b)) return 0;
long key = canonical(b) * 2 + (player == X ? 0 : 1);
Integer cached = memo.get(key);
if (cached != null) return cached;
int best = -2;
for (int i = 0; i < 9; i++) {
if (b[i] != EMPTY) continue;
b[i] = player;
int score = -negamax(b, 3 - player, memo, nodes);
b[i] = EMPTY;
if (score > best) best = score;
}
memo.put(key, best);
return best;
}
六、完整可运行项目
项目采用 Maven 标准布局，只有一个类，main 依次做三件事：统计状态空间、验证 Burnside、对比带/不带置换表的搜索成本。
tic-tac-toe/
├── pom.xml
└── src/main/java/com/daily/algorithm/TicTacToeSymmetry.java
<project xmlns="http://maven.apache.org/POM/4.0.0">
<modelVersion>4.0.0</modelVersion>
<groupId>com.daily</groupId>
<artifactId>tic-tac-toe</artifactId>
<version>1.0</version>
<properties>
<maven.compiler.source>17</maven.compiler.source>
<maven.compiler.target>17</maven.compiler.target>
</properties>
</project>
package com.daily.algorithm;
import java.util.*;
public class TicTacToeSymmetry {
static final int EMPTY = 0, X = 1, O = 2;
static final int[][] LINES = {
{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}
};
/** PERM[t][newIndex] = oldIndex，共 8 个 D4 变换 */
static final int[][] PERM = new int[8][9];
static final long[] POW3 = new long[9];
static {
for (int t = 0; t < 8; t++) {
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
int nr, nc;
switch (t) {
case 0 -> { nr = r; nc = c; } // 恒等
case 1 -> { nr = c; nc = 2 - r; } // 顺转 90°
case 2 -> { nr = 2 - r; nc = 2 - c; } // 转 180°
case 3 -> { nr = 2 - c; nc = r; } // 转 270°
case 4 -> { nr = r; nc = 2 - c; } // 左右镜像
case 5 -> { nr = 2 - r; nc = c; } // 上下镜像
case 6 -> { nr = c; nc = r; } // 主对角镜像
default ->{ nr = 2 - c; nc = 2 - r; } // 副对角镜像
}
PERM[t][nr * 3 + nc] = r * 3 + c;
}
}
}
POW3[0] = 1;
for (int i = 1; i < 9; i++) POW3[i] = POW3[i - 1] * 3;
}
/* ---------------- 基础判定 ---------------- */
static int winner(int[] b) {
for (int[] l : LINES)
if (b[l[0]] != EMPTY && b[l[0]] == b[l[1]] && b[l[1]] == b[l[2]]) return b[l[0]];
return EMPTY;
}
static int winLines(int[] b, int player) {
int cnt = 0;
for (int[] l : LINES)
if (b[l[0]] == player && b[l[1]] == player && b[l[2]] == player) cnt++;
return cnt;
}
static boolean isFull(int[] b) {
for (int v : b) if (v == EMPTY) return false;
return true;
}
static boolean legal(int[] b) {
int cx = 0, co = 0;
for (int v : b) { if (v == X) cx++; else if (v == O) co++; }
if (cx - co != 0 && cx - co != 1) return false;
int wx = winLines(b, X), wo = winLines(b, O);
if (wx > 0 && wo > 0) return false;
if (wx > 0) return cx == co + 1 && canBeLastMove(b, X);
if (wo > 0) return cx == co && canBeLastMove(b, O);
return true;
}
static boolean canBeLastMove(int[] b, int player) {
for (int i = 0; i < 9; i++) {
if (b[i] != player) continue;
b[i] = EMPTY;
boolean stillWin = winLines(b, player) > 0;
b[i] = player;
if (!stillWin) return true;
}
return false;
}
/* ---------------- 对称性 ---------------- */
static long canonical(int[] b) {
long best = Long.MAX_VALUE;
for (int t = 0; t < 8; t++) {
int[] p = PERM[t];
long code = 0;
for (int i = 0; i < 9; i++) code += b[p[i]] * POW3[i];
if (code < best) best = code;
}
return best;
}
/** 第 t 个变换下的不动点数量 */
static int fixedPoints(int[] boards, int t) {
int cnt = 0;
for (int idx : boards) {
int[] b = decode(idx);
int[] nb = new int[9];
for (int i = 0; i < 9; i++) nb[i] = b[PERM[t][i]];
if (Arrays.equals(b, nb)) cnt++;
}
return cnt;
}
static int[] decode(int code) {
int[] b = new int[9];
for (int i = 8; i >= 0; i--) { b[i] = code % 3; code /= 3; }
return b;
}
/* ---------------- 搜索 ---------------- */
static int negamax(int[] b, int player, Map<Long, Integer> memo, int[] nodes) {
nodes[0]++;
int w = winner(b);
if (w != EMPTY) return (w == player) ? 1 : -1;
if (isFull(b)) return 0;
long key = canonical(b) * 2 + (player == X ? 0 : 1);
Integer cached = memo.get(key);
if (cached != null) return cached;
int best = -2;
for (int i = 0; i < 9; i++) {
if (b[i] != EMPTY) continue;
b[i] = player;
int score = -negamax(b, 3 - player, memo, nodes);
b[i] = EMPTY;
if (score > best) best = score;
}
memo.put(key, best);
return best;
}
/** 不带对称性约化、不带置换表的朴素 negamax，用作基线 */
static int negamaxPlain(int[] b, int player, int[] nodes) {
nodes[0]++;
int w = winner(b);
if (w != EMPTY) return (w == player) ? 1 : -1;
if (isFull(b)) return 0;
int best = -2;
for (int i = 0; i < 9; i++) {
if (b[i] != EMPTY) continue;
b[i] = player;
best = Math.max(best, -negamaxPlain(b, 3 - player, nodes));
b[i] = EMPTY;
}
return best;
}
/* ---------------- 主流程 ---------------- */
public static void main(String[] args) {
// 1. 统计状态空间
List<Integer> reachable = new ArrayList<>();
for (int code = 0; code < 19683; code++) {
int[] b = decode(code);
if (legal(b)) reachable.add(code);
}
System.out.println("3^9 全部填法 : 19683");
System.out.println("合法可达局面 : " + reachable.size());
// 2. Burnside 验算
int[] boards = reachable.stream().mapToInt(Integer::intValue).toArray();
int total = 0;
String[] names = {"恒等","顺转90","转180","转270","左右镜像","上下镜像","主对角","副对角"};
for (int t = 0; t < 8; t++) {
int f = fixedPoints(boards, t);
total += f;
System.out.printf(" %-8s 不动点 = %5d%n", names[t], f);
}
System.out.println("Burnside 平均值 : " + (total / 8.0) + " (轨道数)");
// 3. 搜索对比
int[] empty = new int[9];
int[] nodes1 = {0};
int v1 = negamaxPlain(empty.clone(), X, nodes1);
int[] nodes2 = {0};
Map<Long, Integer> memo = new HashMap<>();
int v2 = negamax(empty.clone(), X, memo, nodes2);
System.out.println("朴素 negamax 节点数 : " + nodes1[0] + "，估值 = " + v1);
System.out.println("规范形+置换表 节点数 : " + nodes2[0] + "，估值 = " + v2
+ "，表项数 = " + memo.size());
}
}
运行输出（JDK 17，单线程）：
3^9 全部填法 : 19683
合法可达局面 : 5478
恒等 不动点 = 5478
顺转90 不动点 = 6
转180 不动点 = 42
转270 不动点 = 6
左右镜像 不动点 = 136
上下镜像 不动点 = 136
主对角 不动点 = 158
副对角 不动点 = 158
Burnside 平均值 : 765.0 (轨道数)
朴素 negamax 节点数 : 549946，估值 = 0
规范形+置换表 节点数 : 2271，估值 = 0，表项数 = 627
估值 0 是正确结论：井字棋在双方最优下必和。
七、复杂度分析
设棋盘格数为 n、终局深度为 d。
- 朴素 negamax：最坏 O(b^d)，b 为平均分支因子。井字棋 b≈5、d=9，实测约 5.5×10^5 次节点访问。
- 规范形 + 置换表：访问次数降为 O(|S|·b)，|S| 为本质不同局面数。实测 2,271 次调用、627 个表项。注意表项数 627 小于轨道数 765，因为搜索只触及部分局面。
- 单次规范形代价：72 次乘加 ≈ 常数。命中一次置换表可省下整棵子树，收益远大于开销。真正的临界点是“子树规模是否大于 72”，井字棋显然满足。
空间上，置换表最多 O(765×2) 项，HashMap 开销可忽略。
八、几个容易踩坑的细节
第一，键必须带行动方。 只按棋盘做键会得到一个“X 视角”和“O 视角”混在一起的错误值，表现为 AI 走出明显的自损棋。
第二，规范形只对“当前局面”有效，不对“历史”有效。 井字棋是马尔可夫状态，只看棋盘即可。如果给游戏加上禁手或重复局面判负，必须把历史也纳入键。
第三，Burnside 不是必需的性能优化，而是必要的分析工具。 代码里真正用于提速的只有 canonical；Burnside 的用途是告诉你约化的理论上限是 765，从而判断“再优化也没有多少空间”。
第四，用 >= 还是 > 取最大值会影响走法选择。 平局局面下，> 会锁定首个搜索到的着法。若想让 AI 优先选择“更快获胜/更慢落败”的着法，需要引入带步数的估值（如胜 +100−depth），这是 negamax 的常见改写。
小结
井字棋的价值不在于它难，而在于它把“对称性”这一常常被忽略的剪枝维度暴露得非常清楚：在同一轨道内的局面，其博弈价值必然相同。用 D4 群 + 规范形，搜索规模从 549,946 个节点降到 2,271，几乎是一个数量级的三分之一。把这个技巧迁移到五子棋、黑白棋甚至俄罗斯方块，只需替换群的定义和规范形函数，框架完全复用。
