人工智慧在麻將領域能戰勝人類嗎?

2017.01.05 by
段昊
Alexander Savin via Flickr
AlphaGo進階版Master連日來擊敗中、日、台、韓多位頂尖職業圍棋高手,麻將成了人類的「最後防線」?本文作者表示:人工智慧要打敗人類,非常容易。

編按:本文作者為段昊,為國際麻將聯盟(MIL秘書),原文刊載於他的知乎,《數位時代》獲授權轉載。

很高興能藉著AlphaGo的東風,和大家分享一下麻將AI研究的現狀。

一、麻將和圍棋有什麼不同?

從博弈論的角度來講,圍棋是完全訊息動態博弈,而麻將屬於非完全訊息動態博弈。圍棋中對局雙方所掌握的訊息是對稱的,而麻將中各對局者間所掌握的訊息不對稱。雖然大家都能看到每位牌手打過什麼牌,但你不知道我的手牌是什麼,我也不知道你的手牌是什麼。這種訊息不對稱的產生的根本原因是牌牆的隨機性。

圍棋與麻將(或者說棋與牌,弈與博)的上述區別,決定了它們獲勝策略的根本不同。棋類項目本質上就是蒙地卡洛樹,獲勝策略就是選擇或迫使對手選擇一個分支,這個分支下面所有的結局都是自己勝。只不過由於棋類變化很多,連AlphaGo也遠不可能遍歷整棵樹,所以AlphaGo會透過價值網路來估計某一分支下勝結局的概率。其實人類的思維也是類似的,在圍棋裡平白被對手屠掉一條大龍,或者在象棋裡平白送給對手一個車總是不好的——在這些分支下,勝結局的概率大大降低了。

作者提供

而牌類的獲勝策略在於盡可能增大自己的得分期望(EV)。我並不知道我接下來要摸什麼牌,或我的對手有什麼牌,但所有可能的情形組成一個概率空間,我只需做出一個選擇,使得自己的得分函數的期望最大。牌類策略的難點在於,影響這一概率空間的因素過多,且具體影響很難確定,比如對手打牌的習慣。

下圖選自《科學化麻雀》,閒家愚形聽牌打10%危險度的牌對攻,x軸為自己和牌時得分,y軸為牌局巡次,z軸為自己的得分期望。

二、何謂「獲勝」?

選手的競技水平如何衡量?麻將是否是「運七技三」的遊戲?其實無論圍棋還是麻將,區分選手的競技水平都不可能只靠一局,就好比AlphaGo和李世乭要進行五番棋對決,AlphaGo贏第一盤時大家並不覺得AlphaGo一定比李世乭強一樣。圍棋有三番、五番、十番棋,對於競技麻將(國標麻將、日本麻將)而言,區分頂尖選手的競技水平至少需要2,000~10,000手牌(如果採用類似橋牌的複式賽制,這一數字會大幅降低)。

至於衡量一個競技項目的競技性,單純用運氣所佔比例是沒有意義的。隨著對局數的增大,運氣所佔比例會越來越小,選手的長期成績必然會向其真實水平收斂。一個競技項目的競技性應當用「區分選手競技水平所需必要對局時間」來衡量。比如圍棋需要三番棋,麻將需要2,000手牌,圍棋一盤平均需要4小時,三番棋約12小時,而麻將一手牌約3分鐘(網路對局),2,000手牌約100小時。麻將相比圍棋有運氣成分,並不意味著麻將選手的競技水平無法衡量,而意味著麻將需要更多的對局時間來區分選手的競技水平。

