郭榮城，李淑琴，龔元函，黃韶華，衡 鑫

（北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京 100101）

0 引 言

計(jì)算機(jī)博弈作為人工智能的重要發(fā)展方向之一，被稱為是人工智能學(xué)科的“果蠅”。二打一智力游戲（也稱“斗地主”）是一種玩法簡(jiǎn)單、娛樂(lè)性強(qiáng)的撲克游戲。經(jīng)典的玩法是撲克牌一共54張，斗地主智力游戲需由3個(gè)玩家進(jìn)行，每人首先有17張手牌，底牌有3張。其中一名玩家根據(jù)手牌選擇要底牌，該玩家成為地主，其余2名玩家則為農(nóng)民。以某一玩家率先出盡手中牌來(lái)結(jié)束牌局判定勝負(fù)。

隨著斗地主智力游戲作為應(yīng)用軟件在各類電子平臺(tái)的日漸普及，游戲運(yùn)營(yíng)平臺(tái)逐漸對(duì)游戲玩法進(jìn)行拓展，除經(jīng)典玩法外又陸續(xù)推出了多樣化的各種玩法，如殘局玩法、癩子玩法、換三張?zhí)魬?zhàn)賽等，這些玩法基于斗地主智力游戲的基礎(chǔ)規(guī)則衍生出其他新的規(guī)則或針對(duì)傳統(tǒng)牌局的局部進(jìn)行獨(dú)立，其中“殘局玩法”（如圖1）便是其中的一個(gè)代表。

圖1 一殘局模式開(kāi)局Fig.1 One endgame start

“殘局玩法”的規(guī)則為：牌局中有2個(gè)角色：一位地主和一位農(nóng)民，雙方分別有部分手牌（張數(shù)不固定），玩家將固定當(dāng)?shù)刂魇紫瘸雠?，農(nóng)民方為運(yùn)營(yíng)平臺(tái)的智能AI，雙方均為明牌，整個(gè)牌局至少存在一種地主勝利的解法，玩家需要嘗試贏下牌局，出牌規(guī)則與經(jīng)典玩法一致。

二打一智力游戲作為一種經(jīng)典的博弈類游戲，受到機(jī)器博弈領(lǐng)域的廣泛研究與關(guān)注，由于這是一種非完全信息類游戲，每個(gè)玩家看到的信息是不對(duì)稱的，就使得玩家只能靠“猜”來(lái)做決策，增加了很多變數(shù)，并且二打一智力游戲中合作與競(jìng)爭(zhēng)并存的設(shè)定，空間動(dòng)作的巨大使得自身與其他機(jī)器博弈類游戲有很大差距，研究可知針對(duì)圍棋的著名AI算法AlphaZero中的算法MCTS就無(wú)法直接應(yīng)用在二打一中。所以二打一的AI算法很多都采用了蒙特卡洛、深度學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等，例如2021年快手推出的DouZero作為一匹黑馬擊敗344個(gè)AI登頂二打一AI排行榜便是應(yīng)用了蒙特卡洛、深度神經(jīng)網(wǎng)絡(luò)、動(dòng)作編碼等技術(shù)。

而二打一殘局模式相較于經(jīng)典二打一模式，針對(duì)于少量手牌將局面做了很大程度簡(jiǎn)化，由三人非完全信息博弈轉(zhuǎn)變?yōu)殡p人完全信息博弈，殘局模式旨在鍛煉玩家對(duì)拆牌壓牌的理解，以達(dá)到在普通玩法中合理運(yùn)用己方手牌達(dá)到“以弱勝?gòu)?qiáng)”的效果。本文擬采用基于Alpha-Beta剪枝的方法，對(duì)二打一殘局模式進(jìn)行研究。

1 二打一游戲殘局對(duì)弈策略設(shè)計(jì)與實(shí)現(xiàn)

本文二打一游戲殘局對(duì)弈整體策略由手牌拆分、招法過(guò)濾和招法應(yīng)對(duì)三個(gè)主要部分組成。

1.1 手牌拆分的設(shè)計(jì)與實(shí)現(xiàn)

