超越過去三年冠軍，AAMAS2019 橋牌遊戲論文揭秘

雷鋒網 AI 科技評論按，近年來，AI 在博弈遊戲中的研究成為研究者們關注的熱點之一。2017 年，AlphaGo 成功擊敗人類最高圍棋水平的代表柯潔，一度佔據各大媒體的頭條。之後，AlphaGo 不斷進化，AlphaZero 輕鬆擊敗國際象棋和日本將棋並擊敗業內遠超人類冠軍水平的頂尖計算機程序。今年，OpenAI Five 擊敗 DOTA2 世界冠軍 OG 團隊。

而在今年 AAMAS 2019 的 140 篇入選論文中，我們注意到，其中有一篇關於不完全信息博弈遊戲——橋牌遊戲的論文——《Competitive Bridge Bidding with Deep Neural Networks》。該論文的作者是中科院計算所博士生榮江（現在阿里巴巴工作）、微軟亞洲研究院資深研究員秦濤博士、新加坡南洋理工大學計算機科學與工程學院安波博士。

論文主要研究了在橋牌遊戲中，基於神經網路構建叫牌系統的方法。

論文下載地址：https://arxiv.org/abs/1903.00900v2

論文的摘要如下：

雷鋒網 AI 科技評論將摘要翻譯如下：

橋牌遊戲分為叫牌和打牌兩個階段。對計算機程序來說，雖然打牌相對容易，但叫牌是非常具有挑戰性的。在叫牌階段，每個玩家只知道自己牌，但同時，他需要在對手的干擾下與搭檔交換信息。現有的解決完全信息博弈的方法不能直接應用於叫牌中。大多數橋牌程序都是基於人工設計的規則，但是，這些規則並不能覆蓋所有的情況，而且，它們通常模稜兩可甚至相互矛盾。本文首次提出了一種基於深度學習技術的叫牌系統，在文中，我們展示了兩個創新點。首先，我們設計了一個緊湊的表示，對私人和公共信息進行編碼，供玩家投標。第二，在分析其他玩家的未知牌對最終結果的影響的基礎上，設計了兩個神經網路來處理不完全信息，第一個神經網路推斷出搭檔的牌，第二個神經網路將第一個神經網路的輸出作為其輸入的一部分來選擇叫牌。實驗結果表明，我們的叫牌系統優於基於規則的最優方案。

橋牌遊戲的研究背景是什麼？有哪些難點？其現實意義是什麼？本次論文的工作，用了哪些方法，遇到了什麼困難？帶著這些問題，雷鋒網 AI 科技評論採訪了論文的作者。以下是這次採訪的主要內容。

問答記錄：

AI 科技評論：你們著手橋牌遊戲研究有多久了？訓練數據源是什麼？為什麼會研究橋牌而不是德撲？這兩個遊戲都是不完全信息博弈，它們的異同點在哪裡，研究的側重點有區別嗎？

答：我們是 2016 年開始研究橋牌的，一直到 2018 年，歷時一年多，文章於 2019 年發表在 AAMAS 上。

我們的數據包括兩部分，用於監督學習的專家數據和用於強化學習的隨機數據。其中專家數據來自 Vugraph Project（http://www.bridgebase.com/vugraph_archives/vugraph_archives.php），該項目記錄了世界各種高水平橋牌比賽的完整過程，經過處理以後共得到 1200 萬條專家數據。用於強化學習 self-play 的數據是隨機生成的，我們用了 100 萬局比賽。

實習的時候有同事懂橋牌，我們覺得有意思就開始研究橋牌了。橋牌和德撲共同點是，它們都是不完全信息博弈。它們的不同點有兩個，第一點是橋牌有四個人，已有的演算法很難保證像二人德撲那樣找到納什均衡，第二點是，橋牌涉及到隊友間的協作。

相比於德撲，橋牌的難度更大、更具有挑戰性。雖然它們都是不完全信息博弈，但已經發表的德撲演算法（如 CFR 演算法）僅對二人德撲有理論保證，無法拓展到多人。而橋牌是四人博弈，因此會更難一些。此外，橋牌不僅涉及到對手間的對抗，還涉及到隊友間的合作，比德撲更複雜。

