博弈学习笔记博弈前言Part1 SG函数Part2 平等博弈模型Part3 做题心得附录：题单

博弈

Tags：数学

作业部落

评论地址

---

前言

本博文分三部分，第一部分简单介绍SG函数，第二部分简单介绍博主所理解的一些博弈模型，第三部分推荐题目以及分享做题心得，本文基本不适合初学者食用，初学者请移步下方链接

论文：2009贾志豪（百度文库可搜）
自为风月马前卒的总结
自为风月马前卒的题目
orz yyb

Part1 SG函数

优势：可以实现对多个游戏进行加和

计算方式：(SG(x)=mex(SG(y)))，其中(mex)指集合中最小没有出现过的自然数，(y)为(x)的后继状态

游戏加和：(SG=SG(x_1) bigoplus SG(x_2) bigoplus ...bigoplus SG(x_n))

意义：(SG=0)表示先手必败，为P状态，否则为N状态，先手必胜

理解：化为(Nim)游戏，对于每个(SG)不为(0)的状态总有一种方案使得(SG)成为(0)

Part2 平等博弈模型

1.巴什博弈（Bash Game）

问题：只有一堆(n)个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取(m)个。最后取光者得胜
结论：(n%(m+1))为(0)先手必败否则必胜

2.威佐夫博弈（Wythoff Game）

问题：有两堆各若干个物品，两个人轮流同时从一到两堆中取同样多的物品，规定每次至少取一个，最后取光者得胜
结论：
先手必败态的两堆石子之差依次递增，且每个自然数仅出现一次，先手必败态为((0,0),(1,2),(3,5),(4,7),(6,10),(8,13)...)
如果必败态为((a,b))，(k=(a-b))，则(a=frac{1+sqrt{5}}{2}*k)

3.尼姆博弈（Nim Game）

问题：(n)堆石子两人轮流在任意一堆中取任意石子，不能不取，最多取完，取到最后一颗石子者胜
结论：(n)堆石子数量异或和为(0)则先手必败否则必胜
Nim游戏代表了所有平等博弈问题！！

4.Nim 游戏扩展

问题：每次最多丢(k)个石子，其余规则同(Nim)
结论：每堆石子数量(%(k+1))后再求异或和

5.Nim k 博弈

问题：一次最多在(k)堆中取，其余规则同(Nim)
结论：把石子数二进制拆开，每位求和后(%(k+1))，若最后每位都为(0)则先手必败，否则先手必胜

6.阶梯博弈

问题：有(n)堆石子放在(n)层阶梯上，两人轮流选择一层的若干石子，放入下一层（特别地，选择(1)层的石子就被扔掉），无法操作者输
结论：奇数层石子的数量异或和为(0)则先手必败否则必胜

7.Anti-SG（反Nim游戏）

问题：取走最后一颗石子者败，其余规则同(Nim)
结论：
当且仅当以下情况先手必胜
1.整个游戏(SG=0)并且没有单一游戏(SG>1)
2.整个游戏(SG>0)并且至少一个单一游戏(SG>1)

方便记忆的话就是：如果每一堆都是一颗石子也就是所有单一游戏的(SG)值为(1)时，有偶数个单一游戏（即整个游戏(SG=0)）则先手必胜，否则至少有一堆石子大于(1)个，整个游戏的(SG)值不为(0)

8.Multi-SG

问题：在Nim游戏的基础上，操作可以是取石子也可以是把一堆石子分成非空的两堆，无法操作者输
结论：(SG)函数解决，所有后继状态的(mex)

9.Every-SG

问题：玩家对于所有没有结束的单一游戏同时操作，结束最后一个单一游戏的玩家获胜
结论：对于任意一个玩家，对于必胜的单一游戏肯定要尽可能延长时间（延长到最后自己就赢了），对于必败的单一游戏肯定要尽可能缩短时间，所以必胜单一游戏对后继状态的步数取(max)，必败单一游戏对后继状态步数取(min)，整盘游戏是否获胜只与最长步数的单一游戏的步数的奇偶性有关

例题：HDU3595

10.翻硬币游戏

