面向智能博弈游戲的卷積神經網絡估值方法

唐 杰 許華虎 談廣云

1(上海大學計算機工程與科學學院 上海 200444)2(杭州浮云科技網絡有限公司 浙江 杭州 310000)

0 引 言

人工智能研究界中，機器博弈是一個廣受關注的領域。機器博弈具有一組有限的定義良好的規則，研究它們可以方便地測試新的方法，從而準確地衡量新方法的好壞程度。測試是通過比較許多與基于其他方法的程序博弈或與人類選手博弈的結果來完成的，這意味著機器博弈擁有一個定義良好的用于測量其發展進程的度量標準[1]，進而可以更精確地判斷該解決方案是否是解決給定問題的最佳解決方案。此外，機器博弈具有娛樂性，并且對娛樂行業的重要性日益增加，這一事實促進了人們對該領域的進一步研究。

機器博弈研究已經取得了許多顯著的成果，比如著名的深藍計算機，這是第一臺擊敗人類象棋冠軍的計算機[2]。然而，對于非完備信息博弈，尚未取得這樣的成功。因為這類博弈的狀態并不完全可見，意味著存在隱藏的變量/特征。因此，在這類博弈中做出決策更加困難，必須對缺失數據做出預測，這使得獲得最佳解決方案幾乎不可能。

撲克是一款具有這種性質的非常受歡迎的博弈游戲，因為玩家不知道對手的手牌。計算機撲克的研究在過去幾年一直很活躍。人們開發了一些撲克智能程序，但它們都沒有達到類似于專業人類玩家的水平。為了克服在先前開發智能程序過程中出現的問題，本文提出了一個新的思路。該方法試圖利用現在很火的卷積神經網絡來學習人類專家經驗進而讓程序接近或者達到專業人類玩家的水平。

1 背 景

撲克是數百款具有相似規則游戲的通用名稱。計算機撲克研究的重點就是撲克的一種變體——德州撲克，它可能是當今最受歡迎的撲克游戲。德州撲克具有使新開發的方法能夠以較少的成本便能運用在其他種類撲克上的特性。

這個游戲是基于玩家打賭他們現在的手牌比對手的手牌要強的想法。整個游戲中的所有賭注都放在彩池里，游戲結束時，手牌排名最高的玩家獲勝。或者，也可以通過強迫對手下注他們不愿意比賽來贏得比賽。因此，由于對手的牌是隱藏的，用一只得分較低的手牌贏得比賽是有可能的，這是通過虛張聲勢——說服對手自己的手牌是排名最高的一只。

1.1 手牌得分等級

德州撲克中，玩家的手牌指的是由定義玩家得分的5張撲克牌組成的牌組。在游戲的任何階段，手牌等級都是由2張底牌和5張公共牌的組合可能得到的最高得分給出的。可能的手牌等級排行是(從強到弱)：同花順(同一花色，順序的牌)，四條(四張同一點數的牌)，滿堂紅(三張同一點數的牌，加一對其他點數的牌)，同花(五張同一花色的牌)，順子(五張順連的牌)，三條(三張點相同的牌)，兩對(兩張點數相同的牌，加另外兩張點數相同的牌)，一對(兩張點數相同的牌)，高牌(不屬于上面任何一種牌型的牌，由不連續不同花的牌組成，以點數決定大小)。

1.2 德州撲克的規則

德州撲克采用52張撲克牌(除去兩張王牌),游戲玩家人數限制在2～9人。在牌局開始時,荷官會給每個玩家發2張“底牌”(只有個人看到),桌面上會分三次陸續發出3張、1張、1張(共5張)的公共牌,在經過四輪的“加注”、“跟注”和“棄牌”等押注圈操作后,若牌局存在至少兩名玩家仍然沒有棄牌的情況下,進入“攤牌”階段,在自己的2張底牌和5張公共牌中挑選5張卡牌形成牌組,按照牌型大小規則分出勝負,贏家拿下“彩池”中全部籌碼。

1.3 卷積神經網絡

卷積神經網絡(CNN)代表由卷積層、最大池層和完全連接層的各種組合組成的前饋神經網絡，并通過在相鄰層神經元之間實施局部連接模式來利用空間局部相關性。卷積層與最大聚集層交替，模擬哺乳動物視覺皮層中復雜和簡單細胞的性質[3]。CNN由一對或多對卷積和最大池層組成，最終以完全連接的神經網絡結束。典型的卷積網絡結構如圖1所示[4]。

圖1 卷積神經網絡結構

