AI攻陷多人德撲:訓練成本150美元每小時贏1000刀
2019年07月12日15:01

  文章來源:機器之心

  在無限製德州撲克六人對決的比賽中,德撲 AI Pluribus 成功戰勝了五名專家級人類玩家。Pluribus 由 Facebook 與卡耐基梅隆大學(CMU)共同開發,實現了前輩 Libratus(冷撲大師)未能完成的任務,該研究已經登上了最新一期《科學》雜誌。

  六人無限製玩法是德州撲克最受歡迎的遊戲方式,Facebook 與 CMU 的成果是第一個在擁有兩個(或以上)人類玩家的比賽中擊敗人類專業選手的 AI。

  2017 年 1 月,由 CMU 學者 Noam Brown、Tuomas Sandholm 開發的人工智能程式 Libratus 在賓夕法尼亞州匹茲堡的 Rivers 賭場持續 20 天的 1 對 1 無限製德撲比賽中成功戰勝了 4 名全球頂級職業玩家。這也成為了繼圍棋之後,又一個高難度遊戲被 AI 攻陷的里程碑事件。2017 年底,Libratus 的論文也被《科學》雜誌收錄。

  ‘冷撲大師’使用大量算力和博弈論等方法來攻克信息不完整的紙牌遊戲。該研究的另一篇論文《Safe and Nested Subgame Solving for Imperfect-Information Games》也在當年成為了人工智能頂會 NIPS 2017 的最佳論文。

