有趣的组合博弈(1):取石子遊戲

admin

在一個無聊的下战書，小朋侪Alice和Bob一块兒相约在街边牙痛消炎藥,的公园顽耍。已厌倦了秋千、滑梯、跷跷板的他們别開生面地想到了一個新的遊戲。他們從公园的地上抓起一把石子，然後從Alice起頭，轮番從石子堆中取走石子。每次，每小我可以取走起码1個、至多3個石子，终极谁把最後一颗石子取走，谁就得到了遊戲的成功。

比方，一起頭一共有7颗石子。Alice拿走1颗，Bob拿走3颗，Alice再拿走2颗，Bob再拿走最後的1颗，那末Bob就得到了遊戲的成功。固然，Alice也能够在她第二次取石子的時辰把残剩的3颗全数拿走，如许Alice就得到了遊戲的成功。

Alice很想晓得在本身先取石子的环境下，有無一種遊戲计谋可以确保本身获胜呢？

上边的場景简略描写了咱們開启本系列文章的第一個會商工具：【取石子遊戲】。聪慧的讀者們，或小時辰多几多少接触過各類奥数的讀者們，必定已靠“努目法”看出了問题的谜底：在Alice和Bob都尽頭聪慧、永久都采纳最優於本身的计谋的條件下，若是這一堆石子的個数是4的倍数，那末Alice没法获胜，換句隔離霜,话说就是Bob有必胜计谋；不然，Alice具有必胜的计谋。

计谋详细的履行進程也很是简略：若是石子的個数不是4的倍数，那末石子個数除以4的余数必定是1或2或3。不管是哪種环境，Alice均可以拿走對應個数的石子，使得残剩的石子数刚好是4的倍数。尔後，若是Bob拿走K颗石子，新店汽車借款 ,那末Alice就拿走4-K颗石子（由於K只多是一、二、3中的一個，以是4-K也必定是一、二、3中的一個，如许的操作必定是被容许的、可行的，或说“正當”的）。如斯举行下去，Alice可以始终包管本身取完石子以後残剩石子的個数必定是4的倍数，同時包管Bob取完石子以後残剩的石子個数不是4的倍数。因為0也是4的倍数，以是Alice可以包管“取完最後一颗石子”，即“取完石子後残剩石子数為0”這一环境必定產生在本身身上，是以Alice便可以确保本身的成功。

反之，若是石子的個数是4的倍数，那末Alice和Bob的職位地方就反轉了。Alice取完石子後残剩石子的個数必定不是4的倍数，對付Bob来讲正相反。是以，這類环境下，Bob势必得到遊戲的成功。

從上边的阐發可以看出，若是Alice和Bob都足够的聪慧，那末這個遊戲的成果其其實一起頭就已注定了。石子個数是不是為4的倍数决议了Alice和Bob谁将得到遊戲的成功，是以在大白了上边先容的最優计谋以後，遊戲實在已没有真正举行的需要了，由於遊戲的進程中已再也不有任何牵挂，遊戲势必走向注定好的终局。

從取石子遊戲這個活泼的例子，可以引出咱們想要探究的更一般的一類問题：组合博弈遊戲。按照维基百科的界说，取石子遊戲属於如许的一類（無偏）组合博弈遊戲：

合适以上界说的遊戲便可以称為無偏组合博弈遊戲。前边先容的取石子就合适以上所有前提（讀者可以自行测驗考试一一举行查抄）。咱們在平常糊口中可以或许接触到的不少遊戲現實上很靠近無偏组合博弈遊戲。好比围棋，它违背了“無偏性”，由於两名棋手利用的棋子分歧。再好比井字棋（Tic-tac-toe），它违背了“泡腳包,有限步內终止且有独一赢家”，由於井字棋是存在平手的。這些遊戲固然其實不是严酷的無偏组合博弈遊戲，但在一些場景下可以借用無偏组合博弈遊戲的一些理论来举行钻研。

井字棋（Tic-tac-toe）

為了辅助理解，再举一些和界说不同比力大的例子。好比麻将，就是典范的不合适“彻底信息”的遊戲。好比绝大部門的電子遊戲，都不合适“無随機举措”。它們就不在咱們本文的會商范畴以內了。

為了便利表述，後文中，咱們将“無偏组合博弈遊戲”简称為“组合博弈”。

组合博弈的界说中包括“在有限步举措以後依照法则遊戲势必终止，此時有独一的一方成為赢家”。既然有限步举措後遊戲势必终止，那末所有可能呈現在遊戲中的場面地步也是有限的。咱們把每種場面地步称為遊戲的一個“状况”。又由於在组合博弈中没有随機举措，以是在一個状况下采纳一個举措，必定肯定地轉移到另外一個状况上。综上所述，咱們可以将所有可能的状况都罗列出来，而且把状况之間的轉移瓜葛也画出来，如许便可以获得一個状况轉移圖。