在普通的深度神經網絡(Deep Neural Network，DNN)中，一個神經元與下一層的所有神經元相連。CNN不同于普通神經網絡，因為卷積層的神經元僅根據相對位置稀疏地與下一層的神經元相連。在完全連接的DNN中，每個隱藏節點的輸入都是通過將整個輸入乘以該層中的權重來計算的。然而，在CNN中，每個隱藏層節點的輸入都是通過將部分的局部輸入與權重相乘來計算的。然后在整個輸入空間中共享權重，如圖1所示。屬于同一層的神經元具有相同的權重。權重分配是CNN中的一個關鍵原則，因為它有助于減少訓練參數的總數，并產生更有效的訓練和模型。卷積層之后通常是池化層。

池的作用是使特征在位置上保持不變，并通過池函數概括出卷積層中多個神經元的輸出。典型的池函數是max pooling。max pooling將輸入數據劃分為一組不重疊的窗口，并為每個子區域輸出最大值，降低上層的計算復雜性，并提供一種形式的轉換不變性。為了用于分類，CNN的計算鏈以一個完全連接的網絡結束，該網絡集成了下面層所有特征圖中所有位置的信息。

2 相關工作

構建計算機撲克程序的第一種方法是基于規則的方法，它涉及到為給定的游戲狀態指定應該采取的操作[1]。以下方法基于模擬技術[1，5，7]，即生成隨機實例以獲得統計平均值并決定操作。這些方法指導產生了能夠擊敗弱小的人類對手的智能程序。

1951年Johanson[8]在其《非均衡博弈》博士論文中提出納什均衡理論。自此，計算機撲克研究開始有重大突破，基于納什均衡的方法出現了：最佳響應[10]、受限納什響應[1，11]和數據偏向響應[12]。目前，最好的計算機撲克程序Polaris[12]使用這些方法的混合。

其他最近的方法是基于模式匹配[13-14]和蒙特卡洛樹搜索算法[14-15]。

與本文方法密切相關的成功工作是文獻[16]。它為另一個撲克牌變種——斗地主提供了深度學習方法。這種方法是從地主的角度出發使用卷積神經網絡從一定數量的歷史卡片信息的基礎上，提取出地主的主要特征，并對農民的手牌做出合理的預測。還有Clark等[17]針對圍棋問題提出的一種方法。

盡管取得了所有的突破，但目前還沒有一種已知的方法能使智能程序在與人類玩家博弈時取得很好的成績。

3 基于卷積神經網絡的估值算法

縱觀近幾年關于博弈問題的研究，發現多數的研究者使用淺層人工神經網絡來預測對手在博弈中的決策行為以此來建立對手模型，從而規避非完備信息博弈問題中搜索空間過大以及部分信息不可獲取的難題。本文提出的方法是利用現在流行的卷積神經網絡，學習博弈專家的博弈策略，使得估值算法模型得到的估值更加精確和可信。

3.1 網絡輸入的建模方法

如何對德州撲克棋局狀態建模使之能夠作為卷積神經網絡的輸入是一大挑戰。與處理圖像問題不同，圖像本身就是一個三維的矩陣，可以直接作為神經網絡的輸入，但是德州撲克的棋局狀態則不同。因此，我們必須對其進行建模，轉換成可以直接輸入的形式。

每副撲克牌不包括大小王共有52張牌，分為4種不同花色，分別是黑桃(Spade)、紅桃(Heart)、方塊(Diamond)、梅(Club)，每種花色有13張牌，分別是2、3、4、5、6、7、8、9、10、J、Q、K、A，可以用一個4×13的矩陣來表示每一張牌。但在實際工程中，為了方便卷積層做卷積，我們將這個矩陣用0填充擴充成一個17×17的矩陣。

如圖2所示，在一個三維矩陣的[1,1,8]和[2,1,7]位置填充1，其他位置均為0，這代表牌局開始時，玩家拿到的手牌是黑桃8和黑桃9。

圖2 玩家底牌矩陣模型

阿爾伯塔大學的邁克爾·鮑林教授和他的團隊曾經對影響撲克決策的因素展開過研究。研究發現，自己手牌的牌值大小、當前場上的公共牌、對手的動作序列(比如是跟注和加注等行為)、當前的博弈階段、自己對對手手牌的牌值估計、下注金額等因素都會對博弈的決策產生或多或少的影響。本文綜合考慮了上述的情況，最終得到一個16×17×17的三維矩陣作為CNN網絡的輸入。

表1顯示了二人德州撲克局面信息建模所得的矩陣的具體信息。

表1 二人德州撲克局面信息矩陣建模詳情

3.2 估值算法

博弈是一個狀態不斷變化的過程。實際的博弈過程中，第i層博弈局面的估值應該是基于第i-1層博弈局面的估值，因此它們的估值應該是相差不大的。基于以上的假設可以推出以下結論：

