麻將AI難在哪？微軟宣布公開麻將AI Suphx 的十段秘籍

日前，微軟亞洲研究院在arXiv平臺(tái)上正式發(fā)表了關(guān)于麻將AI系統(tǒng)Suphx的論文，公布了Suphx背后的包括決策流程、模型架構(gòu)、訓(xùn)練算法等核心技術(shù)細(xì)節(jié)。

那么，麻將AI 到底有哪些難點(diǎn)？Suphx這一在游戲AI領(lǐng)域具有跨越性的突破具體是如何實(shí)現(xiàn)的？近日，微軟亞洲研究院Suphx研發(fā)團(tuán)隊(duì)在arXiv平臺(tái)上正式發(fā)表論文，公布了Suphx背后的核心技術(shù)。

麻將AI面臨的挑戰(zhàn)

麻將AI系統(tǒng)Suphx主要基于深度強(qiáng)化學(xué)習(xí)技術(shù)。盡管深度強(qiáng)化學(xué)習(xí)在一系列游戲AI中取得了巨大的成功，但想要將其直接應(yīng)用在麻將AI上殊為不易，面臨著若干挑戰(zhàn)。

挑戰(zhàn)一：麻將的計(jì)分規(guī)則通常都非常復(fù)雜，在如天鳳平臺(tái)等競(jìng)技麻將中，計(jì)分規(guī)則更加復(fù)雜。

首先，一輪麻將游戲通常有8局甚至更多，每一局結(jié)束后四位玩家都會(huì)有這一局的得分（可能為正，可能為負(fù)）。當(dāng)一整輪游戲都結(jié)束后，四位玩家按照所有局的累計(jì)得分排名，計(jì)算這一輪游戲的點(diǎn)數(shù)獎(jiǎng)勵(lì)。在天鳳平臺(tái)上，排在一二名的玩家會(huì)得到一定數(shù)目的點(diǎn)數(shù)，排在第三位的玩家點(diǎn)數(shù)不變，排在第四位的玩家會(huì)被扣去一定數(shù)目的點(diǎn)數(shù) 。因此玩家的點(diǎn)數(shù)和段位都可能會(huì)起起落落，當(dāng)點(diǎn)數(shù)增加到一定程度時(shí)段位上升，而點(diǎn)數(shù)扣到0時(shí)則會(huì)被降段。因此，為了提高段位，玩家需要盡量多的排在第一位或者第二位，盡量避免被排在第四位。

有趣的是，由于一輪游戲的最終點(diǎn)數(shù)是由多局的累計(jì)得分決定，所以高手可能會(huì)策略性地輸?shù)粢恍┚?，也就是說，某一局的輸贏并不能直接代表玩家打的好不好，所以不能直接使用每局的得分來作為強(qiáng)化學(xué)習(xí)的獎(jiǎng)勵(lì)反饋信號(hào)。微軟亞洲研究院的研究員們找到了一種其他的方法，會(huì)在后文中解釋。

其次，天鳳平臺(tái)上每一局游戲的計(jì)分規(guī)則都需要根據(jù)贏家手里的牌型來累計(jì)計(jì)算得分，牌型有非常多的可能，例如清一色、混一色、門清等等，不同牌型的得分會(huì)相差很大。這樣的計(jì)分規(guī)則比象棋、圍棋等游戲要復(fù)雜得多。麻將高手需要謹(jǐn)慎選擇牌型，以在胡牌的概率和胡牌的得分上進(jìn)行平衡，從而取得第一、二位或者擺脫第四位。

挑戰(zhàn)二：從博弈論的角度來看，麻將是多人非完美信息博弈。麻將一共有136張牌，每一位玩家只能看到很少的牌，包括自己的13張手牌和所有人打出來的牌，更多的牌是看不到，包括另外三位玩家的手牌以及墻牌。面對(duì)如此多的隱藏未知信息，麻將玩家很難僅根據(jù)自己的手牌做出一個(gè)很好的決策。

挑戰(zhàn)三：麻將除了計(jì)分規(guī)則復(fù)雜之外，打法也比較復(fù)雜，需要考慮多種決策類型，例如，除了正常的摸牌、打牌之外，還要經(jīng)常決定是否吃牌、碰牌、杠牌、立直以及是否胡牌。任意一位玩家的吃碰杠以及胡牌都會(huì)改變摸牌的順序，因此研究員們很難為麻將構(gòu)建一棵規(guī)則的博弈樹（game tree）。即使去構(gòu)建一棵博弈樹，那么這棵博弈樹也會(huì)非常龐大，并且有不計(jì)其數(shù)的分支，導(dǎo)致以前一些很好的方法，如蒙特卡洛樹搜索(MCTS)、蒙特卡洛反事實(shí)遺憾最小化(MCCFR)算法等都無法直接被應(yīng)用。