卡耐基梅隆大學計算機科學教授 Tuomas Sandholm(左)與他的門生,現任 Facebook 科學家 Noam Brown。
卡耐基梅隆大學計算機科學教授 Tuomas Sandholm(左)與他的門生,現任 Facebook 科學家 Noam Brown。

  從 1 對 1 到玩轉 6 人對決,人工智能經曆了怎樣的進步?‘雖然從二到六看起來是一個漸進的過程,但這實際上是一個巨大的挑戰,’研究遊戲與人工智能的紐約大學助理教授 Julian Togelius 表示。‘多人遊戲方面的研究,此前在所有遊戲中都未有出現。’

  在‘冷撲大師’的基礎之上,Noam Brown 與 Tuomas Sandholm 提出的新算法 Pluribus 需要的算力更小。在為期 12 天,超過 10000 手牌的比賽中,Pluribus 擊敗了 15 名人類頂級玩家。‘很多 AI 研究者此前都認為實現這樣的目標是不可能的,’Noam Brown 表示。

  幾十年來,撲克一直是人工智能領域一個困難而又重要的挑戰。原因在於,撲克中含有隱藏信息,也就是說,你無法知道對方的牌。要想在撲克中獲勝,你需要 bluff(嚇唬)或者使用其他策略,這在棋類比賽中一般是不需要的。這一點使得在撲克中應用人工智能變得非常困難。

  現在的人工智能已經學會了 bluff,而且還可以看穿人類選手的 bluff。不過在 Noam Brown 看來,這些技巧也是由數學過程決定的策略。

  據介紹,Facebook 和卡內基梅隆大學設計的比賽分為兩種模式:1 個 AI+5 個人類玩家和 5 個 AI+1 個人類玩家,Pluribus 在這兩種模式中都取得了勝利。如果一個籌碼值 1 美元,Pluribus 平均每局能贏 5 美元,與 5 個人類玩家對戰一小時就能贏 1000 美元。職業撲克玩家認為這些結果是決定性的勝利優勢。

  這是 AI 首次在玩家人數(或隊伍)大於 2 的大型基準遊戲中擊敗頂級職業玩家。以下是關於 Pluribus 的細節。

  論文:Superhuman AI for multiplayer poker

  論文鏈接:https://science.sciencemag.org/content/early/2019/07/10/science.aay2400

  Pluribus 以 Libratus 和其他一些算法、代碼為基礎進行了幾項改進。Libratus 曾於 2017 年在雙人無限注德撲中擊敗人類頂級選手(參見:《學界 | Science 論文揭秘:Libratus 如何在雙人無限注德撲中擊敗人類頂級選手》)。這些算法和代碼都是由 Tuomas Sandholm 帶領的卡內基梅隆大學研究實驗室開發的。

  值得一提的是,Pluribus 整合了一種新的在線搜索算法,可以通過搜索前面的幾步而不是只搜索到遊戲結束來有效地評估其決策。此外,Pluribus 還利用了速度更快的新型 self-play 非完美信息遊戲算法。綜上所述,這些改進使得使用極少的處理能力和內存來訓練 Pluribus 成為可能。訓練所用的雲計算資源總價值還不到 150 美元。這種高效與最近其他人工智能里程碑項目形成了鮮明對比,後者的訓練往往要花費數百萬美元的計算資源。

  這些創新的意義遠不止在撲克遊戲中,因為雙玩家零和交互(一輸一贏)在娛樂遊戲中非常常見,但在實際生活中卻非常罕見。現實世界的——對有害內容採取行動、應對網絡安全挑戰以及管理在線拍賣或導航流量——通常涉及多個參與者和/或隱藏信息。多玩家交互對過去的 AI 技術提出了嚴峻的理論和實踐挑戰。Facebook 的結果表明,一個精心構造的人工智能算法可以在兩人以上的零和遊戲中超越人類的表現

  在 6 人撲克中獲勝

  相比於過去典型的遊戲中,6 人撲克有兩個主要挑戰。

  不只是簡單的雙人零和遊戲

  過去所有遊戲中的突破限製於 2 人或者 2 隊的零和競賽(例如象棋、西洋棋、星際爭霸 2 或者 Dota2)。在這些比賽中,AI 之所以成功,是因為它們試圖評估使用 Nash 均衡策略。在雙人和雙隊的零和遊戲中,無論對手做什麼,作出精確的納什均衡就可能無法輸掉比賽。(例如,石頭剪刀布的納什均衡策略是以相同的概率隨機選擇石頭、布或剪刀。)

  儘管在任何有限製遊戲中都存在納什均衡,但通常在具有三個或更多玩家的遊戲中,難以有效地計算納什均衡。(對於兩人一般和遊戲也是如此。)此外,在兩個以上玩家的遊戲中,即使作出精確的納什均衡策略,也有可能輸掉比賽。例如在遊戲 Lemonade Stand game 中,每個玩家同時在一個圓環上選擇一個點,並且想儘可能遠離任何其他玩家。納什均衡是所有參與者沿著環間隔相等的距離,但是有很多方法可以實現。如果每個玩家獨立計算其中一個平衡點,則聯合策略不太可能導致所有玩家沿著該環間隔開同等距離。如下圖所示:

  除了雙人零和遊戲,納什均衡的缺點引發研究人員思考:這種遊戲的正確目標應該是什麼?

  在六人撲克中,研究者認為其目標不應該是特定的遊戲理論解決概念,而是創建一個長期都能憑經驗擊敗人類對手的 AI,包括精英人類專業人士。(對於 AI 機器人來說,這通常被認為是‘超人’的表現。)

  研究者表示,他們用來構建 Pluribus 的算法並不能保證在雙人零和遊戲之外收斂到納什均衡。儘管如此,它們觀察到 Pluribus 在六人撲克中的策略始終能擊敗職業玩家,因此這些算法,能夠在雙人零和遊戲之外的更廣泛的場景中,產生超人類的策略。

  更複雜環境中的隱藏信息

  沒有其他遊戲像撲克一樣有這麼大隱藏信息的挑戰,每個玩家都擁有其他玩家沒有的信息(自己的牌面)。一個成功的撲克 AI 必須推理這個隱藏的信息,並慎重平衡自己策略(以保持不可預測),同時採取良好的行動。

  例如,bluff 偶爾會有效,但總是 bluff 就容易被抓,從而導致損失大量資金。因此,有必要仔細平衡 bluff 概率和強牌下注的概率。換句話說,不完美信息遊戲中動作的值取決於其被選擇的概率以及選擇其他動作的概率。

  相反,在完美信息遊戲中,玩家不必擔心平衡動作的概率。國際象棋中的好動作,無論選擇的概率如何都是好的。

  像先前 Libratus 這樣的撲克 AI,在兩個玩家無限製德州撲克遊戲這樣的遊戲中,通過基於 Counterfactual Regret Minimization(CFR)理論上合理的自我遊戲算法與精心構造的搜索程式相結合,解決遊戲中的隱藏信息問題。

  然而,在撲克中添加額外的玩家會以指數方式增加遊戲的複雜性。即使計算量高達 10,000 倍,那些以前的技術無法擴展到六人撲克。

  Pluribus 使用的新技術可以比以前的任何東西都更好地應對這一挑戰。

  理解 Pluribus 的藍圖策略

  Pluribus 的核心策略是通過自我博弈的方式學習。在這一過程中,AI 和自己進行對戰,不使用任何人類遊戲數據作為輸入。AI 首先隨機地選擇玩法,接著,隨著決定每一步的行動後,逐漸提升性能,並對這些行動擬合概率分佈。最終,AI 的表現比之前的策略版本會更好。Pluribus 中的自我博弈策略是一種改進版本的蒙特卡洛 CFR(MCCFR)。

  每一次迭代中,MCCFR 指定其中一方為‘traverser’對象,在迭代中更新這一方的當前策略。在迭代開始時,基於所有玩家的當前策略(最開始是完全隨機的),MCCFR 模擬出一幅撲克。當模擬完成時,算法回顧‘traverser’對象的每個策略,並計算如果選擇其他的行動,它的勝率多大程度上能夠提升或下降。之後,AI 再評價根據這一決策實施之後,接下來的每個假設決策的優勢,以此類推。

  探究其他假設的結果是可能的,這是因為 AI 是自我對弈的。如果 AI 想要瞭解其他選擇之後會發生什麼,它只需要問自己如何去回應這些行為。

  ‘traverser’對象實際做了什麼選擇和可能做什麼選擇的差異被加入到反事實後悔(counterfactural regret)行為中。在迭代結束的時候,‘traverser’對象的策略得到更新。因此,有著更高反事實後悔概率的選擇被選中。保持德州撲克這樣沒有限製的遊戲中每一個行動中的策略需要的字節數超過了整個宇宙的原子數。為了減少遊戲的複雜度,研究人員要求 AI 忽略一些行動,並使用一種抽像方法將類似的決策點聚合在一起。在抽像之後,聚合的決策點被認為是獨一無二的。

  Pluribus 的自我博弈結果被稱為藍圖策略。在實際遊戲中,Pluribus 使用搜索算法提升這一藍圖策略。但是 Pluribus 不會根據從對手身上觀察到的傾向調整其策略。