設S1,S2,S3,…,Sn是博弈初始狀態到終局狀態的狀態序列，其中S1代表博弈開始的時候的狀態，Sn代表博弈結束時刻的狀態。E(x)為博弈局面的估值函數，即t時刻的估值就是E(St)。在實際的博弈過程中，博弈體很難做到對所有的中間局面進行準確的估值，但可以輕松地確定終局時刻的博弈局面估值。例如可以設博弈終局時刻的估值為：

E(Sn)=1 代表獲勝

(1)

E(Sn)=0 代表失敗

(2)

第i層博弈局面的估值應該是基于第i-1的。因此，在距離終局的前一時刻的Sn-1的估值可以由下式求出：

E(Sn-1)=γ·E(Sn)

(3)

雖然相鄰兩個狀態的估值相差不大，但也并非是完全相同，因此可以在式中加入一個參數γ滿足γ∈(0,1)，用來調整不同的博弈局面的估值。將該公式進行推廣，可以得到：

E(St-1)=γ·E(St)t=2,3,4,…,n

(4)

對于人工神經網絡來說，在博弈終局時刻的期望輸出可以用式(1)或式(2)來表示，在前面的各個時刻，則可以通過式(3)計算出來。

本文認為學習二維模式(花色和牌值)來代表撲克是很有用的。圖像識別的成功方法建議使用卷積濾波器識別二維圖像中的對象。在文獻[18-20]的啟發下，本文搭建了一個CNN模型，稱為Poker-CNN。文獻[20]采用的深度學習模型中所使用的估值網絡完全沒有做任何局部死活/對殺分析，純粹是用暴力訓練法訓練出一個相當不錯的估值網絡(需要三千萬局自我對局)，而本文提出的估值算法模型考慮了局面因素，能很好地降低網絡訓練所需時間。

3.1節中已經說明了影響撲克決策的種種因素，并對這些因素進行建模最終得到一個16×17×17的三維矩陣作為輸入。網絡的輸出層則應該包含3個節點，分別對應博弈過程中玩家可以做出的3種選擇：棄牌、跟牌和加注。

網絡中設置三個卷積層：第一個隱層設有32個5×5的卷積核，步長為2；第二個隱層設有64個3×3的卷積核，步長為2；第三個隱層設有64個2×2的卷積核，步長為1。與圍棋類似，矩陣中1的位置精確地代表手牌牌值的大小，因此我們必須要保留位置信息，所以本文也舍棄了傳統CNN模型中的pooling層。其后再接一個大小為256×1的全連接層，網絡的最后一層有三個節點。最后將加權輸出輸入到Softmax激活函數再歸一化，以輸出棄牌、跟牌和加注三種行為的概率。網絡的最終結構如圖3所示。

圖3 Poker-CNN模型

本文使用ReLU(Rectified Linear Unit)作為卷積層的激活函數。函數形式如下：

(5)

因為網絡的輸入矩陣是非常稀疏的，所以本文選用在稀疏矩陣中應用較多的Adagrad梯度下降算法。

設定評價函數為E(Si)=max(Y1,Y2,Y3)，它的涵義是取Y1、Y2、Y3三個輸出值中的最大值。針對德州撲克，不同的值可以用來代表玩家跟注、加注和棄牌這三個不同動作。神經網絡模型采用的是MSRA初始化方法，因為MSRA可以加快網絡的收斂。

假設終局局面的狀態為Sn，首先根據Sn調整一次網絡的誤差，然后再根據終局前一時刻Sn-1的估值，計算誤差來調整網絡權值，逐步反向向前計算，直到學習過程結束。可見，由于要獲得終局時刻實際的網絡輸出，估值算法訓練需要在一次完整的比賽記錄之上進行。

(6)

可以通過的卷積神經網絡的不斷學習(即修改期望值)來減小該誤差，綜上所述，可以得出估值算法訓練的幾個主要步驟：

(3) 按照經驗初步設置系數γ和學習速率α(訓練過程中可以修改)。

(4) 依次計算出隱藏層的輸出Cp、實際輸出Yn、期望輸出Yp的修正量并通過反向傳播更新網絡連接權值。

(5) 檢測學習過程是否結束。若結束則轉向步驟9；反之，則繼續執行。

(8) 設p=p-1，轉步驟4。

(9) 結束。

4 實 驗

4.1 實驗環境

表2說明了本文實驗的硬件環境。

表2 實驗環境

4.2 實驗數據

美國人工智能會議(AAAI)或國際人工智能聯合會議(IJCAI)每年都會舉辦世界計算機撲克大賽，該比賽吸引了各國的高校及研究機構參賽。他們中的一些競賽程序具有很高的智能，達到了接近人類大師的程度。