下圖選自日本麻將平台天鳳麻雀鳳凰桌1,000場以上玩家安定段位排行。這裡的「試合」是指半莊,也就是兩圈牌,考慮到連莊,平均一試合是10手牌,1,000試合是10,000手牌。可以看到牌手的競技水平得到了很顯著的區分,結果也與麻將圈內認知相似。(具體講解請參見

作者提供

所以在這個問題下我們討論麻將AI能否戰勝人類,指的是麻將AI長期成績(10,000手牌以上)能否比人類更好,並不是單指一手牌。只打一手牌,誰都有可能和牌,這是牌類游戲的本質所決定的。

當然,這裡也不考慮牌手或AI作弊的問題。如果透過作弊獲得別人手牌的非法訊息,麻將的競技平衡就完全被打破了。再強的麻將AI成績也不可能比作弊的人類好,反之亦然。事實上,現在很多單機麻將游戲的AI就是透過作弊來增加「智慧」的。

三、麻將會成為人類面對人工智慧的「最後壁壘」嗎?

一言以蔽之,麻將AI不是做不了,而是沒人做。之所以目前還沒有能夠戰勝人類的麻將AI,主要原因還是人們在麻將AI研究方面的投入不夠。目前的麻將AI基本都是麻將游戲製作團隊為麻將遊戲設計的,在單機上就可以運行,強度自然有限。如果像AlphaGo一樣,世界頂級團隊製作,背後龐大資金支持,使用1,000個CPU運行,想要設計一個輕易戰勝人類頂尖麻將牌手的AI沒有任何難度。

首先,麻將的複雜度要遠遠小於圍棋。單就自己的14張手牌來說(總牌數136張),組合共有326,520,504,500種(計算方法詳見麻雀の數學),遠遠小於圍棋的2.08×10^170。不足10^12的手牌種類意味著麻將AI完全可以提前計算好每手牌的打法估值並儲存在資料庫中,打牌時調用即可。

作者提供

當然,打麻將也要考慮別人打的牌以及各家的得分。各家分差的複雜度是很小的,而別人打的牌雖然複雜度會很高(136張牌的牌牆組合為4.3×10^185種,甚至超越了圍棋的複雜度),但別人打的10張牌大多只有1~2張是有用的訊息,AI只需要識別這種模式並蒐索對比以往對局的牌譜即可。

其次,人類對麻將的研究遠不及圍棋,頂尖麻將牌手的訓練水平很低。相比圍棋研究幾千年的歷史,麻將誕生不過百餘年,人們真正開始利用科學手段(統計學、大數據)來研究麻將只是近十年剛剛起步。例如「間四間」是上世紀流行的日本麻將理論,指的是別人打過中間相隔4張的2張同花色數牌,則這2張牌的內側筋牌是危險牌。如別人打過三筒、八筒(中間相隔四五六七筒),則四七筒是危險牌,這是因為別人手裡一開始可能是三五六八筒,三八筒效率較低被打掉,留下的五六筒要四七筒。這一理論在近十年的大數據研究中已被證明是完全錯誤的——別人要四七筒的概率並沒有顯著性的上升。

作者提供

可見,目前人們對麻將的研究還處在很初級的階段,透過別人打過的牌來分析別人想要的牌的科學研究才剛剛開始。麻將界也沒有圍棋那樣3歲開始學棋,10幾歲就和世界頂級高手過招,接受世界頂級指導的職業選手。麻將本身複雜度低,人類頂尖牌手水平又不高,被人工智慧擊敗會比圍棋要容易得多,不可能是「最後壁壘」。

四、現在有哪些比較強的麻將AI?

競技麻將方面,目前國標麻將和日本麻將都有比較強的AI(高於人類平均水平)。日本麻將的AI目前最強的當然是「爆打」。

作者提供
作者提供

「爆打」是由東京大學工學系在讀博士生水上直紀開發的日本麻將AI,他所在的課題組就是專門研究麻將AI的。爆打和AlphaGo一樣,也具有自我對局和分析並學習人類牌譜的能力。水上發表過的論文題目為《Realizing a Four-Player Computer Mahjong Program by Supervised Learning with Isolated Multi-Player Aspects》,全文詳見

爆打從2015年開始在最大的日本麻將平台——天鳳麻雀上開始運行,至2016年2月已經打了1.3萬多場(約13萬手牌)。 2015年9月,爆打達到天鳳麻雀四段,2015年12月更是一度衝進天鳳七段,長期成績顯示平均為六段以上。這意味著什麼呢?

作者提供

上圖是天鳳麻雀平台2016年3月13日的段位成績分佈圖。天鳳平台具有非常科學的段位和Elo Rating體系,越是和高水平牌手對局,獲勝後Rate增加越多,失敗後Rate減少越少;越是和低水平牌手對局,獲勝後Rate增加越少,失敗後Rate減少越多。最終段位和Rate值的穩定值就代表了牌手的真實實力。

可以看到,天鳳麻雀平台的活躍用戶數約為17萬人(不包括新人殭屍號),而六段以上的用戶總數為5793人,約佔3.4%。也就是說,爆打打麻將比96.6% 的麻將玩家要好,全世界麻將打得比爆打好的人,數量僅有幾萬人左右(包含所有麻將規則的估算)。這只是一個課題組,用時一年多研究出的,在一台電腦上運行的麻將AI,就已經基本趕上AlphaGo早期版本所取得的成績了。

國標麻將方面,目前最強的AI大概是我本人目前正在參與設計的國標麻將AI了。最初的版本只加入了最常用的十幾個番種的分值判斷,防守端幾乎沒有做,實測對隨機牌手和牌率就已經達到24% 左右,基本與國標麻將平均和牌率24.3%持平(國標麻將數據可見)。實際水平大概處在所有牌手中上位10~20%左右的水平(低段位牌手多,大部分牌手的水平處在平均以下)。

五、麻將AI的算法應該是什麼樣子的?

最後,我來淺談一下麻將AI的基本算法。

1. 基礎牌效率

麻將的牌效率指的是能使手牌更快和牌的打牌方法,是麻將的基本功。來簡單舉個例子:

作者提供

這是一手13張牌的手牌,現階段是一上聽(差1張牌就可以聽牌),那麼哪些牌是有用的牌,或者說我摸到哪些牌會留下呢?這些有用的牌稱為「有效牌」,最有用的當然是能讓我直接聽牌的牌,這類牌稱為「第一類有效牌」。

  • 第一類有效牌:能使手牌向和牌前進一步(上聽數降低)的牌,包括:
作者提供

除了第一類有效牌,有用的牌還有以下這些:

  • 第二類有效牌:不能使上聽數降低,但能使第一類有效牌增多的牌,包括:
作者提供

比如摸到九索,一般情況下應該選擇留下九索打掉三索,因為第一類有效牌變多了:(註:計算採用天鳳牌理オンライン対戦麻雀 天鳳 / 牌理。)

作者提供
  • 第三類有效牌:不能使上聽數降低,也不能使第一類有效牌增多,但能使第二類有效牌增多的牌,包括:
作者提供

比如摸到五索,一般情況下應該選擇留下三五索拆掉八九索,雖然第一類有效牌張數沒變,但三五索相比八九索多了1種第二類有效牌——六索(原是第三類有效牌)。

作者提供

(也許看到這裡,你有點算不過來,或者感覺這和你平時打的麻將壓根不是一個遊戲。沒關係,這很正常,你可以找張紙,在紙上仔細算一下每種第二類有效牌都新增了哪些第一類有效牌。)

可見,對於一開始一上聽的13張手牌而言,除了七八九筒外的所有數牌都是有用的牌。麻將的牌效率就是這樣——不斷透過有效牌增大自己的進張面,最終使得和牌的概率越來越大。也許你已經發現,麻將牌效率的本質就是一個搜索樹,最開始的手牌:

作者提供

經過多輪選擇後可能對應多種結局(和牌),例如:

作者提供

路徑:摸到第一類有效牌八萬或七索聽牌,再自摸另一張和牌(最大概率結局)。

作者提供

路徑:先摸到第二類有效牌一萬或七萬後打掉三索,然後摸到一萬或七萬的另一張聽
七索,或者摸到七索選擇聽一萬和七萬對倒和牌。

作者提供

路徑:先摸到第三類有效牌三筒後打掉三索,然後摸到四筒後拆掉八九索,之後和牌。

對於一個兩上聽以內的手牌來說,這個樹的深度最多也就是4~5步,每一步的分支平均在15種左右,也就是說複雜度最多在10^5數量級。由於每條路徑都對應著一個確定的概率,一個好的麻將AI完全可以做到遍歷這個樹,比較兩種或更多種打牌選擇之間所對應結局的和牌期望之和。

對於三上聽以外的手牌(由上文圖中可知三上聽以外的手牌約佔手牌所有組合的80%),由於手牌中會存在大量的孤張或簡單搭子,只需單獨比較孤張或簡單搭子的效率即可,計算量更小。

除了上述窮舉手牌搜索樹的方法,還可以採用模擬的方法。比如讓麻將AI在短時間內模擬兩種打法各1,000手牌,哪個和牌率更高就選哪種打法。雖然這樣不太精確但已經足夠保證比人要強了。

2. 和牌限制與番數價值

很多麻將規則對和牌有限制,比如國標麻將必須八番起和,四川麻將必須缺一門,太原麻將和牌必須包含指定牌張等等。我們只需在上述基礎牌效率算法搜索樹的基礎上,「砍掉」那些結局不符合要求的分支即可。

有些時候我們不僅關注和牌的概率,也關注和牌的大小,比如有些牌我們寧可損失一些進張也想去做清一色,追求更高的和牌得分。我們只需為樹的所有結果賦值(和牌得分),並用結局對應的值與路徑對應的概率求出不同打法的得分期望並進行比較。

3. 副露判斷

「這個牌該不該碰」似乎是打麻將時比較令人頭疼的問題。但其實副露判斷只是計算量大,並不需要特殊的算法,依然是對比碰與不碰兩種選擇所對應的所有結局的得分期望即可。日本麻將中的立直(報聽)判斷也是同理。只不過當我們在考慮「打哪張好」的時候,兩種打牌選擇之間所對應的路徑和結局有大部分都是重合的;而我們在考慮「該不該碰」的時候,兩種選擇所對應的路徑和結局基本是完全不同的,這無形中增大了計算量。其實人腦在做蒙特卡洛樹搜索時,比較容易做到「想得很深」,比如職業棋手可以提前算到20甚至30步棋;但難以做到「想得很廣」,通常情況下大腦只能做到從兩種選擇中找幾個概率較大、有代表性的結局樣本做比較。所以副露判斷顯得難,其實只是計算量的問題,而對於麻將AI來說,這不是問題。

4. 防守端

防守端需要解決的是攻守判斷和防守打法兩個問題,即「什麼時候要防守」和「要防守應該打什麼」。解決這些問題最好的方法是讓麻將AI自己透過大量的牌譜(千萬場量級)進行自我學習。正如前文我所提到的,其實人們對於麻將應該如何科學防守的研究也才剛剛開始,想要分析一個打過三筒和八筒的人真正需要的是幾筒,需要大量的牌譜作為樣本進行研究。這部分研究現在還要等待電腦去完成,未來的麻將AI在這方面要比人類做得更好可以說是必然的。對大量牌譜所做的出牌模式研究還可反過來應用於牌效率算法的改進中。比如早巡打過八萬的人手牌中有九萬的概率較小,那麼牌牆中剩餘九萬的概率就有所上升,牌效率中利用九萬的路徑的概率就可以做出相應的修正。

5. 狀況判斷

狀況判斷指的是麻將的「大局觀」,如為了爭取第一名或者為了規避第四名而採取不同的策略。狀況判斷其實就是對得分期望做進一步的修正。比如某狀況下我必須自摸13番牌才能逆轉,那麼最終結果是13番以下的牌的得分期望可以進一步降低,而13番及以上的牌的得分期望則可以提高。

總之,麻將的複雜度較低,演算法上可以用搜索樹窮舉法以及大量牌譜的自我學習來解決,只要有大量牌譜資料,有人肯花時間,有人願意出資,開發一個能勝過人類的麻將AI,非常容易。

本文授權轉載自:段昊知乎

每日精選科技圈重要消息