二打一智力游戲中殘局局面數(shù)據(jù)標(biāo)定方法研究

代鵬程，李淑琴，鄭藍(lán)舟，孟 坤，丁 濛

（1.北京信息科技大學(xué)，北京 100010；2.感知與計(jì)算智能聯(lián)合實(shí)驗(yàn)室，北京 100010；3.微智娛（北京）科技有限公司，北京 100010）

計(jì)算機(jī)博弈作為人工智能的重要發(fā)展方向之一，被稱為人工智能學(xué)科的“果蠅”［1］。計(jì)算機(jī)博弈領(lǐng)域分為完備信息和非完備信息博弈2個(gè)分支。非完備信息博弈的特點(diǎn)是博弈者在博弈過程中無法獲得全部以及可信的局面信息。在非完備信息博弈中，博弈環(huán)境的真實(shí)狀態(tài)往往是不可知的，參與其中的博弈者所掌握的信息是不對(duì)稱和不完備的，這使得非完備信息博弈的研究更為復(fù)雜，更具有挑戰(zhàn)性。現(xiàn)實(shí)世界中的大多數(shù)應(yīng)用都是不完全的信息游戲，如商業(yè)戰(zhàn)略談判、金融投資等，在具有廣闊應(yīng)用場景的非完全信息博弈領(lǐng)域，在面對(duì)這些不確定性問題時(shí)，如何幫助人們找到最優(yōu)策略，亟待進(jìn)一步研究和探索。

目前關(guān)于非完全信息博弈主要有2種思路：第一種是基于博弈論的方法，通過各種方法縮小并創(chuàng)建博弈樹［2-3］，使用類似完全信息博弈的搜索方法遍歷博弈樹、尋找納什均衡點(diǎn)得到最佳策略［4-6］；第二種是基于知識(shí)的方法，通過學(xué)習(xí)大量職業(yè)人類玩家的行動(dòng)特點(diǎn)，結(jié)合人為加入的規(guī)則信息，最終制定博弈策略［7-8］。

傳統(tǒng)計(jì)算機(jī)博弈多專注于完全信息類的棋類游戲。最初，基于Alpha-Beta剪枝［9］的極大極小值搜索被用作計(jì)算機(jī)博弈系統(tǒng)中博弈狀態(tài)樹搜索的通用方法。2015年DeepMind團(tuán)隊(duì)將深度學(xué)習(xí)技術(shù)引入計(jì)算機(jī)博弈之后［10-12］，集成深度學(xué)習(xí)［13］方法在計(jì)算機(jī)博弈領(lǐng)域得到了廣泛關(guān)注與長足的發(fā)展。AlphaGo使用的卷積神經(jīng)網(wǎng)絡(luò)本質(zhì)上屬于監(jiān)督學(xué)習(xí)方法，一般來說好的學(xué)習(xí)模型的生成，需要大量的標(biāo)定樣本進(jìn)行訓(xùn)練，才能使其具有良好的泛化效果。

德州撲克作為非完全信息博弈的代表游戲，在2015年Univ of Alberta設(shè)計(jì)的Cepheus［14］已經(jīng)解決兩人有限注德州撲克，但因?yàn)橥婕业倪x擇比較少且可以強(qiáng)行計(jì)算，其使用CFR+得到的策略離納什均衡點(diǎn)非常接近。在2017年CMU設(shè)計(jì)的Libratus［4］中，基于CFR使用更優(yōu)化的子樹解決方案endgame solving以細(xì)化狀態(tài)空間和策略空間，在不斷的自我提升中，達(dá)到更高的智能水平，在非完全信息博弈上人類再一次輸給了AI。

本文基于博弈論的方法，對(duì)非完全信息二打一智力游戲進(jìn)行研究，主要使用CNN模型對(duì)非完全信息博弈中局面數(shù)據(jù)的標(biāo)定問題進(jìn)行研究。

1 二打一智力游戲規(guī)則簡介

