阶梯博弈

今天做了一道很普通的博弈题。想起来还有这个有趣的世界。于是打算把博弈题的基础总结一下，以阶梯博弈为引子。

首先你需要懂Nim游戏，理解SG函数更好。第一次理解它们的时候，你应该会被惊艳到，无他，巧妙！

在博弈题中，有一种常用的思路是：

1. 考虑在最终胜局中一定成立的某种性质。
2. 判断命题"任一玩家进入满足该性质的局面后能垄断这一性质（能使这一性质在且仅在自己的轮次中成立）"
3. 如果2中命题为真，那么初始局面满足该性质则先手胜利，否则后手胜利。

现在介绍阶梯博弈问题：设$n$阶楼梯上散落着一些硬币，第$i (0\le i<n)$ 阶台阶上有$a_i$ 枚硬币，有两位玩家轮流行动，每次行动可以从第$i$阶台阶上取若干硬币移动到第$i-1$阶台阶上。当某方无法完成行动时，另一方获胜。

考虑最后的胜局：第1阶台阶上还剩若干硬币，从第2阶起往上都没有硬币，这一轮把第1阶台阶上的硬币放到第0阶台阶上即可获胜。

很显然，最后的胜局一定满足性质 “所有奇数台阶上石子数量的异或和$>0$", 也就是说，如果把奇数台阶上的石子看作Nim游戏的一个个石子堆，那么该Nim游戏处于胜态。

这个性质可以被某玩家垄断吗？

可以的。对于进入Nim游戏胜态的玩家$x$，他总能通过移动奇数台阶上的石子使对手进入Nim游戏的败态（类似Nim游戏中的取石子）。考虑Nim游戏的处于败态中的对手，可能的两个选择：

1. 移动奇数台阶上的石子。玩家$x$再次进入胜态；
2. 移动偶数台阶上的石子，比如把第$2k$ 阶台阶上的$w$个硬币移到第$2k-1$阶台阶上。下一轮玩家$x$ 只要把$2k-1$ 阶台阶上的$w$ 个硬币移动到$2k-2$ 阶台阶（想一想为什么玩家$x$一定可以这么做），就能给对手与本轮一模一样的Nim游戏败态。