之所以選擇橋牌，是因為現實中大部分環境是既充滿合作也充滿競爭的，如果我們能做好橋牌這種非完全信息遊戲，那麼我們就能對很多實際生活中遇到的問題進行建模了。比如，這項研究成果可以用在處理國家和國家之間的關係上，任何國家和國家之間關係都不是兩個國家之間的關係，我們要考慮到多方的關係，而這些國家之間既存在競爭也可能同時存在合作。其中會涉及到很多私有信息，這些信息都是未公開的，為非完全信息，這就和橋牌遊戲是類似的。我們覺得，這項工作是比較接近現實的抽象，通過這項研究，我們可以發掘相關算和積累相關技術，便於日後落地到實際應用。

AI 科技評論：你們的文章中提到，橋牌遊戲的難點有兩個，一是進行決策時需要考慮的狀態空間很大，二是來自對手的挑戰，你們是如何應對這些難點的？

答：第一，我們用了一個緊湊的向量來表徵狀態（如下圖所示），從而降低模型輸入的維度。此外，由於每個玩家只能看到自己的 13 張牌，其餘 39 張都是未知的，這導致不完全信息的信息集很大，我們通過預測隊友的牌來縮小信息集，從而降低結果的不確定性。

第二，我們首先通過監督學習來較好地初始化智能體，然後通過強化學習演算法讓我們的智能體不停地 self-play，這個過程中同一個團隊的 2 個智能體會通過不斷修正對隊友牌面的預測準確性來保持信息交換和協作，同時與自己的歷史版本對抗，在不斷的學習中提升自己的勝率。

AI 科技評論：你們的成果超越了過去三年的冠軍，和他們相比，你們的優勢和創新點在哪裡？

答：橋牌分兩個階段，叫牌（bidding）和打牌（playing）。我們目前的工作只是在叫牌階段超越了當前版本的 Wbridge5，當然，Wbridge5 也在不斷優化中。我們的優勢在於用神經網路構建叫牌系統，這樣能夠通過監督和強化學習讓該系統不停地探索和優化自己的策略，而 Wbridge5 是基於規則的，他們通過消除已有規則中的歧義和衝突來優化自己的系統，這樣就會有一定的局限性，把系統的性能的上限局限在了人類已有的知識中。

AI 科技評論：你們的工作是如何分工的？在研究的過程中，選取了哪些特徵，嘗試過哪些機器學習演算法？未來會在哪些方面進行改進和提升？

答：榮江主要負責具體實現工作，秦濤老師和安波老師參與方案的討論並指導榮江工作。

我們用到的特徵包括完全信息和不完全信息兩部分，其中完全信息包括自己的牌、局況（vulnerability）、叫牌序列（bidding history），不完全信息包括對隊友牌的預測。

研究過程中，我們嘗試過 DQN 演算法，但由於不完全信息帶來的不確定性，DQN 演算法的方差很大。另外，我們還試過 boosting tree 演算法，這種演算法的好處是有很好的模型可解釋性，但演算法的性能並沒有基於 policy 的強化學習演算法好。此外，我們還嘗試過單純用強化學習演算法，但是演算法不收斂，這跟完全信息類型的博弈（如圍棋）有很大差別。

未來，我們會嘗試加入帶有 reward shaping 功能的 value-network，用於位叫牌過程的每一步中間結果生成一個單獨的即時收益，而不是等到叫牌結束後給所有中間過程一個相同的收益，這可能會有讓策略更新的方向更加精準。此外，我們還會嘗試加入 attention 模塊（如 Transformer），對叫牌序列做權重處理，讓智能體能捕捉到更加關鍵的信息，從而得到更好的策略。

AI 科技評論：這項工作成果的應用前景如何？可以用在工業上嗎？

答：我們的演算法說明「策略網路+預測網路」這種組合是有效的，這個思路可以用在很多地方，比如商業推薦系統。我們正在嘗試用一個預測網路來預測用戶的興趣，然後通過一個打分網路來對用戶感興趣的商品進行排序。

