一種德州撲克牌力評(píng)估方法

張小川，杜 松，趙海璐，劉 賀，伍 帆

(1.重慶理工大學(xué) 兩江人工智能學(xué)院， 重慶 401135；2.重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 重慶 400054)

計(jì)算機(jī)博弈是人工智能研究中的一個(gè)重要領(lǐng)域，以人類(lèi)所創(chuàng)造的博弈類(lèi)智力游戲?yàn)橹?，如中?guó)象棋[1]、圍棋[2]、二打一撲克[3]、兵棋推演[4]等。非限制性德州撲克作為不完美信息博弈，其博弈狀態(tài)空間達(dá)到10165級(jí)別[5]，是一項(xiàng)極為困難的牌類(lèi)博弈。

近年來(lái)，開(kāi)發(fā)頂級(jí)德州撲克博弈智能體主要基于以下2種方案：尋找納什均衡策略[6]、對(duì)手模型[7]。2種方案都涉及到牌力評(píng)估。反事實(shí)遺憾最小化算法(CFR)[8]是求解納什均衡策略的熱門(mén)算法。CFR需要計(jì)算期望手牌牌力來(lái)完成信息集抽象，以此簡(jiǎn)化博弈狀態(tài)空間。智能體建立對(duì)手模型需要以對(duì)手特定牌力時(shí)的動(dòng)作概率分布為依據(jù)[9]。牌力也可以直接用作智能體行為決策的依據(jù)[10]。優(yōu)秀的人類(lèi)玩家必須能夠?qū)ψ陨砼屏珳?zhǔn)地評(píng)估，對(duì)于計(jì)算機(jī)博弈智能體而言同樣如此。

傳統(tǒng)牌力評(píng)估方法如TPT(two-plus-two)[11]、Bit Manual[12]、ARS(average rank strength)[13]等，計(jì)算數(shù)學(xué)以領(lǐng)先對(duì)手的自然概率作為牌力。這種靜態(tài)的方法忽略了游戲中的動(dòng)作信息，且不能針對(duì)不同風(fēng)格的對(duì)手調(diào)整，導(dǎo)致牌力評(píng)估往往不夠準(zhǔn)確。

為了使智能體對(duì)自身牌力有更為準(zhǔn)確的認(rèn)識(shí)，提升智能體對(duì)抗不同風(fēng)格對(duì)手的實(shí)際效益，本文中提出一種方法，通過(guò)創(chuàng)建對(duì)手模型來(lái)輔助牌力評(píng)估。該方法充分利用已知信息，使智能體可以根據(jù)不同的對(duì)手調(diào)整自身策略，從而獲得更大的收益。

1 背景

1.1 基本概念

德州撲克是2～10人以不帶王牌的52張牌進(jìn)行的撲克游戲。一局游戲有4個(gè)階段：Pre-flop、Flop、Turn、River。Pre-flop階段每名玩家獲得2張手牌僅自己可見(jiàn)，之后的每個(gè)階段分別發(fā)出3張、1張、1張公告牌。經(jīng)過(guò)4個(gè)階段的下注后進(jìn)入攤牌階段，未棄牌的玩家從公共牌與手牌共7張牌中選出5張組成最大成牌決勝。每個(gè)階段玩家可執(zhí)行4個(gè)動(dòng)作：Fold、Check、Call、Raise。根據(jù)玩家的動(dòng)作概率分布可以將玩家風(fēng)格分為兇、弱、緊、松。本文的研究以2人非限制性德州撲克為主要研究對(duì)象展開(kāi)。

游戲中，假定牌桌上所有的牌的集合為Δ，玩家的手牌集合為Φ，場(chǎng)上的公共牌的集合為Ω，任何一位玩家的手牌不會(huì)與公共牌重合。排名值函數(shù)可定義為Rank=f([Δ]5)。玩家從手牌與公共牌的合集中選出5張牌的組合，該組合的排名值是最大的。該過(guò)程可由式(1)表示：

Rank=max({?x∈[Φ∪Ω]5∶f(x)})

(1)

排名值可類(lèi)比為一手牌的得分，當(dāng)牌局進(jìn)入攤牌階段時(shí)，得分最高的玩家將贏得所有籌碼。牌力表示玩家的排名值大于其他未棄牌玩家的概率，取值在0～1。簡(jiǎn)言之，牌力是一個(gè)玩家在攤牌階段中獲勝的概率。