每年比賽的所有比賽數據日志記錄，賽事官網都會保留下來并放在http://www.computerpokercompetition.org/downloads/competitions/供大家下載使用。本文下載了2017年世界計算機撲克大賽共2 809 000條二人限制型博弈比賽數據作為網絡訓練的數據集。

典型的比賽數據如下所示：

STATE:0:cc/cc/cr200c/cr400f:7c4s|2hQh/Ac5h3c/4h/8h:-200|200:Slumbot_ 2pn_ 2017|SimpleRule_ 2pn_ 2017

STATE:1:f:JsTc|5s2d:50|-50:SimpleRule_ 2pn_ 2017|Slumbot_ 2pn_ 2017

STATE:2:cr300c/cc/cr2300f:TcTs|4d5c/5s2dAc/7h:-300|300:Slumbot_ 2pn_ 2017|SimpleRule_ 2pn_ 2017

一條數據表示一局比賽所有的局面狀態信息，例如每輪發的牌以及每輪博弈雙方采取的行動以及最后的輸贏情況。圖4簡要解釋了數據中各項的具體含義。

圖4 歷史比賽數據格式

對這些日志數據進行清洗，然后寫成16×17×17三維矩陣的形式，最后給卷積神經網絡作為網絡的輸入訓練該模型。

4.3 結果分析

4.3.1算法預測準確率分析

本文從數據集中隨機抽取200 000條數據作為訓練集，再在剩余的數據中隨機抽取40 000條數據作為測試集對網絡進行訓練。將訓練集分成4個子集，每個子集50 000條數據，對網路作交叉訓練。選取下式作為結果的準確率計算方法：

(7)

圖5 估值算法的準確率

4.3.2智能體博弈結果分析

本文搭建了一個如圖6所示的智能體博弈系統，該系統通過Socket通信，服務器相當于發牌員，負責發牌給智能體、判定輸贏等。

圖6 智能博弈系統

牌局初始化階段，每個智能體通過特定端口接入到服務器。牌局正式開始后服務器會把牌局各個階段的信息發送給雙方，比如手牌、公共牌、對手是跟牌還是棄牌以及最后的輸贏信息。同時，服務器會生成該局對戰日志放在log文件夾下。

進行對比測試的其他智能體包括：ACPC官方提供的智能體、基于對手建模算法的智能體[21](獲得了2013年ACPC二人限制性德州撲克第四名)，以及基于CFR算法和對手建模的智能體[22](獲得2016年ACPC二人非限制性德州撲克第四名)。

為減少實驗誤差，所有比賽都采用相同的種子，相同的種子玩家獲得的牌也是相同的，即輸贏完全取決于玩家的策略。

通過分析計算系統日志文件中各智能體的勝負以及輸贏籌碼數，可以得到圖7所示結果。圖7給出了本文的智能體與其他3個不同的對手進行博弈時，每局博弈獲得的平均獎勵(各局的平均獎勵用現在手中的總籌碼除以當前的局數表示)。

圖7 實驗智能體與其他智能體對弈每局獲得的平均收益

5 結 語

一個完整的非完備信息博弈系統，主要包括五個部分：博弈系統的表示方法、搜索引擎、估值算法、規則解釋器、通信系統。估值算法主要作用是評估博弈中每一步的好壞程度，因此估值算法是機器博弈程序的核心與關鍵。本文主要以德州撲克的二人限制型博弈作為研究對象。首先對牌局的狀態進行建模，結合阿爾伯特大學團隊對影響德州撲克博弈決策因素的研究，最終得到一個16×17×17的三維矩陣作為估值算法的輸入。估值算法模型的核心是卷積神經網絡，結合文獻[20]的卷積神經網絡設計思想與文獻[18-19]的研究結論最終得到具體的卷積神經網絡模型結構，并用人類大師歷史博弈記錄來訓練該模型。最后將基于該模型的博弈程序與前人開發的博弈程序進行博弈，實驗結果顯示該模型擁有更高的收益。該估值算法模型為大規模機器博弈系統的實現提供了一個可行的方法，同時為將算法拓展到現實生活提供了可能。

雖然基于人類大師經驗的深度神經網絡估值算法模型取得不錯的成績，但是該模型還是要依賴人類的專家知識，并且德州撲克每輪的決策與上一輪的決策有關，也就是說決策具有時序性，因此網絡模型應該具備記憶性，而本文提出的網絡模型沒有解決這個問題。克服以上兩點是下一步研究工作的重點，可以考慮采用強化學習[23]來減少對于人類經驗的依賴以及在不減少模型估值準確率的情況下改善網絡結構，同時可以結合循環神經網絡或者是長短期記憶網絡使網絡模型具備記憶性，從而進一步提高博弈程序的性能。