基于預(yù)期收益策略與UCT的德州撲克算法

王亞杰，丁傲冬，祁冰枝，張云博

（沈陽航空航天大學(xué) a.工程訓(xùn)練中心；b.計算機學(xué)院，沈陽 110135）

機器博弈，也稱計算機博弈，它既是人工智能領(lǐng)域的重要應(yīng)用，也是研究人類思維和實現(xiàn)機器思維絕佳的實驗載體，國內(nèi)外很多學(xué)者一直進(jìn)行不懈的研究［1-3］，各種國際、國內(nèi)的比賽也促進(jìn)了機器博弈理論和方法的快速發(fā)展［4］。機器博弈通常分為完備信息博弈與非完備信息博弈，如今完備信息博弈已經(jīng)取得了重大突破，如谷歌的ALPHA GO［5］系列，通過使用深度強化學(xué)習(xí)算法在無需相關(guān)領(lǐng)域知識情況下實現(xiàn)多棋種對弈，達(dá)到了遠(yuǎn)超人類的水平。深度強化學(xué)習(xí)在電子游戲領(lǐng)域也取得了較好的效果，如Atari［6］。

由于對手信息的缺失，非完備信息博弈一直是機器博弈領(lǐng)域的難點，作為此類博弈的典型代表，德州撲克一直是人工智能領(lǐng)域內(nèi)的難題［7］，分為有限注和無限注，玩家一般2～10人。本文以二人無限注德州撲克作為研究對象。

德州撲克常用算法有基于博弈樹的搜索、虛擬遺憾最小化算法（counterfactual regret minimization，CFR）、對手建模等。2006年，Billings等提出了基于對手建模和樹搜索的德州撲克算法［8］；2014年北京郵電大學(xué)的曹一鳴實現(xiàn)了基于上限置信區(qū)間算法（upper confidence bound apply to tree，UCT，一種基于蒙特卡羅的博弈樹搜索）的德州撲克程序［9］，在結(jié)合了領(lǐng)域知識后取得了較好的效果。2007年，CFR被Zinkevich等提出［10］，同時證明CFR算法能夠在二人零和博弈中達(dá)到近似納什均衡，并且能夠利用對手的弱點［11］；2015年，Billings等在CFR算法的基礎(chǔ)上改進(jìn)得到了CFR+算法，并證明改進(jìn)后的CFR+算法能夠解決二人限制性德州撲克，但是需要大量的相關(guān)領(lǐng)域知識［12］。2017年，來自加拿大Alberta大學(xué)、捷克Charles大學(xué)、布拉格捷克理工大學(xué)的研究人員們使用CFR算法結(jié)合深度學(xué)習(xí)實現(xiàn)的德州撲克人工智能系統(tǒng)DeepStack是世界上第一個在 “一對一無限注德州撲克”上擊敗了職業(yè)撲克玩家的計算機程序。2018年，浙江大學(xué)的李翔等提出基于手牌預(yù)測［7］（對手建模的一種）的算法，在結(jié)合領(lǐng)域知識的前提下首次在3人及以上無限注德州撲克上實現(xiàn)了對手手牌預(yù)測。

本文針對上述算法需要結(jié)合領(lǐng)域知識這一點，首先提出了預(yù)期收益策略，即每個階段都根據(jù)每個可選動作的期望收益選擇下一步動作。計算期望收益時考慮了3個指標(biāo)：己方勝率、己方可選動作的下注量和損失率（下注量占己方總籌碼量的比例）。己方勝率使用蒙特卡羅方法計算得到；己方可選動作的下注量代表動作執(zhí)行完之后，己方在當(dāng)前階段的下注籌碼總量；損失率代表己方如果輸了要承擔(dān)的損失。然后通過己方勝率和對手下注量評估對手勝率，得到對手勝率后把預(yù)期收益策略作為對手策略模型應(yīng)用在UCT算法的模擬部分，即，將傳統(tǒng)UCT算法用的隨機模擬替換成雙方都使用預(yù)期收益策略模擬。無論是計算預(yù)期收益考慮的3個指標(biāo)還是評估對手勝率時用到的對手下注量都無需任何領(lǐng)域知識，因此改進(jìn)后的UCT算法也是一種無需領(lǐng)域知識的算法。

1 預(yù)期收益策略

1.1 勝率的計算

在德州撲克中，游戲分為5個階段：

Perflop（翻牌前）：每人發(fā)2張底牌，決定大小盲注，雙方輪流表態(tài)（棄牌、跟注、下注）；