1.2 牌力評(píng)估算法

通常，牌力值的計(jì)算使用式(2)[14]：

(2)

式中：Total、Ahead、Tied分別表示對(duì)手手牌可能的組合總數(shù)、領(lǐng)先的組合數(shù)、排名值相等即平局的組合數(shù)；n表示場(chǎng)上對(duì)手的數(shù)量。在牌局未進(jìn)行到River階段時(shí)，尚有公共牌未發(fā)出，此時(shí)需要考慮潛力，使用式(3)[14]來(lái)計(jì)算有效牌力值。

EHSn=HSn+(1-HSn)×Ppot

(3)

式中：Ppot表示發(fā)出新的公共牌后反超或平局的概率。在Flop階段，有2張公共牌未發(fā)出，此時(shí)使用式(3)求解有效牌力值需要計(jì)算排名值約106次。優(yōu)化排名值的計(jì)算能提高評(píng)估算法的整體效率。

TPT[11]算法是一種快速計(jì)算排名值的算法。它需要一個(gè)250 M大小的查找表。該算法利用嵌套表結(jié)構(gòu)，每個(gè)條目存儲(chǔ)著當(dāng)前索引對(duì)應(yīng)的排名值和另一個(gè)表，表中包含所有后續(xù)狀態(tài)。以每張牌的信息作為索引，可以對(duì)應(yīng)找到包含此牌的排名值和下一個(gè)狀態(tài)，在查找牌的數(shù)量n次后可得n張牌所代表的排名值。此處n可以是5、6、7，TPT算法支持5、6、7張牌的排名值直接查找，有效提高了效率。王帥等[12]提出Bit Manual算法以5張牌為基礎(chǔ)計(jì)算排名值。用一個(gè)64位整數(shù)表達(dá)5張牌忽略花色后的牌值信息，通過(guò)簡(jiǎn)單的位運(yùn)算判別牌型后，結(jié)合排序后的牌值計(jì)算出排名值。該方法節(jié)約了空間占用，但效率并不高。高強(qiáng)等[15]提出一種基于經(jīng)驗(yàn)的德州撲克博弈系統(tǒng)架構(gòu)，在系統(tǒng)的估值核心模塊中，設(shè)計(jì)哈希表存儲(chǔ)排名值，通過(guò)查詢哈希表，比較排名值來(lái)快速判別勝負(fù)。

一些算法不依據(jù)式(3)來(lái)評(píng)估牌力。Teófilo等[13]提出ARS來(lái)替代由式(3)計(jì)算得到的EHS值。該算法采用3個(gè)10 M的查找表，分別對(duì)應(yīng)3個(gè)階段(Flop、Turn、River)。每個(gè)表中存儲(chǔ)167種手牌發(fā)展成7 462種排名值時(shí)對(duì)應(yīng)狀態(tài)的平均有效牌力值。唐杰等[16]利用卷積神經(jīng)網(wǎng)絡(luò)，加入對(duì)手動(dòng)作等因素評(píng)估當(dāng)前局面，將勝負(fù)結(jié)果作為網(wǎng)絡(luò)輸出，其準(zhǔn)確率達(dá)到了89%。此類(lèi)監(jiān)督學(xué)習(xí)的方法存在一定缺陷，非完美信息博弈中專(zhuān)家經(jīng)驗(yàn)可能是不可靠的，因此難以提取深度學(xué)習(xí)所需的高質(zhì)量數(shù)據(jù)。張佳佳等[17]采用深度強(qiáng)化學(xué)習(xí)，提出一種基于蒙特卡羅采樣的算法來(lái)計(jì)算終結(jié)狀態(tài)的期望勝率與期望獎(jiǎng)勵(lì)，減小不完全信息條件下的數(shù)據(jù)波動(dòng)影響。