二打一智力游戲（也稱“斗地主”）是一種玩法簡單、娛樂性強(qiáng)的撲克游戲。撲克牌一共54張，二打一智力游戲需由3名玩家進(jìn)行，每人首先有17張手牌，底牌有3張。其中1名玩家根據(jù)手牌選擇要底牌，該玩家成為地主，其余2名玩家則為農(nóng)民，2個(gè)農(nóng)民合作與之對(duì)戰(zhàn)。地主位先出牌，其次為地主下家（逆時(shí)針第一個(gè)農(nóng)民），最后是地主上家（逆時(shí)針第二個(gè)農(nóng)民），以某一玩家率先出盡手中牌來結(jié)束牌局判定勝負(fù)，并計(jì)算本局小分。二打一智力游戲?qū)儆诜峭耆畔⒉┺拇碛螒颍螒騾⑴c者都用私人信息，所以任意1名玩家只知道自己的手牌以及以往的出牌情況。游戲規(guī)則為火箭最大，可以打任意其他的牌。炸彈比火箭小，比其他牌大。都是炸彈時(shí)按牌的分值比大小。除火箭和炸彈外，其他牌必須要牌型相同且總張數(shù)相同才能比大小。對(duì)牌、3張牌都按分值比大小。順牌按最大的一張牌的分值來比大小。單牌按分值比大小，依次是：大王＞小王＞2＞A＞K＞Q＞J＞10＞9＞8＞7＞6＞5＞4＞3，不分花色。二打一智力游戲牌型如表1所示。

表1 二打一智力游戲牌型

2 局面標(biāo)定的設(shè)計(jì)與實(shí)現(xiàn)

基于Alpha-Beta剪枝的極大極小值搜索被稱為Alpha-Beta搜索，被廣泛用于計(jì)算機(jī)博弈狀態(tài)樹的搜索中。可以將Alpha-Beta搜索結(jié)果作為當(dāng)前局面下評(píng)分最高的決策。AlphaGo使用的卷積神經(jīng)網(wǎng)絡(luò)本質(zhì)上屬于監(jiān)督學(xué)習(xí)方法，一般來說好的學(xué)習(xí)模型的生成，需要大量的標(biāo)定樣本進(jìn)行訓(xùn)練，才能具有良好的泛化效果。本文首先對(duì)大量實(shí)際平臺(tái)打牌的原始數(shù)據(jù)進(jìn)行預(yù)處理，提取殘局局面數(shù)據(jù)，通過將2個(gè)農(nóng)民玩家看作一家進(jìn)行Alpha-Beta完全搜索來進(jìn)行局面標(biāo)定。然后根據(jù)得到的標(biāo)定樣本設(shè)計(jì)CNN網(wǎng)絡(luò)的結(jié)構(gòu)，將原始數(shù)據(jù)以合適的方式組合成模型的輸入數(shù)據(jù)，數(shù)據(jù)經(jīng)過網(wǎng)絡(luò)的特征提取過程后獲得模型，使其能夠?qū)Χ蛞恢橇τ螒驓埦诌M(jìn)行局面評(píng)估。具體設(shè)計(jì)框架如圖1所示。

圖1 模型框圖

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

數(shù)據(jù)預(yù)處理主要包括對(duì)原始數(shù)據(jù)的清洗和對(duì)殘局?jǐn)?shù)據(jù)的提取。

2.1.1 原始數(shù)據(jù)形式與含義

本文處理的數(shù)據(jù)來源于國內(nèi)某知名網(wǎng)絡(luò)游戲公司的真實(shí)數(shù)據(jù)，原始數(shù)據(jù)存儲(chǔ)于文本文件中，一行數(shù)據(jù)包含平臺(tái)一次游戲的完整流程，即賬號(hào)、初始手牌與底牌、叫牌過程、出牌過程。所有數(shù)據(jù)由2種分隔符分割開來，其中SOH是ASCII中的01號(hào)對(duì)應(yīng)的字符；SXT是02號(hào)對(duì)應(yīng)的字符。SOH用于分割上述CSBP流程，SXT用于分割不同流程內(nèi)的不同內(nèi)容，如圖2所示，為便于觀察，此時(shí)將數(shù)據(jù)以不同流程顯示為4行，真實(shí)數(shù)據(jù)中為1行存儲(chǔ)。

