許多小朋友喜歡棋牌游戲,比如象棋、圍棋、麻將、撲克…當你和對手廝殺的昏天黑地時,有沒有想過這樣一個問題:這些游戲有必勝策略嗎?
如果你某一天偶然間在一個洞穴中找到了一本秘籍,從而獲得了某種棋牌的必勝套路,什么深藍、阿爾法狗,統(tǒng)統(tǒng)需要讓位,那該是一件多么榮耀的事情??!
今天,我們就來討論一下這個問題。
策梅洛定理
首先,我們要把游戲分為兩種:完全信息博弈和不完全信息博弈。如果所有的參與者,在游戲的任何階段都可以獲知過去以及現(xiàn)在的所有游戲信息,這類游游戲就稱為為完全信息博弈。否則,就稱為不完全信息博弈。
比如:象棋、圍棋、五子棋,大家都能看到對方是怎么走的,這就是完全信息博弈。但是,軍棋卻不是這樣——四國軍棋你不知道對方的排兵布陣,翻翻棋你連自己的棋子在哪里都不知道。撲克牌你不知道對方手里的牌,麻將你不光不知道對方手里的牌,也不知道牌桌上剩下的牌,像軍棋、撲克、麻將這樣的游戲,就叫做不完全信息博弈。
1913年,數(shù)學(xué)家策梅洛證明:對于一個兩人的完全信息游戲,一定存在一個策略,要么先手一定獲勝,要么后手一定獲勝,要么雙方一定平局,這就是策梅洛定理。
策梅洛
這個定理如何證明呢?其實很簡單:一個輪流走棋的游戲,每一步的走法都是有限個,這稱為游戲分支,游戲的分支是有限的。由于制定了一些勝負以及和棋規(guī)則,游戲的步驟也是有限的。
我們假設(shè)有一個非常簡單的游戲,先手A和后手B各做一次決策(選擇上路或者下路),根據(jù)二人決策的結(jié)果,游戲的勝負如下。通過這個表格,你能知道游戲的結(jié)果是誰獲勝嗎?
某個游戲的策略和結(jié)果
也許有同學(xué)認為:A的贏面大一些,其實并非如此。這盤棋的結(jié)果一定是和棋(除非有一方實在腦子不太好用,才會輸?shù)簦N覀兛梢援嬕粋€游戲樹來解釋:
游戲樹
如果先手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