競(jìng)技二打一游戲中同等牌力的研究

李淑琴，陳子鵬，鄭藍(lán)舟，孟坤

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

國家體育總局棋牌運(yùn)動(dòng)管理中心以“創(chuàng)新、協(xié)調(diào)、綠色、開放、共享”的發(fā)展理念為指導(dǎo)，以提升國民素質(zhì)與人民健康水平為發(fā)展目標(biāo)，提出了“傳統(tǒng)棋牌項(xiàng)目趣味化”和“趣味棋牌項(xiàng)目競(jìng)技化”的重要發(fā)展戰(zhàn)略。在鞏固傳統(tǒng)五棋一牌項(xiàng)目(圍棋[1-3]、象棋[4]、國際象棋[5]、國際跳棋[6]、五子棋[7]、橋牌[8])基礎(chǔ)的同時(shí)，針對(duì)趣味棋牌競(jìng)技化的發(fā)展戰(zhàn)略，國家體育總局棋牌運(yùn)動(dòng)管理中心首先推出了以民間趣味棋牌運(yùn)動(dòng)“斗地主”[9]為原型的競(jìng)技二打一撲克項(xiàng)目。2016年9月3日，舉辦了首屆全國競(jìng)技二打一撲克錦標(biāo)賽(China competitive poker championship，CCPC)[10]，錦標(biāo)賽中引入了復(fù)式賽制[11]，復(fù)式賽制就是在不同的牌桌上，同一個(gè)方位的選手發(fā)一模一樣的牌，把相同牌面下打出的成績(jī)進(jìn)行匯總，看誰能打出最好的效果，這樣就完全避免了發(fā)牌的偶然性，達(dá)到競(jìng)技化的目的。復(fù)式賽制的這些特點(diǎn)決定了二打一游戲等項(xiàng)目能夠被納入智力運(yùn)動(dòng)這一體系。但與傳統(tǒng)線下的比賽不同，在互聯(lián)網(wǎng)環(huán)境下，復(fù)式賽制尚存在一些不公平因素，例如，兩個(gè)不同方位的人很容易通過語音、視頻等方式互相告知自己的手牌，存在網(wǎng)上作弊的問題。同等牌力賽制不需要把同樣的牌發(fā)給每個(gè)參賽的人，而是發(fā)同樣牌力的牌，以此杜絕網(wǎng)絡(luò)上打相同牌帶來的作弊問題。同時(shí)，在同等牌力賽制中，用戶不再需要同時(shí)開賽，可以充分利用其碎片時(shí)間隨時(shí)參賽，也可以中途停頓，而不會(huì)影響整個(gè)競(jìng)賽的過程，等完成打牌的人數(shù)滿足比賽要求時(shí)就計(jì)算排名，比復(fù)式賽制更加方便。同時(shí)，同等牌力的相關(guān)研究成果還能應(yīng)用于能力評(píng)測(cè)系統(tǒng)。目前該項(xiàng)目已列入中國大學(xué)生計(jì)算機(jī)博弈大賽暨全國錦標(biāo)賽競(jìng)標(biāo)賽中[12-14]。因此，本文擬對(duì)競(jìng)技二打一比賽中的同等牌力問題進(jìn)行研究。

1 相關(guān)工作

競(jìng)技二打一是一種玩法簡(jiǎn)單、娛樂性強(qiáng)的3人撲克牌游戲。一局牌需3個(gè)玩家，1個(gè)玩家稱為地主，地主的逆時(shí)針第1個(gè)農(nóng)民稱為下家，逆時(shí)針第2個(gè)農(nóng)民稱為上家或頂家。在每一局游戲中，地主獨(dú)立存在，而其他兩名玩家以農(nóng)民的身份組成一隊(duì)與地主對(duì)抗。農(nóng)民隊(duì)伍只要有一人比地主先出完手中的牌，農(nóng)民便可獲得游戲勝利，否則地主勝，并計(jì)算本局地主得分。