圖2 原始數(shù)據(jù)存儲(chǔ)形式

第一行使用SXT分割不同的賬號(hào)信息，使用SOH與第二行的初始手牌與底牌分割；第二行中前3個(gè)位置為3名玩家的初始手牌，“4TA”代表底牌；第三行為叫牌過程，“bid”代表“叫地主”，“twice”代表“加倍”，最后一個(gè)加倍的玩家成為地主，圖中0號(hào)位玩家成為地主；第四行為出牌過程，“0，1，4448”代表“0號(hào)位玩家出牌4448”，以“0，1，2，0，1…”的循環(huán)順序從地主先開始出牌。癩子牌局會(huì)在底牌位置標(biāo)記一張正牌，它可以充當(dāng)任何正牌。

2.1.2 數(shù)據(jù)集的構(gòu)成

數(shù)據(jù)清洗是為了把臟數(shù)據(jù)清洗掉，提高數(shù)據(jù)質(zhì)量，其結(jié)果質(zhì)量直接關(guān)系到模型效果和最終結(jié)論。此部分主要經(jīng)過2個(gè)數(shù)據(jù)清洗步驟：

第一步，剔除癩子局?jǐn)?shù)據(jù)。在游戲日志中，包括正常局與癩子局（癩子局是二打一智力游戲中另一種游戲形式，整體與正常局相似，但另外有一張“癩子牌”，其可以與除大小王外的其他牌組合到一起，得到更加靈活的出牌組合）比賽記錄，而本文只研究正常局的猜牌算法，所以先剔除癩子局?jǐn)?shù)據(jù)。

第二步，剔除回合數(shù)太少的數(shù)據(jù)。在經(jīng)過第一步清洗后的游戲數(shù)據(jù)中，隨機(jī)選取了24萬局?jǐn)?shù)據(jù)，對(duì)每局所花的回合數(shù)進(jìn)行統(tǒng)計(jì)，發(fā)現(xiàn)回合數(shù)大部分集中于6到12回合中。如圖3所示。二打一智力游戲中地主先出牌為游戲的開始，以地主、下家、上家的順序依次出完牌為一回合。一般若回合在6步左右游戲就結(jié)束的話，通常某方牌比較大，此玩家會(huì)連續(xù)出牌而其他方基本無法出牌，于是將原數(shù)據(jù)中6步以內(nèi)就游戲結(jié)束的牌局剔除掉，最終得到400萬游戲數(shù)據(jù)。

圖3 以不同回合數(shù)結(jié)束對(duì)應(yīng)的局?jǐn)?shù)（24萬數(shù)據(jù)）

2.1.3 基于啟發(fā)式規(guī)則的殘局?jǐn)?shù)據(jù)

通過統(tǒng)計(jì)分析發(fā)現(xiàn)二打一智力游戲倒數(shù)第三回合的局面有以下特點(diǎn)：第一，地主和2個(gè)農(nóng)民所剩的手牌已經(jīng)不多。第二，比較容易人為判斷結(jié)局的輸贏。不同的回合選用對(duì)數(shù)據(jù)分析的過程和結(jié)果會(huì)有影響。對(duì)倒數(shù)第四回合局面進(jìn)行分析發(fā)現(xiàn)地主和2個(gè)農(nóng)民玩家手牌所剩數(shù)量較多，而且牌型相對(duì)復(fù)雜。故提取倒數(shù)第三回合殘局?jǐn)?shù)據(jù)，但并不是僅采用單一規(guī)則進(jìn)行殘局提取。采用殘局是因?yàn)楸疚氖褂玫木_標(biāo)定方法是Alpha-Beta剪枝，該方法在非殘局狀態(tài)下會(huì)耗時(shí)較長。