Flop（翻牌）：發(fā)3張公共牌，輪流表態(tài)；

Turn（轉(zhuǎn)牌）：發(fā)第4張公共牌，輪流表態(tài)；

River（河牌）：發(fā)第5張公共牌，輪流表態(tài)；

比牌階段：經(jīng)過4輪的發(fā)牌和下注，雙方選擇最大5張牌，最大牌型的玩家贏得籌碼。

上述5個階段中前4個階段都需要計算勝率作為表態(tài)依據(jù)，并且到一個新階段勝率會發(fā)生變化。由于不知道對方底牌與未發(fā)的公共牌，所以采用蒙特卡羅方法進(jìn)行計算。蒙特卡羅方法是通過重復(fù)隨機采樣來計算結(jié)果的一類概率算法。這里剩余公共牌滿足均勻概率分布，對手底牌概率分布和對方策略相關(guān)，但是本文不考慮對手建模，仍然采用均勻概率分布。因此，隨機地生成剩余公共牌與對方底牌，并統(tǒng)計雙方勝負(fù)關(guān)系，將此過程重復(fù)，最終得到一個穩(wěn)定的勝率作為當(dāng)前階段己方的勝率［13］。

本文采用蒙特卡羅方法計算勝率流程如圖1所示。

圖1 蒙特卡羅方法計算勝率流程

圖2～5分別是在一次對局中Perflop、Flop、Turn和River 4個階段模擬次數(shù)與勝率的關(guān)系，橫坐標(biāo)為模擬次數(shù)，縱坐標(biāo)為己方勝率。

圖2 Preflop階段模擬次數(shù)與勝率關(guān)系

圖3 Flop階段模擬次數(shù)與勝率關(guān)系

圖4 Turn階段模擬次數(shù)與勝率關(guān)系

圖5 River階段模擬次數(shù)與勝率關(guān)系

在這4個階段中，每次都隨機地生成剩余公共牌與對方底牌，Perflop、Flop、Turn和River分別生成公共牌數(shù)量為：5張、2張、1張、1張；對方底牌數(shù)量為：2張。理論上，模擬次數(shù)足夠多時得到的統(tǒng)計勝率就是真實勝率。從圖像看，隨著模擬次數(shù)N的增大，勝率W趨于穩(wěn)定。表1統(tǒng)計了Preflop階段N處于不同范圍時的勝率情況。

表1 模擬次數(shù)與勝率

表1的模擬次數(shù)N∈［a+10，a+100］表示N分別取值為a+10、a+20、…、a+100共10組值，得到10個勝率值，分別取最大勝率，最小勝率、平均勝率、最大與最小勝率差值。其中，平均勝率作為真實勝率的參考值，勝率差描述平均勝率的穩(wěn)定性，值越小平均勝率越穩(wěn)定。隨著N逐漸增大，勝率差逐漸減小。當(dāng)模擬次數(shù)N∈［810，1 000］時，勝率差小于0.05；當(dāng)N∈［410，500］時，勝率差已經(jīng)接近0.05，勝率已經(jīng)非常穩(wěn)定，可以代替真實勝率。同時，考慮到模擬次數(shù)越多耗時也會相應(yīng)增長，實驗中將模擬次數(shù)設(shè)置為500。

1.2 動作預(yù)期收益的計算

計算出當(dāng)前階段的勝率之后，根據(jù)勝率獲得每個動作對應(yīng)的預(yù)期收益。德州撲克中有5種動作：Fold、Call、Check、Raise、Bet、Allin。其中，F(xiàn)old代表棄牌；Call代表將籌碼加注到和對手一樣多；Check代表不加注，看作將籌碼加注到和當(dāng)前一樣多；Raise代表加注到指定籌碼；Bet代表直接下注，可以看成直接把籌碼加注到一個值；Allin代表剩余籌碼全下注，可以看成直接把籌碼加注到最大值，所以除了Fold之外的5種動作都可以用Raise代替，因此在程序中只有2種動作：Fold和Raise。Fold代表棄牌，執(zhí)行Fold即損失所有下注籌碼；對于動作Raise，需要根據(jù)勝率和對應(yīng)下注量chip值計算出預(yù)期收益，用于估計動作的價值。用式（1）計算預(yù)期收益：

