一、为什么用井字棋讲强化学习
井字棋（Tic-Tac-Toe）是强化学习教科书里最常见的入门沙盘，原因有三个：
- 状态空间可穷举。全部合法局面只有 5478 个（其中 4520 个非终局），一台笔记本就能把所有状态算完，结果可验证。
- 有明确的最优值。在「我方先手 X、对手随机走」的设定下，最优策略的胜率是一个确定的数——不是估计值，是可对比的基准。
- 不需要神经网络。井字棋足够小，用表格（tabular）方法就能精确求解，这让算法的骨架完全暴露，不被函数逼近的细节掩盖。
本文用策略迭代（Policy Iteration）求解：交替执行「策略评估」和「策略改进」，直到策略不再变化。这是动态规划（DP）类强化学习最经典的形式，比 Q-Learning 更直接——因为它假设环境模型（状态转移概率）已知，而井字棋的规则完全已知。
二、把井字棋写成 MDP
强化学习的第一步永远是把问题形式化成马尔可夫决策过程（MDP），即四元组 (S, A, P, R)：
- 状态 S：9 格棋盘的局面，用
('','','','X','O','','','','')这样的字符串元组表示。 - 动作 A：把一个空格填上自己的符号，即空格下标。
- 转移 P：我方落子后由对手行动。对手按均匀随机选择，所以转移是概率性的——这是「随机环境」的关键建模。
- 奖励 R：终局时 X 赢 = +1，O 赢 = −1，平局 = 0。
一个重要的建模选择：只对我方（X）的状态建表。因为对手是随机策略（不属于要学习的对象），我方决策只发生在「轮到 X 走」的局面。这样状态数从 4520 降到 2423，省掉一半内存，也让 V(s) 的语义更清晰——它是「轮到 X 走时，X 的期望回报」。
这个建模有一个隐含前提：对手的行为是固定的随机策略。因此学到的是「针对随机对手的最优应对」，而不是「博弈论意义上的不可被击败策略」。这两者不同：前者会主动追求高风险高回报的赢法（因为对手容易犯错），后者只保证不输。区分这两点，是理解本文结果的关键。
三、策略迭代的两个阶段
3.1 策略评估
给定策略 π，计算每个状态的期望回报 V^π(s)：
V(s) ← Σ_{s'} P(s'|s, π(s)) × [ R(s') + γ·V(s') ]
井字棋是有限步终止的（最多 9 手），所以折扣因子 γ = 1 即可，不需要担心无限循环。这一点很重要：井字棋的状态图是一个 DAG（有向无环图，局面只会增加符号，不会回退），因此策略评估的贝尔曼回溯天然收敛，且最多只需「树深 + 1」次扫描。
3.2 策略改进
对每个状态，选择让 Q 值最大的动作：
π'(s) ← argmax_a Σ_{s'} P(s'|s,a) × [ R(s') + γ·V(s') ]
若 π’ == π，则 π 已是最优策略（策略改进定理保证：任何贪心于 V^π 的策略都不劣于 π，且若严格优于则必有状态改变）。策略迭代一定会终止，因为策略空间有限且每轮严格单调改进。
四、完整 Java 实现
4.1 局面与规则
import java.util.*;
/** 井字棋局面：9 格，'X'/'O'/'\0' 表示空 */
public class TicTacToe {
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} // 两对角线
};
/** 返回胜者，无胜者返回 '\0' */
static char winner(char[] b) {
for (int[] ln : LINES)
if (b[ln[0]] != '\0' && b[ln[0]] == b[ln[1]] && b[ln[1]] == b[ln[2]])
return b[ln[0]];
return '\0';
}
static boolean isFull(char[] b) {
for (char c : b) if (c == '\0') return false;
return true;
}
/** 终局：有人赢 或 棋盘满 */
static boolean isTerminal(char[] b) {
return winner(b) != '\0' || isFull(b);
}
/** 轮到谁走：X 先手，X 的数量等于 O 的数量时轮到 X */
static char turn(char[] b) {
int x = 0, o = 0;
for (char c : b) { if (c == 'X') x++; else if (c == 'O') o++; }
return (x == o) ? 'X' : 'O';
}
static List<Integer> moves(char[] b) {
List<Integer> ms = new ArrayList<>(9);
for (int i = 0; i < 9; i++) if (b[i] == '\0') ms.add(i);
return ms;
}
/** 终局奖励：X 视角；非终局返回 null（用 Double 包装表示"未定"） */
static Double reward(char[] b) {
char w = winner(b);
if (w == 'X') return 1.0;
if (w == 'O') return -1.0;
if (isFull(b)) return 0.0;
return null;
}
static String key(char[] b) { return new String(b); }
static char[] parse(String s) {
char[] b = new char[9];
for (int i = 0; i < 9; i++) b[i] = s.charAt(i) == '.' ? '\0' : s.charAt(i);
return b;
}
}
用 String 做状态 key 是最简单可靠的做法——9 个字符的字符串，哈希开销可以忽略。也可以压成 int（每格 2 bit），但对 2423 个状态来说没必要。
4.2 MDP 建模：我方状态 + 对手随机转移
import java.util.*;
/**
* 井字棋 MDP 建模。
* 设计取向：只对「轮到 X 走」的非终局局面建表；
* 对手 O 采用均匀随机策略，因此转移概率在建模阶段就被边际化。
*/
public class TicTacToeMDP {
/** 我方状态集合（X 走、非终局） */
final Set<String> agentStates = new LinkedHashSet<>();
/** 状态 -> 可选动作 */
final Map<String, List<Integer>> actionsOf = new HashMap<>();
/** 状态 -> 动作 -> 转移列表（后继状态 key, 概率, 即时奖励或 null） */
final Map<String, Map<Integer, List<Trans>>> transOf = new HashMap<>();
/** 一条转移：落到 next 状态的概率 p；reward 为 null 表示 next 是非终局（其价值需查表） */
static class Trans {
final String next; final double p; final Double reward;
Trans(String next, double p, Double reward) { this.next = next; this.p = p; this.reward = reward; }
}
/** 从初始空盘出发，DFS 枚举所有我方状态 */
public TicTacToeMDP() {
char[] start = new char[9];
build(start);
}
void build(char[] b) {
if (TicTacToe.isTerminal(b)) return;
if (TicTacToe.turn(b) != 'X') return; // 只对我方回合建表
String k = TicTacToe.key(b);
if (agentStates.contains(k)) return;
agentStates.add(k);
List<Integer> acts = TicTacToe.moves(b);
actionsOf.put(k, acts);
Map<Integer, List<Trans>> m = new HashMap<>();
for (int a : acts) {
char[] nb = b.clone();
nb[a] = 'X';
List<Trans> ts = new ArrayList<>();
if (TicTacToe.isTerminal(nb)) {
ts.add(new Trans(TicTacToe.key(nb), 1.0, TicTacToe.reward(nb)));
} else {
// 对手 O 均匀随机：把后续转移按边际化处理
List<Integer> oppActs = TicTacToe.moves(nb);
double p = 1.0 / oppActs.size();
for (int oa : oppActs) {
char[] n2 = nb.clone();
n2[oa] = 'O';
ts.add(new Trans(TicTacToe.key(n2), p, TicTacToe.reward(n2)));
}
}
m.put(a, ts);
}
transOf.put(k, m);
// 递归扩展后继我方状态
for (List<Trans> ts : m.values())
for (Trans t : ts)
if (t.reward == null) build(TicTacToe.parse(t.next));
}
int size() { return agentStates.size(); }
}
关键设计是 Trans.reward 用 null 表示「非终局」。这让「查表」和「立即奖励」在同一个循环里被自然区分，避免了用 -999 之类的魔法值。
4.3 策略迭代
import java.util.*;
/** 策略迭代：策略评估（贝尔曼回溯）+ 策略改进（贪心）交替执行 */
public class PolicyIteration {
final TicTacToeMDP mdp;
final Map<String, Integer> policy = new HashMap<>();
final Map<String, Double> value = new HashMap<>();
int evalSweepsTotal = 0, rounds = 0;
public PolicyIteration(TicTacToeMDP mdp) {
this.mdp = mdp;
// 初始策略：每个状态都选第一个合法动作
for (String s : mdp.agentStates)
policy.put(s, mdp.actionsOf.get(s).get(0));
}
/** 策略评估：原地更新（Gauss-Seidel 风格），DAG 上保证有限步收敛 */
int evaluatePolicy() {
for (String s : mdp.agentStates) value.putIfAbsent(s, 0.0);
int sweeps = 0;
while (true) {
sweeps++;
double delta = 0;
for (String s : mdp.agentStates) {
int a = policy.get(s);
double q = 0;
for (TicTacToeMDP.Trans t : mdp.transOf.get(s).get(a))
q += t.p * (t.reward != null ? t.reward : value.get(t.next));
delta = Math.max(delta, Math.abs(q - value.get(s)));
value.put(s, q); // 原地更新，加速收敛
}
if (delta < 1e-12) break;
if (sweeps > 200) break; // 安全阀
}
evalSweepsTotal += sweeps;
return sweeps;
}
/** 策略改进：对每个状态取 Q 值最大的动作 */
int improvePolicy() {
int changed = 0;
for (String s : mdp.agentStates) {
int bestA = policy.get(s);
double bestQ = Double.NEGATIVE_INFINITY;
for (Map.Entry<Integer, List<TicTacToeMDP.Trans>> e : mdp.transOf.get(s).entrySet()) {
double q = 0;
for (TicTacToeMDP.Trans t : e.getValue())
q += t.p * (t.reward != null ? t.reward : value.get(t.next));
if (q > bestQ + 1e-12) { bestQ = q; bestA = e.getKey(); }
}
if (bestA != policy.get(s)) { policy.put(s, bestA); changed++; }
}
return changed;
}
/** 空盘状态的 key：9 个 '\0' 字符 */
static String emptyKey() { return new String(new char[9]); }
/** 主循环：评估 -> 改进 -> 判断收敛 */
void run(boolean verbose) {
while (true) {
rounds++;
int sweeps = evaluatePolicy();
int changed = improvePolicy();
if (verbose)
System.out.printf("第 %d 轮：评估扫描 %d 次，V(空盘) = %.6f，策略变更 %d 个状态%n",
rounds, sweeps, value.get(emptyKey()), changed);
if (changed == 0) break;
}
}
/** 与我方对弈一局（对手随机） */
char[] playOneGame(String start, Random rnd) {
char[] b = TicTacToe.parse(start);
while (!TicTacToe.isTerminal(b)) {
if (TicTacToe.turn(b) == 'X') {
String k = TicTacToe.key(b);
Integer a = policy.get(k);
if (a == null) a = TicTacToe.moves(b).get(0);
b[a] = 'X';
} else {
List<Integer> ms = TicTacToe.moves(b);
b[ms.get(rnd.nextInt(ms.size()))] = 'O';
}
}
return b;
}
}
注意 emptyKey() 返回的是 9 个 '\0' 字符组成的字符串——空盘的 key 必须与建模阶段由 TicTacToe.key(char[]) 生成的完全一致，否则查不到值。这是这类「字符串当 key」实现里最常见的低级错误。
4.4 跑起来
public class TicTacToeDemo {
public static void main(String[] args) {
TicTacToeMDP mdp = new TicTacToeMDP();
System.out.println("我方状态数 = " + mdp.size());
PolicyIteration pi = new PolicyIteration(mdp);
pi.run(true);
char[] empty = new char[9];
System.out.printf("最优值 V*(空盘) = %.6f%n", pi.value.get(TicTacToe.key(empty)));
// 实战验证：先手 X 用学到的策略，对手随机走，统计 10 万局
Random rnd = new Random(42);
int win = 0, lose = 0, draw = 0;
for (int i = 0; i < 100000; i++) {
char[] r = pi.playOneGame(TicTacToe.key(empty), rnd);
char w = TicTacToe.winner(r);
if (w == 'X') win++;
else if (w == 'O') lose++;
else draw++;
}
System.out.printf("10 万局实战：胜 %d (%.3f%%)，平 %d (%.3f%%)，负 %d (%.3f%%)%n",
win, win / 1000.0, draw, draw / 1000.0, lose, lose / 1000.0);
}
}
五、实测结果
5.1 收敛过程
我方状态数 = 2423
第 1 轮：评估扫描 3 次，V(空盘) = 0.604167，策略变更 1241 个状态
第 2 轮：评估扫描 4 次，V(空盘) = 0.945312，策略变更 345 个状态
第 3 轮：评估扫描 4 次，V(空盘) = 0.994792，策略变更 7 个状态
第 4 轮：评估扫描 4 次，V(空盘) = 0.994792，策略变更 0 个状态
最优值 V*(空盘) = 0.994792
三件事值得注意：
第一，只用 4 轮就收敛。 这与理论一致：策略迭代的轮数上界是「策略数」，但实际远小于此。井字棋的策略改进非常快，因为每轮能同时修正上千个状态。
第二，策略评估每轮只需 3~4 次扫描。 原因在于井字棋的状态图是 DAG，最长路径 9 步。原地更新（Gauss-Seidel）让值沿路径迅速传播——一次前向扫描就能从终局回溯 3~4 层。这是「γ=1 + DAG」结构的直接红利：没有无限循环，就不需要几百次迭代。
第三，用值迭代交叉验证。 我另外跑了值迭代（不做策略，直接对所有动作取 max），4 次扫描后收敛到 V*(空盘) = 0.9947916666。两个算法得到同一个值到小数点后 6 位，说明实现正确。
5.2 这个 0.9948 意味着什么
V*(空盘) = 0.994792 是「X 先手、对手均匀随机」下的期望回报。它的含义是：
- 完全赢（每局 +1）的期望值是 1.0；
- 完全输（每局 −1）是 −1.0；
- 0.9948 表示平均每局接近全胜——只有约 0.26% 的对局会输。
换算一下：(1 − 0.9948) / 2 ≈ 0.0026。也就是说对手随机走的时候，X 的最优策略几乎不可能输，偶尔平局，绝大多数赢。
但这里必须强调：这不是「井字棋不可战胜」的证明。如果对手也最优，双方必然平局，期望回报应该是 0。本文的 0.9948 完全来自「对手随机」这个假设。把对手换成 Minimax 对手，同一个策略迭代框架会算出 V=0，最优策略也会退化成「先占中心、再占角」的保守打法。
5.3 复杂度
- 空间：2423 个我方状态 × (1 个策略 + 1 个价值 + 平均 7 个动作的转移表)。约 1.7 万个转移条目，内存占用在 MB 级以下。
- 时间：策略迭代 4 轮 × 每轮 4 次扫描 × 2423 个状态 × 平均 7 个动作 × 平均 7 条转移 ≈ 1.9×10⁶ 次浮点运算。Java 下毫秒级完成。
- 对比穷举：BFS 求「最短必胜路径」也能解井字棋，但它只能回答「能否必胜」，回答不了「对手会犯错时期望收益多高」。这是 RL 与纯搜索的本质分工。
六、策略迭代 vs 值迭代 vs Q-Learning
| 维度 | 策略迭代 | 值迭代 | Q-Learning |
|---|---|---|---|
| 是否需环境模型 | 需要 P | 需要 P | 不需要（采样） |
| 每轮计算量 | 大（完整策略评估） | 小（一次扫描） | 极小（单样本更新） |
| 收敛轮数 | 少（本例 4 轮） | 多 | 依赖探索量 |
| 中间策略可用性 | 每轮都是合法策略 | 只有值，不直接给策略 | 逐步改善 |
| 适合场景 | 状态少、模型已知 | 状态少、模型已知 | 状态多、模型未知 |
对井字棋这种状态数只有 2423 的问题，策略迭代几乎总是最优选择：轮数少、结果精确、每轮策略都可用。只有在状态数上万、每次策略评估都昂贵时，值迭代的「一次扫描」优势才显现。
七、几个容易踩的坑
- 不要把对手的状态也放进表里。如果对 X 和 O 的所有状态统一建表，奖励的符号会混乱（同一个终局对 X 是 +1、对 O 是 −1）。按「决策者视角」切分状态集，是表格型 RL 的第一条纪律。
- 终止状态的 V 必须是 0。本文把终局的价值直接折进
reward，非终局才查表。如果误把终局也放进表并赋非零初值，评估会算出错误结果。 - 原地更新比批量更新收敛快 2~3 倍。上面
evaluatePolicy里直接value.put(s, q)就是原地更新——只要扫描顺序是从终局往初始局面推，值传播一轮能走多层。批量更新则需要更多扫描次数。 - 收敛判据要同时看值和策略。只看值的 delta 可能过早停止；本文以「策略变更数为 0」作为主判据，这是策略迭代的正确终止条件（策略改进定理）。
八、小结
井字棋的价值不在游戏本身，而在于它是一个能被完整算清的最小 MDP。你可以在这里看到策略迭代的每一个环节：状态枚举、概率边际化、贝尔曼回溯、贪心改进、收敛判定，全部以最朴素的表格形式呈现。
把 2423 个状态、4 轮迭代、V*=0.9948 这三个数字记住，你就有了一个可复用的「正确性基准」——以后写任何强化学习代码，都可以先在井字棋上跑一遍，如果收敛不到 0.9948，说明实现有 bug。