在400萬游戲數(shù)據(jù)中提取殘局?jǐn)?shù)據(jù)，具體運(yùn)用了以下規(guī)則：第一，提取倒數(shù)第三回合局面數(shù)據(jù)；第二，總手牌數(shù)少于30張；第三，任何一個(gè)玩家手牌數(shù)量少于13張。經(jīng)過提取后的數(shù)據(jù)作為本文實(shí)際處理的數(shù)據(jù)集。

2.2 基于Alpha-Beta的標(biāo)定數(shù)據(jù)集

二打一智力游戲局面尤其是接近殘局的局面下，決策近乎唯一。從游戲牌局記錄中提取殘局?jǐn)?shù)據(jù)，對(duì)于二打一智力游戲來說，地主和2個(gè)農(nóng)民所剩手牌已經(jīng)不多，在這種殘局情況下進(jìn)行Alpha-Beta搜索，可以找出最佳出牌路徑，通過搜索到底得到精確的輸贏反饋值，進(jìn)而對(duì)局面進(jìn)行標(biāo)定。

Alpha-Beta搜索經(jīng)常用于計(jì)算機(jī)零和博弈游戲中。二打一智力游戲作為一種非完全信息博弈游戲，可以將2個(gè)農(nóng)民看作一家，與地主進(jìn)行競爭，也就可以轉(zhuǎn)化為零和博弈問題。在建立博弈樹的過程中，地主狀態(tài)層和農(nóng)民狀態(tài)層交替建立，2個(gè)農(nóng)民玩家出牌情況看作一種狀態(tài)。3者博弈樹如圖4所示。其中白子代表地主，黑子代表農(nóng)民，在當(dāng)前局面下出牌記為1，不出牌記為0，（0，0）表示2個(gè)農(nóng)民都不出牌，以此類推。

圖4 二打一智力游戲博弈樹

完全搜索局面標(biāo)定法步驟如下：

①從游戲記錄中取出殘局?jǐn)?shù)據(jù)作為當(dāng)前局面；

②對(duì)當(dāng)前局面執(zhí)行Alpha-Beta完全搜索，記錄出現(xiàn)的炸彈數(shù)量num；

③若Alpha-Beta完全搜索判定地主勝利進(jìn)入步驟④，否則進(jìn)入步驟⑤；

④將當(dāng)前局面價(jià)值標(biāo)定為1+num；

⑤將當(dāng)前局面價(jià)值標(biāo)定為-1-num。

具體實(shí)現(xiàn)的偽代碼如圖5所示。

圖5 完全搜索標(biāo)定偽代碼

經(jīng)過對(duì)二打一智力游戲殘局進(jìn)行Alpha-Beta完全搜索，得到的局面價(jià)值有-4、-3、-2、-1、1、2、3、4共8種。如果完全搜索過程中沒有出現(xiàn)炸彈，則地主獲勝標(biāo)為1，農(nóng)民獲勝標(biāo)為-1。如果搜索過程中出現(xiàn)1個(gè)炸彈，則地主獲勝標(biāo)為2，農(nóng)民獲勝標(biāo)為-2，依此類推。局面估值以勝負(fù)和炸彈數(shù)作為標(biāo)定依據(jù)，是因?yàn)樵诙蛞恢橇τ螒蛑杏谐霈F(xiàn)炸彈獎(jiǎng)勵(lì)加倍情況，對(duì)游戲結(jié)果有較大的影響。

2.3 基于CNN的殘局局面標(biāo)定模型

本文將CNN模型應(yīng)用到二打一智力游戲中，對(duì)游戲局面進(jìn)行特征提取，總結(jié)一定的特征規(guī)律，來對(duì)殘局狀態(tài)進(jìn)行局面標(biāo)定。首先對(duì)經(jīng)過完全搜索得到的標(biāo)定數(shù)據(jù)進(jìn)行合理的數(shù)據(jù)表示，將其量化；其次設(shè)計(jì)CNN網(wǎng)絡(luò)的結(jié)構(gòu)，將數(shù)據(jù)以合適的形式組合成模型的輸入，數(shù)據(jù)經(jīng)過網(wǎng)絡(luò)的多層特征提取后，進(jìn)而得出當(dāng)前局面的估計(jì)值，從而進(jìn)行局面標(biāo)定。

