許多小朋友喜歡棋牌遊戲，比如象棋、圍棋、麻將、撲克…當你和對手廝殺的昏天黑地時，有沒有想過這樣一個問題：

這些遊戲有必勝策略嗎？

如果你某一天偶然間在一個洞穴中找到了一本秘籍，從而獲得了某種棋牌的必勝套路，什麼深藍、阿法狗，統統需要讓位，那該是一件多麼榮耀的事情啊！

今天，我們就來討論一下這個問題。

策梅洛定理

首先，我們要把遊戲分為兩種：完全資訊博弈和不完全資訊博弈。

如果所有的參與者，在遊戲的任何階段都可以獲知過去以及現在的所有遊戲資訊，這類遊遊戲就稱為為完全資訊博弈。

否則，就稱為不完全資訊博弈。

比如：象棋、圍棋、五子棋，大家都能看到對方是怎麼走的，這就是

完全資訊博弈

。但是，軍棋卻不是這樣——四國軍棋你不知道對方的排兵佈陣，翻翻棋你連自己的棋子在哪裡都不知道。撲克牌你不知道對方手裡的牌，麻將你不光不知道對方手裡的牌，也不知道牌桌上剩下的牌，像軍棋、撲克、麻將這樣的遊戲，就叫做

不完全資訊博弈

。

1913年，數學家策梅洛證明：

對於一個兩人的完全資訊遊戲，一定存在一個策略，要麼先手一定獲勝，要麼後手一定獲勝，要麼雙方一定平局，這就是策梅洛定理。

策梅洛

這個定理如何證明呢？其實很簡單：一個輪流走棋的遊戲，每一步的走法都是有限個，這稱為遊戲分支，遊戲的分支是有限的。由於制定了一些勝負以及和棋規則，遊戲的步驟也是有限的。

我們假設有一個非常簡單的遊戲，先手A和後手B各做一次決策（選擇上路或者下路），根據二人決策的結果，遊戲的勝負如下。透過這個表格，你能知道遊戲的結果是誰獲勝嗎？

某個遊戲的策略和結果

也許有同學認為：A的贏面大一些，其實並非如此。這盤棋的結果一定是和棋（除非有一方實在腦子不太好用，才會輸掉）。我們可以畫一個遊戲樹來解釋：

遊戲樹

如果先手A選擇上方，遊戲進入到一個由進行B進行決策的分支，這叫做一個

子游戲

。在這個子游戲中，B選上方就A獲勝，B選下方就B獲勝，B要選擇對自己有利的，所以他一定選擇下方。這個子游戲的結局是固定的，就是B獲勝。

如果先手A選擇下方，遊戲進入到另一個由B做決策的子游戲中，這時B選上方就A獲勝，B選下方就和棋，B要選擇對自己有利的，所以這個子游戲的結局一定是和棋。

我們再來考慮A：若A走上方，進入子游戲1，一定B獲勝；A走下方，進入子游戲2，一定和棋。A也要選擇對自己有利的，所以A選擇下方。最終的遊戲就是和棋。

如果遊戲複雜一些，也不過是分支變多，長度變長，但是隻要我們從最後端的子游戲開始，一層層倒推，就一定能推算出在最優策略下，遊戲到底是先手勝，還是後手勝，還是和棋，這種勝負是不可避免的。

比如五子棋：雙方輪流下子，五子連線獲勝。人們逐漸發現：先手有必勝法。為了遊戲公平，就設計了三三禁手、四四禁手、長連禁手，先手走出禁手就算輸。

無禁手時五子棋的兩種先手必勝開局

與五子棋相比，中國象棋、圍棋的規則就複雜很多，但是它們依然是雙人完全資訊博弈。雖然我們不知道最優套路是什麼，但是我們確信：

一定存在那樣一種最優的策略，如果雙方都執行了這種策略，則一定是先手贏、或者後手贏、或者一定和棋。

可是，為什麼我們從來沒聽說過誰掌握了象棋和圍棋的必勝法呢？

井字棋

我們舉一個最簡單的棋——井字棋來說明。

井字棋非常簡單。首先畫一個井字，然後先手畫叉，後手畫圈，在九個格子中輪流畫。誰的三個子橫豎斜連成一條線，誰就贏了。如果畫滿了雙方都沒有贏，那就是和棋。比如，下面就是一個先手勝的井字棋局。

一個井字棋牌局

這個遊戲的規則雖然簡單，但是可玩性還是很高的，因為它其實也有不少變化，說準確一點，應該叫遊戲的複雜度。

首先，我們討論

遊戲的狀態複雜度，它表示在這個棋盤上到底會出現多少種可能的局面

。

一般來講，我們沒辦法準確算出一個遊戲的狀態複雜度，很多時候也沒必要準確算出來，我們只要估算一個上限，或者一個數量級，就可以了。

比如井字棋：每一個格子都有叉、圈、空白3種可能，一共有9個格子，所以，最多能夠出現的局面也不會超過39=19683種。這裡面有許多不符合規則的情況，比如叉的數量要麼和圈相同，要麼多1個，其他情況都不符合規則。對稱的情況，其實應該算作一種情況。如果把這些不符合規則和對稱都去掉，最終餘下的狀態數是765種——你在井字棋中只能看到這765種局面。

