【Science封面】數字紙牌奇才：AI拿下德州撲克，不完美信息博弈里程碑式突破

新智元為COO和執行總編提供最高超百萬的年薪激勵；為骨幹員工提供最完整的培訓體系、高於業界平均水平的工資和獎金。加盟新智元，與人工智慧業界領袖攜手改變世界。

簡歷投遞：j[email protected] 13552313024

【新智元導讀】AlphaGo之後，又一人機大戰被登上了Science 封面，這一次是德州撲克AI 程序DeepStack。來自加拿大和捷克的幾位計算機科學研究者提出一種新演算法 DeepStack，在一對一無限注德州撲克中打敗了人類對手。這是AI 在不完美信息博弈中堪稱里程碑式的突破。

計算機在象棋和圍棋遊戲中已經能擊敗人類。這些以及其他類似的遊戲，對於當下的遊戲狀態，所有的玩家能夠獲得的確定性信息是相同的。但是，在撲克遊戲中，由於無法看到對手的牌，教計算機玩好撲克是很棘手的。來自加拿大和捷克的幾位計算機科學研究者提出一種新演算法 DeepStack，在一對一無限注德州撲克中打敗了人類對手。DeepStack 不是事先制定策略，而是考慮當前的遊戲狀態，在每一步重新計算策略。DeepStack 背後的原理有助於解決現實世界中涉及信息不對稱的問題。

這項研究登上 Science 最新一期封面。

摘要

近年來，人工智慧領域取得了很多突破，其中遊戲方面取得的突破常常是里程碑式的。這些遊戲的共同特徵是所有玩家都能得到完美信息（perfect information）。撲克是典型的不完美信息（imperfect information）博弈，是人工智慧領域長期的一個挑戰性問題。在這篇論文中，我們介紹了 DeepStack，這是一種用於不完美信息環境的演算法。它結合使用遞歸推理（ recursive reasoning）來處理信息不對稱，利用分解（decomposition）將計算集中在相關的決策上，以及一種有關撲克的任意狀態的直覺形式，該直覺可以利用深度學習從單人玩牌過程中自動學習到。在一項有數十名參賽者進行的44000手撲克的比賽中，DeepStack 以顯著差異在一對一無限注德州撲克中擊敗職業撲克玩家。這種方法在理論上是可靠的，而且已經證明它產生的策略比以前的方法的策略更難被利用。

引言：不完美信息博弈

遊戲長久以來都被認為是用來測量人工智慧進步的一個基準。在過去的20年間，我們見證了許多遊戲程序在許多遊戲上超越了人類，比如西洋雙陸棋、跳棋、國際象棋、Jeopardy 、Atari 電子遊戲和圍棋。計算機程序在這些方面的成功涉及的都是信息的對稱性，也就是對於當下的遊戲狀態，所有的玩家能夠獲得的確定性信息是相同的。這種完美信息的屬性也是讓這些程序取得成功的演算法的核心，比如，在遊戲中進行局部搜索。

現代博弈理論創建者、計算機先鋒馮·諾依曼（von Neumann）曾對無完美信息的博弈中的推理行為進行過解釋：「現實世界與此不同。現實世界有很多假象、騙術，需要你去思考別人對你的策略到底看穿了多少。這就是我提出的理論所涉及的博弈。」馮·諾依曼最痴迷的一個遊戲是撲克，在撲克遊戲中，玩家在得到自己的牌后，需要輪流下注，讓對手跟注，他們或跟注或棄牌。撲克是一種不完美信息博弈，玩家只能根據自己手上的牌提供的非對稱的信息來對遊戲狀態進行評估。

在一對一對戰（也就是只有兩位玩家）的有限下注德州撲克中，AI 曾經取得了一些成功。但是，一對一有限注的德州撲克，全部的決策點（decision points）只有不到10的14次方個。作為對比，計算機已經在圍棋上完勝人類專業棋手，圍棋是一個完美信息的遊戲，約包含有10的170次方個決策點。

不完美信息博弈要求更複雜的推理能力。在特定時刻的正確決策依賴於對手所透露出來的個人信息的概率分佈，這通常會在他們的行動中表現出來。但是， 對手的行為如何暗示他的信息，反過來也要取決於他對我們的私人信息有多少了解，我們的行為已經透露了多少信息。這種循環性的推理正是為什麼一個人很難孤立地推理出遊戲的狀態的原因，不過在完美信息博弈中，這是局部搜索方法的核心。