本文首先將二打一中手牌定義為火箭、炸彈、單牌、對(duì)子、三張、三帶一、三帶二、單順、連對(duì)、飛機(jī)、三帶一飛機(jī)、三帶二飛機(jī)、四帶二和四帶兩對(duì)，總共14種牌型。由二打一游戲?qū)囊?guī)則，火箭最大，可以打任意其他的牌。炸彈比火箭小，比其他牌大，都是炸彈時(shí)按牌的分值比大小。除火箭和炸彈外，其他牌必須要牌型相同且總張數(shù)相同才能比大小。對(duì)牌、三張牌都按分值比大小。單順牌按最大的一張牌的分值來(lái)比大小。單牌按分值比大小，依次是：大王＞小王＞2＞A＞K＞Q＞J＞10＞9＞8＞7＞6＞5＞4＞3，不分花色。為此，本文根據(jù)對(duì)弈規(guī)則為每種牌型賦予了牌型內(nèi)分值和牌型價(jià)。其中，牌型內(nèi)分值指各牌型中的招法之間存在分值大小關(guān)系。牌型價(jià)值是指除炸彈與火箭外所有牌型價(jià)值為0，炸彈價(jià)值為1，火箭價(jià)值為2。具體見(jiàn)表1。

表1 牌型定義及分值表Tab.1 Card type definition and score table

手牌拆分就是當(dāng)輪到己方出牌時(shí)將手牌進(jìn)行循環(huán)遍歷，將手牌依據(jù)表1中的牌型組合出所有對(duì)應(yīng)的招法，招法指根據(jù)14種牌型組出的具體手牌組合。然后將招法分別存入到對(duì)應(yīng)的牌型中，并根據(jù)牌型類型與點(diǎn)數(shù)大小賦予對(duì)應(yīng)的分值。程序針對(duì)圖1返回的己方所有可行招法的實(shí)際演示見(jiàn)圖2，共有11種組合招法。

圖2 針對(duì)圖1的己方所有招法Fig.2 All the moves against Fig.1 in self side

1.2 招法過(guò)濾設(shè)計(jì)與實(shí)現(xiàn)

拆分好手牌后進(jìn)行招法過(guò)濾，招法過(guò)濾分2種情況：

（1）當(dāng)牌局開(kāi)始或?qū)Ψ絇ass輪到己方出牌時(shí)，遍歷存儲(chǔ)己方招法的，按表1中牌型順序返回當(dāng)前手牌可組成的所有招法。

（2）當(dāng)對(duì)方出牌后，將對(duì)方的招法與14種牌型做對(duì)比，判斷對(duì)手招法是14種牌型類型的哪一種，依據(jù)前文中提到的招法價(jià)值大小關(guān)系將對(duì)方招法與己方所有招法進(jìn)行牌型內(nèi)分值與牌型價(jià)值比較，返回所有牌型內(nèi)分值或牌型價(jià)值大于對(duì)方招法的己方招法。

1.3 招法應(yīng)對(duì)設(shè)計(jì)與實(shí)現(xiàn)

招法應(yīng)對(duì)對(duì)應(yīng)招法過(guò)濾也分2種情況：

（1）當(dāng)牌局開(kāi)始或?qū)Ψ絇ass輪到己方出牌時(shí)，招法選擇分值為100的招式作為出牌策略。

（2）當(dāng)對(duì)方出牌后、己方跟牌時(shí)，從招法過(guò)濾獲取到己方所有可組成的招法中，通過(guò)Alpha-Beta剪枝算法，選擇出一種必勝的出牌策略。Alpha-Beta剪枝搜索大體可以分為3個(gè)步驟：局面標(biāo)定、傳遞倒推、剪枝。3個(gè)步驟依次進(jìn)行，最終獲取到一條最優(yōu)路徑，即選出最佳出牌策略。

1.3.1 深度搜索局面標(biāo)定

Alpha-Beta剪枝搜索經(jīng)常用于計(jì)算機(jī)零和博弈游戲中。在建立博弈樹(shù)的過(guò)程中，地主狀態(tài)層，農(nóng)民狀態(tài)層交替建立，兩者博弈樹(shù)關(guān)系如圖3所示。圖3中，方形代表地主，圓形代表農(nóng)民。由于斗地主殘局模式屬于雙人完備信息游戲，所以獲得勝利的決策近乎唯一。在這種情況下進(jìn)行Alpha-Beta剪枝搜索，可以找出最佳出牌路徑，通過(guò)搜索到底得到精確的輸贏反饋值，從而對(duì)局面進(jìn)行標(biāo)定。

圖3 完全搜索倒推的預(yù)計(jì)結(jié)果Fig.3 Expected results of full search backwards

深度搜索局面標(biāo)定法步驟如下：

（1）將雙方剩余手牌作為當(dāng)前局面。

（2）對(duì)當(dāng)前局面執(zhí)行Alpha-Beta深度搜索，每執(zhí)行一步為一節(jié)點(diǎn)。

（3）每走一步便進(jìn)行手牌拆分，并將新拆分出的招法作為下一步的分支。

（4）將一條分支延伸到一方手牌出盡，若地主勝利則將當(dāng)前局面值標(biāo)定為100，若農(nóng)民勝利則將當(dāng)前局面值標(biāo)定為0。

1.3.2 向上傳遞

