OI里面考的一般是完全信息博弈,也就是谁都知道问题的全部信息,也就是说在双方绝对聪明的条件下一定会有一个确定的胜者.
下面的内容参考了队友QianK的部分板子.
sg函数
必输状态的sg值为0.
其他状态的sg值为 mex(所有可到达的子状态) .
上面是一个独立游戏的sg函数值,对于多个独立游戏(比如多个石堆彼此取石子是独立的),sg函数为 xor(所有子游戏的sg) .
Nim游戏
每次可以从一堆石子拿走任意个数的石子,不能不拿,谁拿不了就输.
下文除了反Nim游戏外均默认拿到最后一个石子的赢.
结论:所有石子xor为0必输,其余情况必赢.
证明:假设当前xor不为0,前手必定能构造一个方案满足拿走之后剩余的xor为0,然后效仿后手拿即可.
反Nim游戏
和Nim游戏一样的拿石头规则,但是拿到最后一个石子的反而会输.
结论:所有堆<=1的时候,xor为0必胜.
如果存在有堆>1的时候xor为0必输.
证明:如果所有堆都小于等于1,那么二人每次都只能拿一个石子,那就和奇偶有关,换句话说就是xor.
如果有石堆大于1个的时候,考虑这个非1的堆:后手可以效仿先手构造xor不变的手法,那么xor本来就是0,一定会拿到最后一个石头,就必输了.
阶梯Nim游戏
有n堆石子,每次可以把第i(1<=i<=n)堆的任意数量石子移动到第i-1堆,不能不动.
结论:等价于在奇数堆做Nim游戏.
证明:先考虑只有偶数堆有石子,此时先手必败,因为先手只能把石子移动到奇数堆,后手可以随意效仿.
所以把奇数堆石子拿到偶数堆就相当于取走了这些石子,我们对奇数堆做xor就行了.
K-Nim游戏
n堆石子,每次取至少一堆,至多k堆的任意颗,不能不拿.
结论:当二进制每一位的1的数量和为k+1的倍数时先手必败.
证明:首先全0局面先手必败.那么当所有位的和都是k+1的倍数时,任意一次操作不能覆盖这k+1堆,但两次操作就可以了.
还有一个发现:Nim游戏就是k=1时的K-Nim游戏.
巴什博弈
一堆石子n个,每次拿至少1至多m个,先取完的胜.
结论:先手必败当且仅当 $(m+1)|n$ .
证明:当n<m+1时,先手一次全拿走直接赢了.
当n=m+1时先手一次肯定拿不走后手一次肯定拿走就赢了.
其余情况当 $n=p(m+1)$ 时先手随便拿,后手一定能构造出 $n’=(p-1)(m+1)$ 所以是必输的.
威佐夫博弈
有两堆石子a和b,每次取时可以选一堆取任意颗,或者选两堆取走相同个数的石子,不能不取.
结论:先手必败当且仅当存在k满足:
证明:QianK不会,但据说可以打表找规律.
稍稍的挖一个坑.
斐波那契博弈
一堆n石子,先手第一次不能全部取走,从后手第一次取开始每次取的石子至多为对手上一次取的两倍,不能不取.
结论:先手必败当且仅当n是个斐波那契数.
证明:Zeckendorf定理(齐肯多夫定理,一个数能被表示成若干不连续的斐波那契数字和)
chomp博弈
有一个 $n\times m$ 的棋盘,每一个格子都有一个石子,每次可以选一个坐标(a,b)然后把所有 $(x,y)(a\ge a,y\ge b)$ 的石子全部拿走,取到(1,1)的输了,问先手是否必胜.
结论:除非开局就剩(1,1)否则必胜.
三维chomp博弈
挖坑.
二分图博弈
挖坑.
典题
- 小质数棋盘硬币游戏
首先硬币的两维是独立的,考虑分开.
打表出硬币的sg序列为0,0,1,1,2,2,3,3,4,硬币的sg可以用维度mex起来.
所有的独立硬币xor起来.