一種德州撲克牌力評估方法

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

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

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

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

傳統牌力評估方法如TPT(two-plus-two)[11]、Bit Manual[12]、ARS(average rank strength)[13]等，計算數學以領先對手的自然概率作為牌力。這種靜態的方法忽略了游戲中的動作信息，且不能針對不同風格的對手調整，導致牌力評估往往不夠準確。

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

1 背景

1.1 基本概念

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

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

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

(1)

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

1.2 牌力評估算法

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

(2)

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

EHSn=HSn+(1-HSn)×Ppot

(3)

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

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

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

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

2 本文的方法

2.1 行為模式樹

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

圖1 Pre-flop階段對手模式樹結構

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

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

步驟1根據當前牌局階段，選擇對應的樹的根結點為當前結點S，S中times++。

步驟2根據玩家的動作A，選擇S中對應的子結點，將該子結點作為新的當前結點S。

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

步驟4判斷S是否為葉結點，如果是則轉到步驟1，否則轉到步驟2。

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

2.2 虛擬對手智能體

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

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

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

2.3 牌力評估

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

算法1

define update_w：

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

For eachain 動作記錄 do：

Ifa是對手執行的do：

For eachhiin opponent_hands do：

計算S虛擬對手策略P;

wi=wi*P(a);};

End For

End If

更新牌局狀態S;

End For

每次對手執行動作以后，可以更新W中的權重。

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

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

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

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

表1 實驗對手參數設置

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

表2 對局結果

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

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

4 結論

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