Game Theory

Nim游戏和sg函数

题意

给出n堆石子，每堆石子的数量为a[i]，两个人轮流拿石子，每个人可以挑选任意一堆并拿任意颗石子(不能不拿)，轮到谁时没有石子算输，问最后谁获胜

分析

结论：若a[1]^a[2]^a[3]........^a[n]=0，则先手必输，反之先手赢

证明：Nim游戏的证明需引出sg函数

status：状态

P-status：在当前局面下，先手必败

N-status：在当前局面下，先手必赢

不难想出有如下性质：

1.集合为空时的局面为P-status

2.如果某个状态可以移动为P-status，那么这个状态一定为N-status

3.如果某个状态都只能移动到N-status，那么这个状态一定为P-status

回到Nim游戏，我们知道最终状态a[]={0,0,.....0}的局面为P-status，那么可以从终态出发逆推楚所有可能的局面，总共的转态数量为：a[1]×a[2]×....×a[n]，考虑记忆化搜索即可得出每个状态的情况

考虑将每个局面看做一个顶点，每个局面的子局面之间有一条有向边，则这个游戏可以转化为一个DAG

定义：mex运算，对于集合运算来说，表示最小的不属于这个集合的非负整数

对于一个Nim游戏，定义：sg函数：sg[x]=mex { sg[y] | x可以移动到达y }

例如：

取石子问题，有 $1$

可以递推出1~n每个点的sg值

最后若g[n]=0，则先手输，反之后手赢

为什么可以这样做？这样做为什么是正确的呢？

证明：

考虑sg值得含义，每个sg值代表一个状态

如果sg=0，表示当前为p状态，因为mex操作中都是>0，即移动将必定将对手的状态变为必胜态

sg≠0，表示通过几次操作可以变为p状态（即当前为N状态），因为N转态可以一步到达P状态，而p状态的当前选手必输

考虑sg函数和Nim函数，当sg[x]=k，表示x状态可一步转移到0~k-1，故Nim游戏中，每一堆石子相当于一个sg值，最终所有堆的sg即为所有子堆得sg值得xor异或

求解sg值得方法可以直接递推/DFS 求解

Bash Game

题意

只有一堆 $n$

$n$

$n$

$n$

$n$

$n$

$n$