陕西快乐十分开奖预测|陕西快乐十分今日开奖结果查询
  • 一篇AI打麻將的論文,理科生眼中的麻將是這樣的

    /2019-04-15 14:27:42/

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

    \

    從 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 張。

    麻將規則

    定義 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)。簡單而言,缺牌數表示的就是當前牌面到胡牌還差多少張牌。

    \

    理科生怎樣看待牌面?

    如果我們定義了隨機 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。當然,如果需要對打牌的過程建模,并找到最優策略,我們還需要更多的研究。

    結語與討論

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

    盡管麻將是個非常流行的棋牌游戲,但少有專門研究麻將的數學或者 AI 論文。據我們所知,Yuan Cheng 等人的論文 [4] 是首個使用數學技術(主要是基本組合理論)嚴肅研究麻將的論文。在那篇論文中,作者們研究了麻將中一組特殊的組合問題,也就是 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 張牌可以有不同的得分,例如,清一色比雜牌得分多。未來研究可以嘗試解決這些問題。


<
上一篇: 最流行的50款App,告訴你如何提高用戶粘性 下一篇: 如何用產品思維迭代項目管理流程?

聯系我們

一個新的需求,從這里開始。歡迎填寫表格或發送合作郵件至: [email protected] [email protected] 加微信: 13765801787

13765801787
在線留言
陕西快乐十分开奖预测 超级大乐透开奖结果 球探篮球比分网即时比分 贵州快三预测号码推荐 福彩快三规律破解 重庆时时彩输死多少人 穷人用时间赚钱 山西泳坛夺金 白小中特免费网站1392 内蒙古快三走势图360 qq竞彩比分直播 甘肃十一选五玩法技巧 中彩网可信吗 闲来宁夏麻将怎么开挂 湖南德州麻将 1zplay 电竞比分 尚牛电竞比分网