狀態數並不是衡量遊戲複雜程度的唯一方式，因為同一個局面狀態，也可以從不同的路徑得出。要考察遊戲玩法總數，我們得計算

遊戲樹

的大小。

井字棋的一部分遊戲樹

大家看：先手畫第一個叉時，去掉對稱性，其實只有三種畫法：中間、邊中點和角。這是樹的第一層，有3個分支。

如果先手在中間畫叉，去掉對稱性，後手的圈只有兩種畫法：角和邊的中點。如果先手畫在邊上或者角上，後手分別將如圖所示的五種畫法。這是樹的第二層，有12個分支。

之後，遊戲還有很多層，每層又有很多分支，直到最後有一方獲勝或者和棋。遊戲樹有多少個不同路徑，就表示了遊戲一共有多少種可能的變化。

在井字棋遊戲中，我們可以估算遊戲樹的複雜度：先手先選位置，有9種可能；後手只剩下8種可能，先手又剩下7種可能…直到最後填滿9個格子，所以遊戲樹複雜度不超過9！=362880種。這裡面有許多不符合規則的，比如已經有一方獲勝了，就不用再下了，還要去掉重複和對稱的，最終的遊戲樹複雜度是26830。

人們已經考察了井字棋的全部26830條路經，並發現：

如果雙方都採用最優策略，那麼井字棋一定是和棋。

先手最優策略

後手最優策略

像這樣完整畫出遊戲樹，找出最優策略的遊戲叫做

已解決遊戲

。儘管如此，大部分情況下，井字棋還是會出現輸贏，這是因為有些人對遊戲樹掌握的好，有些人掌握的不好。一旦對方出現失誤，對遊戲樹掌握資訊好的人就能迅速抓住這個漏洞，讓不會玩的人陷入必敗的遊戲樹分支之中。這就是大師和新手的區別。

圍棋

其實，象棋也好，圍棋也好，它們與井字棋沒有本質不同，只是複雜度比井字棋高很多。

圍棋

以圍棋為例。圍棋在19x19=361個格子上輪流放棋子，所以每個格子有黑白空三種可能，整個圍棋棋盤上的狀態數上限是3361=1。7x10172，去掉一些重複和對稱，

圍棋的狀態複雜度大約是1

171

量級

。

要知道：宇宙中的原子個數只有大約1080個，就算用宇宙中的一個原子代表一個圍棋局面，窮盡宇宙中所有的原子，也不能表示出圍棋所有的棋局局面。

圍棋的遊戲樹就更難畫了。因為圍棋可以提子，有了空白的地方可以繼續下，所以並不一定是填滿了棋盤就結束。不過，我們可以估計遊戲樹的總層數和每一層的平均分支。根據統計和計算：一盤圍棋的平均手數是150手，每一手的平均分支數是250種，所以整個

圍棋的遊戲樹複雜度大約是

250

150

≈

10

360

。

理論上講，如果我們遍歷了所有10360種情況，就能知道圍棋結局到底是先手必勝，還是後手必勝，或者一定是和棋了。但是，這個計算量實在太大了。世界上最快的計算機富嶽每秒最高可以計算100億億次浮點運算，假如1次浮點運算就能算出一條路徑，那麼算完所有圍棋遊戲的可能情況，需要10342秒，而宇宙的年齡只有138億年，大約只等於1017s。

顯然，

我們知道圍棋一定有最優策略，但是我們無法計算出這個最優策略

。

不過，數學家們也找到了一些其他方法，不用遍歷所有情況，也能找到比較好的獲勝方法，比如1997年深藍戰勝國際象棋世界冠軍卡斯帕羅夫，2016年阿法狗打遍天下無敵手，都是採用了人工智慧的方法。

人工智慧戰勝人類的過程

除了圍棋以外，人們也估算了其他幾種棋類遊戲的複雜度，如下表所示。你會發現井字棋情況特別少，因此很容易成為大師，兩位大師碰到一起，只能是和棋。五子棋情況稍多，但是隻要玩的多，也能發現套路，從而成為大師，無禁手時先手必勝。像國際象棋、中國象棋，圍棋複雜度就更高了。

軍棋

剛才我們討論的幾種棋，雖然複雜度不同，但它們都是明棋，也就是博弈雙方都對目前的局勢瞭如指掌。這樣的棋有最優解，誰更接近最優解，誰的棋術就更高，不出意外的情況下，棋術低的人絕不可能贏棋術高的人，就比如我和阿法狗下圍棋，是絕對贏不了的。

但也有一些棋，下棋的人並不知道所有棋子的情況。有的時候，因為運氣好，棋術差的人也能戰勝棋術好的人，這就為遊戲增添了很多樂趣。這種暗棋就是不完全資訊博弈。

比如，大家還記得軍棋嗎？

軍棋