Suphx的決策流程及模型架構(gòu)

Suphx的打牌策略包含5個(gè)需要訓(xùn)練的模型，以應(yīng)對(duì)麻將復(fù)雜的決策類型——丟牌模型、立直模型、吃牌模型、碰牌模型以及杠牌模型，5個(gè)模型都基于深度殘差卷積神經(jīng)網(wǎng)絡(luò)。另外Suphx還有一個(gè)基于規(guī)則的贏牌模型決定在可以贏牌的時(shí)候要不要贏牌。

圖1：Suphx決策流程

這些模型的輸入包含了兩大類信息：

1. 當(dāng)前可觀測(cè)的信息，例如玩家自己的手牌、公開牌（包括丟出來的牌、碰的牌、明杠的牌），以及每個(gè)玩家的累計(jì)得分、座位、段位等等。

2. 對(duì)將來進(jìn)行預(yù)測(cè)的信息，比如打某張牌還需要拿幾張牌才能胡牌、能夠贏多少分、胡牌概率有多大，等等。

Suphx訓(xùn)練算法

Suphx訓(xùn)練過程分為三個(gè)主要步驟：首先使用來自天鳳平臺(tái)的高手打牌記錄，通過監(jiān)督學(xué)習(xí)來訓(xùn)練這5個(gè)模型，然后使用自我博弈強(qiáng)化學(xué)習(xí)以及由微軟亞洲研究院Suphx研發(fā)團(tuán)隊(duì)設(shè)計(jì)的兩個(gè)技術(shù)解決麻將本身的獨(dú)特性所帶來的挑戰(zhàn)，最后在實(shí)戰(zhàn)時(shí)采用在線策略自適應(yīng)算法來進(jìn)一步提高Suphx的能力。

分布式強(qiáng)化學(xué)習(xí)

Suphx的整個(gè)訓(xùn)練過程十分復(fù)雜，需要多GPU和多CPU協(xié)同，因此Suphx研發(fā)團(tuán)隊(duì)采用了分布式架構(gòu)（圖2所示）。架構(gòu)包括一個(gè)參數(shù)服務(wù)器以及多個(gè)自我博弈節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)里包含了多個(gè)麻將的模擬器以及多個(gè)推理引擎來進(jìn)行多個(gè)策略之間的博弈（即打麻將）。每個(gè)自我博弈節(jié)點(diǎn)定期將打牌的記錄發(fā)送給參數(shù)服務(wù)器，參數(shù)服務(wù)器會(huì)利用這些打牌記錄來訓(xùn)練提高當(dāng)前策略。每過一段時(shí)間，自我博弈節(jié)點(diǎn)就會(huì)從參數(shù)服務(wù)器拿回最新的策略，用來進(jìn)行下一階段的自我博弈。

圖2：分布式訓(xùn)練

全局獎(jiǎng)勵(lì)預(yù)測(cè)

麻將的計(jì)分規(guī)則很復(fù)雜——玩家每局有得分，一輪游戲根據(jù)多局累計(jì)分?jǐn)?shù)的排名計(jì)算點(diǎn)數(shù)。如何讓麻將AI知道自己打得好不好呢？

無論是每局得分還是一輪游戲的最終點(diǎn)數(shù)，都不適合用來做強(qiáng)化學(xué)習(xí)訓(xùn)練的反饋信號(hào)。以最終獎(jiǎng)勵(lì)點(diǎn)數(shù)作為反饋信號(hào)不能區(qū)分打得好的局和打得差的局，因此研究員們需要對(duì)每局都單獨(dú)提供強(qiáng)化學(xué)習(xí)的訓(xùn)練信號(hào)。但單獨(dú)計(jì)算每局分?jǐn)?shù)也未必能反映出一局打的好壞，因?yàn)轫敿?jí)玩家會(huì)策略性輸牌，比如，在一輪游戲的最后一兩局中，累計(jì)得分排位第一的選手在累計(jì)分?jǐn)?shù)領(lǐng)先較大的情況下，會(huì)有意識(shí)地讓排位第三或第四的選手贏下這一局，不讓排第二位的玩家贏，這樣就可以穩(wěn)穩(wěn)地保住總排位第一。也就是說，某一局得分為負(fù)不一定意味著策略不好。