其中，S代表預(yù)期收益，W代表當(dāng)前階段己方勝率，chip代表當(dāng)前動作的下注量，max_chip代表最大籌碼量，即開局時己方擁有的籌碼量。1-W是己方負(fù)率，W-（1-W）＝2×W-1是期望收益率。如果只考慮W則會出現(xiàn)期望收益率大于零時Allin總會被選為最佳策略；反之，Call或Check總會被選為最佳策略。考慮到無論選擇哪種策略（除了Fold），都伴隨著損失下注籌碼的風(fēng)險，因此引入損失率的概念，即下注籌碼量占己方總籌碼量的比例（chip／max_chip），比例越高，可能的損失越大。因此，在期望收益率的基礎(chǔ)上減去損失率作為最終的預(yù)期收益率。在作出最終決策之前，先算出n個預(yù)期收益，加上選擇Fold獲得的收益，從n+1個收益中選擇最大的收益對應(yīng)的動作作為下一步動作。

圖6是預(yù)期收益策略決策流程圖。

圖6 預(yù)期收益策略決策流程

基于預(yù)期收益策略的德州撲克程序THPZZ參加了2019屆中國計算機博弈大賽2人非限制德州撲克項目，獲得第3名。在實驗中將作為基準(zhǔn)程序與本文方法作對比。

2 UCT算法

2.1 傳統(tǒng)UCT算法

UCT算法，即上限置信區(qū)間算法，是一種常見的博弈樹搜索算法，該算法結(jié)合了蒙特卡羅樹搜索和UCB（upper confidence bound）公式［14］，利用UCB公式進(jìn)行選擇。UCB公式來源于K臂強盜問題。K臂強盜問題是指一個具有K個手臂的強盜，每次用不同的手臂都可以獲得具有不同分布的收益［15］。對于這個問題，首先把所有手臂嘗試一次，然后根據(jù)式（2）：

蒙特卡洛樹搜索有4個步驟：選擇、擴展、模擬、回溯。UCT算法在選擇階段把蒙特卡羅樹的每個節(jié)點看成K臂強盜問題中的強盜，把該節(jié)點的子節(jié)點作為強盜的K條手臂［15］，使用UCB公式選擇下一個節(jié)點。

2.2 UCT與預(yù)期收益策略的結(jié)合

預(yù)期收益策略主要和蒙特卡洛樹搜索4個步驟中的模擬結(jié)合，在蒙特卡羅樹搜索中模擬是讓博弈雙方進(jìn)行隨機對弈［9］，直到終局狀態(tài)。如UCT策略應(yīng)用在圍棋上時，當(dāng)選擇到一個葉子節(jié)點時，讓雙方隨機下棋一直到結(jié)束，獲得一個勝負(fù)結(jié)果，然后進(jìn)行回溯更新節(jié)點信息。

這種模擬策略對于德州撲克來說雖然理論上可行，但是存在2個問題：

問題1：對于玩家來說每種動作被選擇執(zhí)行的概率不是均等的，牌型越好（即勝率高）的玩家平均下注量越大；反之，則越低。

問題2：模擬過程中缺少對手每個階段的勝率信息，無法直接使用預(yù)期收益策略并且模擬到游戲結(jié)束時，不同于完全信息博弈，非完備信息博弈游戲不能得到一個精確的反饋值。例如：德州撲克中由于對方底牌不能確定，因此無法得到一個精確的勝負(fù)結(jié)果。

針對問題1，使用預(yù)期收益策略代替隨機策略進(jìn)行模擬。預(yù)期收益策略具有2個特點：①下注量與勝率正相關(guān)；②避免了隨機策略里每種動作被選擇概率都是均等的情況。在對對手風(fēng)格、偏好完全不了解的情況下，預(yù)期收益策略完全可以作為一種對手平均策略模型來使用。

針對問題2，目前有2種解決方法：

①對手建模：利用對手下注信息估算出對手底牌范圍，得到對手的勝率和最終的收益值；

②隨機模擬：隨機地給對方發(fā)底牌，得到對手的平均勝率和一個平均的收益值。

對手建模方法能夠較為準(zhǔn)確地預(yù)測特定對手的底牌［16-17］，但是比較復(fù)雜，本文主要研究了方法②，并對其做了一些改進(jìn)。

對于方法②，雖然通過多次隨機發(fā)牌能夠計算出對方平均勝率并得到一個己方的平均收益值，但是用這種方法只能計算出對手的平均勝率，與實際情況略有差異。如果對手底牌較弱，實際勝率較低，多次隨機發(fā)牌的方法相當(dāng)于高估了對方的勝率，使得己方在做決策時平均下注量偏低，從而導(dǎo)致收益偏低。如果對手底牌較強，多次隨機發(fā)牌的方法等同于低估了對方的勝率，容易誤導(dǎo)己方加大下注量從而擴大損失。相比高估對方勝率情況，更需要避免低估對方勝率的情況，特別是在己方勝率低的情況下，低估對方勝率帶來的損失更大。

