博弈游戲中的數學必勝策略

女士們，先生們，老少爺們兒們！在下張大少。

數學家們熱愛游戲。他們不僅能在看似忙于工作的同時享受樂趣，而且即使是最簡單的游戲也可能需要巧妙的戰術和策略才能獲勝。這類問題正是用數學來解決的理想對象。

數學的一個分支，稱為組合博弈論，大約在30年前發展起來，專門用于分析游戲。它提供了一種將游戲分解為更易于研究的較小部分的方法，然后利用一種特殊的代數將這些子游戲的值相加。如果說數學家們擅長一件事，那就是計數。

組合博弈論

盡管組合博弈論（CGT）功能強大，但它僅適用于滿足某些條件的游戲。最重要的條件是：游戲有兩名玩家，雙方對游戲狀態擁有完全信息，不存在隨機因素（如擲骰子或洗牌），并且雙方輪流行動（不允許跳過回合），最終無法行動的一方輸掉游戲。因此，雙陸棋、撲克、海戰棋、大富翁和紙牌接龍等游戲無法用CGT來分析，因為它們在各種不同組合上不滿足這些標準。

能夠應用CGT的游戲都具有相同的本質：你通過確保自己能比對手多走至少一步來獲勝。這類游戲的經典例子是我們小時候都玩過的，那就是……

《棋手》，作者：托馬斯·埃金斯

二十一（取物游戲）

先回憶一下玩法，二十一游戲的玩法是：在兩個參賽者之間放一堆共21枚硬幣（或火柴棍，或其他任何小物件）。玩家輪流從堆中取走1枚、2枚或3枚硬幣，目標是取走最后一枚硬幣，從而讓對手無法繼續行動而輸掉游戲。

事實證明，二十一是一個“先手必勝”的游戲——無論第二名玩家玩得多么好，先手玩家都擁有一種無解的策略。如果你先開始，你可以確保在對手回合時恰好剩下四枚硬幣。對手最多能拿走其中三枚，然后你就可以取走剩下的硬幣從而獲勝。

研究組合博弈論的數學家花了大量時間分析一個與二十一非常相似的游戲，叫做尼姆游戲。尼姆游戲可以用任意多堆硬幣來玩，兩名選手被允許取走一整堆，或從同一堆中取任意數量的硬幣。同樣，勝者是取走最后一堆或最后一枚硬幣、使得對手沒有硬幣剩下的人。事實上，二十一游戲是尼姆游戲的一個特例，相當于有七堆，每堆只有3枚硬幣。

尼姆游戲

事實證明，尼姆游戲非常適合用組合博弈論（CGT）進行分析。尼姆游戲的目標是確保你總能走出一步，而對手在你之前就無法繼續行動。那么，CGT所做的就是計算出雙方玩家能夠走出的最大步數，從而判斷誰擁有額外的“多余步數”。尼姆游戲是一種所謂的“impartial game”（無偏博弈），因為雙方使用相同的棋子，因此有相同的可選步數——這與國際象棋不同，國際象棋是一種“partisan game”（有偏博弈），意味著每個玩家擁有自己獨有的棋子，只有自己才能移動它們。

在尼姆游戲中，雙方玩家擁有相同數量的“額外步數”，唯一重要的是輪到誰走棋。例如，當只剩下一枚硬幣時，接下來輪到誰走誰就獲勝。第一名玩家取走最后一枚硬幣后，對手就沒有硬幣可取了，因此輸掉比賽。CGT有自己獨特的方式來描述此類局面，并有一套自己的代數來計算出博弈的值。只剩一枚硬幣的情形記作：

{ 0 | 0 } = *

由于CGT不知道下一步輪到誰，它給出的是在任意一方走棋后剩余的可走步數。花括號中的數字表示：在取走最后一枚硬幣后，左邊的玩家將沒有剩余步數，右邊的玩家也同樣如此。因為尼姆游戲是無偏博弈，中間豎線左右兩側的數字總是相同的。該博弈的值寫在等號后面。星號表示下一步走棋的一方獲勝，這被稱為模糊局面。二十一游戲從一開始就是一個模糊局面，因為先走的一方總能強行獲勝。

然而，如果剩下兩枚孤立的硬幣，那么下一步走棋的一方將會輸掉。這是因為無論左方還是右方先走，都只能留下一枚硬幣。對方取走這枚硬幣，從而贏得游戲。這種情況記作：

