快手開源鬥地主AI,入選ICML,能否幹得過「冠軍」柯潔?

機器之心編輯部

AI 打鬥地主,除了資訊不完全,還要學會合作與競爭。

眾所周知,AI 在圍棋上的實力是人類所不能及的。不過鬥地主還不一定。在 2017 年 AlphaGo 3 比 0 戰勝中國棋手,被授予職業九段之後,柯潔決定參加鬥地主比賽,並獲得了冠軍。在當時的賽後採訪中,柯潔表示,「很歡樂,希望以後再多拿一些冠軍,無論什麼樣的冠軍都想拿!」

但是好景不長,在這種隨機性更高的遊戲上, AI 緊隨而至。

近日,快手 AI 平臺部的研究者用非常簡單的方法在鬥地主遊戲中取得了突破,幾天內就戰勝了所有已知的鬥地主打牌機器人,並達到了人類玩家水平。而且,復現這個研究只需要一個普通的四卡 GPU 伺服器。

隨著鬥地主 AI 的不斷進化,人(Ke)類(Jie)的鬥地主冠軍寶座不知還能否保住。

人工智慧在很多棋牌類遊戲中取得了很大的成功,例如阿爾法狗(圍棋)、冷撲大師(德州撲克)、Suphx(麻將)。但鬥地主卻因其極大的狀態空間、豐富的隱含資訊、複雜的牌型和並存的合作與競技,一直以來被認為是一個極具挑戰的領域。

近日,快手 AI 平臺部在鬥地主上取得了突破,提出了首個從零開始的鬥地主人工智慧系統——鬥零(DouZero)。

比較有趣的是,該系統所使用的演算法極其簡單卻非常有效。團隊創新性地將傳統的蒙特卡羅方法(即我們初高中課本中常說的「用頻率估計概率」)與深度學習相結合,並提出了動作編碼機制來應付鬥地主複雜的牌型組合。