基于以上分析本文提出了一種新的勝率模擬方法：通過多次隨機發(fā)牌得到己方勝率Wself，把1-Wself作為對方勝率的一個基礎(chǔ)值，同時考慮到把預(yù)期收益策略作為對手初始策略模型使用，因此把對手當(dāng)前下注量chip與總籌碼量chipsum的比值作為對方勝率的增量值。即使用式（3）計算對方勝率Wopponent：

得到雙方勝率估值之后，可用于預(yù)期收益策略并在結(jié)束時使用式（4）計算最終收益。

其中，Ssimluate是模擬到結(jié)束時的收益。chipbet是下注量。

對于式（3），考慮2種情況：

1）己方勝率較低。計算得到的對方勝率會一直處于較高水平。所以會出現(xiàn)狀態(tài)1（己方勝率低，對方勝率低），此時會高估對方勝率。

2）己方勝率較高。計算得到的對方勝率取決于對方下注量的高低。所以會出現(xiàn)2種狀態(tài)：狀態(tài)2（對方勝率低，但下注量高）；狀態(tài)3（對方勝率高，但下注量低）。這2種狀態(tài)都會導(dǎo)致預(yù)測對方勝率不準(zhǔn)確的問題。

相對于隨機發(fā)牌的方法，式（3）在避免了己方勝率低的同時又低估對方勝率的情況。

在狀態(tài)1中，己方會傾向于棄牌或下小注。

在狀態(tài)2中，對方要想通過詐唬策略使己方棄牌，必須下注極高的籌碼量，然而在對方Allin情況下，只有己方勝率低于2／3時會認(rèn)為對方勝率高過己方，即當(dāng)己方勝率高于2／3時，對方的詐唬策略作用不大。

在狀態(tài)3中，雙方有較大概率一直進(jìn)行到游戲結(jié)束，通過比較牌型判斷勝負(fù)，這種情況下由于己方勝率較高，在結(jié)果上沒有明顯劣勢。綜上所述，公式（3）使得在己方勝率較低（低于2／3）情況下傾向于較為保守的打法，表現(xiàn)為有最高總下注量限制；在勝率較高（高于2／3）情況下傾向于激進(jìn)的打法，表現(xiàn)為無最高總下注量限制。

2.3 UCT與動作映射

對于無限注德州撲克，只要下注量在合法范圍內(nèi)都可以下注，如果下注量按照最小單位1來計算的話，下注行為會有很多種，構(gòu)造出來的博弈樹將會非常龐大。

動作映射［18］是把多個下注行為映射為一個行為，比如：將下注的籌碼數(shù)規(guī)定為100的倍數(shù)，那么下注量在100周圍（110、90等）的下注動作都可以用下注100代替。本次實驗因算力有限，在確定最小下注量與最大下注量后，規(guī)定最小下注單位為500（僅在己方構(gòu)建博弈樹時限制），極大地減少了可選動作數(shù)量，從而降低了博弈樹規(guī)模。

3 實驗結(jié)果

3.1 實驗環(huán)境與要求

本文的實驗程序使用Python3.7實現(xiàn)，在一臺AMD epyc 7k62（128核心），內(nèi)存為512 GB，系統(tǒng)為windows server 2019的機器上運行。

德州撲克的規(guī)則按照中國計算機博弈大賽的比賽規(guī)則執(zhí)行。即比賽開始時雙方各有20 000籌碼，每步策略計算時間不超過60 s。每進(jìn)行完一局復(fù)位一次。雙方進(jìn)行100局比賽，累計每局贏得的籌碼量，最后贏得籌碼量多者獲勝。

