|
|
作者先容：冯伟，新东方超尖生規劃讲课教员，清华硕士。天下初中数學、物理、化學三項比赛一等奖，中國西部数學奥林匹克銀牌，北京市大學生数學比赛一等奖，天下大學生物理比赛一等奖，清华大學優异硕士结業生。
有如许一個遊戲，估量大師小時辰都曾玩過：
這個遊戲的名字，叫尼姆（Nim）遊戲。
這是一個十分古老的遊戲，十六世纪初在欧洲已有關於此遊戲的記录，遊戲發源已不成考 (有说發源於中國民間)。法则很简略，不外想赢却其實不轻易。1940年纽约世界展览會上曾展出過一台尼姆機，這称得上是世界上第一台電子遊戲機，旅客可以同呆板一较高低，但是胜者却百里挑一。
下面咱們就来钻研這個遊戲。
如斯“跟從计谋”可以包管背工总能拿走最後一颗石子而取胜，咱們称這類先手必败的場合排場為必败局。所有石子都取光的場合排場称為零局。零局時無子可取而必败，故也是必败局。
若是两堆石子数目纷歧样，则先手可以經由過程在数目多的那堆取子使两堆数目同样，继而在背工取子後采纳“跟從计谋”包管成功，故两堆石子数目纷歧样的開局為必胜局。
從上表咱們發明彷佛大部門第三堆石子数是前两堆石子数之和。
因而，咱們可以創建一個以下的一個映照表，横行和竖行的表頭别離代表此中两堆石子的数目，它們交织的處所则是使之成為必败局的第三堆的石子数。
咱們如今換個角度思虑一下。
咱們认為這類“均衡”的開局上風相互抵消。
有了場面地步比力這類思惟以後，咱們無妨参照物理中對势能的處置，劃定一個势能零點作為基准，很轻易想到咱們可以令零局[0]的場面地步值為0，而場合排水位控制器,場[1]比零局[]0有一個子的上風，因而[1]的場面地步值為1。
也就是说對付場面地步值分歧的两個遊戲局，先手可以每次從場面地步值高的石子堆中取石子，把它的場面地步值降至和另外一個遊戲局的場面地步不异，使两者場面地步到达均衡，而背工拿子後會粉碎這類均衡，因為终极的零局可以看作[0]+[0]的均衡状况，是以對付場面地步值分歧的两個遊戲局老是必胜局。
反之對付場面地步值不异的两個遊戲局，先手总會粉碎這類均衡，而背工會使之規复到均衡状况，因此這類場合排場為必败局。
咱們将這類思惟扩大到n=3来尝尝。
究竟是不是如许呢？咱們来驗证一下。
既然對付一個含两堆石子的遊戲局，咱們可以找到一個場面地步值不异的只含一堆石子的遊戲局與之均衡，而每種場合排場中肆意两堆石子是互相自力的（由於一次只能從此中一堆取石子），如许咱們便可以把两堆石子用一堆“等價”的石子更換掉而不影响遊戲成果！
有了“等價代換”這一思惟利器，再连系上表，咱們欣喜的發明如今已可以處置堆数n比力大的尼姆遊戲了。
由於咱們不竭的举行這類等價代換，就可以将堆数终极削减到1，而對付堆数為1的遊戲場合排場，只有零局是必败局，其他任何場面地步值大於0的場合排場都是必胜局。
不管若何拆分，咱們都获得了不异的成果，這也阐明了咱們“等價代換”的准确性。
“等價代換”不但可以正着用，還可以反着用，也就是说咱們可以把一堆石子用两堆乃至多堆石子更換掉。這可以帮忙咱們考查映照瓜葛。
同窗們可能看出来了，這現實上就是操纵数的二進制暗示，并消去不异位数上的数字。這類运算操作叫异或运算。
固然仅果断出胜负是不敷的，咱們得要還原豐胸產品,出可以或许获胜的详细计谋才行。那遊戲中應當怎样玩呢？
咱們只需看哪一堆和12异或操作以後比原堆石子数小便可，而這是总能辦到的 （缘由可見下节）。
如斯来去，因為石子数老是削减的，终极必定遏制在場面地步值為0的零局，而這一均衡状况只能由先手完成，因而终极能取告捷利。
對付場面地步值為0的必败局，则要末让對方先走，要末只能瞻仰敌手出错，以後用一样的法子来克服對方了。
到這里咱們根基可以完胜没有履历的敌手了。
不外用到的法子没有举行周密的证實，學霸們必定不會止步於此，為了知足列位的需求，下面咱們把理论和相干的证實写出来，给讀者們参考。
理论與证實
尼姆遊戲的完备计谋是1901年由Charles L. Bouton初次论述的。值得一提的是 Nim 這個名字也是由他给出的。
下面给出破解 Nim 遊戲秘密的 Bouton 定理 (Bouton's Theorem)：
证毕。
尼姆遊戲，是组合博弈理论中的最根基的也是最首要的一個模子，他属於無偏博弈（Impartial Games）。
限於篇幅今天就讲到這里，在後续的文章中我會继续给同窗們先容组合博弈中的小遊戲和相干理论。
你學會了嗎？快去找小火伴們PK吧！
作者先容：冯伟，新东方超尖生規劃讲课教员，清华硕士。天下初中数學、物理、化學三項比赛一等奖，中國西部数學奥林匹克銀牌，北京市大學生数學比赛一等奖，天下大學生物理比赛一等奖，清华大學優异硕士结業生。新东方伶俐書院（zhihuixuetang_xdf），與精英為伍，成绩将来精英。 |
|
發表於 2023-8-23 16:19:40
收藏