打麻將有必勝法嗎？象棋、圍棋、麻將、德州…哪種游戲更復(fù)雜？

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

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

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

策梅洛定理

首先，我們要把游戲分為兩種：完全信息博弈和不完全信息博弈。如果所有的參與者，在游戲的任何階段都可以獲知過去以及現(xiàn)在的所有游戲信息，這類游游戲就稱為為完全信息博弈。否則，就稱為不完全信息博弈。

比如：象棋、圍棋、五子棋，大家都能看到對方是怎么走的，這就是完全信息博弈。但是，軍棋卻不是這樣——四國軍棋你不知道對方的排兵布陣，翻翻棋你連自己的棋子在哪里都不知道。撲克牌你不知道對方手里的牌，麻將你不光不知道對方手里的牌，也不知道牌桌上剩下的牌，像軍棋、撲克、麻將這樣的游戲，就叫做不完全信息博弈。

1913年，數(shù)學(xué)家策梅洛證明：對于一個兩人的完全信息游戲，一定存在一個策略，要么先手一定獲勝，要么后手一定獲勝，要么雙方一定平局，這就是策梅洛定理。

策梅洛

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

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

某個游戲的策略和結(jié)果

也許有同學(xué)認為：A的贏面大一些，其實并非如此。這盤棋的結(jié)果一定是和棋（除非有一方實在腦子不太好用，才會輸?shù)簦Ｎ覀兛梢援嬕粋€游戲樹來解釋：

游戲樹

如果先手A選擇上方，游戲進入到一個由進行B進行決策的分支，這叫做一個子游戲。在這個子游戲中，B選上方就A獲勝，B選下方就B獲勝，B要選擇對自己有利的，所以他一定選擇下方。這個子游戲的結(jié)局是固定的，就是B獲勝。

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

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

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

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

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

與五子棋相比，中國象棋、圍棋的規(guī)則就復(fù)雜很多，但是它們依然是雙人完全信息博弈。雖然我們不知道最優(yōu)套路是什么，但是我們確信：一定存在那樣一種最優(yōu)的策略，如果雙方都執(zhí)行了這種策略，則一定是先手贏、或者后手贏、或者一定和棋。

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

井字棋

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

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

一個井字棋牌局

這個游戲的規(guī)則雖然簡單，但是可玩性還是很高的，因為它其實也有不少變化，說準確一點，應(yīng)該叫游戲的復(fù)雜度。

首先，我們討論游戲的狀態(tài)復(fù)雜度，它表示在這個棋盤上到底會出現(xiàn)多少種可能的局面。一般來講，我們沒辦法準確算出一個游戲的狀態(tài)復(fù)雜度，很多時候也沒必要準確算出來，我們只要估算一個上限，或者一個數(shù)量級，就可以了。

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

狀態(tài)數(shù)并不是衡量游戲復(fù)雜程度的唯一方式，因為同一個局面狀態(tài)，也可以從不同的路徑得出。要考察游戲玩法總數(shù)，我們得計算游戲樹的大小。

井字棋的一部分游戲樹

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

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

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

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

人們已經(jīng)考察了井字棋的全部26830條路經(jīng)，并發(fā)現(xiàn)：如果雙方都采用最優(yōu)策略，那么井字棋一定是和棋。

先手最優(yōu)策略

后手最優(yōu)策略

像這樣完整畫出游戲樹，找出最優(yōu)策略的游戲叫做已解決游戲。盡管如此，大部分情況下，井字棋還是會出現(xiàn)輸贏，這是因為有些人對游戲樹掌握的好，有些人掌握的不好。一旦對方出現(xiàn)失誤，對游戲樹掌握信息好的人就能迅速抓住這個漏洞，讓不會玩的人陷入必敗的游戲樹分支之中。這就是大師和新手的區(qū)別。

圍棋

其實，象棋也好，圍棋也好，它們與井字棋沒有本質(zhì)不同，只是復(fù)雜度比井字棋高很多。

圍棋

以圍棋為例。圍棋在19x19=361個格子上輪流放棋子，所以每個格子有黑白空三種可能，整個圍棋棋盤上的狀態(tài)數(shù)上限是3361=1.7x10172，去掉一些重復(fù)和對稱，圍棋的狀態(tài)復(fù)雜度大約是10171量級。

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

