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

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

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

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

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

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

1 背景

1.1 基本概念

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

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

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

(1)

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

1.2 牌力評估算法

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

(2)

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

EHSn=HSn+(1-HSn)×Ppot

(3)

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

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

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

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

2 本文的方法

2.1 行為模式樹

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

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

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

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

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

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

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

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

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

2.2 虛擬對手智能體

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

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

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

2.3 牌力評估

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

算法1

define update_w：

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

For eachain 動作記錄 do：

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

For eachhiin opponent_hands do：

計算S虛擬對手策略P;

wi=wi*P(a);};

End For

End If

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

End For

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

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

算法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 實驗結(jié)果與分析

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

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

表1 實驗對手參數(shù)設(shè)置

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

表2 對局結(jié)果

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

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

4 結(jié)論

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