968
技術社區[雲棲]
【AI VS 人類新高峰】冷撲大師發明人：用於策略推理的超人AI
Tuomas Sandholm：大家好，非常感謝新智元給我機會。今天我想跟大家分享不完全信息博弈，這跟西洋跳棋、圍棋、象棋等其他完全信息博弈是不一樣的。不完全信息博弈更像是談判、撲克，適用於解決現實問題，因為現實生活中很多都是不完全信息。
接下來，我想給大家介紹一下 AI 如何進入到撲克遊戲當中去，以及我們怎麼樣才能夠應對在這些遊戲中的超級複雜性。
首先我想大家都已經聽說過AlphaGo，它是另外一種完全信息博弈。對於完全信息博弈來講，你知道遊戲是如何組成的。所以，在一定程度上，不完全信息博弈的難度比完全信息博弈的難度更大，需要完全不同的算法。
讓我來舉例說明。
例1：我們不僅僅隻為撲克遊戲開發技術，也針對一般的遊戲。我們來看一下這是扔硬幣的遊戲，扔硬幣有一半的概率是正麵，有一半的概率是反麵，我們有兩個玩家，一個是1號玩家，一個是2號玩家，如果P2猜對的話，P2就會得一分，P1就會減少一分，如果P2猜錯的話P1就能得一分，我想說大多數的時候，大家都在不完全遊戲博弈中見到過這樣的一些遊戲樹形結構分析。
我們看一下這是信息集的相關信息，也就是說我們玩家到底應該怎麼玩，各種不同的玩法。紅色的玩家有兩個信息集，基於這點他可以決定到底該怎麼玩。第二個玩家不知道硬幣是正麵還是反麵，二號玩家隻有一個信息集，他每次玩的方法都是一樣的，它的可能性也是一樣的。
這裏，主要的挑戰首先是不確定別人會做什麼以及相應的機會，也就是未知狀態。而且，由於未知狀態，我們不得不考慮我們的行為如何向對手傳達我們的私人信息。相反，對手的行為如何向我們反映他們的私人信息。
而這正是博弈論中納什均衡概念出現的地方。約翰·納什在1950年發明了這個概念，它改變了經濟學和許多其他科學。 1994年，他獲得了諾貝爾獎。但是，當然，這隻是有多個玩家時，並且均為理性玩家前提下的定義。它實際上沒有做任何事情。所以為了實現這一點，你必須結合算法來根據納什均衡實際來計算策略。
現在，這些獨立於的技術成為撲克AI的基準。如果你回到約翰·納什1950年的博士論文，你會發現，納什均衡唯一的應用理論就是撲克。從那以後，撲克 AI 有了很多進展。大約 13 年前，這個領域真的有了很大發展。於2006年開始，每年舉辦年度計算機撲克挑戰賽，世界各地不同的研究小組可以比較他們的結果，並逐年增加難度。這導致了核心技術推理方麵的多個數量級的穩定改進。並且，有限下注的德州撲克問題在2015年已經得到解決。
因此，無限注德州撲克已成為人工智能不完全信息博弈的主要標杆和挑戰問題。這是一個非常大的遊戲。它有10的161次方個不同的情況，讓我們停下來考慮一下這個數字。它不僅僅是宇宙中所有原子數量。而且，如果宇宙中的每個原子都有一個完整的另一個宇宙，並且計算這些子原子的數量，那麼它也不止於此。你需要AI技術來解決它們。而之前沒有人工智能能夠擊敗頂級人類玩家。所以如果想想 AI 中的遊戲，那麼有很多很棒的子集，比如奧賽羅，跳棋，國際象棋和棋子。但是，無限德州撲克仍然是看不到，這是一場艱苦的比賽。因為它非常大，而且是一個不完全信息博弈。
所以，今年1月，我組織了AI複賽的春季版本。我之所以稱之為複賽，是因為我在2015年的4月和5月組織了一場類似的比賽。當時我們無法在這場比賽中擊敗最好的玩家。我邀請了前十名中的4名無限德州撲克專家的專業人士到匹茲堡參加比賽。我們在20天內玩了12萬手牌。
它和人類的遊戲玩法非常不同，因為它不是從學習人類數據開始的。從剛剛輸掉比賽開始，它就使用優化和AI來形成自己的策略。它和人類玩的很不一樣。最終的結果是，我們的AI libratus在這場比賽中大大地擊敗了頂級人類大師。贏率達到99.98％的這是有統計學意義的。而且每個人都輸給了冷撲大師。
之後，我們在中國的海口做了一個類似的比賽，我們打了3萬6000手牌，對手是一個由六名中國撲克職業選手組成的隊伍。獎金是200萬人民幣。對手做好了準備。所以他們不僅是撲克玩家，還是計算機科學家，機器學習專家。 他們中的一個是唯一的中國世界撲克錦標賽係列賽冠軍。為了突破AI，他們事先研究了libratus的手牌曆史。我們9場比賽中打了四天半。他們的策略是行不通的。冷撲大師，意思是“冷酷的撲克大師”，是libratus的中國版。它贏得了9場比賽的每一場勝利，同時也擊敗了每一個人。
libratus是如何工作的：三大模塊
那麼libratus是如何工作的呢？我經常被問到這個問題。所以現在我要講講這些AI背後的細節。
他們有三個主要模塊。這些是主要的部分：一個是事件發生之前，我們將遊戲的規則提供給抽象算法。它運行遊戲的抽象，所以它是納什均衡的近似值。然後有一個次遊戲的解決者實時完善這些策略，然後在後台運行一個自我改進的算法。
在比賽之前，我們運行了一台超級計算機。在使用libratus那一次，我們在匹茲堡超級計算中心的超級計算機上運行了大約1500萬個小時。那麼顯然這個遊戲太大了，不能直接解決，所以我們運行了一個抽象算法來創建一個更小的抽象遊戲。然後，我們使用經典均衡尋找算法來尋找博弈的近似均衡。
Libratus有一個計算近似納什均衡策略的算法（這也是一個近似的最小最大策略）到抽象的遊戲。它為AI的戰略提供了一個高層次的藍圖。新算法是Monte Carlo對策略最小化算法的改進版本。主要的新方麵包括以降低概率的方式抽取智能體的行為。這大大提高了算法的速度，從而使得更細粒度的抽象得到解決。
最先進的遊戲抽象是不完美的 。正因為如此，遊戲模型有多條路徑到相同的抽象狀態。這會導致不同的途徑在這個智能體應該做的事情上“鬥爭”，這就提高了解決方案的質量。新的均衡發現算法也可以通過折扣一些路徑來減少抽象狀態的入度，從而減輕這個問題。
2.解決子遊戲
Libratus有一個新的子遊戲解決算法，重複計算一個更詳細的策略，以上述藍圖策略為指導。這個算法的新方麵包括以下內容。
到目前為止，考慮到對手的錯誤，安全的子遊戲解決。子博弈求解器可以通過錯誤給予對手我們迄今在遊戲中給予我們的數量，同時仍然是完全安全的（即不遜於預先計算的納什均衡近似藍圖）。
我們使用這個觀察來擴展子博弈求解器可以安全地優化的策略空間，從而使其能夠比以前的子博弈求解器更好地發揮與對手可能持有的其他（非錯誤）雙手相比更好的靈活性。
通常情況下，子博弈解決不完美信息遊戲隻進行一次子博弈時。相比之下，Libratus在每個對手在子遊戲中移動之後解決每個剩下的子遊戲。這樣可以實現更細粒度的抽象，也可以避免反向映射對手的抽象外動作和抽象抽象動作的缺點，因為對手的確切動作被添加到剩下的子遊戲中。
子遊戲的解決在遊戲的早期階段開始（在任何足夠大的下注周期，但不遲於第三輪下注開始時）。在子遊戲解決中沒有抽象卡。
在子遊戲解決之前，噪音被添加到動作抽象中。這使得Libratus難以發揮，因為它在每一手牌後都改變了賭注大小。
3.自我改進
Libratus有一個自我完善的模塊，它隨著時間的推移增加了預先計算的藍圖，以便基於對手已經能夠識別哪些漏洞（抽象操作，即撲克中的下注大小），甚至更接近納什均衡。這與以前在遊戲中學習的方法形成了鮮明的對比，在遊戲中，目標通常是建模和開發。相比之下，Libratus的自我改進是普遍的。
對於冷撲大師的比賽觀察。我們決定對於這些頂級的玩家，我們不想讓自己有太多的漏洞給對方，所以我們這裏沒有對手的漏洞分析，這是我們的弱點。
現在我給大家介紹一下我們將會在其他方麵要開展的研究。第一方麵是有損耗的邊界提取，所以我們要對於現實進行一定的抽象提取，否則的話就會有問題，我們需要有更多的關於損耗提取的一些計算，否則這種遊戲就不能夠很好地繼承下去。同樣這也被用在不同的模型方麵，我們發現現在有很多的模型對於現實來講並不是非常的優化，所以我們也是希望能夠找到更加優化的模型。另外我們要找到新的基於梯度的平衡的計算，在今年夏天我們已經出台了一個相關的方法，現在速度已經非常的快了。
另外一點，對於均衡計算我們要進行進一步的優化，在深度學習來講有第三個維度，也就是說對於探索來講開放程度會有多大，我自己也要進行充分的開放，進行進一步的探索。但是我們在進行探索之前是需要進行充分的準備，現在我們對於這種技術已經進行很多不同的應用了，我們現在也要運用這些新的技術，要有這種方麵的應用能力，在這種信息不全的遊戲之下，我們需要有更多的人機互動，我們在玩的時候，不僅僅隻是需要一個玩家，所以在我們來應用新技術的時候，我們有幾點是需要進一步的改良，我們要進行更好的人機互動，在這裏我們需要提前考慮到遊戲的一些玩法。
另外還有像融資、戰略性的一些定價，以及戰略性的產品組合的優化等等，還有像金融方麵，比如說戰略性的一些資產組合的構建，另外還有自動化的磋商，以及磋商的支持等，另外還有一些企業的戰略，我們在企業的戰略當中應該有我們的一些玩法。
另外在進行拍賣的時候，也可以采用相關的技術，這一點也是非常的有益。像電影相關的內容，在虛擬性安全等等，以及在政治方麵進行競選，在自動化駕駛的汽車或者是艦隊，或者半自動化的艦隊等等，我們可以跟人機之間建立起一些互動，但是我們應該建立一些相關的規則，就是在人機互動的時候，另外在軍事方麵的安全等等，在生物應用等等，比如在醫療、治療、規劃的時候，我們在預防一些疾病或者是感染以及像癌症等等，所有的這些領域我們都可以采用新的技術，另外在培訓以及在娛樂行業也可以有更多的相關技術的應用。
我想說機器學習隻是人工智能的一部分，人工智能可以在其他領域可以進一步應用，比如在戰略推理也可以有更多的人工智能相關的應用。我們認為對於戰略性的推理來講，實際上我們更多的不僅僅是關注於過去，而是更多地關注於未來。從過去進行學習，這是我們進行戰略性推理的一部分，比如說在我們進行人機交互的時候，應該對我們的對手進行更多的分析，來進行進一步的推理等等。謝謝大家。
原文發布時間為：2017-11-12
本文作者:AIWORLD2017
本文來自雲棲社區合作夥伴新智元，了解相關信息可以關注“AI_era”微信公眾號
原文鏈接:【AI VS 人類新高峰】冷撲大師發明人：用於策略推理的超人AI
最後更新：2017-11-13 11:04:54