在不完全信息博弈的德州撲克擊敗人類對手的AI

Topic:  Safe and Nested Subgame Solving for Imperfect-Information Games

5TvZJU2b7a0w0

Editor: George Wu

Resources:   NIPS paper   Science paper   video   中文post

Label:  game theory, Imperfect-Information, Nash equilibrium

簡介

這篇論文是之前卡內基團隊推出的著名的德州撲克 AI (Libratus)大勝四位頂級玩家的不完全信息博弈的paper. 由於是不完全信息所以無法用精確的博弈理論求解, 近似方法就是把遊戲分成很多小局分別求解, 這手段稱為子博弈求解(subgame solving). 這篇論文提出在理論及實際上都比之前更好的子博弈求解方法.

德州撲克玩法

我想不少人對德州撲克(Texas Hold’em poker)比較陌生, 所以這裡先簡介一下它的規則. 德州撲克使用撲克牌的52張牌不包含鬼牌, 玩家要想辦法將自己的兩張底牌及公開桌上的五張公共牌組合成最好的五張牌牌型(同花順>四條>同花…). 贏家將可以拿走賭桌上的所有籌碼. 遊戲流程如下: 每一場開始由莊家的順時鐘開始, 左邊第一位強制先下注(小盲注), 左邊第二位強制接著下注(大盲注). 之後賭桌上的籌碼不能小於大盲注. 接著莊家會發給每個玩家兩張底牌 (只有自己看得到的牌). 接著是兩輪的玩家下賭注, 玩家可以跟注或加注或全押或者棄牌. 接著莊家先在牌桌上發三張公開牌(每位玩家都看得到), 接著再一輪下注. 然後再發一張公開牌再下注一輪, 接著最後一張公開牌再下注一輪. 最後沒棄牌的玩家展示最佳的五張牌型, 贏家拿走全部籌碼. 另外無限注(no-limit poker)的意思是下注金額沒有上限.

Libratus是什麼及有什麼特點?

Libratus是由卡內基美隆大學(CMU) CS系教授Tuomas Sandholm及其學生Noam Brown 開發的德州撲克AI. 在2017年初在匹茲堡就曾舉辦一場人機大賽邀請世界四名頂尖的德州撲克玩家分別進行 1v1 無限注比賽, 結果Libratus 大獲全勝. 而在2017年底將他們的研究成果在2017 NIPS發表並得到Best paper, 更詳細的研究成果發表在Science期刊上. 德州撲克和圍棋相比最大的不同在於很多訊息是未知的, 譬如其他玩家的底牌或對方是否詐唬等. 這類問題被稱為不完美信息博弈(Imperfect-Information Games), 難度也提高了因為很難分解成獨立的子狀況求最佳解, 因為這些未知的信息都會影響到這些子狀況. 這類的問題其實應用性很廣因為像拍賣, 談判, 股市資訊等都牽涉到不完美信息. Libratus的最大貢獻就在於為不完美信息博提供了新的思路, 而另外一個特點在於它是基於傳統博弈論, 並不使用目前最熱門的深度學習技術.

納許均衡(Nash equilibrium) 及嵌套安全子博弈求解(Nested safe subgame solving)

這裡用一個簡單的遊戲(Coin Toss)來解釋Libratus的基本概念. 假設有P1,P2兩人, P1投一枚硬幣如果是人頭則可以獲得0.5元, 如果是字則賠0.5元. 但也可以選擇讓P2猜人頭與字. 如果P2猜對則P2獲得1元, P2猜錯則要給P1 1元. 以P2的角度來看他不知道P1的硬幣是哪一面也不知道P1的策略, 所以這是Imperfect-information subgame. P1的這些未知訊息確實影響了P2 的勝負或金額. 而且P1也可能因應P2採取的戰術而調整策略, 所以不可能將這sub-game獨立出來求最佳解(像AlphaGo一樣), 所以在這裡subgame所要達到的目的為納許均衡, 確保P1無論採取各種策略, P2的策略和P1的策略都是穩當的.

螢幕快照 2018-01-05 上午6.03.29

Figure 1.  Coin Toss遊戲示意圖. 框框處代表P1所能獲得的資訊, 框框之外是P1所做的策略會影響到P2的勝率但P1無法得知. 
在計算sub-game的納許均衡時, 因為是不完美信息博弈所以就像前面所說的無法獨立成子博弈進行計算, 過去的方式在於計算每件事件的機率值, 譬如在這個例子裡P1丟硬幣人頭p=0.5, 字p=0.5, 但這樣無法考量到因應對手調整策略的部分. 他們提出的方式稱為Safe subgame 改為以預估對手最後獲利來計算, 譬如 P1投一枚硬幣如果是人頭則可以獲得0.5元, 如果是字則賠0.5元. 這樣就可以有效的估計及計算子博弈(sub-game)的部分
回到Libratus其實就是把上面的納許均衡子博弈求解概念應用在德州撲克上. 在德州撲克初期兩輪還未發公開牌的玩家下賭注階段, Libratus 使用稱為藍圖策略(blueprint strategy)對牌面進行簡化的計算擬定粗略的策略, 譬如下注200元和201元便可簡化成同樣的效果. 之後再針對子博弈把粗略的策略擴展成更精細的計算, 這就是嵌套安全子博弈求解(Nested safe subgame solving). 並不斷更新局面的訊息強化每一步得到更好的納許均衡點.
螢幕快照 2018-01-05 下午2.09.53.png
Figure 2. (上) 代表開始時訂立的藍圖策略(blueprint strategy), 在圖中紅色部分代表藍圖策略下的某個子博弈,  (中) 應用safe subgame solving 讓子博弈能達到納許均衡, (下)取代紅色變成更精細的子博弈求解. 這稱為嵌套安全子博弈求解(Nested safe subgame solving).

結論

這篇paper提出來的是在不完美信息博弈問題上目前最好的子博弈求解方式, 而且這方式不只適用在德州撲克上, 也適用在所有不完美信息博弈問題上. 透過這樣的方式可以將包含很多未知訊息的局面分解成可計算的子博弈進行求解. 以這個為基礎發展出來的德州撲克AI系統Libratus 應用了(1) 藍圖策略, (2) 嵌套安全子博弈求解, (3) 納許均衡以及(4)持續的自我進化, 在人機大賽上勝過了人類頂尖玩家.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s