知識星球
作者：Sanjiang Li、Xueqing Yan
來源：機器之心（ID：almosthuman2014）編譯
從 AI 研究的早期階段，遊戲就開始充當許多 AI 技術和想法的試驗臺，從跳棋、國際象棋、圍棋、撲克到星際爭霸 II。在過去的幾十年裡，AI 程式已經在跳棋、國際象棋、圍棋等完整資訊遊戲中接連打敗最優秀的人類棋手。
在這些遊戲中，玩家在做出決策之前可以知道所有資訊。相比較而言，非完整資訊遊戲更加具有挑戰性。最近，AI 在兩人對決有限制和無限制德州撲克遊戲中都取得了重要進展，這是人類在競爭中玩的最小的撲克變體。
在本文中，研究者對更流行、更複雜的麻將遊戲展開了數學和 AI 研究。
麻將是一種風靡全世界的多人對抗遊戲。一套麻將有 144 張牌，牌面上有漢字或符號（見圖 1），其出牌規則、得分靈活多變。開始的時候，每個玩家都有 13 張牌。接下來，他們會摸牌、出牌，直到攢夠 14 張可以胡的牌型。
在這篇論文中，研究者對麻將進行數學和 AI 方面的研究，嘗試回答兩個最基本的問題：當前 14 張牌的牌面到底有多好；我們該打出哪一張牌？作者定義了缺牌數的概念，並提出最優策略來確定當前該打的牌，以在 k 次牌面變換（k ≥ 1）的條件下增加胡牌的機率。
在此論文中，為了簡化問題，我們只考慮麻將最基礎的打法 Mahjong-0。其他的打法可以用類推的方式處理。在 Mahjong-0 打法中，只有三類牌：
-
條：從 B1 至 B9 表示一條到九條，每類 4 張；
-
萬：從 C1 至 C9 表示一萬到九萬，每類 4 張；
-
筒：從 D1 至 D9 表示一筒到九筒，每類 4 張。
此論文把牌面稱為條（B）、萬（C）、筒（D），把整副麻將記為 M_0，總共 108 張。
01 麻將規則
定義 1：將牌（eye）指一對同樣的牌，碰（槓）指三張或者四張同樣的牌。吃（chow）指同類牌組成連續的三張牌。槓子、刻子或者順子都稱之為組（meld）。
在此論文中，作者也給出了一些非標準概念。
定義 2：待吃（pseudochow，縮寫為 pchow）是指一對同花色的牌，吃了一張牌之後能夠成為一組順子。待組（pseudomeld，縮寫為 pmeld）是指一個待吃或者對。牌 c 能夠和 ab 組成一組，就是一攤（abc）。類似的，一張牌 t 加上另一張 t 就是一將。
例如，B3B4B5 就是吃，C1C1 是將，B7B7B7 是碰，D9D9D9D9 是槓，B1B3 和 C2C3 都可以吃。
論文的第二部分介紹了很多形式化的麻將規則，包括什麼是清一色，怎麼樣才算完整的牌面（胡牌）等等。例如定義 4 展示了 14 張牌的標準形式，其中作者將條（B）、萬（C）、筒（D）表示為 0、1、2，因此 (0, 3) 就表示 B3：三條。
定義牌面的組合後，我們需要一種度量方法以確定到底當前 14 張牌離胡牌還有多遠，這裡作者引入了缺牌數（deficiency）。簡單而言，缺牌數表示的就是當前牌面到胡牌還差多少張牌。
02 理科生怎樣看待牌面？
如果我們定義了隨機 14 張牌的牌面表示和缺牌數，現在只需要知道怎樣評估當前牌面的好壞，並透過打牌來把缺牌數降低到 0 就行了。首先對於清一色的 14 張牌，它的缺牌數少於等於 3 張，論文的第三章主要就在討論和證明這一點。
如下對於清一色的牌，只有在以下情況才會令缺牌數為 3：
對於常規牌，最大的缺牌數為 6，論文的第四章主要就在討論和證明這一點。
現在根據缺牌數的定義與證明，我們就能度量當前牌面的好壞。我們首先需要定義根據缺牌完善後的完整牌面，然後計算缺牌和胡牌之間的成本。
這裡我們可以舉個慄子，如果我們摸上來的 14 張牌為：T = (B1B1B2B2B2B2B3B3)(C1C2C8)(D2D2D8)，其中 C2 表示二萬。那麼現在 p-decompositions 可以表示為：
π_0 中的 (B1 B3) 並不能組成順，因為π_0 中已經有 4 張 B2 了。π_1 和 π_2 都是飽和與可被組合完全的，例如π_1 缺少的牌為：
它的成本 cost (π_1) = 4。確定最優成本後我們就需要尋找最優策略，並盡可能在最小的輪數下將成本或缺牌數降低為 0。當然，如果需要對打牌的過程建模，並找到最優策略，我們還需要更多的研究。
03 結語與討論
在此論文中，作者開啟了對麻將的數學和 AI 研究。在設計玩麻將的計算機程式時，本文先描述了缺牌數的定義，知識庫的概念和步驟 k 值扮演者重要角色。
儘管麻將是個非常流行的棋牌遊戲，但少有專門研究麻將的數學或者 AI 論文。據我們所知，Yuan Cheng 等人的論文是首個使用數學技術（主要是基本組合理論）嚴肅研究麻將的論文。在那篇論文中，作者們研究了麻將中一組特殊的組合問題，也就是 k-gate 問題。
清一色的 13 張牌 T 可以稱為 nine-gate，其中我們可以向 T 中新增任意同類牌而胡牌。對於 1 ≤ k ≤ 9，如果存在不同值的 K 張牌，且只能由這 k 張牌補全 T，那麼 T 就可以稱為 k-gate 問題。
很容易看出，k-gate 問題能透過這篇論文構建的形式化表達進行描述。為了找到所有的 k-gate，我們只需要為每一個清一色的 13 張牌做決策，而不需要管是否正好有 k 張牌使得 T 加上 i 就能補全。
至少有三個可以擴充套件上述研究的方向。
-
首先，我們可以在 M_0 中囊括更多牌，例如，東南西北這些風牌，紅中、發財、白板這些箭牌，以及花牌。
-
其次，我們可以增加或者減少 14 張手牌的規定，例如可以允許任意 7 對，或者要求至少兩個花色。
-
第三，不同的 14 張牌可以有不同的得分，例如，清一色比雜牌得分多。未來研究可以嘗試解決這些問題。
論文：Let’s Play Mahjong!
https://arxiv.org/pdf/1903.03294.pdf