一副完整的紙牌共54張牌，由1張紅色小丑牌、1張黑色小丑牌和52張標(biāo)準(zhǔn)牌組成。52張標(biāo)準(zhǔn)牌共包括大小不同的13種牌(2、A、K、Q、J、T(10)、9、8、7、6、5、4、3)，每一種牌各有4張，且大小相同。在每一輪開始時(shí)，地主將持有20張牌，其他人每人有17張牌。地主先出牌，且可以打一張牌或任何合法的組合。按逆時(shí)針順序玩家依次出牌，每個(gè)后續(xù)玩家必須要么“過”(不打牌)，要么通過打出相同數(shù)量的牌和相同類型的牌的更高組合來擊敗前一個(gè)玩家。最先出完手中的所有牌的玩家為獲勝者。如果對(duì)局結(jié)束，統(tǒng)計(jì)此次對(duì)局每個(gè)玩家的得分。

對(duì)于競(jìng)技游戲，每一場(chǎng)牌局可以被視為一次考試，給選手發(fā)的初始手牌可以看作考試試題。試題的區(qū)分度計(jì)算可以參照心理學(xué)著名的經(jīng)典測(cè)試?yán)碚揫15-16](classical test theory，CTT)，在CTT框架下，通過每個(gè)試題與總測(cè)試分?jǐn)?shù)的相關(guān)關(guān)系來反映試題區(qū)分度?；诖讼敕?，文獻(xiàn)[17]通過統(tǒng)計(jì)真人牌譜，計(jì)算初始手牌的得分均值和方差，利用得分的均值和方差劃分將初始手牌劃分為10個(gè)分類，認(rèn)為同一類中的手牌具有同等牌力。然而，這種用得分均值和方差來劃分區(qū)間的分類方法存在較大的誤差，為此文獻(xiàn)[18]對(duì)其進(jìn)行了改進(jìn)，通過統(tǒng)計(jì)真人牌譜計(jì)算初始手牌的得分概率分布，并以得分概率分布為特征進(jìn)行聚類從而將初始手牌劃分成若干個(gè)分類。然而，其仍存在兩個(gè)問題：1)通過統(tǒng)計(jì)不同批玩家的得分分布，來計(jì)算不同初始手牌的得分概率分布，作為該初始手牌的特征，這個(gè)方法在小樣本的情況下，由于不同批玩家統(tǒng)計(jì)的得分概率分布不同，實(shí)驗(yàn)結(jié)果難以驗(yàn)證；2)聚類個(gè)數(shù)是人為預(yù)設(shè)定的，無法在實(shí)際應(yīng)用中準(zhǔn)確地設(shè)定出準(zhǔn)確的類別數(shù)。為解決第1個(gè)問題，本文訓(xùn)練了多個(gè)不同水平的“競(jìng)技二打一AI程序”，作為固定的“玩家”，打牌生成大量的牌譜，易于同等牌力的驗(yàn)證；為解決第2個(gè)問題，本文提出同等牌力的選取方法。

2 同等牌力系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

2.1 同等牌力系統(tǒng)設(shè)計(jì)思想

同等牌力就是初始手牌的難度近似。本文通過等級(jí)評(píng)估指標(biāo)(grade difficulty index，GDI)來表示初始手牌的難度。等級(jí)難度評(píng)估指標(biāo)的含義是：假設(shè)一局牌玩完對(duì)應(yīng)的得分共有k種，得分按從小到大排列，將它們看成k個(gè)等級(jí)。本文認(rèn)為如果玩家能達(dá)到第i個(gè)等級(jí)，則玩家必能達(dá)到第i?1個(gè)等級(jí)，不必考慮比他低的等級(jí)。故玩家能達(dá)到第i個(gè)等級(jí)的難度就是玩家能達(dá)到第i個(gè)及其以上等級(jí)的概率。由于玩家達(dá)到第1個(gè)等級(jí)的概率是100%，所以不考慮玩家達(dá)到第1個(gè)等級(jí)的難度。等級(jí)評(píng)估指標(biāo)由k?1個(gè)等級(jí)概率值組成。

定義1 等級(jí)難度評(píng)估指標(biāo)。衡量一副牌難易程度的指標(biāo)，記為G=(g1,g2,···,gk?1)， 其中g(shù)i表示固定玩家能達(dá)到第i個(gè)及其以上等級(jí)的概率，k表示二打一規(guī)則中規(guī)定得分的數(shù)量。