這幅圖顯示了 Pluribus 的藍圖策略是如何在訓練過程中逐漸改進的。其性能通過訓練的最終快照來評估。研究者在這些比較中沒有使用搜索,他們基於與人類專業玩家的討論對普通人類玩家和頂級人類玩家的表現進行評估。該圖還顯示出了 Pluribus 何時停止 limping,這是高級人類玩家通常會去避免的一種打法。
這幅圖顯示了 Pluribus 的藍圖策略是如何在訓練過程中逐漸改進的。其性能通過訓練的最終快照來評估。研究者在這些比較中沒有使用搜索,他們基於與人類專業玩家的討論對普通人類玩家和頂級人類玩家的表現進行評估。該圖還顯示出了 Pluribus 何時停止 limping,這是高級人類玩家通常會去避免的一種打法。

  研究人員訓練藍圖策略用了 8 天,使用了一個 64 核的服務器,需要的內存數量小於 512G。他們沒有使用 GPU。在典型的雲計算中,這隻需要 150 美元。和其他 AI 研究相比,包括其他自我對弈的 AI,這種消耗很小。由於算法上的提升,研究人員可以在低成本的計算環境實現極大的性能提升。

  更高效的搜索策略

  由於無限製德州撲克的規模與複雜性,藍圖策略必須是粗粒度的。在實際過程中,Pluribus 通過實時搜索改進藍圖策略,以針對特定情況確定更好、更細粒度的策略。

  AI bot 經常在很多完美信息博弈中使用實時搜索,包括西洋雙陸棋(two-ply search)、國際象棋(alpha-beta pruning search)、圍棋(Monte Carlo tree search)。例如,當模型在決定下一步該走哪時,國際象棋 AI 通常會考慮以後的一些移動步驟,直到算法的前瞻到達葉節點或深度的上限。

  然而,這些搜索方法並不適合不完美信息博弈,因為它們並不考慮對手轉移到葉節點之外策略的能力。這個弱點令搜索算法產生了脆弱的、不平衡的策略,從而使對手快速發現這個錯誤。AI bot 在以前也就不能將博弈擴展到 6 個參與者。

  相反,Pluribus 使用一種新方法,其中搜索器明確地考慮了不完美信息博弈的實際情況,即任何參與者都可以轉移到子博弈外的葉節點策略上。具體而言,研究者並不假設所有參與者都需要根據葉節點之外的單個固定策略進行博弈,這會導致葉節點只有單個固定值。在搜索已經到葉節點時,研究者假設每一個參與者會從四個不同的策略中選擇,進行賸餘的博弈。

  研究者在 Pluribus 中使用的四個延續策略分別是預計算的藍圖策略;在藍圖策略的基礎上進行修改,以令策略偏置到棄牌;修改藍圖策略以令其偏置到叫牌;修改藍圖策略以令其偏置到加註。

  這種技術可以令搜索器找都一種更均衡的策略,從而在整體性能表現得更好。因為選擇不平衡的策略會使對手轉向其它延續策略,從而產生懲罰。例如玩石頭剪刀布,我只出石頭,那麼對手肯定能學習到只出布的策略。

  正如研究者所指出的,搜索不完全信息博弈的另一個挑戰是,參與者針對特定情況的最佳策略取決於對手對其玩法的看法。例如打德州撲克,如果一個參與者永遠不會 bluff,那麼它的對手總會知道應該在加大注的情況下棄牌。

  為了應對這種情況,Pluribus 根據自身策略,在每一手時追蹤當前狀況的出現概率。不管它實際上在哪一手,Pluribus 首先都會預測每一手時將要採取的行動——從而小心翼翼地在所有手時平衡自身策略,令人類玩家無法預測其下一步行動。一旦計算這一涵蓋所有手的平衡策略,Pluribus 隨後就會為它實際所在的手執行一個操作。

  比賽時,Pluribus 在兩個 CPU 上運行。相比而言,在 2016 年和李世石的圍棋比賽中,AlphaGo 使用了 1920 塊 CPU 和 280 塊 GPU。同時,Pluribus 使用了不多於 128GB 的內存。在對每一個子分支進行搜索的時候,根據現場的情況,它所用的時間介於 1 秒和 33 秒之間。Pluribus 的遊戲時間比人類專業玩家快兩倍:在六人遊戲場景,和自身對弈的時候,它平均每手只需要 20 秒。

  Pluribus 與人類玩家的對抗效果如何?

  研究者令 Pluribus 與一組人類頂級撲克玩家對抗,從而評估它的實戰效果。這些玩家包括‘耶穌’Chris Ferguson(2000 年世界撲克系列賽主賽事冠軍)、Greg Merson(2012 年世界撲克系列賽主賽事冠軍)和 Darren Elias(四屆世界撲克巡迴賽冠軍)。人類玩家的完整名單如下:Jimmy Chou、Seth Davies、Michael Gagliano、Anthony Gregg、Dong Kim、Jason Les、Linus Loeliger、Daniel McAulay、Nick Petrangelo、Sean Ruane、Trevor Savage 和 Jake Toole。

  當 AI 系統在其他基準遊戲中與人類對戰時,機器有時在剛開始的時候表現非常好,但隨著人類玩家發現它們的弱點,最終就會擊敗它們。如果 AI 想要徹底掌控一場遊戲,它必須展示出這樣一種能力,即使人類玩家能夠逐漸適應它們的節奏,但它們也能取得勝利。過去幾天,職業撲克玩家與 Pluribus 進行了數千場比賽,因而有足夠的時間來找出它的弱點,並逐漸適應它。

  Elias 說道:‘Pluribus 是在與世界上最好的撲克玩家進行對抗啊。’

  以下是實驗中 Pluribus 與人類玩家對抗時的界面:

  實驗分為兩種模式:其一,5 名人類玩家與 1 個 AI 進行對抗;其二,1 名人類玩家與 5 個 AI 副本進行對抗。因此,在每一種對抗模式下,共有 6 名玩家參與其中,並且每局開始的時候有 10000 籌碼。小盲(small blind)50 籌碼,大盲(big blind)100 籌碼。

  儘管撲克是一款技巧遊戲,但其中也會有非常大的運氣成分。如果運氣不佳的話,頂級職業玩家也會在 10000 手的撲克比賽中輸錢。為了弱化運氣成分在撲克比賽中的作用,研究者使用了一種 AIVAT 方差縮減算法,該算法對各種狀況的值進行基線估計,從而在保持樣本無偏的同時縮減方差。舉例而言,如果 Pluribus 得到一副強手牌,AIVAT 將從它贏得中減去基準值,從而對抗好運氣。

  5 名人類玩家+1 個 AI

  在實驗中,人類玩家和 AI 之間展開的 10000 手撲克比賽持續了 12 天,每天挑選 5 名人類玩家與 AI 進行比賽。這些玩家將根據自身表現瓜分 50000 美元的獎勵,以激勵他們發揮最佳水平。在採用 AIVAT 後,Pluribus 的勝率預計約為每 100 手 5 個大盲注(標準誤差為 5 bb/100),這對頂級人類撲克玩家而言是巨大勝利(盈利 P 值為 0.021)。所以,如果每個籌碼價值 1 美元,Pluribus 每手平均能贏 5 美元,每小時能贏 1000 美元。這一結果超過了純職業玩家在與職業和業餘混合玩家對抗時的勝率。

  Ferguson 在比賽實驗結束後說道:‘Pluribus 真是太難對付了!我們很難在任何一手中盯死它。它不僅非常擅長進行薄的價值下注,而且擅長從好手牌中贏得最大價值。’

  但值得注意的是,Pluribus 本意是成為 AI 研究的工具,研究者僅將撲克比賽作為一種方式,以衡量 AI 在不完全信息多智能體交互(與人類頂級能力相關)中的進展。

  5 個 AI+1 個人類玩家

  參與實驗的有 Ferguson、Elias 和 Linus Loeliger。Loeliger 是很多人公認的六人無限德撲頂級玩家。每個人與五個 Pluribus AI 玩 5000 手撲克。Pluribus 並沒有根據對手的情況調整策略,因此機器人之間的故意勾結不是問題。總的來說,人類每 100 手損失 2.3 bb。Elias 每 100 手損失 4.0 bb(標準誤差為 2.2 bb/100),Ferguson 每 100 手損失 2.5bb(標準誤差為 2.2 bb/100),Loeliger 每 100 手損失 0.5 bb(標準誤差為 1.0 bb/100)。

  這張圖顯示了 Pluribus 在 10000 手實驗中對職業撲克玩家的平均勝率。直線表示實際結果,虛線表示一個標準差。

  ‘這個 AI 最大的優勢就是它使用混合策略的能力,’Elias 表示。‘人類也想這麼做。對人來說,這是一個執行的問題——以一種完全隨機的方式持續去做。多數人類做不到這一點。’

  由於 Pluribus 的策略完全是在沒有任何人類數據的情況下通過 self-play 自己學到的,因此它也提供了一個外部視角,即在多人無限製德州撲克遊戲中最好的玩法應該是什麼樣子。

  Pluribus 證實了人類傳統的聰明玩法——limping(叫大盲而不是加註或棄牌)對於任何除小盲之外的任何玩家來說都不是最佳策略,因為根據規則,小盲已經下了大盲的一半,因此小盲跟注只需再下一半。

  儘管 Pluribus 最初在通過 self-play 離線計算藍圖策略時嚐試 limping,但隨著 self-play 的繼續,它逐漸放棄了這一策略。

  此外,Pluribus 並不認同 donk 是一種錯誤的觀念(在前一輪投注結束時,開始新一輪加註);與專業人士相比,Pluribus 更喜歡這麼做。

  ‘和撲克 AI 比賽,看到它選的一些策略,真的非常過癮,’Gagliano 表示。‘有幾場人類根本就沒有發揮什麼作用,尤其是它下注比較狠的那幾場。’

