博弈入门

定义

先手：第一个行动的玩家

后手：第二个行动的玩家

必败：无论怎么样操作，都会输

必胜：可以选择一种操作，让对方必败

先手必胜：先手采取一定行动以后，可以让下一步变成先手必败（即后手怎么样都无法获胜

先手必败：先手怎么样做都会输

必胜点、必败点

经典问题

巴什博弈

背景：一共n个石头，两人轮流从中取石头，至少取1个，最多取m个，拿不了的人输

结论：当n为（m+1）的倍数时，先手必败。其余先手必胜

先手必败：无论先手怎么取，后手都能让两次取的和为(m+1)

先手必胜：先手可以将局面转换成先手必败态

尼姆博弈

背景：一共n堆石头，每堆石头有$a_i$个，每人每次能从一堆石头中取任意多个，但是不能不取。不能拿的输。

讨论：

n=1时，显然先手必胜

n=2时，假设a1!=a2，且a1>a2，先手可以在第一堆取走a1-a2个,让a1=a2,接下来后手无论取多少个，先手都能复制操作。因此先手必胜

假设a1=a2，后手也一样可以复制操作，后手必胜

猜想：

当$a_1 XOR a_2 XOR a_3...XORa_n=0$ 则先手必败，否则先手必胜

证明：

假设XOR为0，先手在某一堆中取走了k个，那剩余的 $a_1 XOR a_2...XOR a_n=k$

假设k的二进制最高位1为第x位

也就是一定存在一个$a_i$使得 $a_i$的第x位为1。于后手将$a_i$ 变成$a_i XOR k$,这样整体的XOR和又变回了0。

那么，ai变成$a_iXORk$是否可行。

我们知道，k的二进制最高位x一定为1，a_i的这一位也为1，他们XOR后，这个数一定减去的2的x次方，就算后面全是1也没这么大，所以$a_i XOR k$一定小于$a_i$,后手每次取 ($a_i- a_i XOR k$)即可。

策略成立，因此后手必胜

相反的，如果XOR不为0，先手可以将状态转换为后手必胜状态

-阶梯尼姆博弈

有n堆石子，每次每人可以取走第i堆(i>1)任意数量的石子并将它们放到第i−1堆，或者直接取走第一堆的任意数量石子，不能操作的人输

对于这一类问题我们将堆的编号分奇偶考虑，如果只有奇数编号那些堆石子，这就是一个尼姆博弈。现在加入了偶数编号的堆，同样不影响答案，因为如果有人将偶数编号第i堆的石子移到第i-1堆，那么另一个人可以将上一个人操作的石头移到i-2堆，奇数编号堆的石子不变，相当于将偶数编号石子往前移动了两格。一直玩下去，对面只会输，因为我们可以复制对方的操作。

但是对于奇数层的石头，我们将它移动到偶数层后，它变成了无效石头，相当于我们一直在减少奇数层的石头。

因此只需要对奇数层的石头进行尼姆博弈。

威佐夫博弈

有两堆石头，每个人可以拿任意一堆中的任意数量，或者在两堆中拿一样的数量，不能拿的输。

我们用$(p0,p1)$来表示目前的局势，定义先手必败的局势叫$奇异局势$

我们可以发现$(0,0),(1,2),(3,5),(4,7),(6,10)$为小的奇异局势，观察这些奇异局势，不难发现，对于奇异局势的第i个，满足$abs(p0-p1)=i$，且$p0=mex(前面的奇异局势)$

根据beatty定理：

若两个正无理数α、β满足1/α + 1/β = 1，则由它们生成的整数序列⌊nα⌋和⌊nβ⌋将互不重叠且覆盖所有正整数。

第k个奇异局势为

$\left (\left \lfloor \frac{1+\sqrt{5}}{2}k \right \rfloor,\left \lfloor \frac{3+\sqrt{5}}{2}k \right \rfloor \right )$

我们设较多堆的石子为x,少的为y，由于刚刚知道他们的差为i，因此k=x-y。如果x=$\left \lfloor \frac{1+\sqrt{5}}{2}k \right \rfloor$，则为奇异局势先手必败，否则先手必胜

SG函数入门

公平组合游戏 中的各种状态只可能存在两种：以 该状态开始先手必胜 与 以该状态开始先手必败。为了方便，下面简称为 W 状态 和 L 状态。

其次，没有后继状态（从该状态开始进行一次操作后的状态）的状态一定是 L 状态，因为此时无法操作，该玩家也就输了。

然后，一个状态为 W 状态 当且仅当其至少有一个后继状态为 L 状态。显然，你有机会给对手留下 L 状态 就相当于你有方法获得了胜利。

最后，一个状态为 L 状态 需要它的所有后继状态都为 W 状态。这样，无论你怎么操作，都会给对手留下 W 状态，相当于你输了。

SG(x)=mex({SG($y_1$),SG($y_2$),…,SG($y_k$)})。

对于 SG 函数的定义有：

• 终止状态（无合法移动）：SG=0（必败点，P-position）。
• 非终止状态：SG(x)=mex({SG($y_1$),SG($y_2$),…,SG($y_k$)})。

SG 函数本质上可以看作对于当前局面的一种 压缩信息。

而对于一个公平组合游戏，设其起点为 s，则 当 SG(s)!=0时，先手必胜。