一、一个三分钟能学会、但很少有人能说清为什么的游戏
「抢三十」是流传极广的双人游戏：
两人轮流报数，每次可以报 1 个、2 个或 3 个数（连续递增），谁先报到 30 谁就赢。
例如甲报「1、2」，乙报「3」，甲报「4、5、6」……谁喊出 30 谁胜。
玩过几局的人大多会摸到一个规律：先手必胜，而且第一手要报「2」。但”为什么要报 2″、”如果规则改成每次报 1~5 个数呢”、”如果目标不是 30 而是任意 N 呢”——能讲清的人就不多了。
这个游戏其实是一整套博弈论算法的入口：
- 模不变量（必胜态 / 必败态）——用
N mod (m+1)一眼看出答案； - 记忆化搜索（minimax + memo）——不依赖任何洞察，让程序自己”发现”规律；
- 策略证明——为什么”占据倍数是必胜”，用归纳法严格说明；
- SG 函数视角——把单个游戏推广到组合博弈。
本文用 Java 把这四层全部实现一遍，并用程序验证”直觉规律”与”搜索结果”完全一致。
二、形式化：把游戏变成一个状态机
定义状态为”当前已经报到 i“，i ∈ [0, N]，其中 N = 30，i = 0 表示尚未开始。
从状态 i 出发，玩家可以移动到 i + 1、i + 2、……、i + m（m = 3），前提是不超过 N。
- 谁把状态推到
N，谁就赢。 - 等价地：状态
N是”上一个行动的玩家获胜”。
用博弈论的标准说法：
- 必胜态（N-position）：当前行动者存在一种走法能到达”必败态”；
- 必败态（P-position）：当前行动者无论怎么走都会到达”必胜态”。
边界：状态 N 之外无意义，我们把”已经到 N“视为上一个玩家已胜，因此对当前行动者来说，N 是”游戏已结束，我输了”——但这需要小心处理。更清晰的写法是：把 N 定为必败态给”面对 N 的人”，因为面对 N 意味着对手刚刚报到 30。
public final class TakeThirty {
private final int target; // N
private final int maxTake; // m，每次最多报 m 个数
private final int[] memo; // 0 = 未知，1 = 必胜，2 = 必败
public TakeThirty(int target, int maxTake) {
this.target = target;
this.maxTake = maxTake;
this.memo = new int[target + 1];
}
/**
* 判定状态 i 是否为必胜态。
* memo[i] = 1 必胜；= 2 必败。
*/
public boolean isWinning(int i) {
if (i >= target) {
return false; // 面对已到 target 的局面，说明对手刚刚获胜
}
if (memo[i] != 0) {
return memo[i] == 1;
}
boolean win = false;
for (int k = 1; k <= maxTake && i + k <= target; k++) {
if (!isWinning(i + k)) {
win = true; // 存在一步到达必败态 → 当前是必胜态
break;
}
}
memo[i] = win ? 1 : 2;
return win;
}
}
关键细节：递归是从 i 向 i + k 走的，也就是向更大的状态走。因此不存在环，memo 是纯粹的”子问题缓存”，不会出现循环依赖。这一点和”取石子”类游戏（状态递减）方向相反，但逻辑完全同构。
复杂度：状态数 O(N)，每状态 O(m) 转移，总 O(N·m)，即 30 × 3 = 90 次运算。
三、让程序自己”发现”模规律
跑一遍 isWinning(0..30)，你会得到一张很有规律的表格：
i: 0 1 2 3 4 5 6 7 8 9 10 ...
胜负: W W L W W W L W W W L ...
必败态恰好是 2, 6, 10, 14, 18, 22, 26, 30 —— 全部是 i ≡ 2 (mod 4)。
为什么会是 4？因为 m = 3，而 m + 1 = 4。
public final class ModInvariant {
/**
* 用模不变量直接判定胜负，O(1)。
* 结论：i 是必败态当且仅当 (target - i) % (maxTake + 1) == 0。
*/
public static boolean isWinningByFormula(int i, int target, int maxTake) {
return (target - i) % (maxTake + 1) != 0;
}
/** 验证公式与记忆化搜索完全一致（对所有 i）。 */
public static boolean verify(int target, int maxTake) {
TakeThirty game = new TakeThirty(target, maxTake);
for (int i = 0; i <= target; i++) {
boolean bySearch = game.isWinning(i);
boolean byFormula = isWinningByFormula(i, target, maxTake);
if (bySearch != byFormula) {
System.out.println("不一致于 i=" + i + " search=" + bySearch + " formula=" + byFormula);
return false;
}
}
return true;
}
}
验证 verify(30, 3) 返回 true。再把 maxTake 从 2 试到 6，全部通过——公式在任意 m 下都成立。
四、为什么是 (N - i) mod (m+1)？归纳法证明
这个公式不是巧合，可以用一个非常干净的归纳论证说明。核心思路是”配对策略“：把每一轮（对手走 + 我走）看成一次”回合组”，让每个回合组总共消耗恰好 m + 1 个数。
引理：若剩余待报数量 r = N - i 是 m + 1 的倍数，则当前行动者必败。
证明（对 r 归纳）：
- 基例
r = 0：已经报到N，当前行动者输，命题成立。 - 归纳步：设
r = k(m+1)，k ≥ 1。当前行动者报t个数（1 ≤ t ≤ m），剩余变为r - t。因为1 ≤ t ≤ m < m+1，所以r - t不是m+1的倍数，即r - t ≡ (m+1-t) mod (m+1)，落在[1, m]区间。
对手的策略是：报m + 1 - t个数。这个数合法（因为1 ≤ m+1-t ≤ m，当t = m时报 1 个，当t = 1时报m个），且让剩余重新回到(k-1)(m+1)的倍数。
由归纳假设，此时”剩余是倍数”的局面轮到当前行动者，他必败。因此无论t取何值，当前行动者都会输。□
推论：若 r 不是 m+1 的倍数，当前行动者可以报 r mod (m+1) 个数（因为余数 ∈ [1, m]，合法），把剩余变成 m+1 的倍数交给对手，从而必胜。
这就是”为什么抢三十要先报 2″的严格答案：30 mod 4 = 2，先手报 2 个数（喊「1、2」），剩余 28 是 4 的倍数，此后对手报 t 个、你报 4 - t 个，每一轮消耗 4，你必然抢到 30。
注意边界：若初始 N mod (m+1) == 0，则先手必败（后手必胜），因为先手无法把局面变成倍数。
五、从”能赢”到”怎么赢”：输出策略
判定胜负只是第一步，实际游戏里需要每一步该怎么走。策略很直接：
- 若当前是必胜态，选一个让对手进入必败态的走法（即走
target - i的余数步）； - 若当前是必败态，随便走（但可以选”能拖最久”的走法，增加对手犯错概率）。
public final class StrategyPlayer {
private final TakeThirty game;
private final int target;
private final int maxTake;
public StrategyPlayer(TakeThirty game, int target, int maxTake) {
this.game = game;
this.target = target;
this.maxTake = maxTake;
}
/**
* 返回本回合应该报几个数。
* 必胜态时返回最优步（把对手推入必败态）；
* 必败态时返回 1（拖延策略，把决策压力交给对手）。
*/
public int decide(int current) {
int remain = target - current;
if (remain <= 0) {
return 0;
}
int r = remain % (maxTake + 1);
if (r != 0) {
return Math.min(r, remain);
}
// 必败态：随便走。这里选 1，让局面尽量复杂，给对手更多犯错机会
return Math.min(1, remain);
}
/** 用记忆化搜索做同样的决策（用于交叉验证公式策略）。 */
public int decideBySearch(int current) {
int best = -1;
for (int k = 1; k <= maxTake && current + k <= target; k++) {
if (!game.isWinning(current + k)) {
return k; // 找到把对手送入必败态的一步
}
if (best == -1) best = k;
}
return best == -1 ? Math.min(1, target - current) : best;
}
}
decide 与 decideBySearch 在必胜态下返回的步数必然相同（因为唯一能到达倍数的余数是唯一的）——这是一个很好的自检点。
六、完整可运行的对战程序
import java.util.Scanner;
public final class TakeThirtyGame {
public static void main(String[] args) {
int target = 30;
int maxTake = 3;
Scanner in = new Scanner(System.in);
TakeThirty game = new TakeThirty(target, maxTake);
StrategyPlayer ai = new StrategyPlayer(game, target, maxTake);
System.out.println("抢 " + target + "，每次可报 1~" + maxTake + " 个数。");
System.out.println("先手是否必胜: " + game.isWinning(0));
int current = 0;
boolean humanTurn = true;
while (current < target) {
if (humanTurn) {
System.out.print("你报几个 (1~" + maxTake + ")? ");
int k = in.nextInt();
if (k < 1 || k > maxTake || current + k > target) {
System.out.println("非法输入，重来");
continue;
}
for (int i = 1; i <= k; i++) {
System.out.print((current + i) + " ");
}
System.out.println();
current += k;
} else {
int k = ai.decide(current);
for (int i = 1; i <= k; i++) {
System.out.print((current + i) + " ");
}
System.out.println(" <- AI 报 " + k + " 个");
current += k;
}
humanTurn = !humanTurn;
}
System.out.println(current >= target
? (humanTurn ? "AI 报到 " + target + "，AI 获胜！" : "你报到了 " + target + "，你获胜！")
: "");
}
}
AI 使用的是 O(1) 的模公式策略，因此即便目标改成 10^9（理论上的超大目标），决策依然是常数时间——这是模不变量的威力，也是”记忆化搜索”做不到的（O(N) 空间）。
七、推广一：变成”取石子”游戏
抢三十换个皮就是经典的巴什博弈（Bash Game）：
一堆
N颗石子，两人轮流取，每人每次可取1..m颗，取走最后一颗者胜。
完全同构：报数 ↔ 取石子，报 k 个数 ↔ 取 k 颗，报到 N ↔ 取完最后一颗。因此结论完全一样：
先手必败 ⇔ N % (m + 1) == 0
/** 巴什博弈通用判定。 */
public static boolean bashGameFirstPlayerWins(int n, int m) {
return n % (m + 1) != 0;
}
/** 变体：取走最后一颗者"输"（misère 版本）。 */
public static boolean bashGameMisereFirstPlayerWins(int n, int m) {
if (m == 1) {
// 每次只能取 1 颗：奇偶决定
return n % 2 == 0;
}
// 一般 misère 版本：先手必败 ⇔ (n - 1) % (m + 1) == 0
return (n - 1) % (m + 1) != 0;
}
misère（恶劣版）的陷阱：如果”取最后一颗者输”，公式会变成 (n-1) mod (m+1)。原因是最后阶段要留给对手 1 颗，所以倒数第二阶段等价于抢到 n-1。这是博弈论里一个经典坑：胜负条件反转时，不变量也要平移一位。
八、推广二：SG 函数与组合博弈
当游戏从”单一堆”变成”多堆独立游戏”时，模不变量就失效了，需要用 Sprague-Grundy 函数把每个子游戏映射成一个”nim 值”，整个游戏等价于 Nim 博弈。
import java.util.HashSet;
import java.util.Set;
public final class Grundy {
/**
* 计算单堆取石子的 Grundy 值。
* 规则：从 n 颗中取 1..m 颗，取完者胜。
*/
public static int grundy(int n, int m) {
int[] g = new int[n + 1];
for (int i = 1; i <= n; i++) {
Set<Integer> reachable = new HashSet<>();
for (int k = 1; k <= m && k <= i; k++) {
reachable.add(g[i - k]);
}
int mex = 0;
while (reachable.contains(mex)) mex++;
g[i] = mex;
}
return g[n];
}
/**
* 多堆组合：各堆 Grundy 值异或非零则先手必胜。
*/
public static boolean multiPileFirstWins(int[] piles, int m) {
int xor = 0;
for (int p : piles) {
xor ^= grundy(p, m);
}
return xor != 0;
}
}
一个有意思的观察：单堆取 1..m 的 Grundy 值恰好是 n mod (m+1)。所以”异或非零”就退化成了”某一堆不是倍数”——多堆版本下，单堆的模结论不再直接适用，但可以化归为 Nim。这正是 SG 定理的内容：
任何”正常玩法”的公平组合游戏，其局面的 SG 值等于所有子游戏 SG 值的异或；异或非零则先手必胜。
注意 grundy 的实现里 mex 是从 0 开始逐个试的，最坏 O(m)，总复杂度 O(n·m·m)（HashSet 常数）。对 n = 10^4 级别完全够用；若追求极致，可以用布尔数组 + 时间戳代替 HashSet（与前面 Hex 的 stamp 技巧同源）。
九、实测：三条结论的程序验证
把上面的代码串起来跑一遍，可以得到三组用程序”确认”的结论：
public final class Verification {
public static void main(String[] args) {
// 结论一：m=3, N=30 时公式与搜索一致，先手必胜
System.out.println("m=3,N=30 公式一致: " + ModInvariant.verify(30, 3));
System.out.println("先手必胜: " + new TakeThirty(30, 3).isWinning(0));
// 结论二：对所有 m=2..8、N=10..100，公式与搜索都一致
boolean allOk = true;
for (int m = 2; m <= 8; m++) {
for (int n = 10; n <= 100; n++) {
if (!ModInvariant.verify(n, m)) { allOk = false; }
}
}
System.out.println("全参数一致: " + allOk);
// 结论三：整个搜索表恰好是周期为 m+1 的周期序列
TakeThirty g = new TakeThirty(100, 4);
boolean periodic = true;
for (int i = 0; i + 5 <= 100; i++) {
if (g.isWinning(i) != g.isWinning(i + 5)) periodic = false;
}
System.out.println("胜负表以 m+1 为周期: " + periodic);
}
}
三行输出分别是 true / true / true / true——记忆化搜索、模公式、周期性质三者互为印证。这是这类问题最优雅的地方：暴力的程序搜索和数学推导给出了同一个答案，你就知道两者都没错。
十、复杂度对照
| 方法 | 时间 | 空间 | 是否给出最优步 |
|---|---|---|---|
| 记忆化搜索（minimax） | O(N·m) |
O(N) |
是 |
| 模 不变量公式 | O(1) |
O(1) |
是（余数即答案） |
| 逆推 DP（从 N 往前打表） | O(N·m) |
O(N) |
是 |
| SG 函数（单堆） | O(n·m·m) |
O(n) |
是 |
| SG 函数（多堆） | 各堆独立计算后异或 | 同上 | 是 |
对 N = 10^9 这种规模，只有模公式可用；对”多堆 + 复杂取法”的情况，只有 SG 函数可用。选哪种，取决于”规则是否能抽象出一个可计算的不变量”。
十一、小结
抢三十这个看似简单的童年游戏，完整地展示了博弈论算法的三层结构：
- 暴力层：记忆化搜索（minimax + memo），不需要任何洞察，程序自己发现规律，
O(N·m)； - 数学层：模 不变量
(N - i) mod (m+1)，把O(N·m)压缩到O(1)，并用”配对策略 + 归纳法”严格证明； - 推广层：巴什博弈（同构）、misère 版本（不变量平移）、SG 定理（组合博弈与 Nim 化归）。
最值得带走的一句：必胜态的本质是”能把局面转化为必败态交给对手”，而”倍数不变量”就是这条规则在取数游戏里的闭式解。找到不变量，O(N) 就能变成 O(1)；找不到，就老老实实让记忆化搜索去发现它。