這張圖顯示了在與頂尖玩家對戰時 Pluribus 的籌碼數量變化。直線表示實際結果,虛線表示一個標準差。
這張圖顯示了在與頂尖玩家對戰時 Pluribus 的籌碼數量變化。直線表示實際結果,虛線表示一個標準差。

  從撲克到其它不完美信息博弈的挑戰

  AI 以前曾經在完美信息零和博弈(兩個參與者)中取得了多次引人注目的成功。但大多數真實世界策略交互都涉及隱信息,且並非兩個參與者的零和博弈。Pluribus 的成功表明,目前還有更大規模的、極其複雜的多參與者場景,仔細構建的自我博弈和搜索算法能夠在這些場景下獲得很好的效果,儘管當前並沒有很強的理論支援來保證這個效果。

  Pluribus 也非同一般,因為與其它近期的 AI 系統相比,在基準博弈中,它的訓練和推斷成本都要低得多。儘管該領域的一些研究者擔心未來的 AI 研究會被擁有大量計算資源的大型團隊主導。但研究者相信 Pluribus 是一個強有力的證據,說明新方法只需要適當的計算資源,就能驅動頂尖的 AI 研究。

  儘管 Pluribus 是為了玩撲克開發的,但其使用的技術並不是撲克所獨有的,它也不需要任何專家領域的知識進行開發。該研究給我們提供了一個更好的基本理解,即如何構建一般的 AI 以應對多智能體環境,這種環境既包括其它 AI 智能體,也包括人類。同時,搭建一般的多智能體 AI,也能使研究人員將研究過程中取得的 AI 基準成績與人類能力的尖峰做對比。

  當然,在 Pluribus 中採取的方法可能並不會在所有多智能體設定上取得成功。在撲克中,參與方很難有機會與其它智能體溝通,這有可能構建非常簡單的調和博弈(coordination game),因此 self-play 算法找不到一個好策略。

  然而對於很多現實世界的交互,包括反欺詐、網絡安全和內容審核等潛在都能通過 Pluribus 的方法建模。即建模為涉及隱藏信息的場景,並(或)通過多個智能體的有限交流來構建不同參與方間的聯繫。這項打德州撲克的技術甚至允許 Pluribus 幫助 AI 社區在不同領域中構建更高效的策略。

  最後,在過去的 16 年中,Tuomas Sandholm 和 CMU 團隊都在研究策略推理技術。Pluribus 構建並融合了策略推理的大部分技術與代碼,但它同樣也包含了撲克的專門代碼,這些代碼 CMU 和 Facebook 合作完成,且並不會用於國防應用。

關注我們Facebook專頁
    相關新聞
      更多瀏覽