博弈论与SG函数

Nim博弈

定义:

• 给定$n$堆物品,第$i$堆有$A_{i}$个。
• 轮流取任意个
• 无法取的人判负

Nim游戏不存在平局, 只有先手必胜和先手必败两种情况

定理

$$NIM博弈先手必胜,当且仅当A_{1}xorA_{2}xor...A_{n} \not=0$$ 下证

• 当上式成立, 若异或和$x$的最大为1为k位, 则存在某个数k位为1, 则从这堆中取$A_{i}xor\text{ }x,则原式异或和为0$.
• 当上式不成立, 则若取完之后$A_{i}$变为$A_{i}'$有异或和为0, 则根据消去律可得$A_{i}=A_{i}'$,矛盾.

公平组合游戏ICG

• 两名玩家交替行动
• 两人合法操作相同
• 不能行动判负

有向图游戏

• 给定有向图, 起点处有一个棋子
• 两名玩家轮流移动
• 不能移动判负

所有的ICG游戏都可以转化为一个有向图游戏, 把一个局面缩成一个点即可

Mex运算

定义: $$mex(S) = x_{min} (x \in \N,x\not\in S)$$

SG函数

定义: $$SG(u) = mex(SG(j)), (u\rightarrow j)$$ 对游戏G定义$SG(G)=SG(s)$

• 某局面SG>0则必胜
• 某局面SG=0则必败
• 整个游戏与局面判法一致
• 若是若干个游戏, 则若干个游戏的SG异或和=0为负,大于0必胜(证明同Nim游戏)