一種德州撲克博弈的決策模型

李 軼，彭麗蓉，杜 松，伍 帆，王 森

（1.重慶理工大學(xué)兩江人工智能學(xué)院，重慶 401135；2.重慶工業(yè)職業(yè)技術(shù)學(xué)院大數(shù)據(jù)與人工智能學(xué)院，重慶 401120）

0 引言

機(jī)器博弈在人工智能領(lǐng)域一直具有重要的研究價(jià)值［1］，根據(jù)博弈信息的可知程度，可將其分為完備信息博弈和非完備信息博弈。完備信息博弈是指博弈各方在決策時(shí)都完全了解曾經(jīng)發(fā)生的所有博弈信息，例如圍棋、象棋和六子棋等；非完備信息博弈是指博弈各方僅能獲取部分信息，無法獲得對方所有信息，例如軍旗或德州撲克，非完備信息博弈的難點(diǎn)就在于此。在完備信息博弈中，極大極小值算法［2］獲得了巨大成功，而在非完備信息博弈中，由于無法得知部分信息，極大極小值中所需的對狀態(tài)的評估過程便無法直接進(jìn)行，也難以推測對手后續(xù)動(dòng)作，因而使原有博弈算法不能直接應(yīng)用于非完備信息博弈中。機(jī)器學(xué)習(xí)中的強(qiáng)化學(xué)習(xí)算法［3］為非完備信息博弈提供了新思路。因此，本文提出一種德州撲克決策模型ACP，并在訓(xùn)練過程中融入先驗(yàn)知識，以提高模型訓(xùn)練效率。將強(qiáng)化學(xué)習(xí)應(yīng)用于非完備信息博弈中，是對計(jì)算機(jī)博弈方法的一次新的探索與嘗試。

1 相關(guān)工作

德州撲克的主要研究方法大多是基于博弈論（gametheoretic）或基于知識（knowledge-based）構(gòu)建的。其中基于博弈論的方法簡單來說就是搜索納什均衡點(diǎn)，德州撲克有很多不同的牌型組合，有限制雙人德州撲克的信息集數(shù)量便達(dá)到了3.19×1014。兩人、三人及多人德州撲克存在博弈樹規(guī)模巨大的問題。針對該問題有兩種解決辦法：①蒙特卡洛樹搜索。不用對博弈樹進(jìn)行全部搜索，通過犧牲較小的精確度可獲得巨大的性能提升；②牌型抽象化。將博弈過程劃分為兩部分：第一部分包括翻牌前、翻牌和轉(zhuǎn)牌3個(gè)階段，第二部分為河牌階段，如果通過勝率進(jìn)行抽象化，就可采用整數(shù)規(guī)劃和狀態(tài)空間算法。如文獻(xiàn)［4］使用平滑區(qū)間UCT 搜索（Smooth UCT Search）算法，可達(dá)到近似納什均衡點(diǎn)。然而，基于博弈論的方法存在的主要問題為：在如此巨大的狀態(tài)空間中求解納什均衡需要消耗大量計(jì)算資源，同時(shí)使用納什均衡策略只能保證自己不輸，因此其期望收益往往很低，在具體博弈場景中實(shí)現(xiàn)難度較大?；谥R的方法主要通過記錄職業(yè)選手比賽數(shù)據(jù)，從相關(guān)數(shù)據(jù)中提取出打牌策略［5］，通?？刹扇「F舉法估算手牌牌力，但窮舉法存在計(jì)算量太大的缺陷。蒙特卡洛搜索能解決計(jì)算量大的問題，如文獻(xiàn)［6］提出在德州撲克博弈系統(tǒng)中使用強(qiáng)化學(xué)習(xí)技術(shù)，采用蒙特卡洛模擬方法計(jì)算勝率作為近似的值函數(shù)回報(bào)；文獻(xiàn)［7］提出采用基于專家知識的方法建立博弈系統(tǒng)，對職業(yè)比賽數(shù)據(jù)進(jìn)行特征提取分析，具體特征包括對手下注列表、潛力等。但是，基于知識的方法缺乏比賽數(shù)據(jù)是德州撲克研究面臨的普遍問題。在數(shù)據(jù)缺乏的情況下，關(guān)鍵在于如何獲得可靠的先驗(yàn)知識以及如何使用先驗(yàn)知識解決策略梯度的收斂問題。為此，本文引入一種德州撲克決策模型ACP，以期解決以上問題。

2 德州撲克決策模型ACP

本文根據(jù)強(qiáng)化學(xué)習(xí)框架［8］建立一種德州撲克決策模型ACP。AC 算法包括Actor 網(wǎng)絡(luò)和Critic 網(wǎng)絡(luò)兩部分，其中Actor 采用基于策略梯度的Reinforce 算法［9］。參數(shù)更新公式為：