多數(shù)算法旨在優(yōu)化使用式(2)(3)的計(jì)算效率，且默認(rèn)對(duì)手持有每種手牌的概率是一樣的?？紤]對(duì)手動(dòng)作和行為模式，例如一個(gè)謹(jǐn)慎的對(duì)手在Pre-flop階段大額加注，那么他持有AK的概率和27的概率顯然是不一樣的，且前者應(yīng)該遠(yuǎn)遠(yuǎn)大于后者。因此，本文中通過(guò)建立對(duì)手模型，結(jié)合對(duì)手動(dòng)作信息來(lái)估算對(duì)手實(shí)際持有每種手牌的概率，提高當(dāng)前狀態(tài)勝率評(píng)估準(zhǔn)確性。

2 本文的方法

2.1 行為模式樹(shù)

用樹(shù)來(lái)存儲(chǔ)對(duì)手在每個(gè)狀態(tài)下的動(dòng)作頻率，稱(chēng)為對(duì)手行動(dòng)模式樹(shù)。理論上，模式樹(shù)的規(guī)模越大，越能體現(xiàn)對(duì)手更細(xì)致的策略模式。然而樹(shù)的規(guī)模越大就需要更多的數(shù)據(jù)來(lái)填充樹(shù)中結(jié)點(diǎn)信息，這在實(shí)際對(duì)局中近乎不可能。由于希望能夠在盡可能少的局?jǐn)?shù)里建立可靠的又足以體現(xiàn)對(duì)手行為特征的模式樹(shù)，因此必須限制模式樹(shù)高度和深度。由于游戲中下注籌碼的多樣性，使得狀態(tài)空間非常巨大。玩家可以下注100～20 000范圍的任意籌碼量，實(shí)際上下注120與下注150僅有細(xì)微差別。使用動(dòng)作抽象方法將近似下注量視為同一動(dòng)作，減少模式樹(shù)中的分支結(jié)點(diǎn)。游戲規(guī)則最多允許玩家在一輪下注中4次Raise，實(shí)際游戲中通常一方Raise，另一方Call則進(jìn)入下一輪。默認(rèn)雙方玩家都不會(huì)在一輪中做出2次Raise動(dòng)作，將模式樹(shù)的深度限定為3層。至此小規(guī)模的模式樹(shù)結(jié)構(gòu)設(shè)計(jì)如圖1所示。

圖1 Pre-flop階段對(duì)手模式樹(shù)結(jié)構(gòu)

與傳統(tǒng)博弈樹(shù)不同，模式樹(shù)中每個(gè)結(jié)點(diǎn)均為對(duì)手的動(dòng)作。游戲中每一局后都會(huì)輪換大小盲注位置，動(dòng)作的先后順序也會(huì)隨之交換。圖1中根節(jié)點(diǎn)P表示當(dāng)前為Pre-flop階段，第1層中的結(jié)點(diǎn)代表對(duì)手在小盲位(SB)的所有合法動(dòng)作，第2層中的結(jié)點(diǎn)代表對(duì)手是大盲位(BB)，在己方執(zhí)行相應(yīng)父節(jié)點(diǎn)動(dòng)作后的選擇。C結(jié)點(diǎn)代表跟注，R代表加注，BR為大額加注，F(xiàn)為棄牌。所有葉子結(jié)點(diǎn)中，F(xiàn)結(jié)點(diǎn)的狀態(tài)為次局游戲結(jié)束，C節(jié)點(diǎn)代表當(dāng)前回合結(jié)束，進(jìn)入下一階段。模式樹(shù)的結(jié)點(diǎn)中保存著對(duì)手進(jìn)入該狀態(tài)的次數(shù)times。

為了分析出對(duì)手在各階段中的策略傾向，需要為4個(gè)階段分別構(gòu)建模式樹(shù)。游戲開(kāi)始時(shí)將各模式樹(shù)中結(jié)點(diǎn)的times初始化為0，在對(duì)局進(jìn)行中更新結(jié)點(diǎn)信息。更新步驟如下：

步驟1根據(jù)當(dāng)前牌局階段，選擇對(duì)應(yīng)的樹(shù)的根結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)S，S中times++。

步驟2根據(jù)玩家的動(dòng)作A，選擇S中對(duì)應(yīng)的子結(jié)點(diǎn)，將該子結(jié)點(diǎn)作為新的當(dāng)前結(jié)點(diǎn)S。

步驟3判斷動(dòng)作A是否是對(duì)手執(zhí)行的，如果是則S中times++。