仍是以Alice和Bob玩的取石子遊戲為例。在這個简略的例子里，遊戲的状况明显可以用残剩石子的個数暗示：

假如最初有7颗石子

取走最後一颗石子的人获胜，這等價於，當一小我面临残剩0颗石子的時辰這小我就失败了，由於這象征着敌手方才取走了最後一颗石子。是以，状况0（残剩0颗石子的状况的简称，後文都用這個表达方法）是全部遊戲的终止状况，且它是一個必败状况。咱們用L来暗示必败状况，在圖顶用赤色标注：

赤色暗示必败状况（L）

按照遊戲的法则，咱們可以画出所有的状况轉移。好比，状况7可以轉移到状况六、状况5和状况4。其它状况也是雷同的：

箭頭比力多比力乱，可是轉移瓜葛理當是不難理解的

若是從一個状况P經由過程某種操作可以轉移到另外一個状况Q的话，那末咱們称状况Q是状况P的一個後继状况，简称為後继。

從状况轉移圖中可以發明，因為状况0是状况一、状况二、状况3的後继，是以在這3個状况下玩家可以經由過程一步操作直接把状况轉移到必败的状况0，從而把状况0這個必败状况留给敌手，使本身获胜。是以，這3個状况其實是必胜状况。咱們用W来暗示必胜状况，在圖顶用绿色标注：

绿色暗示必胜状况（W）

在得悉状况一、状况二、状况3都是必胜状况以後，咱們可以進一步阐發获得，状况4是必败状况。由於，状况4的3個後继都是必胜状况，是以在状况4下，不管玩家若何操作，城市留给敌手一個必胜状况，是以敌手必胜，本身必败：

從上述的推导進程中，可以总结出如下两條结论：

寄托以上两條结论，咱們可以一步一阵势举行推导，终极获得每一個状况是必胜的仍是必败的：

瘦身飲品,至此，咱們就完成為了取石子遊戲的状况轉移圖，而且计较获得了每一個状况是必胜的仍是必败的。终极的结论和本文一起頭經由過程“努目法”获得的结论是同样的（這是必定的）。可是比拟於“努目法”，状况轉移圖给了咱們一種更通用的解题法子。對付其它更普适、更繁杂的問题，咱們极可能没法經由過程“努目法”解决，可是必定可以經由過程状况轉移圖解决。這是由於，因為無偏组合博弈遊戲一定在有限步內竣事，是以状况轉移圖必定是一個有向無环圖（DAG）。咱們操纵上述两條法则，從DAG的最下流举行渐渐反推，必定可以将全部圖中的所有状况的输赢性全数推导得出。

這一结论也阐明：在两边玩家都永久采纳最優计谋的环境下，组合博弈的输赢從一起頭就注定了。若是初始状况是一個必胜状况，那末先手玩家（Alice）必胜，不然背工玩家（Bob）必胜。這也呼應了咱們前文會商取石子遊戲時获得的结论。

咱們上边的阐發中，實在隐含了一個假如：“将状况轉移至终止状况的玩家获胜”（等價於“處於终止状况的玩家失败”）。好比在取石子遊戲中，取走最後一個石子的玩家获胜。若是這個前提反轉，即 将状况轉移至终止状况的玩家失败 / 取走最後一個石子的玩家失败，那末咱們面临的将會是一類彻底分歧的問题。

本文，和本系列後续的其它文章，咱們默许终止状况=失败状况。對付另外一類問题，咱們暂且不做先容。

咱們從一個简略的取石子遊戲动身，先容了组合博弈的根基观點，然後先容了若何從状况轉移圖得到全部遊戲中所有状况的输赢性。這套法子是通用的，可以解决所有（带有上一末节提到的隐含前提的）组合博弈問题。可是，這仅限於理论上的可行，在現實利用的時辰會碰到一個庞大的問题。若是一個组合博弈遊戲比力繁杂，可能呈現的状况很是多，那末罗列所有可能的状况就是不确切際的，把所有状况轉移瓜葛都罗列出来更是不成能的。

以围棋為例（虽然围棋不是一個很严酷的無偏组合博弈遊戲），围棋棋盘一共有19*19=361個點位，每一個點位有空缺、安排黑棋、安排白棋三種可能的状况，是以理论上的全局状况数是3^361個。固然此中有一些状况是不成能呈現的，可是可能状况的数目依然是组合爆炸的，這使得經由過程状况轉移圖来计较获得状况的输赢性是不成行的。

有無甚麼法子可以欠亨過最原始的罗列和遍历状况轉移圖来计较状况的输赢性呢？荣幸的是，存在一些数學东西可以帮忙咱們大大削减计较量，使得一些本来不成计较的問题變得可以计较。咱們鄙人一篇文章起頭先容。

感谢大師♪(･ω･)ﾉ