博弈论入门讲座

（ACM）数学----博弈论

取硬币游戏（POJ2484）

• 题意：N个硬币围成一个圈，然后两个人从这圈硬币中轮流拿1个或相邻的2个硬币。直到全部拿完为止，最后一个拿的人为胜者。
• 题解：当n==1或者n==2时，明显先手必胜。当n>=3时，先手必败。
• n为偶数时，无论先手怎么取，后手都可以取与之中心对称的那几块。
• n为奇数时，可以保证前两次取奇数个硬币使得剩下的偶数个硬币排成相等的两个链，之后每次取硬币，后手只要保证两个部分完全一样即可。

引例

• 取石子游戏：有一堆石子共n个，两人从中轮流取出一定数量，规定每次至少取一个，最多取m个，最后取光者得胜。
• 解决思路：当n=m+1时，由于一次最多只能取m个，所以无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后取者胜，所以当一方面对的局势是n%(m+1)=0时，其面临的是必败的局势。
• 这种博弈叫做巴什博弈。

博弈论解题步骤

• 1、将所有终结局势标记为必败点（0）。
• 2、将所有一步操作能进入必败点（0）的局势标记为必胜点（1）。
• 3、如果从某个点开始的所有一步操作都只能进入必胜点（1），则将该点标记为必败点（0）。
• 4、重复2、3操作直到初始局势被赋值。

具体解题步骤(以引例为例)

• 1、终结局势：无石子可取-->石子数为0个-->$f(0)=0$
• 2、一步操作能进入必败点的局势：$f(m)=f(m-1)=...=f(1)=1$
• 3、只能进入必胜点的局势：$f(m+1)=0$
• 4、...
• 当n的数据范围在可行范围内的时候，一直重复2、3步骤当然是可以的，但是很多时候博弈论的题目给出的数据范围都很大。这种时候就要靠找规律了。比如说本题的规律就是 $n\%(m+1)=0$ 的局面是必败态，否则必胜。

SG函数

• mex运算：对于一个只含非负整数的集合，选取最小的不属于这个集合的非负整数。例如 $mex\{0,1,2,4\}=3$、$mex\{2,3,5\}=0$、$mex\{\}=0$。
• 图：一种数据结构，由点集 $V$ 和边集 $E$ 组成。如果边有带方向，称为有向图，否则称为无向图。
  
• 有向图中的环：从某个结点出发，沿着边箭头指向的方向走，能回到原来位置，则称这张图有环。例如上图(a)中的 a->e->d->a 。
• 有向无环图：顾名思义，边带方向，图中不包含环。
• SG函数：对于一个有向无环图，我们定义它每个点上的SG值如下：
• 1、如果一个点x没有出边，把它的SG值记为0-->$sg(x)=0$。
• 2、如果一个点x有出边，$sg(x)=mex\{sg(y)|y是x的后继\}$。

SG函数(以引例为例)

• 因为上传图片的时候出现了一点偏差，所以内容就看PPT吧...

尼姆博弈

• 问题模型：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，至多不超过该堆石子数，最后取光者得胜。
• 假设三堆石子的个数分别是a,b,c， $a\oplus b\oplus c=0$ 的局面是必败态，否则必胜。证明这里有
• 推广：当石子堆数为n堆时，则推广为当对每堆的数目进行亦或之后值为零是必败态。

尼姆博弈和SG函数的关系

• 引例：有n堆石子，每次可以从第1堆石子里取1颗、2颗或3颗，可以从第2堆石子里取奇数颗，可以从第3堆及以后石子里取任意颗。
• 分析：我们可以把它看作3个子游戏。
• 第1个子游戏只有一堆石子，每次可以取1、2、3颗，很容易看出x颗石子的局面的SG值是$x\%4$。（$g(0)=0,g(1)=1,g(2)=1,g(3)=1,g(4)=0,g(5)=2,g(6)=3,$ 以此类推）
• 第2个子游戏也只有一堆石子，每次可以取奇数颗，可以知道这个游戏有x颗石子时的SG值是$x\%2$。
• 第3个游戏有$n-2$堆石子，就是一个尼姆博弈。
• 对于原游戏的每个局面，把三个子游戏的SG值异或一下就得到了整个游戏的SG值。
• 为什么可以这样做？
• 把三个子游戏看成三堆石子。
• 对于尼姆博弈，假设石子数有$a,b,c$，我们可以在某堆石子中取任意数量x使之变成$a-x,b,c$。
• 对于上述游戏，我们可以对其中一个子游戏进行操作，使它的SG值$a$变成$a-x$。（假设$sg=k$，可以变成$k-1,k-2,...,0$）

威佐夫博弈

• 问题模型：有两堆各若干个物品，两个人轮流从某一堆拿任意数量的物品或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
• 结论：所有必败态 $(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)、...$ $(b[n]=a[n]+n，a[n]$ 取前 $n-1$ 项中， $a[n]$ 和 $b[n]$ 都没有出现过的最小正整数。)
• 通项公式： $a[n] =[n(1+sqrt5)/2]，b[n]= a[n] + n （ a[n]$取前$n-1$项中，$a[n]$和$b[n]$都没有出现过的最小正整数）。
• 证明可以百度。

斐波那契博弈

• 问题模型：
• 有一堆个数为n的石子，游戏双方轮流取石子，满足：
  （1）先手不能在第一次把所有的石子取完；
  （2）之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。约定取走最后一个石子的人为赢家。
• 结论：当n为Fibonacci数时，先手必败。
• 证明可以百度。