问题：正反硬币排成一排，每次可以翻转一段区间，要求左端点必须由反面翻成正面，不能操作者输，求是否先手必胜
结论：每个位置上的硬币独立，分别算(SG)后异或起来

11.树上删边游戏

问题：一个有根树，一次操作是选择一条边，删除此边以及删掉边后和根不连通的部分，不能操作者输
结论：
(SG(x)=mex(S)+1)，(S)表示为(x)的子树内所有点的(SG)值的集合
或者是(SG(x)=sum_{xor}(SG(son)+1))，等价为链再化为(Nim)游戏即可证明

12.无向图删边游戏

问题：
结论：

13.动态减法问题

问题：有一个整数(N)，双方轮流减去一个正整数值，第一次不能减完，之后每次减的数不超过(f(x))，(x)表示为上一次减的值（保证(f(x))单调不降）
结论：
(H_i)表示第(i)个先手必败的状态，找到最小的(x)使得(f(H_x)ge H_i)，则(H_{i+1}=H_i+H_x)
通过这个结论可以快速解决(f(x)=x)必败状态是(2^k)，(f(x)=2x)必败状态是斐波那契数列

14.匹配的应用

问题：无向图中棋子在(s)，双方轮流操作，选一条边走出去并且把之前的结点删去，不能行动者输
结论：先手必胜要求(s)在图中的任意最大匹配中

Part3 做题心得

1.一排石子两头取的问题

描述1

CodeForces 794E Choosing Carrot
一行数依次选择左边或右边的数丢掉，先手想要留下的数最大，后手反之，求最终留下的数

结论1

如果为偶数，留下的是正中间两个数的(max)
如果是奇数（(>1)），假设正中间三个数为(A,B,C)，则留下的为(min(B,max(A,C)))

附录：题单

论文：2009贾志豪
自为风月马前卒总结：http://www.cnblogs.com/zwfymqz/tag/%E5%8D%9A%E5%BC%88%E8%AE%BA/
自为风月马前卒题目：http://www.cnblogs.com/zwfymqz/category/1019908.html

• [x] [HDU1527]取石子游戏 https://vjudge.net/problem/HDU-1527 （威佐夫博弈）
• [x] [BJWC2009]取石子游戏 https://www.lydsy.com/JudgeOnline/problem.php?id=1874
• [ ] [ZJOI2009]取石子游戏 https://www.luogu.org/problemnew/show/P2599
• [x] [luogu2252]取石子游戏 https://www.luogu.org/problemnew/show/P2252（威佐夫博弈）
• [x] [HNOI2010]取石头游戏 https://www.luogu.org/problemnew/show/P3210
• [x] [luogu4136]谁能赢呢 https://www.luogu.org/problemnew/show/P4136
• [ ] [SDOI2009]E&D https://www.luogu.org/problemnew/show/P2148
• [x] [BZOJ4550]小奇的博弈 https://www.lydsy.com/JudgeOnline/problem.php?id=4550
• [x] [SHOI2008]小约翰的游戏 https://www.luogu.org/problemnew/show/P4279（Anti-Nim）
• [x] [HDU1848]Fibonacci again and again https://vjudge.net/problem/HDU-1848
• [x] [HNOI2007]分裂游戏 https://www.luogu.org/problemnew/show/P3185
• [x] [ZJOI2009]染色游戏
• [x] [HAOI2015]数组游戏
• [x] [HNOI2014]江南乐
• [ ] CodeForces 494E Sharti
• [ ] CodeForces 138D World of Darkraft
• [x] [SDOI2011]黑白棋
• [ ] CodeForces 457F An easy problem about trees
• [x] UOJ #26. [IOI2014]Game
• [x] [BZOJ4730]Alice和Bob又在玩游戏
• [x] [HEOI2014]人人尽说江南好
• [ ] CodeForces 731E Funny Game
• [x] CodeForces 794E Choosing Carrot
• [x] AGC010 -ABCDEF（一整场全是博弈）
• [x] AGC005 -E
• [x] HDU3595 GG and MM
• [x] JSOI2009 游戏
• [x] BZOJ1299 巧克力棒