之前其实也只会自己能推出来的博弈论题,都是最简单的那种,然后遇到难的就惨败

来总结一下一些常见的简单博弈的特征及其解决算法


巴什博弈

特征

一堆物品有n个,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个。最后取光者得胜。

引申的还有其它的表述方法,类似于两人操控一个棋子轮流走一段长度,到最后位置的人输或者赢之类的

算法

考虑第一步是不是必败态,否则必胜。证明也很简单,控制剩余石子的数量,使对方无论如何行动都达不到赢面即可

对于巴什博弈,那么我们规定,如果最后取光者输,那么又会如何呢?

n%(m+1)==0则后手胜利


推广:减法博弈

特征

巴什博弈的变形,轮流取石子,只能取给定的集合中的石子个数,取到最后一个石子的人获胜。

算法

这个就得用到动态规划了qaq

可以发现当前石子数m如果可以通过取集合中的任何一个,让m-ai变成一个P态(先手必胜态),则当前m就是N态(后手必胜态),如果不能,则m为P态。

使用dp[i]表示有i颗石子时的胜负状态,则dp[i-a[j]](a[]为集合)是之前能达到的状态,如果他们中至少有一个是必胜态,那么i是必败态,否则i时必胜态。


斐波那契博弈

特征

有一堆石子,两个顶尖聪明的人玩游戏,先取者可以取走任意多个(很明显大于1),但不能全取完,以后每人取的石子数不能超过上个人的两倍

算法

斐波那契博弈有一个非常重要的性质:

先手必败,当且仅当石子数为斐波那契数

就没有什么其他的好说了(


威佐夫博弈

特征

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

算法

这种情况下是颇为复杂的。我们用(a[k],b[k])(a[k] ≤ b[k] ,k=0,1,2,...,n)表示两堆物品的数量并称其为局势,如果甲面对(0,0),那么甲已经输了,这种局势我们称为奇异局势。前几个奇异局势是:(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)。(注:k表示奇异局势的序号, 第一个奇异局势k=0)

可以看出,a[0]=b[0]=0, a[k]是未在前面出现过的最小自然数,而 b[k]= a[k] + k

这里的奇异局势有这样三个性质:

  1. 任何自然数都包含在一个且仅有一个奇异局势中。

  2. 任意操作都可将奇异局势变为非奇异局势。

  3. 采用适当的方法,可以将非奇异局势变为奇异局势。

两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜;反之,则后拿者取胜。

那么任给一个局势(a,b),怎样判断它是不是奇异局势呢?我们有如下公式:

ak =[k*(1+√5)/2],bk= ak + k (k=0,1,2,…n 方括号表示取整函数)

(k=0,1,2,…n 方括号表示取整函数)

奇妙的是其中出现了黄金分割数(1+√5)/2 = 1.618…因此,由ak,bk组成的矩形近似为黄金矩形,由于2/(1+√5)=(√5-1)/2,可以先求出j=[a(√5-1)/2],若a=[j(1+√5)/2],那么a = aj,bj = aj + j,若不等于,那么a = aj+1,b = aj + j + 1,若都不是,那么就不是奇异局势。然后再按照上述法则进行,一定会遇到奇异局势。


尼姆博弈(nim游戏)

特征

有任意堆物品,每堆物品的个数是任意的,双方轮流从中取物品,每一次只能从一堆物品中取部分或全部物品,最少取一件,取到最后一件物品的人获胜。

而这里的物品数可以看作是每堆的最大变化次数(

算法

假设只有三堆,我们用(a,b,c)表示某种局势,首先(0,0,0)显然是必败态,无论谁面对(0,0,0) ,都必然失败;第二种必败态是(0,n,n),自己在某一堆拿走k(k ≤ n)个物品,不论k为多少,对方只要在另一堆拿走k个物品,最后自己都将面临(0,0,0)的局势,必败。仔细分析一下,(1,2,3)也是必败态,无论自己如何拿,接下来对手都可以把局势变为(0,n,n)的情形。

然后之后不知道有哪个天才把这玩意和异或(^)联系了起来,有:

任何奇异局势(a,b,c)都有a XOR b XOR c = 0

面对的是一个非必败态(a,b,c),要如何变为必败态呢?

假设 a < b < c,我们只要将 c 变为a XOR b,即可。因为有如下的运算结果:

a XOR b XOR (a XOR b)=(a XOR a) XOR (b XOR b) = 0 XOR 0 = 0

要将c 变为a XOR b,只要对 c进行 c-(a XOR b)这样的运算即可。

同样的也可以拓展到 n 堆物品,有下述结论:

Bouton定理:先手能够在非平衡尼姆博弈中取胜,而后手能够在平衡的尼姆博弈中取胜。

而平衡的尼姆博奕则为:

a XOR b XOR c XOR …= 0


推广:阶梯博弈(NimStaircase)

特征

游戏开始时有许多硬币任意分布在楼梯上,共n阶楼梯从地面由下向上编号为0到n。游戏者在每次操作时可以将楼梯j(1<=j<=n)上的任意多但至少一个硬币移动到楼梯j-1上。游戏者轮流操作,将最后一枚硬币移至地上的人获胜。

算法

阶梯博弈等效为奇数号阶梯的尼姆博弈。

假设我们是先手。我们按照尼姆博弈的原则进行第一次移动。如果对方移动奇数号阶梯的石子,我们继续按照尼姆博弈的原则移动。如果对方移动的是偶数号阶梯的石子,及对方将偶数号阶梯的石子移动到了奇数号(对奇数号产生了影响)我们就接着将对方移动到奇数号的石子再向下移动一个台阶,移动到偶数号。这就意味着在偶数号的棋子对我们的博弈是没有影响的

而为什么等效于奇数号的尼姆博弈而不是偶数号的?

这是因为如果等效于偶数号的,当后手移动奇数号的,移动到0了,就不能保证状态一致了。

所以有:

将奇数层的状态异或,如果不为0,先手必胜,否则先手必败


环形博弈

特征

n个石子围成一个环,每次可取走1个或相邻的两个,注意若两个石子之间的石子被取走,这两个石子仍然是不相邻的

算法

其实这个博弈可以看作对称博弈的特殊情况,下面在对称博弈的时候证明(

若n<=2则先手胜,否则后手胜


推广:对称博弈

特征

n个石子围成环,每次只能取相邻的一个到k个之间

算法
  1. k等于1时,一次最多只能拿1个(每堆只有一个),那就是看奇偶了。

  2. n≤k 这种情况,那肯定先拿的赢。

  3. 这条就是对称博弈了, 除了上述两种情况外的情况(n>k && k!=1)这时候,无论你第一个人拿什么,怎么拿,后手的人完全可以在第一个人拿的对称的地方做同样的事情。这样,后手就一定会取得胜利,因为最后一步是后手走的。

如果k<n:对k=1,如果n能被2整除,则后手赢;如果k>1,后手赢(先手取什么位置后手就取对称的位置,这样保证后手永远能取到);</br></br>如果k>=n:先手赢.