首先来说博弈论的具有的共性:奇异局势(必败态),非奇异局势(必胜态);

奇异局势:是指任何一个人面对这种局势,最后都会失败。(只要对手一直是正确操作);

非奇异局势:是指任何一个人面对这种局势,最后都会成功。(只要自己一直都是正确操作);

为了方便理解,我用必败态和必胜态来代替:

1.对必胜态的正确操作,会使对手面对失败态;

2.对必败态的任意操作,都会使对手面对必胜态;

3.不同的必胜态存在一些相同之处(同样的,不同的失败态也存在一些共性)。

4.如果有甲乙两人,如果甲一开始面对的是必胜态,那么甲在这个过程一直面对的都是必胜态,

    乙一直面对的是失败态。(反之亦然);

5.博弈论题的关键是推出不同必胜态的相同之处。


接下来我会用三种博弈来讲解上面几条原则:

——————————————————————————————————————————

1.巴什博奕(Bash Game):

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

规定当前物品的数量x为状态s(x);

显然s(0)是必败态(而且是最后一个失败态),任何人面对这种状态一定会输。

那么易得从s(1)~s(m)都是必胜态,因为对这些状态的正确操作都会使对手面对状态s(0),也就是必败态

,离s(0)最近的必败态应该是s(m+1),因为对这种状态的任意的合法操作都会使对手面对状态s(1)~s(m),

也就是必胜态。


所以能推出s(k * (m+1) + r) 是必胜态,因为这种状态正确操作(也就是取出r个物品)都会使对手面临

s(k * (m+1))这种状态(必败态)。而对s(k*(m+1)) 的任意操作都会使对手面临s((k-1) * (m+1) + r1)

这种状态(必胜态)。只要一直保持这样的操作,那么一直面临必败态的那个人倒数第二次面临的必败态是

s(m+1),与我们之前的推论相符。 (其中1<=r,r1<=m);

s(k*(m+1) + r)就是必胜态的共同之处,(在这里可以叫做必胜态的通式)。



2.威佐夫博奕(Wythoff Game)

有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

规定当前两堆物品的数量 a,b 为状态 s(a , b);

显然s(0,0)是必败态。

那么离s(0,0)最近的几个必败态分别是:

s(1,2)  s(3,5)  s(4,7) s(6,10)  s(8,13)  s(9,15)  s(11,18);

观察可以得到必败态的一些共同之处,设必败态为(ai,bi), 0<=i;

1.ai是前面没有出现过的最小自然数;

2.bi = ai + i;

我们可以得到一个公式来求出必败态;

我们设当前状态为(ai,bi),    a > b;

当且仅当 ai = [i *  (1 + √5) /2], ai = bi + i时,(ai , bi)就是必败态;([a]表示对a向下取整)


3.尼姆博奕(Nimm Game):

有n堆石子,每次你能取一堆中的1个至a[i]个,两人轮流取,谁取走最后一颗谁赢问你必胜策略。

        1.假设我们有1堆,那么一定是必胜态;


        2.假设我们有2堆,那么当且仅当a==b时,一定是必败态。因为无论先手怎么取,那么后手就在先手对称的地方怎么

           取,那么一定是先手必败;所以必胜态是a!=b的时候;


        3.假设我们有3堆,那么我们设当前状态为(a,b,c),那么显然(a,a,*)是必胜态,因为可以取出第三堆,让后手面

           临必败态。那么也能推导出来(1,2,3)是必败态,因为无论怎么移动,他都只能到达前面提到过的必胜态。那么之

           后的必败态有(1,4,5),(2,4,6).........。

           假设存在一个函数,SG(a,b,c),该函数表示状态为a,b,c的局面,如果当前局面为必胜态的话,那么SG(a,b,c)为1,

           若当前局面为必败态的话,那么SG(a,b,c)为0。

           如果当前状态为必败态,那么SG(a,b,c) = 0;那么无论经过怎么样的的操作,都会使当前局面变为必胜态;

           也就是存在三个任意的值a1,b1,c1(a1<=a,b1<=b,c1<=c),使得SG(a-a1,b,c), SG(a,b-b1,c), SG(a,b,c-c1)都等于1;

           如果当前状态为必胜态,那么SG(a,b,c) = 1;那么经过特定的操作,会使当前局面变为必败态;也就是存在至少一个

           值k,使得SG(a-k,b,c),SG(a,b-k,c),SG(a,b,c-k)中至少存在一个等于0的值;


        4.假设我们有n堆,我们有一个结论。假设当前状态为(a1,a2,a3,a4,......an),当且仅当a1^a2^a3^a4^..^an= 0,时,那

           当前局面一定是必败态。如果a^b^c^d^e^f^...^n !=0,那么当前局面一定时必胜态。

           这个结论是经过数学家推导出来的,至于是怎么推导的,我们并不知道。但是我们可以通过SG函数来证明这个

           结论正确。

                (1). 如果存在某个局面,使得SG(a1,a2,a3,...an) = 1,此时a1^a2^a3^...^an != k (k!=0)。我们假定k的二进制

                      一共有p位,那么对于a1^a2^a3^...^an != k (k!=0),一定存在至少一个ai, ai的二进制的第p位一定是1。

                      这时ai^p < ai一定成立, 那么a1^a2^a3^a4^..(ai^p)^..^an = 0。

                (2).如果存在某个局面,使得SG(a1,a2,a3,...an) = 0,此时a1^a2^a3^...^an = k (k=0)。一定存在任意一个值ai,

                    使得a1^a2^a3^...^ai^....^an!=0; 

            注:红字加粗部分与二进制运算有关系,^是异或运算符;他会比较两个数在二进制下每位的二进制数,得出来也

                   是二进制数,遵循的规则是相同为0,相异为1;

                   异或在特定的场景有特定的作用,下面是异或的一些总结

                   1.任何数异或本身一定等于0;

                   2.任何数异或不等于本身的数一定是非0的

                   3.a^b = c,那么a^b^d = c ^d;

                   4.根据以上可以得出若存在a^b^c^d^...^n = k (k!=0),那么a^b^c^d^...^n^k = k^k =0;