????許多小朋友喜歡棋牌游戲，比如象棋、圍棋、麻將、撲克…當(dāng)你和對(duì)手廝殺的昏天黑地時(shí)，有沒(méi)有想過(guò)這樣一個(gè)問(wèn)題：這些游戲有必勝策略嗎？

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

????今天，我們就來(lái)討論一下這個(gè)問(wèn)題。

一.策梅洛定理

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

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

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

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

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

????也許有同學(xué)認(rèn)為：A的贏面大一些，其實(shí)并非如此。這盤(pán)棋的結(jié)果一定是和棋（除非有一方實(shí)在腦子不太好用，才會(huì)輸?shù)簦?。我們可以?huà)一個(gè)游戲樹(shù)來(lái)解釋?zhuān)?/p>

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

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

• 我們?cè)賮?lái)考慮A：若A走上方，進(jìn)入子游戲1，一定B獲勝；A走下方，進(jìn)入子游戲2，一定和棋。A也要選擇對(duì)自己有利的，所以A選擇下方。最終的游戲就是和棋。

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

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

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

????可是，為什么我們從來(lái)沒(méi)聽(tīng)說(shuō)過(guò)誰(shuí)掌握了象棋和圍棋的必勝法呢？

二.井字棋

????我們舉一個(gè)最簡(jiǎn)單的棋——井字棋來(lái)說(shuō)明。

????井字棋非常簡(jiǎn)單。首先畫(huà)一個(gè)井字，然后先手畫(huà)叉，后手畫(huà)圈，在九個(gè)格子中輪流畫(huà)。誰(shuí)的三個(gè)子橫豎斜連成一條線，誰(shuí)就贏了。如果畫(huà)滿了雙方都沒(méi)有贏，那就是和棋。比如，下面就是一個(gè)先手勝的井字棋局。

????這個(gè)游戲的規(guī)則雖然簡(jiǎn)單，但是可玩性還是很高的，因?yàn)樗鋵?shí)也有不少變化，說(shuō)準(zhǔn)確一點(diǎn)，應(yīng)該叫游戲的復(fù)雜度。

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

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

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

????大家看：

• 先手畫(huà)第一個(gè)叉時(shí)，去掉對(duì)稱性，其實(shí)只有三種畫(huà)法：中間、邊中點(diǎn)和角。這是樹(shù)的第一層，有3個(gè)分支。

• 如果先手在中間畫(huà)叉，去掉對(duì)稱性，后手的圈只有兩種畫(huà)法：角和邊的中點(diǎn)。如果先手畫(huà)在邊上或者角上，后手分別將如圖所示的五種畫(huà)法。這是樹(shù)的第二層，有12個(gè)分支。

• 之后，游戲還有很多層，每層又有很多分支，直到最后有一方獲勝或者和棋。

????游戲樹(shù)有多少個(gè)不同路徑，就表示了游戲一共有多少種可能的變化。

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

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

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

三.圍棋

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

????以圍棋為例。圍棋在19x19=361個(gè)格子上輪流放棋子，所以每個(gè)格子有黑白空三種可能，整個(gè)圍棋棋盤(pán)上的狀態(tài)數(shù)上限是3^361=1.7x10^172，去掉一些重復(fù)和對(duì)稱，圍棋的狀態(tài)復(fù)雜度大約是10^171量級(jí)。

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

????圍棋的游戲樹(shù)就更難畫(huà)了。因?yàn)閲蹇梢蕴嶙樱辛丝瞻椎牡胤娇梢岳^續(xù)下，所以并不一定是填滿了棋盤(pán)就結(jié)束。不過(guò)，我們可以估計(jì)游戲樹(shù)的總層數(shù)和每一層的平均分支。根據(jù)統(tǒng)計(jì)和計(jì)算：一盤(pán)圍棋的平均手?jǐn)?shù)是150手，每一手的平均分支數(shù)是250種，所以整個(gè)圍棋的游戲樹(shù)復(fù)雜度大約是250^150≈10^360。

????理論上講，如果我們遍歷了所有10^360種情況，就能知道圍棋結(jié)局到底是先手必勝，還是后手必勝，或者一定是和棋了。但是，這個(gè)計(jì)算量實(shí)在太大了。世界上最快的計(jì)算機(jī)富岳每秒最高可以計(jì)算100億億次浮點(diǎn)運(yùn)算，假如1次浮點(diǎn)運(yùn)算就能算出一條路徑，那么算完所有圍棋游戲的可能情況，需要10^342秒，而宇宙的年齡只有138億年，大約只等于10^17s。
顯然，我們知道圍棋一定有最優(yōu)策略，但是我們無(wú)法計(jì)算出這個(gè)最優(yōu)策略。

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

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

四.軍棋

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

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

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

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

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

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

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

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

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

五.麻將

????我們?cè)賮?lái)看看我們的國(guó)粹：麻將。

????麻將也是一種暗棋。34種牌，每種4張，一共136張牌。開(kāi)局時(shí)四方各抓13張，每一輪抓一張?jiān)俅蛞粡垼詈笕绻Ｏ?4~16張還沒(méi)有人胡牌，就算流局。我們知道自己手里的牌，但是不知道別人手里的牌和自己和其他人能抓到的牌，所以是不完全信息博弈，是暗棋。

????咱們具體來(lái)算算信息集個(gè)數(shù)和信息集大?。?/span>

第一輪

• 信息集個(gè)數(shù)：麻將牌一共136張，我起手抓13張牌，不考慮重復(fù)，我拿到的牌的可能方法數(shù)有C(136,13)=4.8x10^17種。

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

第二輪

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

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

?????……

????因?yàn)槁閷⒆詈笠嘞?4~16張牌就流局，所以最多可以打17輪左右。我們按照這種方法，把這17輪的信息集個(gè)數(shù)和信息集大小全部列出來(lái)，如下表所示

????用圖表更清晰一些：

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

????還可以算出：在麻將中，信息集的總個(gè)數(shù)大約是大約是10^115，這就是我們打麻將時(shí)，能看到的狀態(tài)總數(shù)上限。對(duì)每一個(gè)局面，信息集的平均大小大約是10^49，也就是我們未知的、別人手里的牌的可能組合。用信息集總數(shù)乘以平均信息集大小，能夠估計(jì)出麻將的狀態(tài)復(fù)雜度，大約是10^165.
????微軟亞洲研究院曾經(jīng)比較過(guò)幾種棋牌游戲的狀態(tài)復(fù)雜度。在這張圖上，縱軸表示信息集大小，也就是不確定性；橫軸表示信息集個(gè)數(shù)，也就是明牌部分的變化.

????你會(huì)發(fā)現(xiàn)：

• 井字棋、國(guó)際跳棋、中國(guó)象棋、國(guó)際象棋和圍棋，因?yàn)橥耆珱](méi)有不確定性，它的信息集大小為1，只有信息集個(gè)數(shù)一個(gè)維度。如我們剛剛所說(shuō)，這些棋類(lèi)都有最優(yōu)策略。

• 麻將、橋牌、德州撲克，除了自己拿到的牌有很多種變化外，就算你看到了同樣的局面，別人依然有很多種可能的牌，它們是不完全信息博弈，有兩個(gè)維度。

• 相比而言，麻將比橋牌和德州撲克的信息集大小大很多，這說(shuō)明麻將的不確定性更大，運(yùn)氣在麻將里更重要。

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

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

?