2.3.1 數(shù)據(jù)量化

不考慮花色，撲克牌牌面從“A”到“K”共13張牌，將大小王牌看做2種牌，為此將每一副牌的維度設(shè)置為15，其中牌型“10”用“T”表示，牌型“小王”用“B”表示，牌型“大王”用“R”表示，如圖6所示。直接使用相應(yīng)數(shù)字來表示牌型數(shù)量，其中“A”到“K”的總牌數(shù)為4張，大小王各為1張，如圖7為總牌的數(shù)據(jù)表示形式。

圖6 每一維度牌型意義

圖7 總牌牌型數(shù)量表示

2.3.2 CNN整體網(wǎng)絡(luò)設(shè)計(jì)

在設(shè)計(jì)CNN網(wǎng)絡(luò)的過程中，要將3個(gè)玩家的手牌信息充分體現(xiàn)出來，將所有局面特征層堆疊起來，經(jīng)過網(wǎng)絡(luò)的多層特征提取，將原始數(shù)據(jù)抽取為高緯度特征，使其經(jīng)過訓(xùn)練得到的模型可以對(duì)殘局手牌進(jìn)行局面標(biāo)定。圖8為CNN網(wǎng)絡(luò)設(shè)計(jì)。

圖8 CNN網(wǎng)絡(luò)設(shè)計(jì)

2.3.3 CNN模型輸入與輸出

如何將游戲?qū)謹(jǐn)?shù)據(jù)轉(zhuǎn)化為適合于CNN模型的數(shù)據(jù)格式非常重要，也是本文的研究重點(diǎn)。因?yàn)橛螒蛟跀?shù)據(jù)表示上，并未像圍棋一樣出現(xiàn)類似矩陣的局面，所以需要設(shè)計(jì)將量化得到的局面標(biāo)定數(shù)據(jù)規(guī)約到可用于深度學(xué)習(xí)的輸入模式上。在玩家數(shù)據(jù)表示上，以地主、地主下家、地主上家順序鏈接。將所有局面特征層堆疊起來，就組成了符合CNN模型輸入要求的多通道圖像。本文設(shè)計(jì)的模型設(shè)置了3個(gè)通道表示游戲中的3個(gè)玩家，每個(gè)通道抽取單一玩家全部手牌特點(diǎn)，包括單牌、對(duì)子、三帶、連對(duì)、飛機(jī)、順子、炸彈、王炸8種牌型以及總牌共9種特征。CNN輸入維度為［9×15×3］，“3”表示3個(gè)玩家，“9”表示9種手牌特征，“15”表示每種數(shù)據(jù)信息的數(shù)字表示維度，如圖9所示。

圖9 模型輸入設(shè)計(jì)

CNN模型由3層的卷積層、2層全連接層組成。在模型輸出上，使用分類方法，由于完全搜索得到的估值有-4、-3、-2、-1、1、2、3、4共8種結(jié)果。故將模型輸出設(shè)置為8類。如圖10所示。第一個(gè)卷積層選取［3×5］的卷積核，其余卷積層都是［3×3］的卷積核，卷積核的輸出經(jīng)過ReLU激活函數(shù)的調(diào)整可以極大地加快收斂速度。第一個(gè)全連接層設(shè)有32個(gè)節(jié)點(diǎn)，最后一層有8個(gè)節(jié)點(diǎn)，加權(quán)輸出的結(jié)果經(jīng)過softmax激活函數(shù)，將輸出結(jié)果歸一化到相加值為1的約束上，用于輸出相應(yīng)估值的概率。在輸出結(jié)果中取出概率最大的類作為模型的預(yù)測結(jié)果。整個(gè)計(jì)算用梯度下降訓(xùn)練。