步驟4判斷S是否為葉結(jié)點(diǎn)，如果是則轉(zhuǎn)到步驟1，否則轉(zhuǎn)到步驟2。

假設(shè)對(duì)手不改變自身策略，隨著游戲局?jǐn)?shù)增加，樹(shù)中各結(jié)點(diǎn)的times值增大，越能準(zhǔn)確體現(xiàn)對(duì)手的策略偏向。例如在400局后圖1中第2層各結(jié)點(diǎn)的times值對(duì)應(yīng)為[16，110，56，18]，可以看出對(duì)手在小盲位會(huì)傾向于Call，同時(shí)有近似8%的手牌會(huì)直接棄牌。

2.2 虛擬對(duì)手智能體

在游戲中，要憑借已知信息完全破解對(duì)手是不可能的，要實(shí)現(xiàn)一個(gè)智能體能夠模仿對(duì)手的行為模式做出決策，將其稱(chēng)為虛擬對(duì)手。首先需要一個(gè)沒(méi)有任何策略傾向的智能體作為基準(zhǔn)，這樣的智能體是基于CFR[18]算法求解納什均衡方法來(lái)實(shí)現(xiàn)的，其策略稱(chēng)之為均衡策略。理論上，一個(gè)采用均衡策略的智能體在對(duì)陣任何對(duì)手時(shí)都可以保證不輸，頂尖撲克智能體可以求解近似均衡策略[19]。ACPC[20]比賽官方提供了大量的比賽記錄數(shù)據(jù)，可以通過(guò)比賽數(shù)據(jù)來(lái)建立頂尖智能體的模式樹(shù)。一條比賽記錄的格式如下：STATE：6： cr300c/cc/cr1800f：TcTs4d5c/5s2d9c/Th：-300 300： bot1 | bot2。采用2.1節(jié)中方法構(gòu)建頂級(jí)智能體的行為模式樹(shù)，作為均衡模式樹(shù)基準(zhǔn)記為B。

當(dāng)游戲中與對(duì)手進(jìn)行一定局?jǐn)?shù)(一般為500局)后，對(duì)手的行為模式樹(shù)(記為O)信息開(kāi)始較為可靠。對(duì)于非葉子結(jié)點(diǎn)T，每個(gè)子結(jié)點(diǎn)中times值組成元組(T1，T2，T3)，則有Ts為所有子結(jié)點(diǎn)times值總和，歸一化處理可得對(duì)手在T狀態(tài)下的行為模式為OT=(T1/Ts，T2/Ts，T3/Ts)。同理求得均衡模式樹(shù)中T結(jié)點(diǎn)下的行為模式為BT，對(duì)手的行為偏向GT=OT-BT。

虛擬對(duì)手的主要決策算法是一個(gè)簡(jiǎn)單的經(jīng)驗(yàn)算法，必須快速計(jì)算策略才能滿足牌力評(píng)估的時(shí)間要求，此階段主要是針對(duì)對(duì)手的一個(gè)近似模擬，不需要太高的精度。對(duì)于某一具體牌局狀態(tài)Si，為虛擬對(duì)手設(shè)定2張手牌，計(jì)算出的策略為一個(gè)概率分布Pi=(xi，yi，zi)。例如Pi=(0.04，0.36，0.60)，表示在該狀態(tài)下，對(duì)手會(huì)有4%的概率棄牌，36%的概率跟注，60%概率加注。當(dāng)狀態(tài)Si屬于T結(jié)點(diǎn)時(shí)，實(shí)際行動(dòng)策略根據(jù)行為偏向而改變，有P=Pi+GT，至此虛擬對(duì)手智能體的策略構(gòu)建完成。

2.3 牌力評(píng)估

