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

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

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

組合博弈論

盡管組合博弈論（CGT）功能強(qiáng)大，但它僅適用于滿足某些條件的游戲。最重要的條件是：游戲有兩名玩家，雙方對游戲狀態(tài)擁有完全信息，不存在隨機(jī)因素（如擲骰子或洗牌），并且雙方輪流行動（不允許跳過回合），最終無法行動的一方輸?shù)粲螒颉Ｒ虼耍p陸棋、撲克、海戰(zhàn)棋、大富翁和紙牌接龍等游戲無法用CGT來分析，因?yàn)樗鼈冊诟鞣N不同組合上不滿足這些標(biāo)準(zhǔn)。

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

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

二十一（取物游戲）

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

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

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

尼姆游戲

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

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

{ 0 | 0 } = *

由于CGT不知道下一步輪到誰，它給出的是在任意一方走棋后剩余的可走步數(shù)。花括號中的數(shù)字表示：在取走最后一枚硬幣后，左邊的玩家將沒有剩余步數(shù)，右邊的玩家也同樣如此。因?yàn)槟崮酚螒蚴菬o偏博弈，中間豎線左右兩側(cè)的數(shù)字總是相同的。該博弈的值寫在等號后面。星號表示下一步走棋的一方獲勝，這被稱為模糊局面。二十一游戲從一開始就是一個模糊局面，因?yàn)橄茸叩囊环娇偰軓?qiáng)行獲勝。

然而，如果剩下兩枚孤立的硬幣，那么下一步走棋的一方將會輸?shù)簟＿@是因?yàn)闊o論左方還是右方先走，都只能留下一枚硬幣。對方取走這枚硬幣，從而贏得游戲。這種情況記作：

{1∣1}=0.

同樣，左側(cè)和右側(cè)的數(shù)字告訴我們，在任意一方走完下一步之后剩余的可走步數(shù)，在這個例子中就是1。這里的值是0，因?yàn)橄乱徊阶咂宓囊环綄數(shù)粲螒颍虼恕跋仁直財(cái)　钡木置嬉脖环Q為零局面。所有先手必?cái)〉木置娑伎梢院喕癁橛螒蛑袥]有硬幣剩下的最終狀態(tài)：

{ ∣ }=0.

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

{2∣2}=?.

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

{1,2∣1,2}.

但在對手回合開始時，不必要地只留下一枚剩余步數(shù)是完全不理智的，因?yàn)閷κ謺苯尤∽呤Ｏ碌挠矌艔亩A得比賽。在CGT中，這種愚蠢的選擇會被忽略，因?yàn)榧俣p方都是理智地在玩，并試圖獲勝。因此：

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

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

A possible starting setup for Nim

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

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

有偏博弈——國際象棋

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

{4∣3}=1,

它可以簡化為

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

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

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

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

殘局中的CGT

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

{ ∣ }=0.

一個“Trébuchet”局面

雙方的小兵互相阻擋了對方的推進(jìn)，因此接下來必須由某一方的王移動。然而，白王不能走到f4格，黑王也不能走到d5格，因?yàn)槟菢訒?dǎo)致王受到對方小兵的攻擊。因此，必須先移動的王不得不從自己的小兵旁邊退開，從而無法再保護(hù)它（國際象棋規(guī)則禁止雙方的王相距一格之內(nèi)）。此時對手就能吃掉這個小兵，并迫使自己的小兵前進(jìn)到底線。根據(jù)規(guī)則，這個小兵可以升變?yōu)楹螅@一優(yōu)勢被認(rèn)為是決定性的，從而確保后走的一方必勝。

{ 0 | 0 } = *.

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

{0∣0}=?.

殘局中的一個模糊局面

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

然而，如果白方的兵是在a2格而不是a3格，那么局面的值將變?yōu)檎龜?shù)：{0∣ }=1。此時白兵在游戲中尚未移動過，因此它在第一步可以選擇前進(jìn)一格或兩格。正是這個選擇給了白方一個多余的步數(shù)。如果黑方先走，白兵就前進(jìn)一格，像之前那樣擋住黑兵。但如果輪到白方先走，白兵可以一次前進(jìn)兩格直接形成阻塞，從而再次迫使黑方打破Trébuchet局面并輸?shù)舯荣悺Ｒ虼耍瑹o論誰先走，白方都能獲勝。

殘局中的一個正局面

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

Schweda vs Sika, 1929

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

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

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

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

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

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

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

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

最后照例放些跟張大少有關(guān)的圖書鏈接。

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

轉(zhuǎn)發(fā)隨意，轉(zhuǎn)載請聯(lián)系張大少本尊，聯(lián)系方式請見公眾號底部菜單欄。

掃一掃，關(guān)注微信公眾號“宇宙文明帶路黨”