該演算法在不借助任何人類知識的情況下,通過自我博弈學習,在幾天內戰勝了所有已知的鬥地主打牌機器人,並達到了人類玩家水平。相關論文已被國際機器學習頂級會議 ICML 2021 接收,論文程式碼也已開源。同時,論文作者開放了線上演示平臺供研究者和鬥地主愛好者體驗。

  • 論文連結:https://arxiv.org/abs/2106.06135

  • GitHub 連結:https://github.com/kwai/DouZero

  • 線上演示:(電腦打開效果更佳;如果訪問太慢,可從 GitHub 上下載並離線安裝:https://github.com/datamllab/rlcard-showdown)

線上演示支持中文和英文。使用者可以選擇明牌 / 暗牌,並可以調節 AI 出牌速度。在明牌模式下,使用者可以看到 AI 預測出的最好的三個牌型和預計勝率。

讓 AI 玩鬥地主難在哪兒?

讓 AI 玩鬥地主難在哪兒?

一直以來,鬥地主都被視為一個極具挑戰性的領域。首先,與許多撲克遊戲和麻將一樣,鬥地主屬於非完美資訊遊戲(玩家不能看到其他玩家的手牌),且包含很多「運氣」成分。因此,鬥地主有非常複雜的博弈樹,以及非常大的狀態空間(每個狀態代表一種可能遇到的情況)。除此之外,相較於德州撲克和麻將,鬥地主還有兩個獨特的挑戰:

  • 合作與競爭並存:無論是德州撲克還是麻將,玩家之間都是競爭關係。然而,在鬥地主中,兩個農民玩家要相互配合對抗地主。雖然過去有論文研究過遊戲中的合作關係 [1],但是同時考慮合作和競爭仍然是一個很大的挑戰。

  • 龐大而複雜的牌型:鬥地主有複雜的牌型結構,例如單張、對子、三帶一、順子、炸彈等等。

它們的組合衍生出了 27,472 種牌型 [2]:

在強化學習裡,這些牌型被稱為動作空間。作為對比,這裡列舉出了常見強化學習環境及棋牌類遊戲的動作空間大小:

雖然無限注德州撲克本身有與鬥地主有相同數量級的動作空間,但是其動作空間很容易通過抽象的方式縮小,即把類似的動作合併成一個。例如,加註 100 和加註 101 沒有很大的區別,可以合併成一個。然而,鬥地主中一個動作中的每張牌都很重要,且很難進行抽象。例如,三帶一中帶的單張可以是任意手牌。選錯一次(比如拆掉了一個順子)就很可能導致輸掉整局遊戲。

幾乎所有的強化學習論文都只考慮了很小動作集的情況,例如最常用的環境雅達利只有十幾個動作。有部分論文考慮了較大動作集的環境,但一般也只有幾百個。鬥地主卻有上萬個可能的動作,並且不同狀態有不同的合法動作子集,這無疑給設計強化學習演算法帶來了很大挑戰。之前的研究表明,常用的強化學習演算法,如 DQN 和 A3C,在鬥地主上僅僅略微好於隨機策略[2][3]。

「鬥零」是怎麼鬥地主的?

比較有趣的是,鬥零的核心演算法極其簡單。鬥零的設計受啟發於蒙特卡羅方法(Monte-Carlo Methods)[4]。具體來說,演算法的目標是學習一個價值網路。網路的輸入是當前狀態和一個動作,輸出是在當前狀態做這個動作的期望收益(比如勝率)。簡單來說,價值網路在每一步計算出哪種牌型贏的概率最大,然後選擇最有可能贏的牌型。蒙特卡羅方法不斷重複以下步驟來最佳化價值網路:

  • 用價值網路生成一場對局

  • 記錄下該對局中所有的狀態、動作和最後的收益(勝率)

  • 將每一對狀態和動作作為網路輸入,收益作為網路輸出,用梯度下降對價值網路進行一次更新

其實,所謂的蒙特卡羅方法就是一種隨機模擬,即通過不斷的重複實驗來估計真實價值。在初高中課本中,我們學過「用頻率估計概率」,這就是典型的蒙特卡羅方法。以上所述是蒙特卡羅方法在強化學習中的簡單應用。然而,蒙特卡羅方法在強化學習領域中被大多數研究者忽視。學界普遍認為蒙特卡羅方法存在兩個缺點:1. 蒙特卡羅方法不能處理不完整的狀態序列。2. 蒙特卡羅方法有很大的方差,導致取樣效率很低。

然而,作者卻驚訝地發現蒙特卡羅方法非常適合鬥地主。首先,鬥地主可以很容易產生完整的對局,所以不存在不完整的狀態序列。其次,作者發現蒙特卡羅方法的效率其實並沒有很低。因為蒙特卡羅方法實現起來極其簡單,我們可以很容易通過並行化來採集大量的樣本以降低方差。與之相反,很多最先進的強化學習演算法雖然有更好的取樣效率,但是演算法本身就很複雜,因此需要很多計算資源。綜合來看,蒙特卡羅方法在鬥地主上運行時間(wall-clock time)並不一定弱於最先進的方法。除此之外,作者認為蒙特卡羅方法還有以下優點:

  • 很容易對動作進行編碼。鬥地主的動作與動作之前是有內在聯繫的。以三帶一為例:如果智慧體打出 KKK 帶 3,並因為帶牌帶得好得到了獎勵,那麼其他的牌型的價值,例如 JJJ 帶 3,也能得到一定的提高。這是由於神經網路對相似的輸入會預測出相似的輸出。動作編碼對處理鬥地主龐大而複雜的動作空間非常有幫助。智慧體即使沒有見過某個動作,也能通過其他動作對價值作出估計。

  • 不受過度估計(over-estimation)的影響。最常用的基於價值的強化學習方法是 DQN。但眾所周知,DQN 會受過度估計的影響,即 DQN 會傾向於將價值估計得偏高,並且這個問題在動作空間很大時會尤為明顯。不同於 DQN,蒙特卡羅方法直接估計價值,因此不受過度估計影響。這一點在鬥地主龐大的動作空間中非常適用。

  • 蒙特卡羅方法在稀疏獎勵的情況下可能具備一定優勢。在鬥地主中,獎勵是稀疏的,玩家需要打完整場遊戲才能知道輸贏。DQN 的方法通過下一個狀態的價值估計當前狀態的價值。這意味著獎勵需要一點一點地從最後一個狀態向前傳播,這可能導致 DQN 更慢收斂。與之相反,蒙特卡羅方法直接預測最後一個狀態的獎勵,不受稀疏獎勵的影響。

「鬥零」系統如何實現?

鬥零系統的實現也並不複雜,主要包含三個部分:動作 / 狀態編碼、神經網路和並行訓練。

動作 / 狀態編碼

如下圖所示,鬥零將所有的牌型編碼成 15×4 的由 0/1 組成的矩陣。其中每一列代表一種牌,每一行代表對應牌的數量。例如,對於 4 個 10,第 8 列每一行都是 1;而對於一個 4,第一行只有最後一行是 1。這種編碼方式可適用於鬥地主中所有的牌型。

鬥零提取了多個這樣的矩陣來表示狀態,包括當前手牌,其他玩家手牌之和等等。同時,鬥零提取了一些其他 0/1 向量來編碼其他玩家手牌的數量、以及當前打出的炸彈數量。動作可以用同樣的方式進行編碼。

神經網路

如下圖所示,鬥零採用一個價值神經網路,其輸入是狀態和動作,輸出是價值。首先,過去的出牌用 LSTM 神經網路進行編碼。然後 LSTM 的輸出以及其他的表徵被送入了 6 層全連接網路,最後輸出價值。

並行訓練

並行訓練

系統訓練的主要瓶頸在於模擬資料的生成,因為每一步出牌都要對神經網路做一次前向傳播。鬥零採用多演員(actor)的架構,在單個 GPU 伺服器上,用了 45 個演員同時產生資料,最終資料被彙集到一箇中央訓練器進行訓練。比較有趣的是,鬥零並不需要太多的計算資源,僅僅需要一個普通的四卡 GPU 伺服器就能達到不錯的效果。這可以讓大多數實驗室輕鬆基於作者的程式碼做更多的嘗試。

實驗

為驗證鬥零系統的有效性,作者做了大量的實驗。這裡我們選取部分實驗結果。作者將鬥零和多個已有的鬥地主 AI 系統進行了對比,具體包括:

  • DeltaDou [5] 是首個達到人類玩家水平的 AI。演算法主要基於貝葉斯推理和蒙特卡羅樹搜尋,但缺點是需要依賴很多人類經驗,並且訓練時間非常長。即使在用規則初始化的情況下,也需要訓練長達兩個月。

  • CQN [3] 是一個基於牌型分解和 DQN 的一種方法。雖然牌型分解被證明有一定效果,但是該方法依然不能打敗簡單規則。

  • SL (supervised learning,監督學習)是基於內部蒐集的頂級玩家的對戰資料,用同樣的神經網路結構訓練出來的模型。

  • 除此之外,作者儘可能蒐集了所有已知的規則模型,包括 RHCP、RHCP-v2、RLCard 中的規則模型[2],以及一個隨機出牌策略。

鬥地主中玩家分為地主和農民兩個陣營。作者使用了兩個評估指標來比較演算法之間的性能:

  • WP (Winning Percentage) 代表了地主或農民陣營的勝率。演算法 A 對演算法 B 的 WP 指標大於 0.5 代表演算法 A 強於演算法 B。

  • ADP(Average Difference in Points)表示地主或農民的得分情況。每有一個炸彈 ADP 都會翻倍。演算法 A 對演算法 B 的 ADP 指標大於 0 代表演算法 A 強於演算法 B。

實驗 1:與已知鬥地主 AI 系統的對比

作者比較勝率(WP)和分值(ADP)。如下表所示,鬥零(DouZero)在兩項指標上都明顯好於已知方法。值得一提的是,因為鬥地主本身有很大的「運氣」成分,高几個百分點的勝率就代表很大的提高了。

實驗 2:在 Botzone 平臺上的對比

Botzone(https://www.botzone.org.cn/)是由北京大學 AI 實驗室開發的線上對戰平臺,支持多種遊戲的線上評測,並舉辦過多場棋牌類 AI 比賽。作者將鬥零上傳到了鬥地主對戰的系統。Botzone 計分結果表明,鬥零在 344 個對戰機器人中脫穎而出,在 2020 年 10 月 30 日排名第一。

實驗 3:鬥零的訓練效率

實驗 3:鬥零的訓練效率

作者用 DeltaDou 和 SL 作為對手,測量鬥零的訓練效率。所有的實驗都在一個伺服器上進行,該伺服器包括 4 個 1080Ti GPU 和 48 核處理器。如下圖所示,鬥零在兩天內超過了 SL,在 10 天內超過了 DeltaDou。

實驗 4:與人類資料的比較

鬥零究竟學出了什麼樣的策略呢?作者將人類資料作為測試資料,計算不同階段的模型在人類資料上的準確率,如下圖所示。我們可以發現兩個有趣的現象。首先,鬥零在前五天的訓練中準確率不斷提高。這表明鬥零通過自我博弈的方式學到了類似於人類的出牌方式。其次,在五天以後,準確率反而下降,這說明鬥零可能學到了一些超出人類知識的出牌方式。

實驗 5:案例分析

實驗 5:案例分析

上文提到,鬥地主遊戲中兩個農民需要配合才能戰勝地主。作者為此做了一個案例分析,如下圖所示。圖中下方農民出一個小牌就能幫助右方農民獲勝。圖中顯示了預測出的最優的三個牌型和預測的價值。我們可以看到預測結果基本符合預期。下方農民「認為」出 3 有非常高的獲勝概率,而出 4 或 5 的預期價值會明顯變低,因為右方農民的手牌很有可能是 4。結果表明鬥零確實學到了一定的合作策略。

總結

總結

鬥零的成功表明簡單的蒙特卡羅演算法經過一些加強(神經網路和動作編碼)就可以在複雜的鬥地主環境上有著非常好的效果。作者希望這個結果能啟發未來強化學習的研究,特別是在稀疏獎勵、複雜動作空間的任務中。蒙特卡羅演算法在強化學習領域一直不受重視,作者也希望鬥零的成功能啟發其他研究者對蒙特卡羅方法做更深入的研究,更好地理解在什麼情況下蒙特卡羅方法適用,什麼情況下不適用。

為推動後續研究,作者開源了鬥地主的模擬環境和所有的訓練程式碼。值得一提的是,鬥零可以在普通的伺服器上訓練,並不需要雲端運算的支持。作者同時開源了線上演示平臺和分析平臺,以幫助研究者和鬥地主愛好者更好地理解和分析 AI 的出牌行為。鑑於當前的演算法極其簡單,作者認為未來還有很大的改進空間,比如引入經驗回放機制來提高效率、顯性建模農民之間的合作關係等等。作者也希望未來能將鬥零的技術應用到其他撲克遊戲以及更加複雜的問題中。

研發團隊介紹:這項工作是由 Texas A&M University 的 DATA 實驗室和快手 AI 平臺部的遊戲 AI 團隊合作而成。DATA 實驗室主要從事資料探勘和機器學習演算法等方面的研究,以更好地從大規模、網路化、動態和稀疏資料中發現可操作的模式。快手遊戲 AI 團隊,主要依託在最先進的機器學習技術,致力於服務遊戲研發,推廣,運營等各個環節。

參考文獻:

[1] Lerer, Adam, et al. “Improving policies via search in cooperative partially observable games.” Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 05. 2020.

[2] Zha, Daochen, et al. “RLCard: A Platform for Reinforcement Learning in Card Games.” IJCAI. 2020.

[3] You, Yang, et al. “Combinational Q-Learning for Dou Di Zhu.” arXiv preprint arXiv:1901.08925 (2019).

[4] Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.

[5] Jiang, Qiqi, et al. “DeltaDou: Expert-level Doudizhu AI through Self-play.” IJCAI. 2019.

為了讓大家細緻了解快手開源的鬥地主AI,機器之心邀請到了該研究的作者之一、快手AI平臺部研究科學家謝靜如來做線上分享,感興趣的讀者可掃描以下二維碼入群。

直播時間:6月29日20:00-21:00

亞馬遜雲科技中國峰會

亞馬遜雲科技中國峰會

2021亞馬遜雲科技中國峰會將在中國上海、北京、深圳三大城市舉辦。本次峰會以「構建新格局,重塑雲時代」為題,並攜手眾多業內領先的技術踐行者們一起同你分享「雲時代的構建故事與重塑經驗」。

7月21日-22日,2021亞馬遜雲科技中國峰會上海站將有多位重磅業內專家及行業大咖在現場分享獨到的行業見解。

面向開發者,本次峰會將專門設立開發者專區,並聯合 Apache 等各類開源社區,以及多位開源牛人,為開發者們帶來腦洞大開的內容分享!

面向行業,近百位來自業內各領域的合作伙伴、客戶及亞馬遜雲科技技術專家,共同組成的強大嘉賓陣容,為你帶來行業最佳實踐分享及領先技術成果發佈解讀!

識別下方小程序,立即報名。

識別下方小程序,立即報名

相關文章

衛星隱身技術研究進展及發展趨勢

衛星隱身技術研究進展及發展趨勢

摘要: 衛星隱身技術在空間攻防系統中佔有獨特的地位,與在地面裝甲車輛、艦船、飛機上應用的隱身技術有一定的相似之處,但由於衛星研製條件以及所處...

地球人丟棄的塑膠垃圾,都去哪了?

地球人丟棄的塑膠垃圾,都去哪了?

今年5月1日開始,最新制定的《北京市生活垃圾管理條例》正式啟用,嚴格的垃圾分類舉措將重新定義這座城市的街頭巷尾。也許,類似去年上海市垃圾分類...

深度學習的可解釋性

深度學習的可解釋性

一、深度學習的可解釋性研究概述 隨著深度學習模型在人們日常生活中的許多場景下扮演著越來越重要的角色,模型的「可解釋性」成為了決定使用者是否能...

從此,Google 再無 Brain

從此,Google 再無 Brain

世界上最好的 AI Lab,是怎麼走向失敗的? 作者 | Founder Park AI Labs 正在捲土重來,產業界比以往幾十年都更加重...