因此，為了給強(qiáng)化學(xué)習(xí)訓(xùn)練提供有效的信號(hào)，需要將最終的游戲獎(jiǎng)勵(lì)適當(dāng)?shù)貧w因到每一輪的游戲中。Suphx研發(fā)團(tuán)隊(duì)引入了一個(gè)全局獎(jiǎng)勵(lì)預(yù)測(cè)器，它可以基于本局的信息和之前的所有局信息預(yù)測(cè)出最終的游戲獎(jiǎng)勵(lì)。在Suphx中，獎(jiǎng)勵(lì)預(yù)測(cè)器是一個(gè)遞歸神經(jīng)網(wǎng)絡(luò) (GRU)，訓(xùn)練數(shù)據(jù)來自于高手玩家在天鳳平臺(tái)的歷史記錄。預(yù)測(cè)器訓(xùn)練好后，對(duì)于自我博弈生成的游戲，Suphx研發(fā)團(tuán)隊(duì)用當(dāng)前局預(yù)測(cè)的最終獎(jiǎng)勵(lì)和上一局預(yù)測(cè)的最終獎(jiǎng)勵(lì)之間的差值作為該局強(qiáng)化學(xué)習(xí)訓(xùn)練的反饋信號(hào)。

先知教練

麻將中存在著豐富的隱藏信息，如其他玩家的手牌、墻牌等，如果不能獲得這些隱藏信息，那么就很難確保某個(gè)動(dòng)作（例如丟三萬）的好壞，這也是麻將很難的一個(gè)根本原因。在這種情況下，雖然Suphx可以通過強(qiáng)化學(xué)習(xí)來提高策略，但學(xué)習(xí)速度會(huì)非常慢。

為了加快強(qiáng)化學(xué)習(xí)訓(xùn)練的速度，Suphx研發(fā)團(tuán)隊(duì)引入了一個(gè)“先知”，它可以看到所有的信息，包括(1)玩家自己的私有手牌，(2)所有玩家的公開牌，(3)其他公共信息， (4)其他三個(gè)玩家的私有手牌，(5)墻牌。只有(1)(2)和(3)是正常的玩家可以獲得的，而(4)和(5)是只有“先知”才能獲得的額外的"完美"信息。

圖3：左邊為正?？捎^測(cè)信息，右邊為完全信息（包括對(duì)手手牌墻牌這些“完美”信息）

有了這些“不公平”的完美信息，“先知”在經(jīng)過強(qiáng)化學(xué)習(xí)訓(xùn)練后，很容易成為麻將超級(jí)高手，安定段位也很容易就可以超過20段。如何利用“先知”來引導(dǎo)和加速AI的訓(xùn)練呢？實(shí)驗(yàn)表明，簡(jiǎn)單的知識(shí)萃取（knowledge distillation）或者模仿學(xué)習(xí)（imitation learning）并不能很好地把“先知”的“超能力”轉(zhuǎn)移到AI系統(tǒng)上——對(duì)于一個(gè)只能獲取有限信息的正常AI來說，它很難模仿一個(gè)訓(xùn)練有素的“先知”的行為，因?yàn)椤跋戎钡哪芰μ珡?qiáng)，普通AI無法理解。比如，“先知”看到了其他玩家的手牌，知道每個(gè)玩家胡什么牌，所以它可以打出絕對(duì)安全的牌，避免點(diǎn)炮，然而正常的AI并沒有這些信息，它可能完全不能理解為什么“先知”會(huì)打這張牌，所以也不能學(xué)到這種行為。因此，研究人員需要一個(gè)更聰明的方法，用“先知”來引導(dǎo)正常AI的訓(xùn)練。

在Suphx中，Suphx研發(fā)團(tuán)隊(duì)首先使用包括完美信息在內(nèi)的所有特征來對(duì)“先知”進(jìn)行強(qiáng)化學(xué)習(xí)訓(xùn)練，在這一步中控制“先知”的學(xué)習(xí)進(jìn)度，不能讓其過于強(qiáng)大。然后，通過對(duì)完美特征增加mask逐漸使“先知”最終過渡到正常AI。接著，繼續(xù)訓(xùn)練正常AI并進(jìn)行一定數(shù)量的迭代，采用衰減學(xué)習(xí)率和拒絕采樣的技巧來調(diào)整訓(xùn)練過程，讓AI的技術(shù)不斷精進(jìn)。

參數(shù)化的蒙特卡洛策略自適應(yīng)

對(duì)一個(gè)麻將高手來說，初始手牌不同時(shí)，打牌策略也會(huì)有很大的不同。例如，如果初始手牌好，他會(huì)積極進(jìn)攻，以獲得更多的得分；如果初始手牌不好，他會(huì)傾向防守，放棄胡牌，以減少損失。這與此前的圍棋AI和星際爭(zhēng)霸等游戲AI有很大的不同。所以，如果能夠在對(duì)戰(zhàn)過程中對(duì)線下訓(xùn)練的策略進(jìn)行調(diào)整，那么就可以得到更強(qiáng)的麻將AI。