定義2 具有同等牌力的初始手牌。兩副初始手牌，由同一批玩家打，得到的兩個(gè)GDI的歐氏距離小于一定閾值，則兩副初始手牌具有同等牌力。

然而，從現(xiàn)有的真人打牌數(shù)據(jù)中難以找到同一批玩家打若干副初始手牌的數(shù)據(jù)集，短時(shí)間內(nèi)召集一批玩家打若干副初始手牌同樣不現(xiàn)實(shí)。因此，本文提出生成多個(gè)不同水平的“二打一AI程序”來代替真人打牌，以保證一副牌所得等級(jí)難度評(píng)估指標(biāo)的可靠性。

利用“二打一AI程序”生成的大量牌譜數(shù)據(jù)，本文構(gòu)建了一個(gè)可指定難度的同等牌力生成系統(tǒng)。同等牌力生成系統(tǒng)主要由4部分構(gòu)成：1)訓(xùn)練多個(gè)不同水平的DDZAI來產(chǎn)生大量牌譜；2)統(tǒng)計(jì)牌譜，計(jì)算每個(gè)初始手牌的等級(jí)難度評(píng)估指標(biāo)；3)基于等級(jí)難度評(píng)估指標(biāo)，指定1個(gè)或幾個(gè)難度作為同等牌力的中心，設(shè)定閾值，進(jìn)行不同牌譜分類，即得到不同級(jí)別的同等牌力；4)驗(yàn)證同等牌力生成方法的可靠性。同等牌力系統(tǒng)框架如圖1所示。

圖1 同等牌力系統(tǒng)框架Fig.1 System framework of the equal card force

2.2 訓(xùn)練多個(gè)不同水平的“二打一AI程序”

筆者將真人打牌日志進(jìn)行整理，依據(jù)輸贏次數(shù)進(jìn)行歸類，使用文獻(xiàn)[19-25]中提出的競(jìng)技二打一出牌算法，該算法通過真人打牌日志使用CNN模型訓(xùn)練出具有似人智能的出牌策略。訓(xùn)練n個(gè)不同水平的“二打一AI程序”，具體如算法1。

算法1 訓(xùn)練n個(gè)不同水平的DDZAI程序

輸入 真人打牌日志；

輸出n個(gè)不同水平DDZAI程序。

1)將同一玩家的牌譜劃分到同一個(gè)牌譜集；

2)清洗掉牌譜集中數(shù)據(jù)量少于10局的牌譜集；

3)統(tǒng)計(jì)玩家的勝率，并按照勝率對(duì)玩家進(jìn)行非遞減排序；

4)將水平接近玩家對(duì)應(yīng)的牌譜集劃分到同一個(gè)DDZAI訓(xùn)練集中，共分為n個(gè)訓(xùn)練集，要求每個(gè)訓(xùn)練集中數(shù)據(jù)量盡量均衡。

使用文獻(xiàn)[21]中提出的競(jìng)技二打一出牌算法，分別訓(xùn)練出n個(gè)具有不同水平的DDZAI程序。為了驗(yàn)證用上述方法選出的n個(gè)DDZAI水平是否有差異，本文通過讓這n個(gè)DDZAI進(jìn)行復(fù)式賽，其中n個(gè)DDZAI的對(duì)手相同，并組成n桌。復(fù)式賽包括m場(chǎng)比賽，每一場(chǎng)比賽包括多輪比賽來保證n桌DDZAI的地主a1,a2,···,an的排名滿足：ai的水平高于aj的水平，i

圖2 多個(gè)DDZAI不同水平的驗(yàn)證方法Fig.2 Verification methods at different DDZAI levels

2.3 計(jì)算初始手牌的等級(jí)難度評(píng)估指標(biāo)

