简单博弈论

开头部分摘自别人博客，并稍作补充。SG以后再补

寻找平衡状态（也称必败态， 奇异局势），（满足：任意非平衡态经过一次操作可以变为平衡态）

(一)巴什博奕(Bash Game):

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

n = (m+1)r+s , (r为任意自然数,s≤m), 即n%(m+1) != 0, 则先取者肯定获胜

(二)威佐夫博奕(Wythoff Game):

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

(ak,bk)(ak ≤ bk ,k=0,1,2,...,n)表示奇异局势

性质1：任何自然数都包含在一个且仅有一个奇异局势中。
性质2：任意操作都可将奇异局势变为非奇异局势。
性质3：

一定存在规则允许的某种操作可将必胜点（非奇异）移动到必败点（奇异）；

求法：

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

判断：

Gold=(1+sqrt(5.0))/2.0；

1）假设（a，b）为第k种奇异局势(k=0,1,2...) 那么k=b-a;

2）判断其a==(int)(k*Gold),相等则为奇异局势

（

局势（Ak,Bk） 奇异局势特征：Ak =[k（1+√5）/2]，Bk= Ak + k （k=0，1，2，...n 方括号表示取整函数)

结论：Bk - Ak = k; if(Ak == [k * (1 +

√5

) / 2]) ->奇异局势。）

（注：采用适当的方法,可以将非奇异局势变为奇异局势.

假设面对的局势是(a,b) 若 b = a,则同时从两堆中取走 a 个物体,就变为了奇异局势(0,0)；

1. 如果a = ak,

1.1 b > bk, 那么,取走b - bk个物体,即变为奇异局势(ak, bk)；

1.2 b < bk 则同时从两堆中拿走 ak a[b ak]个物体,变为奇异局势( a[b ak] , a[b ak]+ b - ak)；

2 如果a = bk ,

2.1 b > ak ,则从第二堆中拿走多余的数量b ak

2.2 b < ak ,则 若b = aj (j < k) 从第一堆中拿走多余的数量a bj; (a > bj)

若b = bj (j < k) 从第一堆中拿走多余的数量a aj; ( a > aj)

）

例题：pku 1067

(三)尼姆博奕(Nimm Game):

有n堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜.

任何奇异局势(a1, a2, … , an)都有a1(+)a2(+)…(+)an =0. ( (+)为 按位^)

引入 局势 (X1,X2,X3Xn)的Nim-Sum = X1^X2^X3^Xn; 任何奇异局势都有Nim-SUm = 0。