博弈

数学

作业部落

评论地址

前言

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

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

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$
通过下图来理解（QAQ之前画错了，更严谨证明请见贾志豪的论文）

8.Multi-SG

问题：
结论：

9.Every-SG

问题：
结论：

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

• [HDU1527]取石子游戏 https://vjudge.net/problem/HDU-1527 （威佐夫博弈）
• [BJWC2009]取石子游戏 https://www.lydsy.com/JudgeOnline/problem.php?id=1874
• [ZJOI2009]取石子游戏 https://www.luogu.org/problemnew/show/P2599
• [luogu2252]取石子游戏 https://www.luogu.org/problemnew/show/P2252（威佐夫博弈）
• [HNOI2010]取石头游戏 https://www.luogu.org/problemnew/show/P3210
• [luogu4136]谁能赢呢 https://www.luogu.org/problemnew/show/P4136
• [SDOI2009]E&D https://www.luogu.org/problemnew/show/P2148
• [BZOJ4550]小奇的博弈 https://www.lydsy.com/JudgeOnline/problem.php?id=4550
• [SHOI2008]小约翰的游戏 https://www.luogu.org/problemnew/show/P4279（Anti-Nim）
• [POJ3537]Crosses and Crosses
• [HDU1848]Fibonacci again and again https://vjudge.net/problem/HDU-1848
• [POI2000]条纹 （权限题BZOJ2940）
• [HNOI2007]分裂游戏 https://www.luogu.org/problemnew/show/P3185
• [ZJOI2009]染色游戏
• [HAOI2015]数组游戏
• [HNOI2014]江南乐
• CodeForces 494E Sharti
• CodeForces 138D World of Darkraft
• [SDOI2011]黑白棋
• CodeForces 457F An easy problem about trees
• UOJ #26. [IOI2014]Game
• [BZOJP4730]Alice和Bob又在玩游戏
• HDU P5996 dingyeye loves stone
• [HEOI2014]人人尽说江南好
• CodeForces 731E Funny Game
• CodeForces 794E Choosing Carrot