為了對(duì)指定難度挑選同等牌力的初始手牌，需要將每副牌難度量化為GDI，初始手牌h的GDI的計(jì)算過程為：假設(shè)一局牌玩完對(duì)應(yīng)的得分共有k種可能的分值，即s1,s2,···,sk；選取n個(gè)地主DDZAI，每個(gè)地主DDZAI，與同1個(gè)下家DDZAI和1個(gè)頂家DDZAI組成1桌，共構(gòu)成n桌AI牌局。為每桌分發(fā)同一副初始手牌h，對(duì)局后記錄每桌的地主得分，假設(shè)得分分別為c1,c2,···,cn， 其中cu∈{s1,s2,···,sk}，u=1,2,···，n按等級(jí)排序，統(tǒng)計(jì)得分對(duì)應(yīng)的等級(jí)次數(shù)記為l1,l2,···,lk。計(jì)算初始手牌h對(duì)應(yīng)的等級(jí)難度評(píng)估指標(biāo)Gh=(g1,g2,···,gk)，gj的計(jì)算公式為

一般來說，gi值表示玩家能達(dá)到等級(jí)i的概率，某等級(jí)對(duì)應(yīng)的值越大代表能獲勝的難度越小。如例1，Gk的難度就表示地主的獲勝的難度是0.6，出炸彈能夠勝利的難度是0.4。

2.4 選取具有同等牌力的初始手牌

若兩副初始手牌的GDI值完全相同或差距足夠小，就認(rèn)為這兩副牌的難度相同，即它們具有同等牌力。等級(jí)難度評(píng)估指標(biāo)的n個(gè)值之間的差距可用歐氏距離計(jì)算，計(jì)算公式為

式中兩副初始手牌的等級(jí)難度評(píng)估指標(biāo)分別為G1=(g11,g12,···,g1n) 和G2=(g21,g22,···,g2n)， 若d12值小于預(yù)設(shè)距離閾值，則G1與G2具有同等牌力值，否則不具有同等牌力。

系統(tǒng)中也可以任意地或者有目的性地指定一個(gè)難度Gc。比如一輪同等牌力比賽中決定分發(fā)一副難度中等的手牌，就可以指定Gc=(0.75,0.52,0.25)，Gc的難度就表示地主獲勝的難度是0.52，出炸彈能夠勝利的難度是0.25。然后設(shè)定一個(gè)閾值，通過找出GDI與Gc的距離小于ε的初始手牌，來生成與這個(gè)難度相對(duì)應(yīng)的同等牌力的牌。

為驗(yàn)證同等牌力生成方法的可靠性，本文指定了n個(gè)不同水平的地主DDZAI，與相同的1個(gè)下家DDZAI和1個(gè)上家DDZAI組成n桌，作為同一批比賽選手，分別進(jìn)行復(fù)式賽、同等牌力賽和隨機(jī)發(fā)牌賽。復(fù)式賽指每一輪為每桌分發(fā)相同的初始手牌。同等牌力賽是指每一輪為每桌分發(fā)不同的具有同等牌力的初始手牌。隨機(jī)發(fā)牌賽指每一輪為每桌隨機(jī)分發(fā)不同的初始手牌。

3種比賽都采用同一批選手，分別進(jìn)行r場(chǎng)比賽，每場(chǎng)比賽進(jìn)行m輪。每輪比賽記錄每桌DDZAI的地主得分。m輪比賽后，統(tǒng)計(jì)每桌DDZAI地主總得分，并記錄每桌DDZAI的地主名次。r場(chǎng)比賽后，統(tǒng)計(jì)每桌DDZAI地主獲得每個(gè)名次的概率，并以概率最大對(duì)應(yīng)的名次作為地主DDZAI的排名。由于比賽選手固定，如果r場(chǎng)比賽后，同等牌力賽后選手排名與復(fù)式賽后選手的排名基本一致，而與隨機(jī)發(fā)牌比賽后選手的排名不一致，就表明同等牌力生成方法是有效的，同等牌力賽代替復(fù)式賽是可行的。

3 實(shí)驗(yàn)與分析

本文使用Intel Xeon E5-2 640 CPU，NVIDIA 2080Ti GPU和Ubuntu 16.04系統(tǒng)的服務(wù)器，Python語言，對(duì)所提方法進(jìn)行了3個(gè)實(shí)驗(yàn)。

實(shí)驗(yàn)1 生成多個(gè)具有區(qū)分度的DDZAI