（1）在偶數(shù)層節(jié)點(diǎn)的招法、即輪到農(nóng)民出牌的節(jié)點(diǎn)時(shí)，農(nóng)民應(yīng)考慮最好的情況，選擇其全部子節(jié)點(diǎn)中評(píng)估值最大的一個(gè)，即：

其中，（·）為節(jié)點(diǎn)估值，，，…，v為節(jié)點(diǎn)的子節(jié)點(diǎn)。

（2）在奇數(shù)層節(jié)點(diǎn)的招法、即輪到地主出牌的節(jié)點(diǎn)時(shí)，地主應(yīng)考慮最壞的情況，選擇其全部子節(jié)點(diǎn)中評(píng)估值最小的一個(gè)，即：

其中，（·）為節(jié)點(diǎn)估值，，，…，v為節(jié)點(diǎn)的子節(jié)點(diǎn)。

（3）評(píng)價(jià)往回倒推時(shí)，相當(dāng)于2個(gè)局中人的對(duì)抗策略，交替使用（1）、（2）兩種方法傳遞倒推值。具體實(shí)例參見(jiàn)圖3。

1.3.3 Alpha-Beta剪枝

本程序中Alpha-Beta剪枝與普通的Alpha-Beta剪枝算法稍有不同，由于局面標(biāo)定中只會(huì)出現(xiàn)0和100兩個(gè)值，分別代表農(nóng)民勝利和地主勝利，所以當(dāng)min層中出現(xiàn)0，便意味著此條分支的父節(jié)點(diǎn)所選擇的招法已無(wú)法獲得地主勝利的情況，所以當(dāng)前父節(jié)點(diǎn)還未搜索的分支已無(wú)搜索的必要，即減去后續(xù)未搜索的分支。max層中出現(xiàn)100時(shí)與之同理。

剪枝實(shí)例如圖4所示。圖4中，①處分支為min層，由于遍歷搜索已經(jīng)搜索到了值為100的分支，所以①分支便停止搜索即被剪枝，②處同理，③、④分支處于max層，由于已搜索到了值為0的分支，所以③、④分支被剪枝，但由于已搜索到一條分值為100的樹(shù)，程序已經(jīng)停止搜索，故實(shí)際上③、④所處子樹(shù)并未被搜索。

圖4 剪枝實(shí)例Fig.4 Pruning example

上述算法的實(shí)現(xiàn)流程如圖5所示。圖5中，為min層值，為max層值。

圖5 算法流程圖Fig.5 Algorithm flowchart

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

本文通過(guò)微信平臺(tái)小程序“歡樂(lè)斗地主”中的殘局闖關(guān)模式對(duì)算法程序進(jìn)行測(cè)試，以下為其中一殘局的完整對(duì)弈局，并將己方出牌執(zhí)行情況附在圖的右側(cè)。

己方出牌為［‘4’］時(shí)的牌局如圖6所示，將殘局雙方手牌導(dǎo)入進(jìn)程序，第一步為己方出牌，根據(jù)雙方手牌運(yùn)行Alpha-Beta剪枝程序，通過(guò)多線程搜索分別基于不同出牌方式構(gòu)建多個(gè)博弈樹(shù)，由圖6可見(jiàn)，當(dāng)前手牌程序返回了11種出牌方式，即基于這11種出牌方式構(gòu)建11棵博弈樹(shù)，由圖6可見(jiàn)程序依次返回基于出牌方式［‘k’，’k’，’k’］、［‘8’］、［‘6’］、［‘7’］、［‘K’］所構(gòu)建的博弈樹(shù)的返回值為0，即這些出牌方式己方無(wú)法勝利，繼續(xù)返回基于出牌方式［‘4’］所構(gòu)建的博弈樹(shù)，返回值為100，即此種出牌方式己方必勝，搜索到必勝的出牌方法后停止對(duì)其余出牌方式的博弈樹(shù)的構(gòu)建，但考慮到搜索為多線程進(jìn)行，在發(fā)出停止命令之前其他線程又返回了基于出牌方式［‘Q’］、［‘6’，’6’］、［‘7’，’7’］、［‘8’，’8’］、［‘2’］所構(gòu)建的博弈樹(shù)，由于已經(jīng)搜索到必勝的出牌方式［‘4’］，所以下一步的手牌出法為［‘4’］。

對(duì)方出Q，如圖7所示。

