您的位置:首頁 > 宏觀 >

在圍棋上碾壓李世石后,人工智能在麻將領域能夠戰勝人類嗎

2016-03-17 11:13:35 來源:

評論

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

一. 麻將和圍棋有什么不同?

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

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

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

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

二. 何謂「獲勝」?

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

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

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

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

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

三. 麻將會成為人類面對人工智能的「最后壁壘」嗎?

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

首先,麻將的復雜度要遠遠小于圍棋。單就自己的 14 張手牌來說(總牌數 136 張),組合共有326520504500 種(計算方法詳見麻雀の數學),遠遠小于圍棋的 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》,全文詳見http://www.logos.ic.i.u-tokyo.ac.jp/~mizukami/paper/jousho_2014.pdf。

爆打從 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. 基礎牌效率

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

下圖牌畫取自聯眾國標麻將(http://gbmj.lianzhong.com)。

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

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

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

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

比如摸到九索,一般情況下應該選擇留下九索打掉三索,因為第一類有效牌變多了:

計算采用天鳳牌理オンライン対戦麻雀 天鳳 / 牌理。

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

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

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

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

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

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

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

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

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

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

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

2. 和牌限制與番數價值

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

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

3. 副露判斷

「這個牌該不該碰」似乎是打麻將時比較令人頭疼的問題。但其實副露判斷只是計算量大,并不需要特殊的算法,依然是對比碰與不碰兩種選擇所對應的所有結局的得分期望即可。日本麻將中的立直(報聽)判斷也是同理。

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

4. 防守端

防守端需要解決的是攻守判斷和防守打法兩個問題,即「什么時候要防守」和「要防守應該打什么」。解決這些問題最好的方法是讓麻將 AI 自己通過大量的牌譜(千萬場量級)進行自我學習。正如前文我所提到的,其實人們對于麻將應該如何科學防守的研究也才剛剛開始,想要分析一個打過三筒和八筒的人真正需要的是幾筒,需要大量的牌譜作為樣本進行研究。這部分研究現在還要等待電腦去完成,未來的麻將 AI 在這方面要比人類做得更好可以說是必然的。

對大量牌譜所做的出牌模式研究還可反過來應用于牌效率算法的改進中。比如早巡打過八萬的人手牌中有九萬的概率較小,那么牌墻中剩余九萬的概率就有所上升,牌效率中利用九萬的路徑的概率就可以做出相應的修正。

5. 狀況判斷

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

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

[責任編輯:]

相關閱讀

參與評論

每日推薦

圖片新聞

涪陵視覺

900彩票