利用國內(nèi)某著名競(jìng)技二打一游戲平臺(tái)提供的7 000萬條游戲日志，使用算法1，將地主的數(shù)據(jù)集劃分為70個(gè)，分別訓(xùn)練了70個(gè)地主DDZAI；另外利用下家和頂家數(shù)據(jù)，訓(xùn)練了1個(gè)下家DDZAI和1個(gè)頂家DDZAI。每桌固定下家和頂家DDZAI，與不同的地主共組成70桌牌局。本文隨機(jī)選取了其中的10桌DDZAI，根據(jù)圖2所示進(jìn)行復(fù)式賽。10個(gè)DDZAI獲得每個(gè)名次的概率以及每個(gè)DDZAI的排名如圖3所示。

圖3 10個(gè)DDZAI獲得每個(gè)名次的概率Fig.3 Probability of ten DDZAI winning each place

實(shí)驗(yàn)結(jié)果表明：10個(gè)DDZAI在不同名次的概率值是不同的，與復(fù)式賽得出的排名基本一致，表明生成的DDZAI是具有一定區(qū)分度的。

實(shí)驗(yàn)2 具有同等牌力的初始手牌測(cè)試

隨機(jī)生成20萬副3家持有的炸彈總和數(shù)為1的初始手牌，發(fā)給70桌，共生成1 400萬個(gè)牌譜，分別計(jì)算20萬副初始手牌的GDI。

本文以初始手牌Center難度GDI=(0.96,0.91,0.79)作為參照，設(shè)置參數(shù)ε=0.15，選取了5個(gè)具有不同難度的GDI，如表1所示。利用式(2)，分別計(jì)算與center的距離，計(jì)算結(jié)果顯示前3個(gè)都小于0.15，這表明三者具有同等牌力。后2個(gè)計(jì)算與center的距離大于0.15，表明這兩者不具有同等牌力。

表1 5個(gè)具有不同難度的GDITable 1 Five GIDs with different difficulties

首先從手牌對(duì)應(yīng)的難度值上分析同等牌力情況。手牌Center難度GDI=(0.96,0.91,0.79)表明此牌有91%的概率贏得比賽，有79%的概率出炸彈[14]并贏得比賽，對(duì)于地主來說獲勝難度很小。Center1對(duì)應(yīng)的初始手牌有95%的概率贏得比賽，有95%的概率出炸彈并贏得比賽，對(duì)于地主來說獲勝難度很小。Center2獲勝的概率是97%，出炸彈并能勝利的概率為82%，對(duì)于地主來說獲勝難度小。Center3獲勝的概率是85%，出炸彈并能勝利的概率為72%，對(duì)于地主來說獲勝難度較小。Center4獲勝的概率是67.7%，出炸彈并能勝利的概率為61.8%，對(duì)于地主來說打牌難度很大。Center5獲勝的概率是100%，出炸彈并能勝利的概率為100%，對(duì)于地主來說打牌獲勝過于簡(jiǎn)單。

對(duì)應(yīng)表1生成的初始手牌事例，如表2所示，下面從牌面對(duì)這5副初始手牌的難度進(jìn)行分析。

表2 生成的與center具有同等牌力的初始手牌事例Table 2 Generated initial hand case with the same force as center

第1副初始手牌：地主持有最大的3張，且地主出順子6789TJ或者56789TJ后會(huì)將農(nóng)民的手牌拆散，若農(nóng)民的水平不夠，只要放走地主一手小單牌或者小對(duì)子，則地主能夠出炸彈并勝利，因此第1副初始手牌符合Center的難度。

第2副初始手牌：地主持有最大的3張，且2家農(nóng)民掉張過多，會(huì)放走地主的小牌，地主能夠大概率出炸彈并勝利，因此第2副初始手牌符合Center的難度。

第3副初始手牌：地主持有最大的對(duì)子，如果農(nóng)民拆AAA管地主的QQ，則地主的KKK又變成最大，地主能夠大概率出炸彈并勝利，因此第3副初始手牌符合Center的難度。

第4副初始手牌：農(nóng)民持有最大的對(duì)子，且地主不善于打?qū)ψ?，農(nóng)民有控制牌權(quán)的能力，且地主小牌較多，但是地主持有KKKAAA2D大牌和炸彈，能夠大概率勝利，但是難度要高于前3副牌。

