引言
博弈论是研究理性决策者之间冲突与合作的数学理论。在算法竞赛和人工智能领域，组合博弈论（Combinatorial Game Theory）占据了重要地位。Sprague-Grundy定理是组合博弈论中最璀璨的明珠之一，它将任意无偏博弈（Impartial Game）的状态映射为一个非负整数——SG值（Sprague-Grundy Value），从而将复杂的多堆博弈问题转化为简单的Nim游戏。本文将使用Java实现SG函数的计算框架，并通过多个经典游戏实例展示其强大威力。
核心概念
无偏博弈
满足以下条件的博弈称为无偏博弈：
– 两名玩家轮流操作
– 可选操作仅取决于当前状态，与玩家身份无关
– 无法操作者判负（正常游戏规则）
SG函数定义
对于博弈状态x，其SG值定义为：
SG(x) = mex{ SG(y) | y是x的所有后继状态 }
其中mex（Minimum Excluded Value）是集合中未出现的最小非负整数。
关键定理：无偏博弈的初始状态为必败态，当且仅当SG(初始状态) = 0。
Sprague-Grundy定理
对于由多个独立子游戏组成的复合游戏，总SG值等于各子游戏SG值的异或和：
SG(总状态) = SG(子游戏1) ⊕ SG(子游戏2) ⊕ ... ⊕ SG(子游戏n)
这意味着任何无偏博弈组合都等价于一个Nim堆！
Java实现
import java.util.*;
/**
* SG函数计算框架
*/
public class SGSolver {
/**
* 计算mex（Minimum Excluded Value）
*/
public static int mex(Set<Integer> values) {
int m = 0;
while (values.contains(m)) m++;
return m;
}
/**
* 通用SG函数计算（记忆化搜索）
* @param state 当前状态
* @param getNextStates 获取后继状态的函数
* @param memo 记忆化缓存
*/
public static <T> int computeSG(T state,
java.util.function.Function<T, List<T>> getNextStates,
Map<T, Integer> memo) {
if (memo.containsKey(state)) return memo.get(state);
List<T> nextStates = getNextStates.apply(state);
if (nextStates.isEmpty()) {
memo.put(state, 0);
return 0;
}
Set<Integer> sgValues = new HashSet<>();
for (T next : nextStates) {
sgValues.add(computeSG(next, getNextStates, memo));
}
int sg = mex(sgValues);
memo.put(state, sg);
return sg;
}
/**
* 一维取石子游戏的SG函数（从一堆中取1~k个）
* 等价于Nim堆，SG(n) = n
*/
public static int[] computeSGStonePile(int maxN, int maxTake) {
int[] sg = new int[maxN + 1];
for (int i = 1; i <= maxN; i++) {
Set<Integer> values = new HashSet<>();
for (int j = 1; j <= maxTake && j <= i; j++) {
values.add(sg[i - j]);
}
sg[i] = mex(values);
}
return sg;
}
/**
* 一维取石子游戏的SG函数（只能取斐波那契数个）
* 即斐波那契Nim的变体
*/
public static int[] computeSGFibonacciNim(int maxN) {
List<Integer> fib = new ArrayList<>();
fib.add(1); fib.add(2);
while (fib.get(fib.size() - 1) <= maxN) {
fib.add(fib.get(fib.size() - 1) + fib.get(fib.size() - 2));
}
int[] sg = new int[maxN + 1];
for (int i = 1; i <= maxN; i++) {
Set<Integer> values = new HashSet<>();
for (int f : fib) {
if (f > i) break;
values.add(sg[i - f]);
}
sg[i] = mex(values);
}
return sg;
}
/**
* 二维网格移动游戏的SG函数（在一个棋盘上移动棋子）
* 示例：在N×M网格上，棋子每次可以向左或向下移动任意格
*/
public static int[][] computeSGGridMove(int n, int m) {
int[][] sg = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 0 && j == 0) {
sg[i][j] = 0;
continue;
}
Set<Integer> values = new HashSet<>();
// 向左移动
for (int k = 0; k < j; k++) values.add(sg[i][k]);
// 向下移动
for (int k = 0; k < i; k++) values.add(sg[k][j]);
sg[i][j] = mex(values);
}
}
return sg;
}
/**
* 图博弈的SG函数（在有向无环图上移动棋子）
*/
public static int[] computeSGOnDAG(int n, List<Integer>[] graph) {
int[] sg = new int[n];
Arrays.fill(sg, -1);
java.util.function.IntUnaryOperator dfs = new java.util.function.IntUnaryOperator() {
@Override
public int applyAsInt(int u) {
if (sg[u] != -1) return sg[u];
if (graph[u].isEmpty()) {
sg[u] = 0;
return 0;
}
Set<Integer> values = new HashSet<>();
for (int v : graph[u]) {
values.add(applyAsInt(v));
}
sg[u] = mex(values);
return sg[u];
}
};
for (int i = 0; i < n; i++) {
if (sg[i] == -1) dfs.applyAsInt(i);
}
return sg;
}
/**
* 多堆博弈的胜负判断
* @param piles 每堆的状态描述
* @param getSG 获取单堆SG值的函数
*/
public static <T> boolean isWinning(T[] piles, java.util.function.Function<T, Integer> getSG) {
int xor = 0;
for (T pile : piles) {
xor ^= getSG.apply(pile);
}
return xor != 0; // 非零为必胜态
}
/**
* 多堆博弈的必胜移动策略（找到一步使总SG变为0）
*/
public static <T> T[] findWinningMove(T[] piles,
java.util.function.Function<T, Integer> getSG,
java.util.function.Function<T, List<T>> getNextStates) {
int totalSG = 0;
int[] sgValues = new int[piles.length];
for (int i = 0; i < piles.length; i++) {
sgValues[i] = getSG.apply(piles[i]);
totalSG ^= sgValues[i];
}
if (totalSG == 0) return null; // 已经是必败态
for (int i = 0; i < piles.length; i++) {
int targetSG = totalSG ^ sgValues[i];
if (targetSG < sgValues[i]) {
// 找到这堆的一个后继状态，使其SG值等于targetSG
for (T next : getNextStates.apply(piles[i])) {
if (getSG.apply(next) == targetSG) {
@SuppressWarnings("unchecked")
T[] result = (T[]) java.lang.reflect.Array.newInstance(
piles.getClass().getComponentType(), piles.length);
System.arraycopy(piles, 0, result, 0, piles.length);
result[i] = next;
return result;
}
}
}
}
return null;
}
}
/**
* 经典游戏实例：Green Hackenbush（绿色砍竹游戏）
* 简化为：一条由多个线段组成的竹枝，玩家轮流砍一条边，
* 与地面不连通的部分消失。最后能砍的人获胜。
* SG值等于竹枝长度的Nim和。
*/
class GreenHackenbush {
/**
* 计算竹枝的SG值（一条链的SG值等于其长度）
*/
public static int bambooSG(int length) {
return length; // 简单链的SG值就是长度
}
/**
* 多枝竹子的复合游戏
*/
public static boolean isWinning(int[] bamboos) {
int xor = 0;
for (int len : bamboos) xor ^= len;
return xor != 0;
}
}
/**
* 经典游戏实例：翻硬币游戏（Turning Turtles）
* 一排硬币，每次选择一个正面的硬币并翻转它及它左边的任意硬币。
* SG值等于正面硬币位置的异或和。
*/
class TurningTurtles {
/**
* 计算状态的SG值
* @param state 二进制表示，1表示正面朝上
*/
public static int computeSG(int state) {
int sg = 0;
int pos = 0;
while (state > 0) {
if ((state & 1) == 1) {
sg ^= pos;
}
pos++;
state >>= 1;
}
return sg;
}
}
/**
* 经典游戏实例：Kayles（保龄球瓶游戏）
* 一排瓶子，每次可以击倒1个或相邻的2个瓶子。
*/
class Kayles {
private static int[] sgMemo;
public static int computeSG(int n) {
if (sgMemo == null) {
sgMemo = new int[1000];
Arrays.fill(sgMemo, -1);
}
if (n < 0) return 0;
if (sgMemo[n] != -1) return sgMemo[n];
Set<Integer> values = new HashSet<>();
// 击倒第i个瓶子，分成左右两段
for (int i = 0; i < n; i++) {
values.add(computeSG(i) ^ computeSG(n - 1 - i));
}
// 击倒相邻的i和i+1个瓶子
for (int i = 0; i < n - 1; i++) {
values.add(computeSG(i) ^ computeSG(n - 2 - i));
}
sgMemo[n] = SGSolver.mex(values);
return sgMemo[n];
}
}
/**
* 主程序：演示SG函数的应用
*/
public class SGDemo {
public static void main(String[] args) {
System.out.println("=== 一维取石子游戏（取1~3个）SG值 ===");
int[] sg1 = SGSolver.computeSGStonePile(20, 3);
for (int i = 0; i <= 20; i++) {
System.out.printf("SG(%d)=%d ", i, sg1[i]);
if (i % 5 == 4) System.out.println();
}
System.out.println("\n=== 斐波那契Nim SG值 ===");
int[] sg2 = SGSolver.computeSGFibonacciNim(20);
for (int i = 0; i <= 20; i++) {
System.out.printf("SG(%d)=%d ", i, sg2[i]);
if (i % 5 == 4) System.out.println();
}
System.out.println("\n=== 2D网格移动SG值（部分） ===");
int[][] sg3 = SGSolver.computeSGGridMove(5, 5);
for (int i = 0; i <= 5; i++) {
for (int j = 0; j <= 5; j++) {
System.out.printf("%3d", sg3[i][j]);
}
System.out.println();
}
System.out.println("\n=== Kayles游戏SG值 ===");
for (int i = 0; i <= 15; i++) {
System.out.printf("Kayles(%d)=%d%n", i, Kayles.computeSG(i));
}
System.out.println("\n=== Green Hackenbush ===");
int[] bamboos = {3, 5, 7};
System.out.println("竹枝 " + Arrays.toString(bamboos) +
" 是否为必胜态: " + GreenHackenbush.isWinning(bamboos));
System.out.println("\n=== 多堆Nim判断 ===");
Integer[] nimPiles = {3, 4, 5};
boolean winning = SGSolver.isWinning(nimPiles, x -> x);
System.out.println("Nim堆 " + Arrays.toString(nimPiles) +
" 是否为必胜态: " + winning);
}
}
SG函数计算技巧
1. 打表找规律
对于一维状态的SG函数，常可通过打表发现周期性规律：
– 普通Nim：SG(n) = n
– 每次取1~k个：SG(n) = n % (k+1)
– 斐波那契Nim：呈现复杂但有规律的模式
2. 分解子游戏
Sprague-Grundy定理的核心价值在于”分解”：将复杂游戏拆分为独立子游戏，分别计算SG值后异或合并。例如多个独立的竹枝、多堆独立的棋子，都可独立分析。
3. 对称性简化
若游戏状态存在对称性（如中心对称的棋盘），对称状态的SG值相同，可大幅减少计算量。
复杂度分析
| 场景 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 一维线性SG（递推） | O(N × M) | O(N) |
| 一维线性SG（记忆化搜索） | O(N × M) | O(N) |
| 二维网格SG | O(N² × M²) | O(N²) |
| DAG上SG | O(V + E) | O(V) |
| 多堆复合判断 | O(K) | O(1) |
其中N为状态范围，M为单状态后继数，K为子游戏数。
应用场景
- 博弈AI：计算当前状态的SG值，AI在必胜态时选择使SG为0的移动。
- 算法竞赛：Nim游戏及各类变体的标准化解法。
- 游戏设计：评估新设计的无偏博弈是否存在必胜策略。
- 资源分配：将竞争资源建模为无偏博弈，分析最优策略。
总结
Sprague-Grundy定理赋予了组合博弈论一套完整的”代数工具”：任意无偏博弈都被赋予一个SG值，复合博弈通过异或运算求解。这一框架将千变万化的博弈问题统一归约为Nim问题，使分析复杂度大幅降低。本文提供的Java实现涵盖通用SG计算框架、一维/二维/图结构上的具体应用，以及Kayles、Green Hackenbush等经典游戏实例。掌握SG函数后，读者将能够系统化地分析和求解各类无偏博弈问题，为博弈AI和策略分析奠定坚实理论基础。
