题目
N 堆石子，两人轮流行动，每次可以从
任意一堆里取走
任意正数个石子；取到最后一个石子的人获胜，无法操作者落败。问先手是否必胜。
输入: piles = [3, 4, 5]
输出: true
解释: 3 ^ 4 ^ 5 = 2 不为 0 —— 先手必胜。
同族还有两道更常考的变形：
- LC 877 石子游戏：一排 piles，每次只能从头部或尾部取一整堆，堆数为偶数，问先手（Alex）是否必胜；
- LC 292 Nim 游戏：只有一堆，每次最多取
m 个。
三道题看起来都是博弈，解法却分属三个层次：
一行异或、一次奇偶站队、一个取模。本文按这个顺序走，并且把「为什么异或非 0 就一定赢」拆成两句能背下来的论证。
一、核心洞察：把 N 堆压成一个数
博弈题的难点从来不是「算」，是
找不到可以递推的状态。N 堆石子每堆可以取 1 到
piles[i] 个，状态空间大得没法搜。
Bouton 定理的做法是换一个视角：不去描述局面，而是给每个局面算一个数 ——
把所有堆的数量异或起来。
先手必胜，当且仅当 piles[0] ^ piles[1] ^ ... ^ piles[n-1] != 0。
这一行代码就是全部算法。但它为什么对，靠的是两句互相补足的论证：
- 异或非 0 时，一定存在一步走到异或为 0。（构造性证明，见第二节）
- 异或为 0 时，任何一步都走到异或非 0。 假设动了第
i 堆、p -> p'，新局面异或仍为 0，那么 p ^ p' = 0，即 p = p' —— 等于没动，矛盾。
两条合起来就是归纳：先手每次都能把「异或非 0」的局面交还给后手，而后手无论怎么动，交回来的必然是「异或非 0」。石子总数严格递减，游戏必然结束，而最后停在那一步的人是先手。
这就是「必败态」的定义 —— 不是走不动，是你怎么走都把赢的机会送给对方。
二、拆解：制胜一手是构造出来的，不是搜出来的
第一句论证需要给出构造。设全场异或为
x != 0：
- 取
x 的最高置位 h（x 在这一位上为 1）；
- 找一堆
p 满足 (p >> h) & 1 == 1 —— 一定存在，否则所有堆在这一位上都是 0，异或出来不可能是 1；
- 把这堆从
p 改成 p ^ x。
为什么新值一定合法（非负且严格变小）：
p 和
x 在第
h 位上都是 1，异或后这一位变成 0，而比
h 高的位两者都是 0、异或后不变 —— 所以
p ^ x 在最高位上被清掉了一位，严格小于
p，且不会变负。
def first_player_wins(piles) -> bool:
x = 0
for p in piles:
x ^= p
return x != 0
def winning_move(piles):
x = 0
for p in piles:
x ^= p
if x == 0:
return None # 必败态，没有制胜一手
h = x.bit_length() - 1 # 最高置位
for i, p in enumerate(piles):
if (p >> h) & 1:
piles[i] ^= x # 新值 = p ^ x，严格更小且非负
return piles
三、动画怎么看
动画用主例
piles = (3, 4, 5)，四步走完：
- 石子堆行：每格是石子的二进制，黄框 = 本帧要动的那一堆，绿框 = 已经改好的那一堆；
- 累计异或行：逐堆异或累加（
3 -> 7 -> 2），这是把 N 堆压成一个数的过程；
- 制胜一面板：
x = 2 的最高置位是 bit 1，第 1 堆（3）在这一位上为 1，把它改成 3 ^ 2 = 1；
- 答案条：绿色 = 先手必胜，红色 = 先手必败。
(1, 2, 3) 那组值得手动跑一遍：异或恒为 0，动画会直接判
先手必败，并给后手的镜像策略 —— 你动哪堆，我就把那堆改成让全场异或回到 0。
四、完整推演
piles = (3, 4, 5)：
验证一下第二步论证：新局面
(1, 4, 5) 异或为 0，后手无论怎么动都会破坏它。比如他从第 2 堆取 1 个变成 3，异或变成
1 ^ 3 ^ 5 = 7 —— 先手再照着构造走一次即可。
五、进阶：LC 877 两端取，偶数堆靠奇偶位站队
LC 877 换了约束：
只能从头部或尾部取一整堆，而且堆数保证是偶数。这时异或判定完全失效（取法受位置限制），但有个更漂亮的结论：
先手必胜，而且必胜策略是开局站一次队。
按原始下标把堆分成两队：偶数位一堆、奇数位一堆。先手第一次取左端，之后每一步的两端就都只剩
奇数位；取右端则之后只剩偶数位。所以：
第一次取哪一端，就等于选择自己整局站在偶数位还是奇数位。
于是策略一句话：算两个奇偶位的和，取大的那队，用第一次取哪一端来锁定它。主例
[5, 3, 4, 5]：偶数位和
5 + 4 = 9，奇数位和
3 + 5 = 8 —— Alex 取左端，锁定偶数位，终局
9 : 8。
动画把这一点画成了对局：绿色 = 偶数位、橙色 = 奇数位，取走的堆退化成虚线壳并留下
A 5 /
L 5 的分值，两个「和」筹码并排，赢的那边点亮。
注意 Lee 是贪心着打的（每次取两端较大的那堆），Alex 依然赢 —— 因为这个策略不依赖对手怎么走。
堆数是奇数时这个 trick 失效：两端奇偶不同，先手没法一次锁定一整条奇偶带，必须老老实实上区间 DP（
dp[i][j] 表示区间
[i,j] 上先手能比后手多拿多少）。
六、Java 版
public class Nim {
// 判定：一行异或
public static boolean firstPlayerWins(int[] piles) {
int x = 0;
for (int p : piles) x ^= p;
return x != 0;
}
// 制胜一手：返回新局面；必败态返回 null
public static int[] winningMove(int[] piles) {
int x = 0;
for (int p : piles) x ^= p;
if (x == 0) return null;
int h = Integer.highestOneBit(x); // 最高置位
for (int i = 0; i < piles.length; i++) {
if ((piles[i] & h) != 0) {
piles[i] ^= x; // 新值 = p ^ x，严格更小且非负
return piles;
}
}
return null; // 到不了这里
}
}
LC 877 的 Java 版就是一行（堆数保证为偶数时）：
public boolean stoneGame(int[] piles) {
return true; // 偶数堆，先手必胜
}
面试里当然不能只写
return true —— 要把奇偶位和那段讲出来（见第十节）。
七、边界情况
- 只有一堆：异或就是它本身，非 0 必胜（一次全拿）、为 0 必败（这堆本来就是空的）。
- 全场为空：异或为 0，先手无法操作，必败。
- 两堆相等：异或为 0，必败 —— 后手全程镜像（你从一堆取
k，我从另一堆取 k）。
- 一堆为 0：它就是死堆，异或判定天然忽略它，不影响结论。
- LC 877 的奇数堆：结论不成立，必须 DP；
[1, 5, 2] 这种三堆的样例正是用来打「无脑 return true」的。
八、复杂度
真正花时间的是
想清楚判定，不是算。所有 Nim 类博弈的判定都是 O(n) 甚至 O(1)，难的是把局面归约到「一个数」。
九、常见坑
9.1 约定搞反：最后取者胜 vs 最后取者败
正常约定（Nim）是「取到最后一颗者胜」；
反常博弈（misère Nim）是「取到最后一颗者败」，结论不一样：当所有堆都为 1 时胜负按堆数奇偶翻转，其余局面才回到正常约定。LeetCode 上 Nim 系列都是正常约定，但面试官会口头换约定来试你。
9.2 制胜一手选错堆
必须选「在
x 的最高置位上为 1」的那一堆。随便挑一堆改成
p ^ x 会让新值变大（变成送石子给对手），或者根本不能降到非负。构造的每一句都是在保证合法性。
9.3 以为异或为 0 时可以「随便走」
异或为 0 是先手必败态，不是平局。后手有明确策略（镜像应战），不是碰运气。把必败态当平局讲，整道题的论证就塌了。
9.4 把 LC 877 的结论套到通用 Nim
奇偶位站队只在「
两端取 + 堆数偶数」下成立，因为它依赖的是「第一次取哪端就把自己钉死在一条奇偶带上」。换成「从任意一堆取任意个」，两端取的位置约束消失，奇偶带毫无意义 —— 那时仍然是异或判定。
9.5 巴什博弈的取模写成除法
LC 292 是
n % (m + 1) != 0 先手胜。
m 是「每次
最多取
m 个」，不是「必须取
m 个」。写成
n % m 或者
n / (m + 1) 的奇偶，都是把规则记错。
9.6 用异或判定去做带约束的变体
LC 1510（石子游戏 VII，两端取、求分数差最大）和 LC 1140（石子游戏 II，按倍数取）都带额外约束，异或判定一概失效，只能上 DP / 极小化极大。
先判断约束是否破坏了「任意堆任意取」，再决定用哪套工具。
十、面试怎么答
- 先报判定："Nim 先手必胜当且仅当全场异或非 0，这是 Bouton 定理，判定 O(n)。"
- 再补两句论证："异或非 0 时，取最高置位、找一堆在这一位为 1、改成
p ^ x，一步走到异或 0；异或为 0 时任何一步都会走到非 0 —— 否则被改的那堆异或差为 0，等于没动。"
- 说出制胜一手的构造：不要说「存在」，要把三步讲出来；能顺手写
Integer.highestOneBit 是加分项。
- 接住 LC 877："两端取 + 偶数堆，先手必胜 —— 按原始下标奇偶分两队，第一次取哪端就锁定哪一队，取和大的那队。奇数堆必须区间 DP。"
- 报家族：巴什博弈
n % (m+1)、威佐夫博弈（两堆同取，必败态是黄金比例分割）、反常 Nim（全 1 时翻转）、SG 函数（一般博弈论，每堆可归约成一个 Nim 数）。
- 给复杂度对照：判定 O(n)、制胜一手 O(n)、LC 877 偶数堆 O(1) 结论 / 奇数堆 O(n^2) DP —— 强调「这类题的时间都花在归约上，不在计算上」。
结语
石子游戏是博弈论进算法面试的入口，它的教学价值全在
归约：把「N 堆、每堆任意取」的庞大状态空间，压成「一个异或数」—— 判定一行，构造三步。而 LC 877 提醒你，同一副石子换个约束（只能从两端取、堆数为偶数），归约的目标就换成「奇偶两条带」，解法从异或变成一次站队。
博弈题的功夫从来不在搜索，在找到那个不变量：异或值、奇偶带、或者巴什博弈里的
n % (m+1)。