有向图博弈问题

我们先了解一下公平组合游戏的适用范围（定义）

 游戏满足：

　(1)2名玩家交替行动

　(2)任意时刻，可执行的合法行动与轮到哪名玩家无关

　(3)不能行动的玩家为输

再引入2中状态：

　P态：对于前一个玩家是必胜的

　N态：对于后一个玩家是必胜的

这里我们以取石子游戏为例，感受一下P态和N态

玩家2人，a颗石子，每次最少取1个，最多取b个，轮流取石子，最后取的人赢

0个石子显然是P态，而还剩1，2...b显然就是N态了......

所以我们可以结合定义得到，一个P态的后续状态一定都是N态，一个P态的后续状态一定都是N态

这样就简单了

对于任意的a和b，只要a%(b+1)!=0那么先手的人一定胜，否则一定败

 

除此之外，还有一个我们需要了解的东西，我个人认为很玄学，就是mex运算

具体就是，设S表示一个非负整数集合，mex（S）就是不属于S的最小非负整数

 

比mex更玄学的是SG函数：对于任意状态x，它的SG函数值为g(x)=mex{g(y)|y是x的后续状态}

SG有什么用呢？

结合上面，我们可以知道：如果我们能知道一个状态的SG值，那么我们就可以判断当前状态是N态还是P态

若SG值为0，则为P态，否则就是N态

　　

接下来是一些常用博弈结论

1. 巴什博奕（Bash Game）：

例如A：和B一块报数，每人每次报最少1个，最多报4个，看谁先报到30

其实如果知道原理，这游戏一点运气成分都没有，只和先手后手有关，比如第一次报数，A报k个数，那么B报5-k个数，那么B报数之后问题就变为，A和B一块报数，看谁先报到25了，进而变为20,15,10,5，当到5的时候，不管A怎么报数，最后一个数肯定是B报的，可以看出，作为后手的B在个游戏中是不会输的

那么如果我们要报n个数，每次最少报一个，最多报m个，我们可以找到这么一个整数k和r，使n=k*（m+1）+r，代入上面的例子我们就可以知道，如果r=0，那么先手必败；否则，先手必胜

2. 威佐夫博弈（Wythoff Game）：

有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利

结论：，若两堆物品的初始值为x和y，且x<y，则另z=y-x

记w=[（（sqrt（5）+1）/2）*z ]

若w=x，则先手必败，否则先手必胜

3. 尼姆博弈（Nimm Game）：

尼姆博弈指的是这样一个博弈游戏：有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜

结论就是：把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜

4. 斐波那契博弈：

有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后

一件物品的人获胜

结论是：先手胜当且仅当n不是斐波那契数（n为物品总数）

5.阶梯博弈

有 ? 堆石子放在 N 层阶梯上 • 每次选择一层的若干石子，放入下一层。（特别地，1 层的石子 就被扔掉）

结论：计算所有奇数层石子数的异或和，得到整个游戏的 SG 

6.Moore’s Nim

现在，修改游戏规则，约定每次选择至多 K 堆石子，并从每一堆 中各取出任意多个石子

不能行动者负

结论：我们写出石子数的二进制，然后统计每一位中 ‘1’ 的个数之和 mod （? + 1） ，后手必胜当且仅当每一位 ‘1’ 的个数均为 ? + 1的倍数

 

上述结论对一般游戏的和不成立

 

7.Rim

? 堆石子 • 每次的操作是选择一堆石子，去掉其中至少一个，然后把此堆剩 下的石子划分成若干小堆

结论：这个游戏的 SG 函数和 Nim 完全相同

 

 

我们再来看一种题型：有向图游戏和，有以下定理:

有向图游戏的某个局面必胜，当且仅当该局面对应结点的SG函数值大于0

有向图游戏的某个局面必败，当且仅当该局面对应结点的SG函数值等于0

　　

最后是一些扩展

除了上面提到的尼姆和，还有一些游戏可以通过一种叫尼姆积的运算求解SG函数

假如把尼姆游戏的取胜规则改为谁取走最后一个石子谁输的话（终止状态为N状态），先手必胜当且仅当

所有堆的石子数都为1且SG==0

有些堆的石子数大于1且SG!=0

 

以上知识整理于网络，自己的理解，参考《信息学奥赛一本通·提高篇》