機(jī)器之心編譯

  機(jī)器之心編輯部

額……報(bào)道了下圍棋、打德州撲克的 AI 程序之后,小編終于看到了 AI 打麻將的一篇研究,兩位作者分別來自悉尼科技大學(xué)和陜西師范大學(xué)。不過,自信麻將技術(shù)不錯(cuò)的小編翻譯地一臉懵逼。本文強(qiáng)行為大家介紹了這篇 AI 麻將論文,感興趣的同學(xué)可以查看原英文文章。

  從 AI 研究的早期階段,游戲就開始充當(dāng)許多 AI 技術(shù)和想法的試驗(yàn)臺(tái),從跳棋、國(guó)際象棋、圍棋、撲克到星際爭(zhēng)霸 II。在過去的幾十年里,AI 程序已經(jīng)在跳棋、國(guó)際象棋、圍棋等完整信息游戲中接連打敗最優(yōu)秀的人類棋手。在這些游戲中,玩家在做出決策之前可以知道所有信息。相比較而言,非完整信息游戲更加具有挑戰(zhàn)性。最近,AI 在兩人對(duì)決有限制和無限制德州撲克游戲中都取得了重要進(jìn)展,這是人類在競(jìng)爭(zhēng)中玩的最小的撲克變體。在本文中,研究者對(duì)更流行、更復(fù)雜的麻將游戲展開了數(shù)學(xué)和 AI 研究。

  麻將是一種風(fēng)靡全世界的多人對(duì)抗游戲。一套麻將有 144 張牌,牌面上有漢字或符號(hào),其出牌規(guī)則、得分靈活多變。開始的時(shí)候,每個(gè)玩家都有 13 張牌。接下來,他們會(huì)摸牌、出牌,直到攢夠 14 張可以胡的牌型。

  在這篇論文中,研究者對(duì)麻將進(jìn)行數(shù)學(xué)和 AI 方面的研究,嘗試回答兩個(gè)最基本的問題:當(dāng)前 14 張牌的牌面到底有多好;我們?cè)摯虺瞿囊粡埮??作者定義了缺牌數(shù)的概念,并提出最優(yōu)策略來確定當(dāng)前該打的牌,以在 k 次牌面變換的條件下增加胡牌的概率。

  在此論文中,為了簡(jiǎn)化問題,我們只考慮麻將最基礎(chǔ)的打法 Mahjong-0。其他的打法可以用類推的方式處理。在 Mahjong-0 打法中,只有三類牌:

條:從 B1 至 B9 表示一條到九條,每類 4 張;

萬:從 C1 至 C9 表示一萬到九萬,每類 4 張;

筒:從 D1 至 D9 表示一筒到九筒,每類 4 張。

  此論文把牌面稱為條、萬、筒,把整副麻將記為 M_0,總共 108 張。

  麻將規(guī)則

  定義 1:將牌指一對(duì)同樣的牌,碰指三張或者四張同樣的牌。吃指同類牌組成連續(xù)的三張牌。杠子、刻子或者順子都稱之為組。

  在此論文中,作者也給出了一些非標(biāo)準(zhǔn)概念。

  定義 2:待吃是指一對(duì)同花色的牌,吃了一張牌之后能夠成為一組順子。待組是指一個(gè)待吃或者對(duì)。牌 c 能夠和 ab 組成一組,就是一攤。類似的,一張牌 t 加上另一張 t 就是一將。

  例如,B3B4B5 就是吃,C1C1 是將,B7B7B7 是碰,D9D9D9D9 是杠,B1B3 和 C2C3 都可以吃。

  論文的第二部分介紹了很多形式化的麻將規(guī)則,包括什么是清一色,怎么樣才算完整的牌面等等。例如定義 4 展示了 14 張牌的標(biāo)準(zhǔn)形式,其中作者將條、萬、筒表示為 0、1、2,因此 就表示 B3:三條。

  定義牌面的組合后,我們需要一種度量方法以確定到底當(dāng)前 14 張牌離胡牌還有多遠(yuǎn),這里作者引入了缺牌數(shù)。簡(jiǎn)單而言,缺牌數(shù)表示的就是當(dāng)前牌面到胡牌還差多少?gòu)埮啤?/p>

  理科生怎樣看待牌面?

  如果我們定義了隨機(jī) 14 張牌的牌面表示和缺牌數(shù),現(xiàn)在只需要知道怎樣評(píng)估當(dāng)前牌面的好壞,并通過打牌來把缺牌數(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è)栗子,如果我們摸上來的 14 張牌為:T = ,其中 C2 表示二萬。那么現(xiàn)在 p-decompositions 可以表示為:

  π_0 中的 并不能組成順,因?yàn)棣衉0 中已經(jīng)有 4 張 B2 了。π_1 和 π_2 都是飽和與可被組合完全的,例如π_1 缺少的牌為:

  它的成本 cost = 4。確定最優(yōu)成本后我們就需要尋找最優(yōu)策略,并盡可能在最小的輪數(shù)下將成本或缺牌數(shù)降低為 0。當(dāng)然,如果需要對(duì)打牌的過程建模,并找到最優(yōu)策略,我們還需要更多的研究。

  結(jié)語(yǔ)與討論

  在此論文中,作者開啟了對(duì)麻將的數(shù)學(xué)和 AI 研究。在設(shè)計(jì)玩麻將的計(jì)算機(jī)程序時(shí),本文先描述了缺牌數(shù)的定義,知識(shí)庫(kù)的概念和步驟 k 值扮演者重要角色。

  盡管麻將是個(gè)非常流行的棋牌游戲,但少有專門研究麻將的數(shù)學(xué)或者 AI 論文。據(jù)我們所知,Yuan Cheng 等人的論文 [4] 是首個(gè)使用數(shù)學(xué)技術(shù)嚴(yán)肅研究麻將的論文。在那篇論文中,作者們研究了麻將中一組特殊的組合問題,也就是 k-gate 問題。

  清一色的 13 張牌 T 可以稱為 nine-gate,其中我們可以向 T 中添加任意同類牌而胡牌。對(duì)于 1 ≤ k ≤ 9,如果存在不同值的 K 張牌,且只能由這 k 張牌補(bǔ)全 T,那么 T 就可以稱為 k-gate 問題。很容易看出,k-gate 問題能通過這篇論文構(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 張牌可以有不同的得分,例如,清一色比雜牌得分多。未來研究可以嘗試解決這些問題。

  論文:Let‘s Play Mahjong!

  論文地址:https://arxiv.org/pdf/1903.03294.pdf

  菜鳥發(fā)起‘2019 菜鳥全球科技挑戰(zhàn)賽—智能體積測(cè)量’,近百萬元獎(jiǎng)金等你來拿,點(diǎn)擊閱讀原文參與報(bào)名。

1.《麻將一共多少?gòu)?一篇AI打麻將的論文 理科生眼中的麻將是這樣的》援引自互聯(lián)網(wǎng),旨在傳遞更多網(wǎng)絡(luò)信息知識(shí),僅代表作者本人觀點(diǎn),與本網(wǎng)站無關(guān),侵刪請(qǐng)聯(lián)系頁(yè)腳下方聯(lián)系方式。

2.《麻將一共多少?gòu)?一篇AI打麻將的論文 理科生眼中的麻將是這樣的》僅供讀者參考,本網(wǎng)站未對(duì)該內(nèi)容進(jìn)行證實(shí),對(duì)其原創(chuàng)性、真實(shí)性、完整性、及時(shí)性不作任何保證。

3.文章轉(zhuǎn)載時(shí)請(qǐng)保留本站內(nèi)容來源地址,http://f99ss.com/tiyu/279542.html