圖10 模型輸出表示

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

原始數(shù)據(jù)為國內(nèi)某著名平臺(tái)的真人pk日志，經(jīng)過數(shù)據(jù)清洗后進(jìn)行Alpha-Beta完全搜索，共得到了400萬標(biāo)定數(shù)據(jù)，首先對(duì)這些數(shù)據(jù)進(jìn)行劃分，其中90%作為訓(xùn)練數(shù)據(jù)集，10%作為測試數(shù)據(jù)集，使用這些二打一智力游戲數(shù)據(jù)訓(xùn)練局面標(biāo)定網(wǎng)絡(luò)。CNN算法使用TensorFlow編寫，在一個(gè)GPU核上訓(xùn)練，型號(hào)為TITAN Xp。訓(xùn)練時(shí)使用的batchsize大小為500，學(xué)習(xí)率為0.001，優(yōu)化器使用adam，loss為真實(shí)數(shù)據(jù)與預(yù)測結(jié)果的交叉熵（式（1）），其表達(dá)式為：

式中：y表示期望的輸出，a表示神經(jīng)元實(shí)際輸出，x表示樣本，n表示樣本的總數(shù)。優(yōu)化目標(biāo)為最小化loss，當(dāng)模型實(shí)際輸出接近真實(shí)結(jié)果時(shí)，C的值會(huì)逐漸減小。訓(xùn)練時(shí)每次輸入一個(gè)batchsize大小的數(shù)據(jù)，記為一個(gè)epoch，當(dāng)模型訓(xùn)練進(jìn)行一定程度時(shí)，模型逐漸擬合，正確率不再明顯提高。圖11為測試過程的正確率變化，其中縱坐標(biāo)為模型正確率，橫坐標(biāo)為epoch。

圖11 測試過程正確率

模型經(jīng)過訓(xùn)練，在測試集上正確率可以達(dá)到85.5%，對(duì)數(shù)據(jù)集進(jìn)行分析，發(fā)現(xiàn)數(shù)據(jù)集標(biāo)簽為-1，+1的最多，大約占70%，也就是出牌過程無炸彈的最多，標(biāo)簽為-2，+2的大約占20%，也就是出牌過程中出現(xiàn)1個(gè)炸彈的牌局，其他占10%。按照真實(shí)的比例進(jìn)行訓(xùn)練集數(shù)據(jù)的劃分。

將錯(cuò)誤標(biāo)定的牌挑出分析，發(fā)現(xiàn)至少存在1個(gè)玩家手牌數(shù)量大于10張，因此發(fā)現(xiàn)選取后三回合在玩家手牌數(shù)量小于10張的情況下進(jìn)行局面標(biāo)定有一定的優(yōu)勢，但是玩家手牌數(shù)量大于10張時(shí)進(jìn)行標(biāo)定效果不太好，需要后面進(jìn)一步探討。

4 結(jié)論

估值方法的優(yōu)劣，直接影響著博弈的結(jié)果。博弈雙方或多方根據(jù)自身的特點(diǎn)和走法，確定自己的博弈策略和博弈走法，誰對(duì)棋面和整個(gè)局勢的評(píng)估越準(zhǔn)確，誰的搜索深度越深，那么誰就將在博弈中占有優(yōu)勢。為非完全信息博弈進(jìn)行局面評(píng)估，首先將兩個(gè)農(nóng)民玩家看作一家，進(jìn)而轉(zhuǎn)化為零和博弈問題，進(jìn)行Alpha-Beta完全搜索標(biāo)定局面。然后將游戲數(shù)據(jù)規(guī)約到適合模型的形式，使游戲數(shù)據(jù)適合模型輸入，并在一定程度上有利于模型特征的提取，模型根據(jù)手牌情況給出估值。二打一智力游戲智能程序在保證效率的搜索能力下，結(jié)合局面估值，可以具備較好的分辨能力。下一步將對(duì)至少存在1個(gè)玩家手牌數(shù)量大于10張的情況進(jìn)行研究分析。