蒙特卡洛樹搜索(MCTS)是圍棋等游戲AI中一種成熟的技術(shù)，以提高對(duì)戰(zhàn)時(shí)的勝率。然而遺憾的是，如前所述，麻將的摸牌、打牌順序并不固定，很難建立一個(gè)規(guī)則的博弈樹。因此，MCTS不能直接應(yīng)用于麻將AI。在Suphx中，Suphx研發(fā)團(tuán)隊(duì)設(shè)計(jì)了一種新的方法，命名為參數(shù)蒙特卡洛策略自適應(yīng)（pMCPA）。

當(dāng)初始的手牌發(fā)到麻將AI手中時(shí)，通過模擬來調(diào)整離線訓(xùn)練好的策略，使其更適應(yīng)這個(gè)給定的初始手牌。微軟亞洲研究院的實(shí)驗(yàn)表明，相對(duì)麻將隱藏信息集的平均大小10的48+次方倍而言，模擬的次數(shù)不需要很大，pMCPA也并不需要為這一局手牌收集所有可能后續(xù)狀態(tài)的統(tǒng)計(jì)數(shù)據(jù)。由于pMCPA是一種參數(shù)化的方法，所以微調(diào)更新后的策略可以幫助研究團(tuán)隊(duì)將從有限的模擬中獲得的知識(shí)推廣泛化到未見過的狀態(tài)。

天鳳平臺(tái)在線實(shí)戰(zhàn)

在經(jīng)歷這樣的訓(xùn)練后，Suphx就可以“出道”了。Suphx已在天鳳平臺(tái)特上房和其他玩家對(duì)戰(zhàn)了5000多場(chǎng)，達(dá)到了該房間目前的最高段位10段，其安定段位達(dá)到了8.7段（如圖4所示），超過了平臺(tái)上另外兩個(gè)知名AI以及頂級(jí)人類選手的平均水平。

圖4：天鳳平臺(tái)“特上房”安定段位對(duì)比

在實(shí)戰(zhàn)中Suphx非常擅長(zhǎng)防守，它的4位率和點(diǎn)炮率（deal-in rate）都尤其低（如圖5）。此外，Suphx“牌風(fēng)”比較鮮明，也另辟蹊徑地創(chuàng)造了許多新的策略和打法，例如它特別擅長(zhǎng)保留安全牌，傾向于胡混一色等等。圖6展示了Suphx在天鳳平臺(tái)實(shí)戰(zhàn)時(shí)保留安全牌的一個(gè)例子。當(dāng)前時(shí)刻Suphx（南家）需要丟牌，人類玩家在這時(shí)通常會(huì)丟北風(fēng)，但是Suphx丟掉一張7條，這在人類玩家看起來會(huì)覺得很不尋常，因?yàn)?條是一張好牌，丟掉7條會(huì)使得胡牌的進(jìn)度變慢。Suphx之所以丟掉7條而留住北風(fēng)，是因?yàn)楸憋L(fēng)是一張安全牌，這樣在未來某一時(shí)刻，如果有人突然立直要胡牌了，Suphx可以打出北風(fēng)而不點(diǎn)炮，這樣后面還有機(jī)會(huì)胡牌；如果它在前面已經(jīng)把北風(fēng)丟掉，那這個(gè)時(shí)候?yàn)榱舜虺鲆粡埌踩凭筒坏貌徊鸬羰掷锏暮门?，從而大大降低了胡牌的可能?/p>

圖5：Suphx在對(duì)戰(zhàn)中的一些統(tǒng)計(jì)數(shù)據(jù)，包括1/2/3/4位率、胡牌率以及點(diǎn)炮率（注：上表格中的Bakuuchi即東京大學(xué)/HEROZ研發(fā)的麻將AI“爆打”）

圖6：Suphx（南邊位置）保留安全牌北風(fēng)

許多觀看 Suphx比賽的玩家表示在觀戰(zhàn)過程中受到了啟發(fā)，甚至有麻將愛好者將Suphx稱作“麻將教科書”、“Suphx老師”，通過學(xué)習(xí)Suphx的打法來提升和豐富自己的麻將技巧。

“我已經(jīng)看了300多場(chǎng) Suphx的比賽，我甚至不再觀看人類玩家的比賽了。我從Suphx身上學(xué)到了很多新技術(shù)，它們對(duì)于我的三人麻將打法有著非常大的啟發(fā)，”麻將選手太くないお在社交媒體上說，他是第一位在四人麻將和三人麻將中均取得天鳳位的頂級(jí)玩家。

據(jù)介紹，Suphx在天鳳平臺(tái)上取得的成績(jī)只是一個(gè)開始，未來，微軟亞洲研究院將為Suphx引入更多新技術(shù)，繼續(xù)推動(dòng)麻將AI和不完美信息游戲研究的前沿。