當(dāng)前本文程序返回了3種出牌方式，即基于這3種出牌方式構(gòu)建3棵博弈樹(shù)，由圖6、圖7可見(jiàn)程序首先返回基于出牌方式［‘K’］所構(gòu)建的博弈樹(shù)，返回值為100，即此種出牌方式己方必勝，搜索到必勝的出牌方法后停止對(duì)其余出牌方式的博弈樹(shù)的構(gòu)建，但也考慮到搜索為多線程進(jìn)行，在發(fā)出停止命令之前其他線程又返回了基于出牌方式［‘2’］所構(gòu)建的博弈樹(shù)，由于已經(jīng)搜索到必勝的出牌方式［‘K’］，所以下一步的手牌出法為［‘K’］。己方出牌為［‘K’］時(shí)的牌局如圖8所示。

圖6 己方出牌為［‘4’］Fig.6 The card of the self side is［‘4’］

圖7 對(duì)方出牌為［‘Q’］Fig.7 The card of the opponent side is［‘Q’］

圖8 己方出牌為［‘K’］Fig.8 The card of the self side is［‘K’］

對(duì)方出［‘2’］，如圖9所示。

圖9 對(duì)方出牌為［‘2’］Fig.9 The card of the opponent side is［‘2’］

對(duì)方出牌為［‘2’］，己方無(wú)可出牌型，即只有一種手牌出法：“pass”。如圖10所示。

圖10 己方passFig.10 The self is pass

對(duì)方出“334455”，如圖11所示。

己方當(dāng)前手牌程序返回了2種出牌方式，即基于這2種出牌方式構(gòu)建2棵博弈樹(shù)，由圖11可見(jiàn)程序首先返回基于出牌方式［‘6’‘6’‘7’‘7’‘8’‘8’］所構(gòu)建的博弈樹(shù)，返回值為100，即此種出牌方式己方必勝，搜索到必勝的出牌方法后停止對(duì)其余出牌方式的博弈樹(shù)的構(gòu)建，但由于搜索為多線程進(jìn)行看，在發(fā)出停止命令之前其他線程又返回了基于出牌方式pass所構(gòu)建的博弈樹(shù)，由于已經(jīng)搜索到必勝的出牌方式［‘6’‘6’‘7’‘7’‘8’‘8’］，所以下一步的手牌出法為［‘6’‘6’‘7’‘7’‘8’‘8’］。如圖12所示。

圖11 對(duì)方出牌為［‘3’‘3’‘4’‘4’‘5’‘5’］Fig.11 The opponent′s card is［‘3’‘3’‘4’‘4’‘5’‘5’］

圖12 己方出牌為［‘6’‘6’‘7’‘7’‘8’‘8’］Fig.12 The card of the self side is［‘6’‘6’‘7’‘7’‘8’‘8’］

對(duì)方出“pass”，如圖13所示。

圖13 對(duì)方passFig.13 The opponent is pass

己方當(dāng)前手牌程序返回了2種出牌方式，即基于這2種出牌方式構(gòu)建2棵博弈樹(shù)，由圖可見(jiàn)程序首先返回基于出牌方式［‘2’］所構(gòu)建的博弈樹(shù)，返回值為100，即此種出牌方式己方必勝，搜索到必勝的出牌方法后停止對(duì)其余出牌方式的博弈樹(shù)的構(gòu)建，下一步的手牌出法為［‘2’］。如圖14所示。

圖14 己方出牌為［‘2’］Fig.14 The card of the self side is［‘2’］

對(duì)方繼續(xù)“pass”，如圖15所示。

圖15 對(duì)方passFig.15 The opponent is pass

己方只剩一張牌［‘Q’］，下一步的手牌出法為［‘Q’］，手牌出完，游戲勝利。如圖16和圖17所示。

圖16 己方出牌為［‘Q’］Fig.16 The card of the self side is［‘Q’］

圖17 游戲勝利Fig.17 Game victory

本文通過(guò)微信端歡樂(lè)斗地主小程序中的餐具闖關(guān)模式對(duì)程序進(jìn)行實(shí)際測(cè)試，共進(jìn)行了140關(guān)殘局闖關(guān)測(cè)試，均成功取得勝利，實(shí)驗(yàn)結(jié)果如圖18所示。

圖18 殘局闖關(guān)通過(guò)關(guān)數(shù)截圖Fig.18 Screenshot of the number of passes through the endgame

3 結(jié)束語(yǔ)

在斗地主游戲中，殘局策略非常關(guān)鍵，對(duì)博弈勝負(fù)有著至關(guān)重要的作用。本文基于Alpha-Beta剪枝算法對(duì)斗地主殘局模式出牌策略展開(kāi)了研究分析，提出了一種新的殘局策略，并加以實(shí)現(xiàn)，在與雙人明牌斗地主殘局中有著較好的表現(xiàn)。在接下來(lái)的工作中還需進(jìn)一步提煉判定手牌優(yōu)劣的因子加入完善算法，有利于后續(xù)研究的深入開(kāi)展。