第5副初始手牌：地主持有3個(gè)3張帶單，1個(gè)炸彈，2個(gè)對(duì)子，地主必能出炸彈勝利，此手牌過于簡(jiǎn)單，因此第5副初始手牌也不符合Center的難度。

實(shí)驗(yàn)結(jié)果表明，根據(jù)不同初始手牌GDI值的相近程度，來認(rèn)定哪些牌具有同等牌力的方法是可行的。

實(shí)驗(yàn)3 驗(yàn)證同等牌力應(yīng)用于比賽的可行性

本文共選取了5桌DDZAI參加比賽，復(fù)式賽、隨機(jī)發(fā)牌賽和同等牌力賽的比賽場(chǎng)數(shù)都為20，一場(chǎng)比賽的輪數(shù)分別設(shè)置為5、10、20。選取同等牌力的初始手牌時(shí)，設(shè)置Center難度為GDI=(0.96,0.91,0.79)，ε的取值分別設(shè)置為0.15、0.20、0.25。復(fù)式賽每個(gè)DDZAI獲得排名1～5的概率如表3所示。

表3 復(fù)式賽中每個(gè)DDZAI獲得前5名的概率Table 3 Probability of each DDZAI winning the first five places in a duplicate tournament

隨機(jī)發(fā)牌賽每個(gè)DDZAI獲得排名1～5的概率如表4所示，參數(shù)ε不同取值的同等牌力賽后，每個(gè)DDZAI獲得排名1～5的概率如表5所示。

表4 隨機(jī)發(fā)牌賽中每個(gè)DDZAI獲得前5名的概率Table 4 Probability of each DDZAI winning the first five places in a random licensing tournament

表5 同等牌力賽中每個(gè)DDZAI獲得前5名的概率Table 5 Probability of each DDZAI winning the first five places in the equal card force

續(xù)表5

實(shí)驗(yàn)結(jié)果分析：1)對(duì)比表3、4、5，可以看出當(dāng)ε= 0.15時(shí)，同等牌力賽的DDZAI排名與復(fù)式賽的DDZAI排名一致，與隨機(jī)發(fā)牌賽的DDZAI排名不一致，說明了同等牌力生成方法的可靠性；2)從表4可以看出，當(dāng)ε增大時(shí)，DDZAI獲得每個(gè)名次的概率分布越均衡，評(píng)估出AI名次的難度越大，ε<0.15是合適的取值，所以ε的選擇較關(guān)鍵。3)對(duì)比表3、4、5，可以看出當(dāng)ε確定時(shí)，隨著比賽輪數(shù)的增加，DDZAI獲得每個(gè)名次的概率分布沒有變化，因此增加比賽輪數(shù)不會(huì)降低同等牌力賽評(píng)估出AI名次的難度。

4 結(jié)束語

本文創(chuàng)新性地提出由多個(gè)不同水平的“二打一AI程序”來代替真人打牌，產(chǎn)生牌譜，生成同等牌力并進(jìn)行驗(yàn)證的方法，以保證實(shí)驗(yàn)結(jié)果的可靠性；提出了用等級(jí)難度評(píng)估指標(biāo)GDI來表示初始手牌的難度，給出了判定具有同等牌力的初始手牌的方法；通過指定DDZAI分別進(jìn)行隨機(jī)發(fā)牌賽、復(fù)式賽和同等牌力賽。實(shí)驗(yàn)表明，在選擇合適閾值情況下，提出的同等牌力生成方法是有效的，用同等牌力賽代替當(dāng)前的復(fù)式賽是可行的。

本文提出的方法需要通過DDZAI計(jì)算每一副初始手牌的GDI，消耗的時(shí)間較多，只能將得出的具有同等牌力的初始手牌提前存儲(chǔ)在牌庫中用于比賽，這就需要建立一個(gè)可動(dòng)態(tài)、隨機(jī)生成指定難度的初始手牌系統(tǒng)。本文在接下來的研究中，將對(duì)動(dòng)態(tài)的“同等牌力”生成系統(tǒng)進(jìn)行研究。