威佐夫博弈
规则:有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
首先,根据枚举法分析可能性情况得出规律。
当两堆石头处于以下的数量关系时,对先手者是不利的。如(0,0)(1,2)(3,5)(4,7)(6,10)…
举个例子,对于(1,2):
先手在左堆取1个得(0,2),后手取完右堆,后手胜。
先手在右堆取1个得(1,1),后手两堆同取1个,取完,后手胜。
先手在右堆取2个得(1,0),后手取一个,后手胜。
对于(3,5)的情况:
A左取1,(2,5),B右取4,(2,1),A面对此情况必输,后手胜。
A左取2,(1,5),B右取3,(1,2),A必输,后手胜。
A左取3,后手胜。
A右取1,(3,4),B同时取2,(1,2),后手胜。
A右取2,(3,3),后手胜。
A右取3,(3,2),B左取2,(1,2),后手胜。
A右取4,(3,1),B左取1,(2,1),后胜。
A右取5,后手胜。
可以发现,若B总是采取对他最有利的策略,则A面对(3,5)的情况是必输的。(这里留下一个问题,如果B不总是智商在线,那么A有没有翻盘的可能?)
推广到任意自然数:
若两堆石头个数为(a,b)规定a≤b。
a=k*(1+√5)/2 并向下取整 (其中(1+√5)/2为黄金比例)
b=a+k (k为自然数)
(a,b)此时面对此情况的选手为必输,即尽量避免自己面对此情况,并尽移动自己的石头使得对手得到这样的场景,称这样的场景为奇异局势。
奇异局势的性质:
1.对于任意一个数,都一定会是奇异局势中的一个,但是不一定是小的那个还是大的那个。
2.任何自然数都包含在一个且仅有一个奇异局势中。
3. 任意操作都可将奇异局势变为非奇异局势。
4. 采用适当的方法,可以将非奇异局势变为奇异局势。
如何判断自己的局势是否是奇异局势呢?
先将石头数排列成左小右大的情况,并设左边石头数为a,右边为b。
1,计算k=b-a
2,计算a1与b1。a1=k*(1+√5)/2 并向下取整,b1=a1+k
3,若a=a1并且b=b1,则当前局面是奇异局势
如何在自己的回合将局面转换成奇异局势呢?
排列石头左小右大,用(a,b)表示;设某奇异局势石头数为(ak,bk),(aj,bj)。
1,若两堆相等,则同时取走a(b)数量的石头,形成(0,0)的奇异局势。
2,若a=ak,b>bk,则右堆取b-bk个石头
3,若a=ak,b<bk,由于不同奇异局势的差值k都是唯一的,所以计算k=b-a,再两边同时拿去k个石头。
4,若a>ak,b=bk,则左取a-ak个。
5,若a<ak,b=bk,分两种情况(此时不能和3一样,因为左边的石头可能不够减)
(1)a=aj(即左边能构成奇异对的左边部分,只要使得b也凑成奇异对即可),计算k=a/((1+√5)/2 ),右边拿去k个石子。
(2)a=bj(a能构成奇异对的大的那个数,只要使得b凑成奇异对的小的那个数即可),计算k,联立a1和b1的计算式可得,bj-k= k*(1+√5)/2 ,bj=k*(1+ (1+√5)/2) ,k=bj/(1+ (1+√5)/2),随后右边拿k个石头。