{1∣1}=0.

同樣，左側和右側的數字告訴我們，在任意一方走完下一步之后剩余的可走步數，在這個例子中就是1。這里的值是0，因為下一步走棋的一方將會輸掉游戲，因此“先手必敗”的局面也被稱為零局面。所有先手必敗的局面都可以簡化為游戲中沒有硬幣剩下的最終狀態：

{ ∣ }=0.

一個稍微復雜一些的局面是剩下三枚硬幣，排列為一堆兩枚和旁邊一枚孤立的硬幣。先手玩家從兩枚的那堆中取走上面一枚，第二名玩家隨后從剩下的兩枚孤立硬幣中取走一枚，然后先手玩家取走最后一枚硬幣獲勝。因此，無論左方還是右方先走，都能獲勝——這又是一個模糊局面：

{2∣2}=?.

當然，先手玩家也可以一開始就取走那枚孤立的硬幣，或者取走整堆兩枚的硬幣。這種在留下一枚或兩枚剩余步數之間的選擇，可以記為：

{1,2∣1,2}.

但在對手回合開始時，不必要地只留下一枚剩余步數是完全不理智的，因為對手會直接取走剩下的硬幣從而贏得比賽。在CGT中，這種愚蠢的選擇會被忽略，因為假定雙方都是理智地在玩，并試圖獲勝。因此：

{1,2∣1,2}={2∣2}=?.

正如第一個例子那樣，這一局面簡化為了 {0∣0}=?，即第二名玩家走完后的局面。

A possible starting setup for Nim

尼姆游戲的一種可能初始布局

尼姆游戲中的一個模糊局面

有偏博弈——國際象棋

在有偏博弈中，兩位玩家擁有的可選走法不同。此時花括號中的左側數字和右側數字不一定相同。如果左方有四步可行走法，而右方只有三步，那么左方就多出一步優勢，無論誰先走，左方都會獲勝。這種情況記為：

{4∣3}=1,

它可以簡化為

{0∣ }=1。這被稱為“正局面”，因為無論誰先走，左方都能贏。如果情況反過來，右方多出一步優勢，那么該博弈就是“負局面”（按照慣例，博弈的值總是從左方的角度給出）。

國際象棋就是這樣一種有偏博弈。既然我們理解了CGT的工作原理，就可以用它來分析棋局。不過嚴格來說，國際象棋作為一個整體并不符合CGT的分析條件。盡管雙方對棋盤上的棋子有完全的信息，并且不存在隨機因素，但CGT的應用還有一些更微妙的要求。一般而言，國際象棋的勝負并不取決于誰擁有更多的剩余步數，而是取決于誰將死對方。而CGT最適合那些“走一步通常是一種劣勢”的游戲。然而在國際象棋中，擁有下一步走棋權幾乎總是巨大的優勢。事實上，一種為了平衡強弱選手而設計的讓子方式，就是移除強手方某一匹馬前的兵，并讓弱手方在開局時連續走兩步（這種讓子方式稱為“兵加兩著”）。

國際象棋也比尼姆等游戲復雜得多，僅僅擁有比對手更多的剩余步數并不足以讓你獲勝——你仍然可能被將死。此外，國際象棋開局時棋子很多，而且關鍵是有一些非常強大的棋子，它們能在棋盤上大范圍施加影響力；例如，后最多可以攻擊18個格子。結果是，在游戲的大部分時間里，棋盤無法像尼姆中分開的幾堆硬幣那樣分解成獨立的組成部分。然而，在殘局階段，當大多數長距離棋子被兌掉之后，棋盤就可以分解為若干個子博弈。此時，下一步走棋可能不再是一種優勢，而CGT就成了分析這種局面的完美工具。

《兩位棋手肖像》，作者：奧諾雷·杜米埃

殘局中的CGT

在殘局的某些局面中，必須走棋的一方將會輸掉。這與尼姆中的零局面相同，在國際象棋中，這些特殊情況被稱為“相互逼走”。“Zugzwang”是一個德語詞，意為“被迫移動”。右圖所示的“Trébuchet”局面就是這樣一個相互逼走的例子：

{ ∣ }=0.

一個“Trébuchet”局面

