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

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

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

組合博弈論

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

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

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

二十一（取物游戲）

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

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

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

尼姆游戲

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

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

{ 0 | 0 } = *

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

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

{1∣1}=0.

同樣，左側(cè)和右側(cè)的數(shù)字告訴我們，在任意一方走完下一步之后剩余的可走步數(shù)，在這個(gè)例子中就是1。這里的值是0，因?yàn)橄乱徊阶咂宓囊环綄?huì)輸?shù)粲螒?，因此“先手必?cái)　钡木置嬉脖环Q為零局面。所有先手必?cái)〉木置娑伎梢院?jiǎn)化為游戲中沒有硬幣剩下的最終狀態(tài)：

{ ∣ }=0.

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

{2∣2}=?.

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

{1,2∣1,2}.

但在對(duì)手回合開始時(shí)，不必要地只留下一枚剩余步數(shù)是完全不理智的，因?yàn)閷?duì)手會(huì)直接取走剩下的硬幣從而贏得比賽。在CGT中，這種愚蠢的選擇會(huì)被忽略，因?yàn)榧俣p方都是理智地在玩，并試圖獲勝。因此：

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

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

A possible starting setup for Nim

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

尼姆游戲中的一個(gè)模糊局面

有偏博弈——國(guó)際象棋

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

{4∣3}=1,

它可以簡(jiǎn)化為

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

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

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

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

殘局中的CGT

在殘局的某些局面中，必須走棋的一方將會(huì)輸?shù)?。這與尼姆中的零局面相同，在國(guó)際象棋中，這些特殊情況被稱為“相互逼走”?！癦ugzwang”是一個(gè)德語詞，意為“被迫移動(dòng)”。右圖所示的“Trébuchet”局面就是這樣一個(gè)相互逼走的例子：

{ ∣ }=0.

一個(gè)“Trébuchet”局面

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

{ 0 | 0 } = *.

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

{0∣0}=?.

殘局中的一個(gè)模糊局面

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

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

殘局中的一個(gè)正局面

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

Schweda vs Sika, 1929

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

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

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

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

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

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

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

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

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

青山 不改，綠水長(zhǎng)流，在下告退。

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

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