[转]可怕的先手优势

我要吃章鱼丸子

可怕的先手优势
  作者：  来源：网络转载  查看：69  评论：0






      两者对抗的游戏，一般先手占有优势，这很容易理解。但是如果先手完后，让对手选择最后那结果算输还是算赢，估计一般形势立马逆转了，这差不多相当于后手变先手了，这也很容易理解。

      最近看到一个原来研究过的游戏，没有想到的是输赢条件改变后，先手决策策略竟然基本上不变化。这就形成一个可怕的先手优势，那就是先手过后，可以让后手选择最后说定的条件算输还是算赢都稳操胜券。

新孔融让梨故事 新孔融让梨故事

      可怕的先手优势，大多数情况下，先手可以得到非全1的异或=0状态，然后多少步里让对手选择拿到最后一个算输还是算赢，自己都稳操胜券。

      取苹果游戏（新孔融让梨故事）
http://www.mysanco.com/wenda/ind ... d=6236&isSend=1

      有三堆苹果，分别为三只、四只、五只，两小朋友轮流取走苹果，取法规则为：每次都可以任选一堆取走苹果，可取走该堆的部分或全部苹果；经几轮拿取后，给对方留下最后一个苹果的小朋友胜出？问先取必胜的方法？（须有让小朋友听得懂的详细解答过程）

      通解不限定堆数，甚至还可以不拿把自己手里的往哪一堆里面放任意大于0个，但如果手里没有就只能拿了。

      见到原来的题目是谁拿到最后一个，就是拿了就没有了算赢。很简单，学过计算机很容易搞定，必胜态就是所有数据异或结果=0。这个是大约二十年前高中时候解出来的结果，这个证明比较简单。0是必胜态，必胜态任意操作后都变为非必胜态，任意非必胜态可以有一个操作变为必胜态，而必胜态的操作者始终在拿，最终有限步后必定达到0这个必胜态。

第一种拿完算赢，第一种是所有数字异或=0为必胜态。

      第二种拿完剩一个算赢，因为0不影响结果把数字0全部排除。第二种排除全为1的情况，所有数字异或=0为必胜态，全1的情况是相反奇数个1为必胜态。

      第二种证明也很简单，全是1的情况下很简单证明奇数个1是必胜态。第一种里除去全1的情况，只需要证明第一种的必胜态如果要进入全1，总可以改变一下最后一步策略，使得能拿完后变为奇数个1的必胜态就可以了。

      因为第一种最后一步要进入全1，只能是偶数个1。
如果是进入0个1就是（0，0），由非全1状况进入只能由（n,n)n>=2进入，这时候对方是拿后变（0，n)，只需要把自己拿后成（0，0）改变为拿后成（0，1）的必胜态就可以。
如果最后一步是进入大于等于2个的全1，只需要自己最后拿那一步变为再多拿一个，就进入奇数个1的必胜态。

      比较搞的是不管拿到最后一个算输还是算赢，一般非全1情况异或=0的状态都是必胜态，这种状态比较特殊呀。
      可怕的先手优势，大多数情况下，先手可以得到异或=0的状态，然后多少步里让对手选择拿到最后一个算输还是算赢，自己都稳操胜券。

      因为和苹果堆个数顺序无关，都是小数在前更美观，必胜态有：
（0，0，1），（1，1，1），
（0，2，2），（0，3，3），（0，4，4），
（1，2，3），（1，4，5）
      看看这些必胜态，不管你怎么拿都能再一步操作达到毕生态，两个必胜态也没有一步能到的操作。
      证明也很简单，从后面（1，4，5）开始尝试任意一种拿法，都能有对应的回到前面的必胜态的拿法。只要挨着往前证明完就证明好了。