雙方的小兵互相阻擋了對方的推進，因此接下來必須由某一方的王移動。然而，白王不能走到f4格，黑王也不能走到d5格，因為那樣會導致王受到對方小兵的攻擊。因此，必須先移動的王不得不從自己的小兵旁邊退開，從而無法再保護它（國際象棋規則禁止雙方的王相距一格之內）。此時對手就能吃掉這個小兵，并迫使自己的小兵前進到底線。根據規則，這個小兵可以升變為后，這一優勢被認為是決定性的，從而確保后走的一方必勝。

{ 0 | 0 } = *.

如果在棋盤上增加一些額外的棋子，就可以將這一局面轉化為一個模糊局面——先走的一方獲勝：

{0∣0}=?.

殘局中的一個模糊局面

在此局面中，先走的一方可以將自己在a線上的小兵向前推一格。此時對方的小兵被阻塞，除了移動王之外別無選擇。在這種情況下，游戲包含兩個部分：a線小兵的局面值為?，而Trébuchet局面的值為0。因此，整個游戲的總值為?。

然而，如果白方的兵是在a2格而不是a3格，那么局面的值將變為正數：{0∣ }=1。此時白兵在游戲中尚未移動過，因此它在第一步可以選擇前進一格或兩格。正是這個選擇給了白方一個多余的步數。如果黑方先走，白兵就前進一格，像之前那樣擋住黑兵。但如果輪到白方先走，白兵可以一次前進兩格直接形成阻塞，從而再次迫使黑方打破Trébuchet局面并輸掉比賽。因此，無論誰先走，白方都能獲勝。

殘局中的一個正局面

不過，上述局面仍然相對簡單。CGT真正發揮威力的時候，是當棋盤上有更多小兵，局面變得過于復雜以至于無法僅靠觀察來輕易分析時。例如，左圖所示的局面出自1929年Schweda與Sika之間的一盤對局。執白的Schweda正確判斷出這是他的必勝局面。1960年，Euwe證明如果輪到黑方先走，黑方也能獲勝。但即便Euwe曾擔任兩年世界冠軍并擁有數學博士學位，他也無法清晰地解釋為什么這個局面是先走的一方獲勝。然而，在組合博弈論發展起來之后，這個分析就變得容易了。

Schweda vs Sika, 1929

關鍵在于將游戲分解為獨立的組成部分，并計算出每個部分的值。位于e線和f線上的王與兵被鎖定在另一種形式的Trébuchet局面中，正如我們所知，它的值為0。因此，另外兩個子博弈構成了一個“后走者勝”的局面。

位于a線和b線上的小兵實際上處于相當復雜的局面：其中三個小兵擁有雙步移動的選擇，并且再過幾步還會出現吃子的機會。不過，如果把這些數值加起來，結果發現這個a線和b線子博弈的值等于↑。這是一個新的符號，它所表達的意思是：這個局面是無窮小的正數——白方擁有非常微弱的優勢。

第二個組成部分——h線上的兩個小兵——的值更容易計算。在這里，黑方擁有雙步移動的選擇，而白方沒有。如果輪到黑方走棋，黑兵前進兩格，并在下一回合擋住白兵的推進。如果白方先走，黑方則只前進一格，隨后同樣很快擋住白兵。因此，黑方可以利用這個多余的步數，保證在該子博弈結束后輪到白方走棋。這個子博弈的值是↓，它表示一個略為負的數。

利用CGT的代數可以將↑和↓相加，結果發現這兩個組成部分之和為一個模糊值。無論誰在棋盤上先走，都可以巧妙地安排，使得在這些小兵子博弈結束后輪到對方走棋。對方別無選擇，只能移動自己的王，從而輸掉Trébuchet局面，并很快輸掉整盤棋。

因此，組合博弈論是分析某些類型游戲的非常強大的工具。簡單的尼姆游戲很好地展示了這一技術的運作方式，但其真正的威力只有在應用于像國際象棋殘局這樣復雜得多的局面時才會顯現出來。它甚至能解開一個困擾了75年之久的謎題——這個謎題曾難倒了一位擁有數學博士學位的國際象棋特級大師。

《棋手》，作者：托馬斯·埃金斯

1 Winning Ways For Your Mathematical Plays, Volume 1, 2nd edition, Berlekamp, Conway, Guy

2 Games of No Chance, Richard Nowakowski (ed.)

最后照例放些跟張大少有關的圖書鏈接。

青山 不改，綠水長流，在下告退。

轉發隨意，轉載請聯系張大少本尊，聯系方式請見公眾號底部菜單欄。

掃一掃，關注微信公眾號“宇宙文明帶路黨”