圍棋的游戲樹就更難畫了。因為圍棋可以提子，有了空白的地方可以繼續(xù)下，所以并不一定是填滿了棋盤就結(jié)束。不過，我們可以估計游戲樹的總層數(shù)和每一層的平均分支。根據(jù)統(tǒng)計和計算：一盤圍棋的平均手數(shù)是150手，每一手的平均分支數(shù)是250種，所以整個圍棋的游戲樹復(fù)雜度大約是250150≈10360。

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

顯然，我們知道圍棋一定有最優(yōu)策略，但是我們無法計算出這個最優(yōu)策略。

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

人工智能戰(zhàn)勝人類的過程

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

軍棋

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

但也有一些棋，下棋的人并不知道所有棋子的情況。有的時候，因為運氣好，棋術(shù)差的人也能戰(zhàn)勝棋術(shù)好的人，這就為游戲增添了很多樂趣。這種暗棋就是不完全信息博弈。

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

軍棋

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

怎么描述軍棋的復(fù)雜程度呢？我們需要信息集這個概念。

信息集的大小表示所有未知信息的可能數(shù)。比如我和張三對局，我知道張三只會10種排兵布陣的方法，只是我不知道他選用了哪一種。這時，信息集大小就是10.

信息集的個數(shù)表示所有已知信息的可能數(shù)。比如我自己只會5種開局陣型，那么我的信息集個數(shù)就是5.

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

軍棋棋盤

現(xiàn)在，我們就從單一維度的局面狀態(tài)，變成了信息集大小和信息集個數(shù)兩個維度了。信息集大小表示未知可能性的集合，信息集個數(shù)表示已知局面的總狀態(tài)數(shù)。不完全信息博弈有兩個維度的復(fù)雜度。

麻將

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

麻將

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

咱們具體來算算信息集個數(shù)和信息集大?。?/p>

第一輪

信息集個數(shù)：麻將牌一共136張，我起手抓13張牌，不考慮重復(fù)，我拿到的牌的可能方法數(shù)有種。

信息集大?。撼宋沂种械?3張牌外，還有123張牌，其余三名玩家每人手里有13張，所以未知的可能數(shù)有種。

第二輪

信息集個數(shù)：在第一輪中，4個玩家每人打了1張，麻將牌一共有34種，所以打牌的方法數(shù)共有344種。此時，此時我手里還有13張牌，方法數(shù)有，所以現(xiàn)在，我可能面臨的局面有種。

信息集大?。撼宋沂掷锏?3張，以及上一輪打出的4張，還余下119張牌，三家手里還是各有13張牌，可能數(shù)有種.

……

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

麻將每一輪的信息集個數(shù)和大小

用圖表更清晰一些：

你會發(fā)現(xiàn)：隨著打牌的進行，信息集的個數(shù)越變越大，也就是我能夠觀察到的、可能的局面數(shù)量越來越多。信息集的大小越變越小，也就是我未知的局面的可能性越來越少。

還可以算出：在麻將中，信息集的總個數(shù)大約是大約是10115，這就是我們打麻將時，能看到的狀態(tài)總數(shù)上限。對每一個局面，信息集的平均大小大約是1049，也就是我們未知的、別人手里的牌的可能組合。用信息集總數(shù)乘以平均信息集大小，能夠估計出麻將的狀態(tài)復(fù)雜度，大約是10^165.

微軟亞洲研究院曾經(jīng)比較過幾種棋牌游戲的狀態(tài)復(fù)雜度。在這張圖上，縱軸表示信息集大小，也就是不確定性；橫軸表示信息集個數(shù)，也就是明牌部分的變化.

參考微軟亞洲研究院做出的棋牌復(fù)雜度圖

你會發(fā)現(xiàn)：井字棋、國際跳棋、中國象棋、國際象棋和圍棋，因為完全沒有不確定性，它的信息集大小為1，只有信息集個數(shù)一個維度。如我們剛剛所說，這些棋類都有最優(yōu)策略。

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

只要游戲存在兩個維度，存在不確定性，一般就沒有必勝的策略了。顯然，只要我的牌足夠好，無論你水平多高，你打麻將也會大概率輸給我。計算機在計算麻將這類不完全信息博弈問題中的進度，明顯落后于象棋圍棋。

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

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

END