在不完美信息博弈中，比較有競爭力的 AI 方法通常是對整個遊戲進行推理，然後得出一個完整的優先策略。CFR （ Counterfactual regret minimization）是其中一種戰術，使用自我博弈來進行循環推理，也就是在多次成功的循環中，通過採用自己的策略來對抗自己。如果遊戲過大，難以直接解決，常見的方法是先解決更小的、濃縮型的遊戲。最後，如果要玩最初的大型的遊戲，需要把原始版本的遊戲中設計的模擬和行為進行轉移，到一個更「濃縮」的遊戲中完成。

雖然這一方法讓計算機在一對一無限注德州撲克（Heads-up no-limit Texas Hold'em，HUNL）一類的遊戲中進行推理變得可行，但是，它是通過把HUNL下的10的160次方個場景壓縮到10的14次方個縮略場景來實現的。這種方法有很大的可能性會丟失信息，所有這類的程序離專業的人類玩家水平還差得很遠。

2015年，計算機程序 Claudico 輸給了一個專業撲克玩家團隊，並且是以較大的劣勢輸掉的比賽。此外，最近，在年度計算機撲克競賽中，人們發現，基於「濃縮」的計算機程序有很多缺點。其中4個使用了這一方法的計算機程序，其中包括從2016年來一直位列前茅的程序，被認為使用了一個局部最佳響應的技巧，使得在一個策略能輸掉多少這一決策上，產生一個更加接近下限的答案。所有這四個基於「濃縮」方法的程序都可能會輸得很慘，用量化來表示，是每局都棄牌輸率的四倍。

DeepStack 採用了一個完全不同的方法。它持續地使用CFR中的循環推理來處理信息不對稱的問題。但是，它並不會計算和存儲一個完整的優先策略用於博弈，所以也不需要進行簡要的提煉（濃縮）。反之，在遊戲中，它會在每一個具體的場景出現時就進行考慮， 但是並不是獨立的。

通過使用一個快速的近似估計來代替某一種深度的計算，它能避免對整個遊戲的剩餘部分進行推理。這種估計可以被看成是 DeepStack 的直覺：在任何可能的撲克情境下，持有任何可能的個人牌的牌面大小的直覺。

最後，從某種程度上來說與人類的很像的 DeepStack 的直覺，是需要被訓練的。我們使用了隨機生成的撲克情景用深度學習進行訓練。最終，我們證明了，DeepStack從理論上來說是可行的，比起基於「濃縮」的方法，它能產生從實質上需要更少的探索的策略，同時，它也是世界上首個在HUNL遊戲中擊敗人類專業玩家的計算機程序，平均贏率超過450 mbb/g。（mbb/g,milli-big-blinds per game ,是用于衡量撲克玩家表現的指數，50 mbb/g 可以就認為是一個較大的優勢，750mbb/g 就是對手每局都棄牌的贏率。）

DeepStack 是一大類的序列不完美信息博弈的通用演算法。我們將解釋 DeepStack 在 HUNL（heads-up no-limit，一對一無限注）德州撲克中的作用。撲克遊戲的狀態可以分為玩家的私人信息，即兩張牌面朝下的手牌，以及公共狀態，包括牌面朝上的公共牌和玩家的下注順序。遊戲中公共狀態的可能序列形成公共樹，每個公共狀態有一個相關聯的子公共樹。見下圖：

圖1：HUNL公共樹的一部分。紅色和湖藍色代表玩家的動作。綠色代表被翻開的公共牌。

DeepStack 演算法試圖計算玩遊戲的低利用率策略，即，求解一個近似的納什均衡（Nash equilibrium）。DeepStack在玩牌期間計算這個策略，公共樹的狀態如圖2所示。這種本地的計算使得 DeepStack 在對現有演算法來說規模太大的遊戲中可推理，因為需要抽象出的遊戲的10的160次方決策點下降到10的14次方，這讓演算法變得易處理。

圖2：DeepStack 概覽圖。（a）DeepStack 對在每個公共狀態的動作進行 re-solves，使用 depth-limited lookahead，其中子樹值的計算用訓練好的深度神經網路（b）通過隨機生成的撲克狀態在玩牌前進行訓練（c）最終狀態如圖3。

DeepStack 演算法由三個部分組成：針對當前公共狀態的本地策略計算（local strategy computation），使用任意撲克狀態的學習價值函數的 depth-limited lookahead，以及預測動作的受限集合。

連續 Re-Solving

• Own Action：將對手的反事實值替換為在為我們自己選擇動作的解決策略中計算的值。使用計算策略和貝葉斯規則更新我們自己的動作範圍。

