省选-博弈论

发现之前竟然没有一点博弈论的总结。

Nim 游戏

$n$ 堆石子，每次选一堆拿走正整数个，无法操作者输。

$⨁_i a_i=0$ 则先手必败，否则先手必胜。

然后这个的证明就是 $⨁_i a_i=0$ 一定不会转移到自己，否则的话只需要找到最高位与 $⨁_i a_i$ 相同的 $a_k$，下一步转移到 $a_k ⨁ X$。

巴什博弈

$n$ 堆石子，每次选一堆拿走 $[1,k]$ 个，无法操作者输。

只需要 $s_x = x \mod (k+1)$，然后 Nim 游戏了。

阶梯博弈

有 $n$ 堆石子，编号为 $1,2,\dots,n$。每次操作可以选择一堆，将任意正整数个石子移动到第 $i-1$ 堆；若选择第 $1$ 堆，则直接拿走这些石子（相当于移动到第 $0$ 堆）。无法操作者输。

阶梯博弈等价于对所有奇数位置做 $\mathrm{Nim}$ 游戏，也就是先手必败当且仅当

$$\bigoplus_{i} a_{2i-1}=0,$$

其中 $a_j$ 表示第 $j$ 堆的石子数量。

若该定理成立，那么赢家显然只会动奇数上的位置，如果输家可能会动偶数上的位置，赢家就可以把输家移动的那些石子再次往前挪一格到偶数，丢给输家一个所有奇数位置上都和原来一样的局面。

SG 函数

SG 函数的定义是在一个有向无环图上的。

定义一个状态（图上的一个点）的 SG 值为出点 SG 值的 mex，$sg = 0$ 表示该局面先手必败。

对于任意一个 $\bigoplus_{i=1}^n s_{a_i}=0$ 的局面，我们不可能移动一步使得其仍为 $\bigoplus_{i=1}^n s_{a_i}=0$。

对于任意一个 $\bigoplus_{i=1}^n s_{a_i}\neq 0$ 的局面，我们总能移动一步使得其变为 $\bigoplus_{i=1}^n s_{a_i}=0$。