一篇AI打麻將的論文，理科生眼中的麻將是這樣的
從 AI 研究的早期階段，游戲就開(kāi)始充當(dāng)許多 AI 技術(shù)和想法的試驗(yàn)臺(tái)，從跳棋、國(guó)際象棋、圍棋、撲克到星際爭(zhēng)霸 II。在過(guò)去的幾十年里，AI 程序已經(jīng)在跳棋、國(guó)際象棋、圍棋等完整信息游戲中接連打敗人類(lèi)棋手。在這些游戲中，玩家在做出決策之前可以知道所有信息。相比較而言，非完整信息游戲更加具有挑戰(zhàn)性。最近，AI 在兩人對(duì)決游戲中都取得了重要進(jìn)展，這是人類(lèi)在競(jìng)爭(zhēng)中玩的最小的撲克變體。在本文中，研究者對(duì)更流行、更復(fù)雜的麻將游戲展開(kāi)了數(shù)學(xué)和 AI 研究。
麻將是一種風(fēng)靡全世界的多人對(duì)抗游戲。一套麻將有 144 張牌，牌面上有漢字或符號(hào)(見(jiàn)圖 1)，其出牌規(guī)則、得分靈活多變。開(kāi)始的時(shí)候，每個(gè)玩家都有 13 張牌。接下來(lái)，他們會(huì)摸牌、出牌，直到攢夠 14 張可以胡的牌型。
在這篇論文中，研究者對(duì)麻將進(jìn)行數(shù)學(xué)和 AI 方面的研究，嘗試回答兩個(gè)最基本的問(wèn)題：當(dāng)前 14 張牌的牌面到底有多好;我們?cè)摯虺瞿囊粡埮?作者定義了缺牌數(shù)的概念，并提出相對(duì)較優(yōu)策略來(lái)確定當(dāng)前該打的牌，以在 k 次牌面變換(k ≥ 1)的條件下增加胡牌的概率。
在此論文中，為了簡(jiǎn)化問(wèn)題，我們只考慮麻將最基礎(chǔ)的打法 Mahjong-0。其他的打法可以用類(lèi)推的方式處理。在 Mahjong-0 打法中，只有三類(lèi)牌：
- 條：從 B1 至 B9 表示一條到九條，每類(lèi) 4 張;
- 萬(wàn)：從 C1 至 C9 表示一萬(wàn)到九萬(wàn)，每類(lèi) 4 張;
- 筒：從 D1 至 D9 表示一筒到九筒，每類(lèi) 4 張。
此論文把牌面稱(chēng)為條(B)、萬(wàn)(C)、筒(D)，把整副麻將記為 M_0，總共 108 張。
麻將規(guī)則
定義 1：將牌(eye)指一對(duì)同樣的牌，碰(杠)指三張或者四張同樣的牌。吃(chow)指同類(lèi)牌組成連續(xù)的三張牌。杠子、刻子或者順子都稱(chēng)之為組(meld)。
在此論文中，作者也給出了一些非標(biāo)準(zhǔn)概念。
定義 2：待吃(pseudochow，縮寫(xiě)為 pchow)是指一對(duì)同花色的牌，吃了一張牌之后能夠成為一組順子。待組(pseudomeld，縮寫(xiě)為 pmeld)是指一個(gè)待吃或者對(duì)。牌 c 能夠和 ab 組成一組，就是一攤(abc)。類(lèi)似的，一張牌 t 加上另一張 t 就是一將。例如，B3B4B5 就是吃，C1C1 是將，B7B7B7 是碰，D9D9D9D9 是杠，B1B3 和 C2C3 都可以吃。
論文的第二部分介紹了很多形式化的麻將規(guī)則，包括什么是清一色，怎么樣才算完整的牌面(胡牌)等等。例如定義 4 展示了 14 張牌的標(biāo)準(zhǔn)形式，其中作者將條(B)、萬(wàn)(C)、筒(D)表示為 0、1、2，因此 (0, 3) 就表示 B3：三條。
定義牌面的組合后，我們需要一種度量方法以確定到底當(dāng)前 14 張牌離胡牌還有多遠(yuǎn)，這里作者引入了缺牌數(shù)(deficiency)。簡(jiǎn)單而言，缺牌數(shù)表示的就是當(dāng)前牌面到胡牌還差多少?gòu)埮啤?/p>
理科生怎樣看待牌面?
如果我們定義了隨機(jī) 14 張牌的牌面表示和缺牌數(shù)，現(xiàn)在只需要知道怎樣評(píng)估當(dāng)前牌面的好壞，并通過(guò)打牌來(lái)把缺牌數(shù)降低到 0 就行了。首先對(duì)于清一色的 14 張牌，它的缺牌數(shù)少于等于 3 張，論文的第三章主要就在討論和證明這一點(diǎn)。
如下對(duì)于清一色的牌，只有在以下情況才會(huì)令缺牌數(shù)為 3：
對(duì)于常規(guī)牌，缺牌數(shù)為上限 6，論文的第四章主要就在討論和證明這一點(diǎn)。
現(xiàn)在根據(jù)缺牌數(shù)的定義與證明，我們就能度量當(dāng)前牌面的好壞。我們首先需要定義根據(jù)缺牌完善后的完整牌面，然后計(jì)算缺牌和胡牌之間的成本。
這里我們可以舉個(gè)栗子，如果我們摸上來(lái)的 14 張牌為：T = (B1B1B2B2B2B2B3B3)(C1C2C8)(D2D2D8)，其中 C2 表示二萬(wàn)。那么現(xiàn)在 p-decompositions 可以表示為：
π_0 中的 (B1 B3) 并不能組成順，因?yàn)?pi;_0 中已經(jīng)有 4 張 B2 了。π_1 和 π_2 都是飽和與可被組合完全的，例如π_1 缺少的牌為：
它的成本 cost (π_1) = 4。確定理想成本后我們就需要尋找理想策略，并盡可能在最小的輪數(shù)下將成本或缺牌數(shù)降低為 0。當(dāng)然，如果需要對(duì)打牌的過(guò)程建模，并找到理想策略，我們還需要更多的研究。
結(jié)語(yǔ)與討論
在此論文中，作者開(kāi)啟了對(duì)麻將的數(shù)學(xué)和 AI 研究。在設(shè)計(jì)玩麻將的計(jì)算機(jī)程序時(shí)，本文先描述了缺牌數(shù)的定義，知識(shí)庫(kù)的概念和步驟 k 值扮演者重要角色。
盡管麻將是個(gè)非常流行的游戲，但少有專(zhuān)門(mén)研究麻將的數(shù)學(xué)或者 AI 論文。據(jù)我們所知，Yuan Cheng 等人的論文 [4] 是一個(gè)使用數(shù)學(xué)技術(shù)(主要是基本組合理論)嚴(yán)肅研究麻將的論文。在那篇論文中，作者們研究了麻將中一組特殊的組合問(wèn)題，也就是 k-gate 問(wèn)題。
清一色的 13 張牌 T 可以稱(chēng)為 nine-gate，其中我們可以向 T 中添加任意同類(lèi)牌而胡牌。對(duì)于 1 ≤ k ≤ 9，如果存在不同值的 K 張牌，且只能由這 k 張牌補(bǔ)全 T，那么 T 就可以稱(chēng)為 k-gate 問(wèn)題。很容易看出，k-gate 問(wèn)題能通過(guò)這篇論文構(gòu)建的形式化表達(dá)進(jìn)行描述。為了找到所有的 k-gate，我們只需要為每一個(gè)清一色的 13 張牌做決策，而不需要管是否正好有 k 張牌使得 T 加上 i 就能補(bǔ)全。
至少有三個(gè)可以擴(kuò)展上述研究的方向。首先，我們可以在 M_0 中囊括更多牌，例如，東南西北這些風(fēng)牌，紅中、發(fā)財(cái)、白板這些箭牌，以及花牌。其次，我們可以增加或者減少 14 張手牌的規(guī)定，例如可以允許任意 7 對(duì)，或者要求至少兩個(gè)花色。第三，不同的 14 張牌可以有不同的得分，例如，清一色比雜牌得分多。未來(lái)研究可以嘗試解決這些問(wèn)題。
論文：Let's Play Mahjong!
論文地址：https://arxiv.org/pdf/1903.03294.pdf
【本文是51CTO專(zhuān)欄機(jī)構(gòu)“機(jī)器之心”的原創(chuàng)譯文，微信公眾號(hào)“機(jī)器之心( id: almosthuman2014)”】
