这是威佐夫博弈(Wythoff Game)
有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
这种规则下游戏是颇为复杂的。我们用(a[k],b[k])(a[k] ≤ b[k] ,k=0,1,2,...,n)表示两堆物品的数量并称其为局势。
策略类游戏技巧:
我们在玩策略类游戏的时候,经常会想象自己是一个纵横古今中外的指挥官,可以对建设和发展文明;或者,运筹帷幄之中,决胜千里之外,和各种各样可怕的怪物、敌人作战。
当结束游戏后,回想起来,往往会发现大量的时间在不知不觉中流逝了。每次本想着最后再玩一个回合,但是不知不觉就到第二天早上了,玩过《文明》的玩家应该都有这种体验。
我找到一个很类似的题,方法是一样的:
有一堆石子,小张和小刘两人玩取石子游戏,两人轮流取,轮到自己取的时候,可以取1颗、3颗或4颗,谁取到最后一颗谁赢。第一局一开始只有1颗石子,以后每一局开始的石子颗数都比上一局多1颗,总共玩了76局。第一局小张先取,第二局小刘先取……两个人轮流先取。现在假设小张和小刘都是足够聪明的人,都会选择最优的策略,小张一共赢了多少局?(2007年北京奥数网思维能力测试题)
分析与解答 先从比较简单的石子数讨论,找出输赢的规律。
若石子数是1,3或4,则先取者可以全取走,从而先取者赢。
若石子数是2,则先取者只能取1颗,后取者取剩下的1颗,从而后取者赢。
若石子数是5,6,则先取者可以分别取3颗、4颗,后取者只能取1颗,先取者再取剩下的1颗,从而先取者赢。
若石子数是7,则先取者取后可能剩下6颗、4颗或3颗。根据上面的结论,可推得都是后取者赢。
若石子数是8,10,11,则先取者可以分别先取1颗、3颗和4颗,给后取者留下7颗,从而先取者赢。
若石子数是9,则先取者取后可能剩下8颗、6颗或5颗。根据上面的结论,可推得都是后取者赢。
若石子数是12,13,则先取者分别取3颗、4颗,给后取者留下9颗,从而先取者赢。
若石子数是14,先取者取后可能剩下13颗、11颗或10颗。根据上面的结论,可推得都是后取者赢。
这样推算下去,我们发现,当石子数被7整除或被7除余2时,后取者赢,否则先取者赢。
所以,他们都足够聪明,都会选择最优的策略,先取就能赢,所以是20局
石子数已知先取先赢,为20局。
石子数未知,因为是轮流取,所以每个人的最优策略都是让自己取最后一颗石子,在开始时就会计算石子的重量,第一局赢的概率是1/2(不知道石子数),第一局赢,下局别人会跟到这样开始,赢20局
第一局输,第二局赢,为20局,第一局输,第二局输,赢的是(40-2)/2=19局。
20局
都是20局哦