當(dāng)給定手牌和公共牌信息，虛擬對(duì)手根據(jù)計(jì)算出的策略選擇一個(gè)動(dòng)作，各階段動(dòng)作集合成完整的行動(dòng)路線。但是由于策略是一個(gè)概率分布，相同狀態(tài)下選擇的動(dòng)作也可能不同，因此虛擬對(duì)手給出的策略中執(zhí)行實(shí)際的概率可作為評(píng)估對(duì)手實(shí)際持有該手牌概率的依據(jù)。例如在Flop階段，對(duì)手的所有可能手牌為47張牌任意2張組合共 1 081種。令W=(w1，w2，w3，…，w1 081)，所有w值對(duì)應(yīng)手牌的權(quán)重，權(quán)重wi越大，對(duì)手持有對(duì)應(yīng)手牌hi可能性就越大。當(dāng)前信息包括自身手牌K4，公共牌3Q4，對(duì)手為小盲注，所有動(dòng)作記錄為r300c/cr600c。依靠算法1更新權(quán)重后，一些與公告牌無(wú)關(guān)的組合的權(quán)重會(huì)變得較低，比如虛擬對(duì)手持有T7在連續(xù)2個(gè)階段下注的概率是較低的，其相應(yīng)的權(quán)重會(huì)更新為2個(gè)較小的概率的乘積。一些帶Q的組合如QJ對(duì)應(yīng)的權(quán)重則會(huì)相應(yīng)較高，因?yàn)樘摂M對(duì)手的策略中加注的概率會(huì)較大，其行動(dòng)路線更加符合實(shí)際2次加注。

算法1

define update_w：

初始化W=(1，1，1…1)，牌局狀態(tài)S；

For eachain 動(dòng)作記錄 do：

Ifa是對(duì)手執(zhí)行的do：

For eachhiin opponent_hands do：

計(jì)算S虛擬對(duì)手策略P;

wi=wi*P(a);};

End For

End If

更新牌局狀態(tài)S;

End For

每次對(duì)手執(zhí)行動(dòng)作以后，可以更新W中的權(quán)重。

算法2以式(2)為基礎(chǔ)，根據(jù)W可計(jì)算牌力值。初始時(shí)權(quán)重均為1，此時(shí)算法2退化為計(jì)算數(shù)學(xué)上獲勝的自然概率。通過(guò)對(duì)手動(dòng)作信息來(lái)更新W后，計(jì)算出的牌力值相對(duì)可靠。在公共牌沒(méi)完全發(fā)出之前，還需考慮潛力值，此時(shí)使用式(3)結(jié)合蒙特卡洛模擬計(jì)算有效牌力值。由于德州撲克中花色沒(méi)有大小之分，2個(gè)算法中迭代對(duì)手可能的手牌的過(guò)程會(huì)出現(xiàn)很多重復(fù)的計(jì)算，通過(guò)存儲(chǔ)計(jì)算歷史，可以減小計(jì)算耗時(shí)。

算法2

define compute_HS：

初始化ahead=tied=behind=total=0;

//使用TPT算法求排名值

self_rank=TPT(self_hand+common_cards);

For eachhiin opponent_hands do：

total=total+wi;

op_rank= TPT(hi+common_cards);

if(self_rank>op_rank)

ahead=ahead+wi;