AI 科技評論：目前，橋牌遊戲研究在國內外的研究現狀如何，這項研究未來的方向是什麼？

答：目前，做棋牌類遊戲研究的人非常多。目前，科學家們已經攻破了圍棋這種完全信息的遊戲，因此我們著手研究橋牌這種非完全信息遊戲。目前，這些遊戲在國外的研究相對於國內來說要多一些。

目前幾乎所有的橋牌軟體（如 GIB，Wbridge5，Jack 等）都是基於規則的。雖然深度學習已經在很多完全信息類博弈中取得了顯著的效果（如 AlphaGo），但目前橋牌領域使用的還很少。ECAI16 發表了一篇基於神經網路和強化學習的橋牌演算法，但該演算法不考慮競爭，即假設對手一直出「pass」。我們的論文應該是第一篇用深度學習演算法來求解橋牌叫牌遊戲的文章。今後應該會出現更多基於神經網路和深度學習的橋牌演算法。

AI 科技評論：您對遊戲類的研究有什麼看法？這種研究有什麼實際意義嗎？

答：科學研究始終要走在工業應用的前面，要有前瞻性。從 AI 的發展歷史來看，很多精妙的演算法和理論都是從研究遊戲開始的，學者們在研究的過程中能積累大量的知識和技術，最後用於實際應用，如博弈論的研究可從最簡單的囚徒困境遊戲開始，強化學習演算法也基本上是基於遊戲（如 Atari Games）來不斷發展的。

現實應用往往過於複雜，而遊戲的規則明確，易於建模，為科學研究提供了很好的對象，從遊戲研究入手來探索新的理論和技術然後拓展到實際是一個自然的過程。

雖然，這些工作未來具體會用在哪裡我們並不知道，但是在 AI 的發展歷史上，遊戲起到非常重要的作用，它是一項比較偏基礎性的研究，短期內也很難看它的應用，但是，這些研究能夠推動整個領域的發展。因此，研究遊戲的解法是很有意義的。

附：論文作者簡介

• 榮江

榮江，於 2019 年在中國科學院計算技術研究所獲得計算機科學博士學位，主要研究領域包括機器學習、強化學習、博弈論、多智能體系統等，在相關國際會議（AAAI、AAMAS 等）發表過多篇論文，現任阿里巴巴高級演算法工程師。

• 秦濤

秦濤博士，微軟亞洲研究院資深研究員，研究重點是深度學習和強化學習的演算法設計、理論分析及在實際問題中的應用，在國際會議和期刊上發表學術論文 100 余篇，曾/現任機器學習及人工智慧方向多個國際大會領域主席，曾任多個國際學術研討會聯合主席。秦濤博士是中國科學技術大學兼職博士生導師，IEEE、ACM 高級會員。他的團隊獲得國際機器翻譯大賽（WMT2019）8 項第一。

• 安波

安波，南洋理工大學校長委員會講席副教授，於 2011 年在美國麻省大學 Amherst 分校獲計算機科學博士學位。主要研究領域包括人工智慧、多智能體系統、演算法博弈論、強化學習、及優化。曾獲 2010 年國際智能體及多智能體系統協會 (IFAAMAS) 傑出博士論文獎、 2011 年美國海岸警衛隊的卓越運營獎、2012 年國際智能體及多智能體系統年會 (AAMAS) 最佳應用論文獎、2016 年人工智慧創新應用會議 (IAAI) 創新應用論文獎，2012 年美國運籌學和管理學研究協會 (INFORMS)Daniel H. Wagner 傑出運籌學應用獎，以及 2018 年南洋青年研究獎等榮譽。受邀在 2017 年國際人工智慧聯合會議 (IJCAI) 上做 Early Career Spotlight talk。獲得 2017 年微軟合作 AI 挑戰賽的冠軍。入選 2018 年度 IEEE Intelligent Systems 的「人工智慧 10 大新星」(AI"s 10 to Watch)。當選為國際智能體及多智能體系統協會理事會成員和 AAAI 高級會員。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！