Libratus是如何在雙人無限注德撲中擊敗人類頂級選手的？

Libratus 提出了一種在大型狀態空間、隱藏信息中有效地應對博弈論推理挑戰的方法；它在 12 萬手單挑無限注德州撲克比賽中擊敗了四個頂尖的人類選手，成功解決了處理不完美信息博弈的領先基準問題與長期存在的挑戰。由於現實世界策略交互中的隱藏信息無處不在，因此 Libratus 引入的範式將在 AI 的未來發展和廣泛應用中發揮重要作用。

近年來，人工智慧已經取得了非常大的進步。很多情況下，這種進步體現在基準遊戲中和人類表現的對比。目前 AI 程序已在跳棋、國際象棋和圍棋等擊敗了人類頂尖選手。在這些完美信息博弈中，雙方都知道博弈中每一個點的確切狀態。相反在不完美信息博弈中，關於博弈狀態的一些信息是隱藏的，即博弈中存在包含多個決策點的信息集或博弈者無法區分對手的一些行動。隱藏信息在現實世界策略互動中無處不在，這使得研究不完美信息博弈的技術更加重要。

由於多種原因，隱藏信息使博弈變得更加複雜。對於不完美信息博弈而言，AI 不是簡單地搜索一個最佳行動序列，而是必須確定如何適當地行動，這樣對手才不會過多地發現我方所擁有的私人信息。例如虛張聲勢是任何競技性撲克都需要的技巧，但經常唬人就會被對方抓住特點而被擊敗。因此換句話來說，一個行動獲得的價值取決於它出現的概率。

另一個關鍵點是博弈的不同部分不能獨立地考慮。對於一個給定的情況，最佳策略可能取決於未發生情況下將執行的策略。因此，一個競爭性的 AI 總需要考慮整個遊戲的策略。

撲克遊戲作為理解隱藏信息的博弈有很長歷史，而德撲是目前最受歡迎的撲克遊戲之一。由於其龐大的規模和複雜的戰略，單挑無限注德州撲克（HUNL）已經成為近年來不完美信息博弈研究的主要遊戲和基準挑戰問題。這個遊戲中，之前沒有 AI 擊敗過頂尖的人類玩家。

在本論文中，我們介紹了 Libratus，它採用了一種獨特的方法來處理不完美信息博弈。該 AI 在為期 20 天、擁有 20 萬獎金池、總數 12 萬手的競賽中，擊敗了 HUNL 頂尖選手。Libratus 中的技術並不是使用專家領域知識或人類數據，也不是專門針對撲克的，因此它們適用於大量不完美信息博弈。

論文：Superhuman AI for heads-up no-limit poker: Libratus beats top professionals

論文鏈接：http://science.sciencemag.org/content/early/2017/12/15/science.aao1733/tab-pdf

摘要：無限注德州撲克是最流行的撲克形式之一。儘管人工智慧在完美信息博弈中取得了成功，但私人信息和大規模博弈樹使得無限制博弈問題很難解決。我們提出了 Libratus，它在 12 萬手單挑無限注德州撲克比賽中擊敗了四個頂尖的人類選手，解決了處理不完美信息博弈的領先基準問題與長期存在的挑戰。我們的博弈論方法以獨立於應用的技術為特徵：一個演算法用於計算總體策略的藍圖，另一個演算法在博弈中求解並充實子博弈的具體策略，還有一個自提升演算法用於修正可能存在的弱點，該弱點可能已經在對手的藍圖策略中得到了識別與針對。

圖 1：子博弈求解

上：博弈過程中出現了一個子博弈。中：通過求解一個增強子博弈，為該子博弈確定一個更加詳細的策略，其中每次迭代中的對手持有一個隨機牌組，並給出了策略選擇，選擇舊抽象（紅色）的期待值，或選擇新的細粒度的抽象（綠色，其中對弈雙方的策略都是可變的）。這迫使 Libratus 將細粒度策略設置成至少和初始抽象（和所有的對手牌組對弈）一樣好。下：新策略取代了原來的策略。

圖 2：嵌套子博弈解決方案的 2A 可視化。每次在遊戲中達到一個子博弈，就會為這個子博弈構建和解決一個更加詳細的抽象，同時將其解決方案納入整體藍圖策略之中。

圖 3：Libratus 與人類頂級玩家的表現對比。上圖給出了 2017 Brains vs. AI 的競賽結果。其中 95% 的置信區間（如果手牌相互獨立且分布相同）由虛線表示。

結論

Libratus 提出了一種在大型狀態空間、隱藏信息中有效地解決博弈論推理挑戰的方法。我們開發的技術在很大程度上是獨立於域的，因此可被應用於其他策略性不完美信息交互，包括非娛樂性應用。由於現實世界策略交互中的隱藏信息無處不在，我們認為 Libratus 引入的範式對 AI 的未來發展和廣泛應用將非常重要。