else if(self_rank

behind=behind+wi;

else

tied=tied+wi;

End For

HS=(ahead+tied/2)/total

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

為驗(yàn)證基于對(duì)手模型的牌力評(píng)估方法針對(duì)不同對(duì)手的有效性。設(shè)計(jì)了4個(gè)風(fēng)格迥異的對(duì)手進(jìn)行對(duì)局實(shí)驗(yàn)。對(duì)手風(fēng)格的分類(lèi)基于專(zhuān)家知識(shí)，在文獻(xiàn)[9]中也有相關(guān)描述，“松”指玩家會(huì)以大范圍的手牌進(jìn)入翻牌圈，與之相反的是“緊”，這類(lèi)玩家在持有勝率較低的起始手牌時(shí)會(huì)棄牌?！皟础眲t代表了玩家的激進(jìn)程度，“弱”為保守程度，與下注攻擊對(duì)手的頻率有關(guān)。

通過(guò)分析全國(guó)博弈大賽的對(duì)局記錄，選擇對(duì)手傾向的參數(shù)配置如表1所示，4個(gè)對(duì)手均采用同一決策方法計(jì)算基準(zhǔn)策略P，然后添加傾向得到在實(shí)際博弈狀態(tài)中采用的策略P′。實(shí)驗(yàn)對(duì)手在大量博弈中即可表現(xiàn)出明顯的風(fēng)格特征，表1中“松兇”型對(duì)手會(huì)玩絕大多數(shù)手牌，在翻牌前主動(dòng)棄牌的概率會(huì)小于%5，面對(duì)加注時(shí)也更傾向于跟注。如果翻牌后行成一對(duì)或者更強(qiáng)的牌，便會(huì)瘋狂的加注。而“緊弱”型與之相反，會(huì)大概率棄掉不好的牌，且很少會(huì)主動(dòng)加注。表1中的4個(gè)對(duì)手都有一定程度的缺點(diǎn)，以此來(lái)觀察使用對(duì)手模型評(píng)估方法的智能體能否有效針對(duì)不同的對(duì)手以獲得更大的收益。

表1 實(shí)驗(yàn)對(duì)手參數(shù)設(shè)置

設(shè)置實(shí)驗(yàn)對(duì)照組智能體SM，它采用靜態(tài)的牌力評(píng)估方法。因建立對(duì)手模式樹(shù)需要一定量的對(duì)局?jǐn)?shù)據(jù)，在與對(duì)手的前500局游戲中，OM也采用靜態(tài)評(píng)估方法。500局以后，對(duì)手模式樹(shù)中的數(shù)據(jù)足夠可靠，OM采用本文的方法繼續(xù)對(duì)局。除了評(píng)估方法以外，OM與SM的架構(gòu)均相同，在實(shí)驗(yàn)中2個(gè)智能體分別與表1中的4個(gè)對(duì)手分別進(jìn)行5 000局，游戲盲注級(jí)別設(shè)置為50/100，籌碼上限 20 000，每局結(jié)束重置籌碼量。對(duì)局結(jié)果如表2所示。

表2 對(duì)局結(jié)果

表2中顯示的各智能體5 000局后的累計(jì)盈虧籌碼量，在面對(duì)不同對(duì)手OM的收益均高于SM。TA和TP是2個(gè)謹(jǐn)慎的對(duì)手，棄牌的頻率較高，因此無(wú)法獲得較大的收益，但OM在掌握對(duì)手謹(jǐn)慎的風(fēng)格后，可以更精準(zhǔn)地推測(cè)對(duì)方手牌范圍，使得其收益相較SM提高近1倍。LP和LA棄牌較少，所以其最后輸?shù)舻幕I碼較多，他們的手牌范圍很大，建立對(duì)手模型的效果有所降低，OM的收益提升較小。圖2為OM和SM與LA對(duì)局的平均每局收益折線，SM在2 000局時(shí)可能由于隨機(jī)發(fā)牌的運(yùn)氣因素收益有波動(dòng)，而后趨于平穩(wěn)。而OM在1 000局后，收益穩(wěn)定上升，原因是此階段對(duì)手的行為模式樹(shù)構(gòu)建逐漸完善。2 000局后收益趨于平穩(wěn)，說(shuō)明此時(shí)已經(jīng)充分掌握了對(duì)手的特點(diǎn)，從而獲得穩(wěn)定的收益。

圖2 SM和OM對(duì)抗LA平均每局收益折線

4 結(jié)論

提出的德州撲克牌力評(píng)估算法通過(guò)牌局信息構(gòu)建對(duì)手行為模式樹(shù)，分析對(duì)手各階段的行為偏向，計(jì)算對(duì)手可能的手牌概率分布，完成牌力評(píng)估。實(shí)驗(yàn)結(jié)果顯示，基于對(duì)手模型的評(píng)估方法的效益明顯高于靜態(tài)方法，使用本文方法的智能體可以有效地針對(duì)不同風(fēng)格的對(duì)手獲得更大的收益，該智能體在2020年全國(guó)計(jì)算機(jī)博弈錦標(biāo)賽中獲得一等獎(jiǎng)。本文方法存在的缺點(diǎn)是在面對(duì)陌生對(duì)手時(shí)必須先收集對(duì)手信息，不能在游戲初始的對(duì)局中使用。如果對(duì)手在對(duì)局中采用的是混合的策略，模式樹(shù)對(duì)于對(duì)手風(fēng)格的分析會(huì)存在不可避免的偏差。后續(xù)的研究工作重點(diǎn)在于快速判斷對(duì)手類(lèi)型，針對(duì)混合策略的對(duì)手改進(jìn)對(duì)手模型。