式中，πθ(st,at)表示t 時(shí)刻的一種策略，α是學(xué)習(xí)率，vt、st、at分別表示在t 時(shí)刻的獎(jiǎng)勵(lì)、狀態(tài)與動(dòng)作，參數(shù)為θ。在ACP 模型中，Critic 加入先驗(yàn)知識，即首先通過有監(jiān)督學(xué)習(xí)預(yù)訓(xùn)練網(wǎng)絡(luò)參數(shù)，然后在自博弈中實(shí)時(shí)存儲(chǔ)對戰(zhàn)數(shù)據(jù)，再結(jié)合已有數(shù)據(jù)形成系統(tǒng)的知識庫，最后通過損失函數(shù)更新整個(gè)神經(jīng)網(wǎng)絡(luò)［10］。

整個(gè)德州撲克決策模型包含4 個(gè)模塊：卷積神經(jīng)網(wǎng)絡(luò)模塊、預(yù)測勝率模塊、強(qiáng)化學(xué)習(xí)模塊、損失函數(shù)模塊。決策模型結(jié)構(gòu)與網(wǎng)絡(luò)結(jié)構(gòu)如圖1、圖2 所示。

Fig.1 The structure of ACP model圖1 ACP 模型結(jié)構(gòu)

Fig.2 The structure of network圖2 網(wǎng)絡(luò)結(jié)構(gòu)

2.1 卷積神經(jīng)網(wǎng)絡(luò)模塊

德州撲克需要52 張牌（王牌除外），本文將52 張牌用一個(gè)4*13 的0、1 矩陣表示。該模塊的輸入為4*13*1 的矩陣，4 表示高度（height），13 表示寬度（width），1 表示通道數(shù)（filters），中間設(shè)置3 個(gè)卷積層，卷積核為3*3，步長為1，通道數(shù)分別為16、32、64，提取特征得到一個(gè)4*13*64 的矩陣。

2.2 預(yù)測勝率模塊

提取特征得到矩陣4*13*64，通過壓縮層（Flatten）轉(zhuǎn)換為1*3 382 的一維數(shù)組，再通過激活函數(shù)tanh 輸出勝率，勝率值在（-1，1）之間。

2.3 強(qiáng)化學(xué)習(xí)模塊

將特征提取得到的數(shù)據(jù)通過3 個(gè)全連接神經(jīng)網(wǎng)絡(luò)，神經(jīng)元個(gè)數(shù)分別為10、3、1。要注意在第3 層網(wǎng)絡(luò)，數(shù)據(jù)經(jīng)過一次轉(zhuǎn)置才能得到想要的輸出形式。通過第1 層網(wǎng)絡(luò)得到4*10 的矩陣，第2 層網(wǎng)絡(luò)得到4*3 的矩陣，第3 層網(wǎng)絡(luò)得到3*4 的矩陣，第4 層網(wǎng)絡(luò)得到3*1 的矩陣，再通過soft?max 分類器輸出一個(gè)動(dòng)作，用3*1 的矩陣表示。將該動(dòng)作輸入環(huán)境，勝輸出1，負(fù)輸出0，最后將勝負(fù)結(jié)果輸入損失函數(shù)。

2.4 損失函數(shù)模塊

該模型采用的損失函數(shù)為KL 散度（Kullback-Leibler divergence）與交叉熵（Cross Entropy）之和，如式（2）所示。

式中，V網(wǎng)表示網(wǎng)絡(luò)預(yù)測勝率，R網(wǎng)表示動(dòng)作勝率，V標(biāo)表示實(shí)際勝率，損失函數(shù)中包含數(shù)據(jù)庫，數(shù)據(jù)庫記錄獲勝的牌型和牌型勝率，產(chǎn)生實(shí)際勝率。V網(wǎng)對應(yīng)q(xi)，V標(biāo)、R網(wǎng)對應(yīng)p(xi),KL(V網(wǎng),V標(biāo))能夠提高預(yù)測勝率與實(shí)際勝率的相似度，H(V網(wǎng),R網(wǎng))能夠提高動(dòng)作勝率與預(yù)測勝率的相似度。

交叉熵能夠通過判斷不同信息源之間的兩兩相交程度確定相互支持度，并依據(jù)相互支持度確定信息源權(quán)重。相互支持度越高，所占權(quán)重越大［11］。在離散情況下，具體公式為：

其中，p(xi)、q(xi)表示概率矢量，交叉熵表示概率p(xi)與q(xi)之間的距離，即兩概率分布之間的接近程度。

KL 散度用來度量兩個(gè)概率分布的相似程度，可以衡量兩個(gè)隨機(jī)分布之間的距離。當(dāng)兩個(gè)隨機(jī)分布相同時(shí)，其相對熵為零。當(dāng)兩個(gè)隨機(jī)分布的差別增大時(shí)，其相對熵也會(huì)增大［12］，如式（4）所示。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

數(shù)據(jù)來源：ACPC（http：//www.computerpokercompetition.org/downloads/competitions/）、中國大學(xué)生計(jì)算機(jī)博弈大賽（http：//computergames.caai.cn/download.html）以及ACP 模型自我對戰(zhàn)產(chǎn)生的數(shù)據(jù)。

3.1.1 數(shù)據(jù)預(yù)處理

提取勝率和牌型數(shù)據(jù)進(jìn)行預(yù)處理：

（1）按行讀取，提取每一小局比賽數(shù)據(jù)，如手牌和公共牌：QsJd|9sKd|Qd6hTc/Ks/Qc 。

