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

（北京信息科技大學 計算機學院，北京 100101）

0 引 言

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

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

圖1 一殘局模式開局Fig.1 One endgame start

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

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

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

1 二打一游戲殘局對弈策略設計與實現(xiàn)

本文二打一游戲殘局對弈整體策略由手牌拆分、招法過濾和招法應對三個主要部分組成。

1.1 手牌拆分的設計與實現(xiàn)

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

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

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

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

1.2 招法過濾設計與實現(xiàn)

拆分好手牌后進行招法過濾，招法過濾分2種情況：

（1）當牌局開始或對方Pass輪到己方出牌時，遍歷存儲己方招法的，按表1中牌型順序返回當前手牌可組成的所有招法。

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

1.3 招法應對設計與實現(xiàn)

招法應對對應招法過濾也分2種情況：

（1）當牌局開始或對方Pass輪到己方出牌時，招法選擇分值為100的招式作為出牌策略。

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

1.3.1 深度搜索局面標定

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

圖3 完全搜索倒推的預計結果Fig.3 Expected results of full search backwards

深度搜索局面標定法步驟如下：

（1）將雙方剩余手牌作為當前局面。

（2）對當前局面執(zhí)行Alpha-Beta深度搜索，每執(zhí)行一步為一節(jié)點。

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

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

1.3.2 向上傳遞

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

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

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

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

（3）評價往回倒推時，相當于2個局中人的對抗策略，交替使用（1）、（2）兩種方法傳遞倒推值。具體實例參見圖3。

1.3.3 Alpha-Beta剪枝

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

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

圖4 剪枝實例Fig.4 Pruning example

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

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

2 實驗結果與分析

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

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

對方出Q，如圖7所示。

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

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

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

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

對方出［‘2’］，如圖9所示。

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

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

圖10 己方passFig.10 The self is pass

對方出“334455”，如圖11所示。

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

圖11 對方出牌為［‘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’］

對方出“pass”，如圖13所示。

圖13 對方passFig.13 The opponent is pass

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

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

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

圖15 對方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

本文通過微信端歡樂斗地主小程序中的餐具闖關模式對程序進行實際測試，共進行了140關殘局闖關測試，均成功取得勝利，實驗結果如圖18所示。

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

3 結束語

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