• Chance Action：用從最後一次分解為這個動作計算出的反事實值替換對手反事實值。通過清除在任何新公共牌不可能的手牌範圍，更新我們自己的範圍。

• Opponent Action：不用做什麼。

Limited Lookahead 和 Sparse Trees

連續re-solving在理論上是可行的，但實際使用上不現實。它沒有維持一個完整的策略，除非遊戲接近結束，re-solving本身就很棘手。例如，對於第一次動作的re-solving需要為整個遊戲臨時計算近似解決方案。

Deep Counterfactual Value Networks

深度神經網路（DNN）已被證明在圖像和語音識別、自動生成音樂以及玩遊戲等任務上是強有力的模型。DeepStack 使用DNN和定製的架構作為它的 depth-limited lookahead其的價值函數。如圖3。

圖3：Deep Counterfactual Value Networks。網路的輸入是pot的大小，公共牌和玩家範圍，玩家範圍先被處理為bucket ranges。輸出來自七個完全連接的隱藏層，被后處理以保證值滿足零和限制（zero-sum constraint）。

訓練兩個獨立的網路：一個在第一次三張公共牌被處理（flop網路）后估計反事實值，另一個在處理第四張公共牌（turn網路）后估計反事實值。一個輔助網路用於在發任意公共牌之前加速對前面的動作的re-solving。

DeepStack 表現

圖4總結了用 AIVAT 衡量的每個參賽者的表現。在完成所要求的 3000手牌的玩家中，DeepStack 預估贏率是 394 mbb/g，與11名玩家對戰贏了其中10名，差距顯著。人類玩家中表現最好者估計贏率是 70 mbb/g，這個結果沒有顯著的統計學意義。

圖4：人類專業撲克玩家和DeepStack的表現。用 AIVAT衡量，置信區間是95%。下方的柱形圖表示參與者完成的手數。

DeepStack 在 HUNL 中以顯著差異擊敗人類職業撲克玩家；HUNL 的計算規模與圍棋相似，但不完美信息的性質增加了其複雜性。DeepStack 沒有用專業人士的遊戲經驗來訓練，只利用很少的領域知識實現了打敗人類的目標。它的影響不僅僅是人工智慧領域取得突破。DeepStack 代表了大規模、連續的不完美信息博弈近似解決方案的範式發生了改變。在過去20年中，對完全策略（complete strategies）進行抽象（abstraction）和離線計算（offline computation）是這類問題的主要方法。DeepStack 允許計算集中於進行決策時出現的特定情況，使用自動訓練的值函數（value functions）。這些是在完美信息博弈中取得成功的兩個核心原則，儘管在這些設置中從概念上來說更簡單就能實現。因此，完美信息博弈和不完美信息博弈之間的差距已經消除。

由於包含信息不對稱的許多現實世界的問題，DeepStack 也對不符合完美信息假設的環境有影響。處理不完美信息的 abstraction 範式可以用於保護戰略資源以及在醫療中進行穩健的決策。DeepStack 的連續 re-solving 範式將能夠開闢更多的可能性。

新智元招聘

新智元日前宣布，獲6家頂級機構總額達數千萬元的PreA輪融資，藍馳創投領投，紅杉資本基金、高瓴智成、藍湖資本 、藍象資本跟投。本輪融資將用於新智元團隊規模擴充並增加新產品服務線，目標打造 To B 的人工智慧全產業鏈服務平台。

職位：客戶經理

職位年薪：12 - 25萬（工資+獎金）

工作地點：北京-海淀區

所屬部門：客戶部

彙報對象：客戶總監

工作年限：3 年

語言：英語 + 普通話

學歷要求：全日制統招大學部

職位描述：

• 精準把握客戶需求和公司品牌定位，策劃撰寫合作方案；

• 思維活躍、富有創意，文字駕馭能力強，熟練使用PPT，具有良好的視覺欣賞及表現能力，PS 能力優秀者最佳；

• 熱情開朗，擅長人際交往，良好的溝通和協作能力，具有團隊精神；
  
  

• 優秀的活動籌備與執行能力，較強的抗壓能力和應變能力，適應高強度工作；

• 有4A、公關公司工作經歷優先；

• 對高科技尤其是人工智慧領域有強烈興趣者加分。

崗位職責：

參與、管理、跟進上級指派的項目進展，確保計劃落實。制定、參與或協助上層執行相關的政策和制度。定期向公司提供準確的市場資訊及所屬客戶信息，分析客戶需求，維護與指定公司關鍵顧客的關係，積極尋求機會發展新的業務。建立並管理客戶資料庫，跟蹤分析相關信息。

應聘郵箱：[email protected]