雙方各有25個棋子，司令可以吃軍長，軍長可以吃師長，工兵可以挖地雷，挖完了地雷扛軍旗就贏了。軍棋有很多種玩法，其中一種是：開局之前，你要先暗自排兵佈陣，把自己的25個子放在25個位置上，不讓對方看到。兩個子相遇，由裁判判定誰吃誰。所以雙方都不知道對方的棋子是什麼。我小時候特別喜歡玩軍棋，運氣好的時候自己的司令吃了敵方的軍長，或者敵方司令踩了我的地雷，我就特別高興。

怎麼描述軍棋的複雜程度呢？我們需要

資訊集

這個概念。

資訊集的大小表示所有未知資訊的可能數

。

比如我和張三對局，我知道張三隻會10種排兵佈陣的方法，只是我不知道他選用了哪一種。這時，資訊集大小就是10。

資訊集的個數表示所有已知資訊的可能數

。

比如我自己只會5種開局陣型，那麼我的資訊集個數就是5。

大家想想，我和張三對局時，局面有多少種可能？應該是50種對嗎？只要用資訊集大小乘以資訊集個數就可以了。實際上如果兩人對壘，雙方各有25個子，排到自己的25個兵站上，開局時軍棋的資訊集的大小和個數都是25！=1。5x1025種（忽略重複的子）。

軍棋棋盤

現在，我們就從單一維度的局面狀態，變成了資訊集大小和資訊集個數兩個維度了。

資訊集大小表示未知可能性的集合，資訊集個數表示已知局面的總狀態數。不完全資訊博弈有兩個維度的複雜度。

麻將

我們再來看看我們的國粹：麻將。

麻將

麻將也是一種暗棋。34種牌，每種4張，一共136張牌。開局時四方各抓13張，每一輪抓一張再打一張，最後如果剩下14~16張還沒有人胡牌，就算流局。我們知道自己手裡的牌，但是不知道別人手裡的牌和自己和其他人能抓到的牌，所以是

不完全資訊博弈，是暗棋。

咱們具體來算算資訊集個數和資訊集大小：

第一輪

資訊集個數：麻將牌一共136張，我起手抓13張牌，不考慮重複，我拿到的牌的可能方法數有種。

資訊集大小：除了我手中的13張牌外，還有123張牌，其餘三名玩家每人手裡有13張，所以未知的可能數有種。

第二輪

資訊集個數：在第一輪中，4個玩家每人打了1張，麻將牌一共有34種，所以打牌的方法數共有344種。此時，此時我手裡還有13張牌，方法數有，所以現在，我可能面臨的局面有種。

資訊集大小：除了我手裡的13張，以及上一輪打出的4張，還餘下119張牌，三家手裡還是各有13張牌，可能數有種。

……

因為麻將最後要餘下14~16張牌就流局，所以最多可以打17輪左右。我們按照這種方法，把這17輪的資訊集個數和資訊集大小全部列出來，如下表所示

麻將每一輪的資訊集個數和大小

用圖表更清晰一些：

你會發現：

隨著打牌的進行，資訊集的個數越變越大，也就是我能夠觀察到的、可能的局面數量越來越多。資訊集的大小越變越小，也就是我未知的局面的可能性越來越少。

還可以算出：在麻將中，資訊集的總個數大約是大約是10115，這就是我們打麻將時，能看到的狀態總數上限。對每一個局面，資訊集的平均大小大約是1049，也就是我們未知的、別人手裡的牌的可能組合。用資訊集總數乘以平均資訊集大小，能夠估計出

麻將的狀態複雜度，大約是10^165

。

微軟亞洲研究院曾經比較過幾種棋牌遊戲的狀態複雜度。在這張圖上，縱軸表示資訊集大小，也就是不確定性；橫軸表示資訊集個數，也就是明牌部分的變化。

參考微軟亞洲研究院做出的棋牌複雜度圖

你會發現：井字棋、國際跳棋、中國象棋、國際象棋和圍棋，因為完全沒有不確定性，它的資訊集大小為1，只有資訊集個數一個維度。如我們剛剛所說，這些棋類都有最優策略。

而麻將、橋牌、德州撲克，除了自己拿到的牌有很多種變化外，就算你看到了同樣的局面，別人依然有很多種可能的牌，它們是不完全資訊博弈，有兩個維度。相比而言，麻將比橋牌和德州撲克的資訊集大小大很多，這說明麻將的不確定性更大，運氣在麻將裡更重要。

只要遊戲存在兩個維度，存在不確定性，一般就沒有必勝的策略了

。顯然，只要我的牌足夠好，無論你水平多高，你打麻將也會大機率輸給我。計算機在計算麻將這類不完全資訊博弈問題中的進度，明顯落後於象棋圍棋。

麻將具有很多的變化和不確定性，讓一個普通選手也可能戰勝大師，偶爾的意外之喜，才會讓許多人上癮，打麻將要順勢而為，無論你的牌術多高，都有可能無法掌控牌局的發展。比如，你要是打麻將就想胡清一色，那很有可能要輸一晚上。

打麻將是這樣，生活又何嘗不是呢？

END