11/9
16:03
OI

简单博弈论 | SG函数 学习笔记

昨日膜你赛考了SG函数 发现一道题都没写过所以也没想到 大惊 赶快补习一下…


Nim游戏

估计全世界博弈论都是第一个学的Nim游戏… Nim游戏就是给定n堆物品,i堆有A_i个,每个人可以选一堆拿任意多,没的取的输.

做法是,先手必胜,

\oplus_{i=1}^n A_i \neq 0

简单证明

如果xor和不为0,设最高二进制不为0位为k,肯定有一个数,k位为1,那么我们可以取走一些使得它变成0.

对于对手一个使得xor不为0的操作,显然可以用上述办法消除影响,因此必败

貌似这个操作叫Nim和的说

Nim-k游戏

就是可以取k堆.推广xor运算为\mod (k+1)的即可

阶梯Nim游戏

挑选一个位置i,任选个数移到i-1

如果一个人把一个位置上的移动了,另一个人可以把那些再前移,所以等价于在奇数位置玩Nim游戏

反Nim游戏

取走最后一个的人输

必胜要求满足以下条件之一:

存在一堆个数> 1,xor不为0

每一堆个数都是1,xor为0


Sprague-Grundy函数

SG(x) = {\rm mex}_y \lbrace SG(y) \rbrace

其中y是有向图游戏中x可以到达的状态

必胜SG函数>0,否则必败

简单证明:

归纳法.

最终状态为0

如果存在必胜态,那么必有后继必败,SG必不为0

反之亦然

Sprague-Grundy定理

游戏的和

存在有向图游戏G_i,定义G是任选某个G_i并且行动的有向图游戏,那么有

SG(G) = \oplus_{i=1}^n SG(G_i)

简单证明

其实和Nim游戏证明差不多…

SG函数与Nim游戏

我们考虑用SG函数处理Nim游戏.每一堆都是一个有向图游戏,石子数量正好等于SG函数值. 完 全 一 致

反SG函数

就是反Nim游戏那个东西,规则也一样


其他博弈问题

这部分证明大部分先咕了…

Bash博弈

一堆n个物品,每次取[1,m]

取光胜必败条件: n \mod (m+1) = 0,归纳可

简单证明

很简单,一定存在方案使得两个人各取一次,sum = m +1

Wythoff博弈

我是鸽王

树上删边游戏

SG(leaf) = 0

SG(x) = \oplus (SG(y)+1)

无向图删边游戏

“将图中的任意一个偶环缩成一个新点,任意一个奇环缩成一个新点加一个新边;所有连到原先环上的边全部改为与新点相连。这样的改动不会影响图的SG 值。”