為了降低UCT算法構(gòu)建的博弈樹規(guī)模，在2.3節(jié)已經(jīng)將模擬階段的最小下注單位設(shè)置為500，起始籌碼量為20 000，每種牌局狀態(tài)的下一步動作最多為40個。在UCT算法中，選擇、擴展、模擬、回溯是一次完整的搜索過程，搜索次數(shù)越多得到的結(jié)果越準(zhǔn)確。模擬是一次搜索的子過程，在傳統(tǒng)的UCT中一般采用隨機的策略模擬1次得到結(jié)果并回溯。但在本文實驗中，由于模擬過程中剩余公共牌與對方底牌（在采用隨機模擬的UCT算法中存在）具有隨機性，導(dǎo)致一次模擬得到的勝率隨機性過大，所以需要進(jìn)行多次模擬得到一個穩(wěn)定的結(jié)果，進(jìn)而需要設(shè)置2個參數(shù)：搜索次數(shù)與模擬次數(shù)。參數(shù)設(shè)置得越多，結(jié)果越準(zhǔn)確，但是考慮到計算力有限，本文在對結(jié)果準(zhǔn)確性影響不大的情況下盡量降低2個參數(shù)的值。

從表1結(jié)果分析得出：在計算勝率時，模擬次數(shù)N為［110，200］和［910，1 000］（這個區(qū)間的模擬次數(shù)最多，結(jié)果作為真實值參考）時得到的勝率均值差距較小，說明模擬次數(shù)超過100就可以得到和真實值接近的勝率。本文實驗為了充分發(fā)揮硬件多核心的優(yōu)勢，將模擬次數(shù)設(shè)置為128（本文實驗硬件的核心數(shù)量）次。當(dāng)模擬次數(shù)設(shè)置為128次后，搜索次數(shù)直接決定程序運行時間，為了滿足每步策略計算時間不超過60 s，將搜索次數(shù)設(shè)置為100次。

3.2 實驗結(jié)果與分析

本次實驗基準(zhǔn)程序是THPZZ，分別和本文提出的2個算法進(jìn)行對比：

算法1：UCT結(jié)合預(yù)期收益策略，采用隨機模擬方式。

算法2：UCT結(jié)合預(yù)期收益策略，采用勝率模擬方式。

表2是采用勝率模擬與隨機模擬的程序與THPZZ的比賽結(jié)果。

表2 實驗結(jié)果

從表2中可以看出：算法2的水平高于THPZZ，THPZZ水平高于算法1。圖7是算法2與算法1的比賽局?jǐn)?shù)與累計贏得籌碼的關(guān)系。

圖7 比賽局?jǐn)?shù)與贏得籌碼量關(guān)系

從圖7可以看出：算法2的策略較為平穩(wěn)，隨著比賽總局?jǐn)?shù)增加，贏得的總籌碼量穩(wěn)定增長。算法1的策略隨著比賽總局?jǐn)?shù)的增長，贏得的總籌碼量多次出現(xiàn)較大的起伏。

圖8顯示了在100局對弈中2個算法在不同下注范圍的頻數(shù)分布情況。

圖8 下注范圍頻數(shù)分布

算法2在100次對局中有99次總下注量低于5 000，僅有1次下注量超過10 000的情況?？傮w策略較為保守。

算法1在100次對局中有82次總下注量低于5 000，18次總下注量超過10 000。

由于預(yù)期收益策略是根據(jù)己方勝率做出決策，而下注區(qū)間［10 000，20 000］對應(yīng)較高的勝率。在與基于此策略的THPZZ的對比實驗中，算法1由于在估算對手勝率時用的是隨機模擬，因此得到的對手勝率是一個均值。由2.2的分析得知這種隨機模擬在對手牌較強時得到的是比實際偏低的勝率，導(dǎo)致出現(xiàn)了多次盲目跟隨對方下大注的行為。實際上在這18次下注量超過10 000的對局中，算法1僅有5次獲得勝利。

而算法2采用式（3）估算對手勝率，由2.2的分析可知：這種估計方法在對手下注量較高的情況下估計到的對手勝率較高，能夠改善隨機模擬低估對手勝率的情況，因此下大注的情況較少，在100次對局中僅有1次。

4 結(jié)束語

本文提出了無需領(lǐng)域知識的預(yù)期收益策略，利用蒙特卡羅方法計算己方勝率，并根據(jù)己方勝率和對方下注量評估對方勝率，然后利用雙方勝率與下注量計算不同動作的預(yù)期收益，最后根據(jù)預(yù)期收益選擇下一步的動作，并且把預(yù)期收益策略與UCT算法結(jié)合，取得了較好的效果。

由于沒有對手底牌的任何信息，預(yù)期收益策略在計算己方勝率時用的蒙特卡羅方法只能求出一個平均的勝率，在計算對手勝率時也只能根據(jù)己方勝率和對方下注量進(jìn)行粗略的計算。因此，想要精確地獲取己方和對方勝率，還需要結(jié)合對手建模的方法進(jìn)行深入研究。