（2）根據(jù)“/”劃分出每個(gè)階段，將手牌、公共牌分別存入一個(gè)數(shù)組。

（3）循環(huán)每個(gè)階段：①讀取時(shí)默認(rèn)從小盲位開始，并對變量賦值，小盲賦值為1，否則為0；②對階段變量賦值，如flop 階段=｛1 0 0｝，turn 階段=｛010｝，river 階段=｛001｝；③讀取對應(yīng)階段公共牌，存在A、K、Q 則相應(yīng)變量賦值為1，否則為0；④判斷是否有2 張相同牌值出現(xiàn)，出現(xiàn)一對牌時(shí)相應(yīng)變量賦值為1，否則為0；⑤判斷是否存在3 張牌值相同的牌，參考步驟④；⑥A、K、Q 在公共牌中出現(xiàn)的次數(shù)統(tǒng)計(jì)，參考步驟④；⑦統(tǒng)計(jì)花色相同的牌數(shù)量，參考步驟④。

（4）存儲(chǔ)處理得到的數(shù)據(jù)到表中。

3.1.2 實(shí)驗(yàn)流程

（1）打牌程序生成2 個(gè)手牌，隨機(jī)輸出公告牌（從flop階段開始記錄），然后輸出勝負(fù)結(jié)果，將手牌信息及勝率記錄到表中。

（2）使用表中數(shù)據(jù)預(yù)訓(xùn)練網(wǎng)絡(luò)參數(shù)。

（3）將完全相同的兩個(gè)模型相互對弈，一個(gè)更新參數(shù)，一個(gè)不更新參數(shù)。訓(xùn)練一定局?jǐn)?shù)后，將更新模型的參數(shù)復(fù)制給不更新的模型，再進(jìn)行對弈。通過模型間不斷的參數(shù)交替，反復(fù)對弈，得到最終版本。

（4）將模型最終版本與其他3 個(gè)版本進(jìn)行對弈，得出結(jié)果。

3.2 損失函數(shù)收斂對比

圖3 為普通PG 模型損失函數(shù)走勢圖，該模型采用與ACP 模型類似的網(wǎng)絡(luò)結(jié)構(gòu)，但不融入先驗(yàn)知識。PG 模型和ACP 模型訓(xùn)練100 000 局，PG 模型損失函數(shù)值在2.25～2.26 之間振蕩幅度較大，隨著訓(xùn)練局?jǐn)?shù)的增加，損失函數(shù)也沒有明顯的收斂趨勢，模型在沒有先驗(yàn)知識的指導(dǎo)下，收斂性較差。圖4 中ACP 模型的損失函數(shù)值在10 000 局后呈現(xiàn)較明顯的收斂趨勢，振蕩幅度減小。因此，融入先驗(yàn)知識的ACP 模型具有更好的收斂性。

Fig.3 Trend of PG model loss function圖3 PG 模型損失函數(shù)走勢

Fig.4 Trend of ACP model loss function圖4 ACP 模型損失函數(shù)走勢

3.3 ACP 模型與其訓(xùn)練版本對比

圖5 為ACP 模型自博弈訓(xùn)練最終版本與其它3 個(gè)版本智能體分別對弈5 000 局的平均收益對比圖（平均收益=當(dāng)前贏得的總籌碼÷當(dāng)前完成局?jǐn)?shù)），版本1 為一個(gè)只會(huì)跟注、不會(huì)棄牌的撲克智能體，版本2 是單純根據(jù)勝率決策的智能體，版本3 是采用ACP 模型自博弈訓(xùn)練了100 000局后的智能體。隨著訓(xùn)練局?jǐn)?shù)的增加，ACP 模型在先驗(yàn)知識的指導(dǎo)下，通過損失函數(shù)不斷更新神經(jīng)網(wǎng)絡(luò)，決策勝率也逐步提高。實(shí)驗(yàn)結(jié)果表明，ACP 模型最終版本與其他3個(gè)版本相比具有一定優(yōu)勢，但不能保證持續(xù)獲得更大的收益。

Fig.5 The game benefits result of ACP model vs 3 agents圖5 ACP 模型與其他3 個(gè)版本對局收益情況

4 結(jié)語

本文從基于知識和基于博弈論兩個(gè)方面簡單介紹了德州撲克的主要決策方法，并根據(jù)強(qiáng)化學(xué)習(xí)框架設(shè)計(jì)了一種德州撲克決策模型。該模型采用AC 算法，融入了先驗(yàn)知識，一定程度上提高了強(qiáng)化學(xué)習(xí)算法的收斂速度。該模型與其他3 個(gè)版本對局時(shí)有較好表現(xiàn)，缺點(diǎn)是ACP 模型的決策不能針對特定對手獲得極限收益。此外，該模型存在高方差、收斂速度慢等缺陷。因此，如何將A3C 算法運(yùn)用于該模型中，對網(wǎng)絡(luò)參數(shù)進(jìn)行分布式訓(xùn)練，同時(shí)提高訓(xùn)練效率，是后續(xù)研究重點(diǎn)。