雷捷維，王嘉旸，任 航，閆天偉，黃 偉

（1.南昌大學(xué)信息工程學(xué)院，南昌 330031；2.江西農(nóng)業(yè)大學(xué)軟件學(xué)院，南昌 330000）

0 概述

博弈論是研究具有斗爭(zhēng)或競(jìng)爭(zhēng)性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法，是經(jīng)典的研究領(lǐng)域之一。博弈問題存在于人們生活各個(gè)方面。例如，商品定價(jià)可看作商人和顧客之間的博弈，國(guó)家之間的經(jīng)濟(jì)與軍事競(jìng)爭(zhēng)也可視為博弈問題。現(xiàn)實(shí)中博弈問題比較復(fù)雜，人們通常將其經(jīng)過抽象處理轉(zhuǎn)化為便于研究的游戲模型再加以解決。博弈主要分為完備信息博弈和非完備信息博弈。在完備信息博弈中，玩家可看到全部游戲狀態(tài)信息，不存在隱藏信息。例如，圍棋、國(guó)際象棋和五子棋等均為完備信息博弈。在非完備信息博弈中，玩家僅可看到自身游戲狀態(tài)信息和公共信息，而無(wú)法獲取其他游戲信息。例如，麻將、橋牌和德州撲克等均為非完備信息博弈。由于現(xiàn)實(shí)中許多博弈問題無(wú)法獲取全部信息而被歸類為非完備信息博弈，因此非完備信息博弈問題受到廣泛關(guān)注。研究非完備信息博弈，可解決金融競(jìng)爭(zhēng)［1］、交通疏導(dǎo)［2］、網(wǎng)絡(luò)安全［3］和軍事安全［4］等領(lǐng)域的問題。

近年來(lái)，關(guān)于完備信息博弈和非完備信息博弈的研究在多個(gè)應(yīng)用領(lǐng)域取得突破性進(jìn)展。在圍棋應(yīng)用方面，Google 公司DeepMind 團(tuán)隊(duì)開發(fā)出AlphaGo、AlphaGoZero 和AlphaZero 等系列圍棋博弈程序，并結(jié)合蒙特卡洛樹搜索與深度強(qiáng)化學(xué)習(xí)算法［5-7］進(jìn)行實(shí)現(xiàn)。2016 年，AlphaGo 以4∶1 擊敗韓國(guó)專業(yè)圍棋選手李世石引發(fā)社會(huì)關(guān)注。在德州撲克應(yīng)用方面，2015 年BOWLING 等人［8］在《Science》雜志發(fā)表關(guān)于CFR+算法的論文，證明該算法已完全解決兩人受限的德州撲克博弈問題。2017 年，阿爾伯塔大學(xué)開發(fā)出DeepStack系統(tǒng)，結(jié)合CFR 算法與多層深度神經(jīng)網(wǎng)絡(luò)（Deep Neural Network，DNN）［9］解決了德州撲克一對(duì)一無(wú)限注博弈問題。此外，人們還對(duì)《星際爭(zhēng)霸II》等多人非合作游戲進(jìn)行研究，取得眾多研究成果［10-12］。

相關(guān)研究顯示，麻將的復(fù)雜度要高于圍棋和德州撲克［13］，然而目前關(guān)于麻將研究較少，大多數(shù)麻將程序僅基于人工經(jīng)驗(yàn)進(jìn)行設(shè)計(jì)，未結(jié)合最新的強(qiáng)化學(xué)習(xí)等方法。目前麻將程序設(shè)計(jì)主要采用Expectimax 搜索算法［14-15］。2008 年，林典余［16］根據(jù)Expectimax 搜索算法以贏牌最快為原則設(shè)計(jì)麻將程序LongCat。2015 年，荘立楷［17］提出轉(zhuǎn)張概念對(duì)LongCat進(jìn)行改進(jìn)，利用所得麻將程序VeryLongCat進(jìn)一步提升LongCat的贏牌效率，并贏得該年度臺(tái)灣計(jì)算機(jī)博弈比賽和國(guó)際計(jì)算機(jī)博弈比賽的冠軍。然而在麻將游戲中要想贏牌，除了提高贏牌效率之外，還需提高贏牌得分。目前LongCat 和VeryLongCat 的剪枝策略和估值函數(shù)均基于人工先驗(yàn)知識(shí)設(shè)計(jì)，由于人類經(jīng)驗(yàn)中常存在不合理的決定或假設(shè)［18-19］，因此設(shè)計(jì)更合理的剪枝策略和估值函數(shù)成為亟待解決的問題。

為解決上述非完備信息博弈問題，本文以麻將為例進(jìn)行研究。目前麻將程序主要采用Expectimax搜索算法，其計(jì)算時(shí)間隨著搜索層數(shù)的增加呈指數(shù)級(jí)增長(zhǎng)，且其剪枝策略與估值函數(shù)基于人工先驗(yàn)知識(shí)設(shè)計(jì)得到。本文提出一種結(jié)合Expectimax 搜索與Double DQN 算法的非完備信息博弈算法，利用Double DQN［20］算法給出的子節(jié)點(diǎn)預(yù)估得分，為Expectimax 搜索算法設(shè)計(jì)更合理的估值函數(shù)與剪枝策略，并將游戲?qū)嶋H得分作為獎(jiǎng)勵(lì)訓(xùn)練Double DQN網(wǎng)絡(luò)模型以得到更高得分與勝率。

1 相關(guān)理論

1.1 Expectimax 搜索算法

Expectimax搜索樹［14-15］是一種常見的搜索算法，廣泛應(yīng)用于非完備信息博弈游戲，其結(jié)構(gòu)如圖1所示。在此類游戲中，由于某些信息具有隨機(jī)性和隱藏性，因此無(wú)法使用傳統(tǒng)的minimax搜索樹算法［21］來(lái)解決。針對(duì)該問題，Expectimax 搜索算法中設(shè)計(jì)了max 節(jié)點(diǎn)和chance 節(jié)點(diǎn)。其中，max 節(jié)點(diǎn)和chance 節(jié)點(diǎn)的效用值分別是其全部子節(jié)點(diǎn)效用值的最大值與加權(quán)平均值（即當(dāng)前節(jié)點(diǎn)到達(dá)每個(gè)子節(jié)點(diǎn)的概率）。例如，對(duì)于圖1中值為39 的max 節(jié)點(diǎn)，39 為其所有子節(jié)點(diǎn)（chance 節(jié)點(diǎn)）的最大值；對(duì)于值為14的chance節(jié)點(diǎn)，14為其所有子節(jié)點(diǎn)（max節(jié)點(diǎn)）的加權(quán)平均值，即：14=20×0.4+10×0.6。Expectimax 搜索算法與大多數(shù)游戲樹搜索算法類似，也是通過啟發(fā)式估值函數(shù)計(jì)算各節(jié)點(diǎn)估值。

圖1 Expectimax 算法的搜索樹結(jié)構(gòu)Fig.1 Search tree structure of Expectimax algorithm

1.2 Double DQN 強(qiáng)化學(xué)習(xí)算法

強(qiáng)化學(xué)習(xí)源于智能體對(duì)人類學(xué)習(xí)方式的模仿，是智能體通過與環(huán)境交互不斷增強(qiáng)其決策能力的過程。強(qiáng)化學(xué)習(xí)算法主要包括動(dòng)態(tài)規(guī)劃算法［22］、時(shí)序差分算法［23］、蒙特卡洛算法［24］和Q 學(xué)習(xí)算法［25］。這些算法均存在局限性：動(dòng)態(tài)規(guī)劃算法雖然數(shù)學(xué)理論完備，但是其使用條件非常嚴(yán)格；時(shí)序差分算法可在無(wú)法獲取環(huán)境全部信息的情況下得到較好效果；蒙特卡洛算法需對(duì)當(dāng)前未知環(huán)境進(jìn)行采樣分析，由于時(shí)間與空間具有復(fù)雜性，因此其很難應(yīng)用于解決時(shí)序決策問題；Q 學(xué)習(xí)算法是通過計(jì)算每個(gè)動(dòng)作的Q 值進(jìn)行決策，但是其存在過估計(jì)問題。

隨著對(duì)強(qiáng)化學(xué)習(xí)研究的不斷深入，研究人員對(duì)Q 學(xué)習(xí)算法改進(jìn)后提出深度Q 學(xué)習(xí)算法DQN［26-27］，該算法與Q 學(xué)習(xí)算法一樣，也是通過計(jì)算每個(gè)動(dòng)作的Q 值進(jìn)行決策，仍存在過估計(jì)問題。為解決該問題，研究人員在DQN 基礎(chǔ)上提出雙重深度Q 學(xué)習(xí)算法Double DQN［20］。

DQN 算法具有原始網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)兩個(gè)神經(jīng)網(wǎng)絡(luò)，雖然其結(jié)構(gòu)相同，但是權(quán)重更新不同步。DQN算法的權(quán)重更新使用均方誤差（Mean Squared Error，MSE）定義損失函數(shù)，其表達(dá)式如下：

其中，a為執(zhí)行動(dòng)作，Rt+1為獎(jiǎng)勵(lì)分?jǐn)?shù)，St為當(dāng)前游戲狀態(tài)信息，St+1為下一個(gè)游戲狀態(tài)信息，θ為網(wǎng)絡(luò)權(quán)重，γ為折扣因子，Q(S，a)為狀態(tài)S下執(zhí)行動(dòng)作a的估值。

由于Q 學(xué)習(xí)算法和DQN 算法中Max 操作使用相同值選擇和衡量一個(gè)動(dòng)作，可能選擇估計(jì)值過高的動(dòng)作導(dǎo)致過估計(jì)問題。為此，Double DQN 算法對(duì)動(dòng)作的選擇和衡量進(jìn)行解耦，將式（2）改寫為以下形式：

2 本文算法

2.1 基于Expectimax 搜索的麻將決策過程

由于麻將游戲過程中存在發(fā)牌隨機(jī)性等不確定因素，因此其規(guī)則比較復(fù)雜。在麻將游戲中，玩家可通過捉牌、吃牌、碰牌和杠牌等方式獲得一張牌，隨后需再打出一張牌，后續(xù)重復(fù)上述步驟，直到游戲結(jié)束為止。如果將吃牌、碰牌和杠牌視為特殊的捉牌，則麻將中所有動(dòng)作均可用序列<捉牌，打牌，捉牌，打牌…>來(lái)表示。其中，捉牌動(dòng)作記錄捉牌玩家的用戶ID 以及捉哪張牌等信息，打牌動(dòng)作記錄打牌玩家的用戶ID 以及打哪張牌等信息。

假設(shè)A、B、C 和D 代表4 名玩家，其中A 為當(dāng)前玩家，B、C、D 為其他玩家。如果A 捉牌“9 萬(wàn)”后打牌“6 萬(wàn)”，B 碰牌“3 萬(wàn)”后打牌“7 筒”，A 碰牌“7 筒”后打牌“1 萬(wàn)”，那么上述動(dòng)作序列可表示為。

實(shí)際上，如果在決策中考慮所有玩家的動(dòng)作，則Expectimax 算法的搜索樹很大，從而無(wú)法在有限時(shí)間內(nèi)做出決策。為解決該問題，通常將整個(gè)游戲博弈過程進(jìn)行抽象處理，僅考慮當(dāng)前玩家的捉牌與打牌動(dòng)作，并以此構(gòu)建Expectimax 算法的搜索樹。此外，為進(jìn)一步簡(jiǎn)化搜索樹，將吃牌、碰牌和杠牌也作為特殊的捉牌，則上述動(dòng)作序列表示為。

通過上述方法，本文將麻將游戲過程簡(jiǎn)化為捉牌和打牌兩個(gè)動(dòng)作。結(jié)合Expectimax 搜索算法，將捉牌動(dòng)作看作chance 節(jié)點(diǎn)，打牌動(dòng)作看作max 節(jié)點(diǎn)。例如，假設(shè)當(dāng)前玩家手中持有的牌（以下稱為手牌）為1 萬(wàn)、2 萬(wàn)、4 萬(wàn)、9 萬(wàn)和9 萬(wàn)，那么基于Expectimax算法的麻將搜索樹結(jié)構(gòu)如圖2 所示。

圖2 基于Expectimax 算法的麻將搜索樹Fig.2 Mahjong search tree based on Expectimax algorithm

在圖2 中：max 節(jié)點(diǎn)表示打牌節(jié)點(diǎn)；chance 節(jié)點(diǎn)表示捉牌節(jié)點(diǎn)；將“打牌節(jié)點(diǎn)，捉牌節(jié)點(diǎn)”作為搜索樹的一層；value 值表示游戲結(jié)束時(shí)當(dāng)前游戲樹分支獲得的分?jǐn)?shù)表示當(dāng)前第i層捉牌節(jié)點(diǎn)（父節(jié)點(diǎn)）轉(zhuǎn)移到第j個(gè)打牌節(jié)點(diǎn)的概率。計(jì)算公式如下：

其中，num(RmainTiles)表示牌庫(kù)中剩余牌的數(shù)量，表示使第i層捉牌節(jié)點(diǎn)轉(zhuǎn)移到第j個(gè)打牌節(jié)點(diǎn)的麻將牌。而表示該麻將牌在牌庫(kù)中的剩余數(shù)量。由圖2 和式（4）可計(jì)算出每個(gè)捉牌節(jié)點(diǎn)與打牌節(jié)點(diǎn)的值。

捉牌節(jié)點(diǎn)的值等于其所有子節(jié)點(diǎn)分?jǐn)?shù)的加權(quán)平均值，計(jì)算公式為：

打牌節(jié)點(diǎn)的值等于其所有子節(jié)點(diǎn)的最大分?jǐn)?shù)，計(jì)算公式為：

在有限時(shí)間內(nèi)通常無(wú)法完全搜索整個(gè)游戲樹，為使算法能在限定時(shí)間內(nèi)響應(yīng)，主要采取兩種方法：1）限制搜索樹深度并用估值函數(shù)評(píng)估當(dāng)前節(jié)點(diǎn)的值；2）設(shè)計(jì)一種合理的剪枝策略對(duì)游戲樹進(jìn)行剪枝。由于Expectimax 搜索算法的估值函數(shù)與剪枝策略均基于人工先驗(yàn)知識(shí)而設(shè)計(jì)，因此該算法的決策水平在很大程度上取決于設(shè)計(jì)者對(duì)麻將的理解。為擺脫人工先驗(yàn)知識(shí)的局限性，進(jìn)一步提高算法決策水平，本文結(jié)合Double DQN 算法對(duì)傳統(tǒng)的Expectimax 搜索算法進(jìn)行改進(jìn)。

本文將Double DQN 算法所用神經(jīng)網(wǎng)絡(luò)設(shè)為fθ。其中，參數(shù)θ表示神經(jīng)網(wǎng)絡(luò)的權(quán)重，神經(jīng)網(wǎng)絡(luò)的輸出是一個(gè)34 維的數(shù)據(jù)，表示34 種出牌對(duì)應(yīng)的分?jǐn)?shù)（Q值）。

1）對(duì)Expectimax 搜索算法中剪枝策略進(jìn)行改進(jìn)，如圖3 所示。對(duì)于當(dāng)前玩家的手牌，可通過神經(jīng)網(wǎng)絡(luò)fθ(S)計(jì)算每個(gè)打牌動(dòng)作對(duì)應(yīng)的Q值。

圖3 改進(jìn)Expectimax 搜索算法的剪枝策略Fig.3 The pruning strategy of the improved Expectimax search algorithm

在搜索樹擴(kuò)展的過程中，先通過神經(jīng)網(wǎng)絡(luò)的估值對(duì)所有打牌動(dòng)作從大到小進(jìn)行排序，再將前k個(gè)動(dòng)作擴(kuò)展為子節(jié)點(diǎn)，余下動(dòng)作不再擴(kuò)展，從而達(dá)到剪枝的目的。k值的計(jì)算公式如下：

其中，num(hand)表示當(dāng)前玩家手牌的牌數(shù)。由于神經(jīng)網(wǎng)絡(luò)能估算出每個(gè)動(dòng)作的Q值，因此通過為每個(gè)動(dòng)作的Q值排序，只擴(kuò)展前k個(gè)動(dòng)作來(lái)減小搜索樹的廣度，從而實(shí)現(xiàn)對(duì)搜索樹剪枝，使計(jì)算機(jī)在有限時(shí)間內(nèi)將更多時(shí)間用于搜索樹的深度擴(kuò)展。

2）改進(jìn)Expectimax 搜索算法的估值函數(shù)，如圖4所示。若麻將搜索樹某個(gè)分支在限定搜索層數(shù)內(nèi)能到達(dá)游戲結(jié)束狀態(tài)并獲得分?jǐn)?shù)，則將該分支的值設(shè)置為游戲?qū)嶋H分?jǐn)?shù)；否則需設(shè)計(jì)合理的評(píng)估函數(shù)，并將其估值作為該分支的值。

圖4 改進(jìn)Expectimax 搜索算法的估值函數(shù)架構(gòu)Fig.4 Evaluation function architecture of the improved Expectimax search algorithm

傳統(tǒng)Expectimax 搜索算法的估值函數(shù)大部分是基于人工先驗(yàn)知識(shí)而設(shè)計(jì)，存在不合理的決定或假設(shè)。本文采用Double DQN 神經(jīng)網(wǎng)絡(luò)的Q值解決該問題。如果麻將搜索樹的一個(gè)分支在限定搜索層數(shù)內(nèi)無(wú)法到達(dá)游戲結(jié)束狀態(tài)，則可通過神經(jīng)網(wǎng)絡(luò)計(jì)算當(dāng)前節(jié)點(diǎn)的Q值作為該分支的值，即：構(gòu)造一個(gè)打牌節(jié)點(diǎn)，再根據(jù)神經(jīng)網(wǎng)絡(luò)計(jì)算出每個(gè)動(dòng)作的Q值，并選擇最大的Q值max(Q) 作為該分支的值。改進(jìn)Expectimax 搜索算法的估值函數(shù)架構(gòu)如圖4 所示。

2.2 基于Double DQN 的麻將模型訓(xùn)練過程

2.2.1 基于麻將先驗(yàn)知識(shí)的特征編碼

在麻將游戲中，由于當(dāng)前玩家對(duì)其他玩家的手牌以及牌庫(kù)內(nèi)的牌不可見，因此麻將是典型的非完備信息博弈游戲，如何只根據(jù)游戲部分信息進(jìn)行正確決策是需要考慮的問題。

以下介紹基于麻將先驗(yàn)知識(shí)的特征編碼，如表1所示。這些特征包括當(dāng)前玩家的手牌、當(dāng)前玩家的副露、其他玩家的副露、所有玩家的棄牌以及游戲輪數(shù)等?；诼閷⑾嚓P(guān)先驗(yàn)知識(shí)可描述當(dāng)前游戲全部可見信息，從而加快麻將模型訓(xùn)練速度。本文使用ResNet 網(wǎng)絡(luò)［28］模型進(jìn)行訓(xùn)練，因此，需要將特征重塑為二維矩陣，即以填零的方式將特征向量轉(zhuǎn)換為19×19的二維矩陣，并將其輸入到ResNet 網(wǎng)絡(luò)。

表1 基于麻將先驗(yàn)知識(shí)的特征編碼Table 1 Feature coding based on mahjong prior knowledge

2.2.2 Double DQN 麻將模型的訓(xùn)練過程

圖5 為結(jié)合Expectimax 搜索算法的Double DQN網(wǎng)絡(luò)模型訓(xùn)練過程，其具體步驟如下：

1）獲取游戲中當(dāng)前玩家的手牌、當(dāng)前玩家的副露、其他玩家的副露、所有玩家的棄牌、游戲輪數(shù)、牌庫(kù)剩余牌數(shù)等全部可見信息。

2）根據(jù)麻將的先驗(yàn)知識(shí)，將可見信息編碼為特征數(shù)據(jù)。

3）將編碼后的特征數(shù)據(jù)輸入Double DQN 神經(jīng)網(wǎng)絡(luò)，從而獲得每個(gè)動(dòng)作的估值。

4）基于每個(gè)動(dòng)作的估值，使用改進(jìn)的Expectimax搜索算法精確計(jì)算出具有最高得分的推薦動(dòng)作，然后執(zhí)行該動(dòng)作。

5）動(dòng)作執(zhí)行完畢即可獲得下一個(gè)游戲狀態(tài)信息與該動(dòng)作的獎(jiǎng)勵(lì)分?jǐn)?shù)。

6）根據(jù)執(zhí)行動(dòng)作、獎(jiǎng)勵(lì)分?jǐn)?shù)、當(dāng)前游戲狀態(tài)信息和下一個(gè)游戲狀態(tài)信息，結(jié)合梯度下降算法對(duì)Double DQN神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練后得到麻將強(qiáng)化學(xué)習(xí)模型。其中，梯度下降算法在Double DQN 神經(jīng)網(wǎng)絡(luò)中需最小化的損失函數(shù)如式（1）所示，Double DQN 算法中Y值按照式（3）進(jìn)行計(jì)算。

圖5 Double DQN 麻將模型的訓(xùn)練過程Fig.5 Training procedure of Double DQN mahjong model

由于麻將游戲在結(jié)束時(shí)才能獲得獎(jiǎng)勵(lì)分?jǐn)?shù)，在游戲期間沒有任何獎(jiǎng)勵(lì)，因此麻將是一種典型的獎(jiǎng)勵(lì)稀疏游戲。為改變這一狀況，本文設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù)如下：

其中，VExpectimax為通過Expectimax 搜索算法計(jì)算得到的推薦動(dòng)作效用值。在式（8）中，將游戲結(jié)束時(shí)實(shí)際得分設(shè)置為模型的獎(jiǎng)勵(lì)，并將游戲中的獎(jiǎng)勵(lì)設(shè)置為0.1×VExpectimax。

由上述可知，Expectimax 搜索算法使用Double DQN 神經(jīng)網(wǎng)絡(luò)輸出的Q值來(lái)設(shè)計(jì)剪枝策略與評(píng)估函數(shù)。而在強(qiáng)化學(xué)習(xí)模型訓(xùn)練過程中，使用Expectimax 搜索算法改進(jìn)Double DQN 算法的探索策略與獎(jiǎng)勵(lì)函數(shù)。在該過程中，Double DQN 算法和Expectimax 搜索算法相互結(jié)合與促進(jìn)，進(jìn)一步提高麻將模型的決策水平。

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

3.1 數(shù)據(jù)描述和數(shù)據(jù)預(yù)處理

將本文算法與其他監(jiān)督學(xué)習(xí)算法進(jìn)行對(duì)比，并討論參數(shù)α的設(shè)置對(duì)模型的影響。實(shí)驗(yàn)環(huán)境為：3.6.5 Python，1.6.0 tensorflow，GTX 108 顯卡，16 GB RAM 內(nèi)存以及Ubuntu 16.04 系統(tǒng)。從某麻將游戲公司篩選大量高水平玩家的游戲數(shù)據(jù)（只篩選游戲得分排名前1 000 的玩家游戲記錄，且每位玩家至少已贏得500 場(chǎng)比賽）對(duì)監(jiān)督學(xué)習(xí)算法的網(wǎng)絡(luò)模型進(jìn)行訓(xùn)練，共篩選出360 萬(wàn)條游戲數(shù)據(jù)，按照數(shù)量比例3∶1∶1 將數(shù)據(jù)分為訓(xùn)練集、測(cè)試集和驗(yàn)證集，并根據(jù)表1 中特征編碼處理數(shù)據(jù)。值得注意的是，對(duì)于CNN、DenseNet 和ResNet 等具有卷積層結(jié)構(gòu)的網(wǎng)絡(luò)模型，需采用填零的方式將特征轉(zhuǎn)換為19×19 的二維矩陣。

3.2 對(duì)比實(shí)驗(yàn)

將本文提出的Expectimax搜索+Double DQN算法（以下稱為本文算法）與線性分類（Linear）、支持向量機(jī)（SVM）［29］、FC［30］、CNN、DenseNet-BC-190-40［31］、ResNet-1001［32］、DQN、Double DQN 以及Expectimax 搜索等算法進(jìn)行對(duì)比。其中，DQN、Double DQN 和本文算法（以下稱為第1 類算法）均使用20 層的ResNet作為神經(jīng)網(wǎng)絡(luò)。為便于比較，上述算法實(shí)驗(yàn)參數(shù)設(shè)置相同，如表2 所示。

表2 第1 類算法的實(shí)驗(yàn)參數(shù)設(shè)置Table 2 Experimental parameter setting of the first kind of algorithm

對(duì)于Linear、SVM、FC、CNN、DenseNet、ResNet-1001算法以及本文算法中的Expectimax搜索部分（第2類算法），相關(guān)參數(shù)設(shè)置如表3所示。其中，參數(shù)α采用多次實(shí)驗(yàn)得到的最佳值（關(guān)于參數(shù)α設(shè)置的討論見3.3節(jié)）。

表3 第2 類算法的實(shí)驗(yàn)參數(shù)設(shè)置Table 3 Experimental parameter setting of the second kind of algorithm

本文采用臺(tái)灣麻將游戲平臺(tái)進(jìn)行實(shí)驗(yàn)。與大部分麻將游戲不同，臺(tái)灣麻將在開局時(shí)，每位玩家持有16 張牌，且有花牌等特殊牌型。臺(tái)灣麻將贏牌的方式較簡(jiǎn)單，只有平胡，但其得分計(jì)算較復(fù)雜，計(jì)算公式如下：

其中，底分與番型得分需要玩家在游戲開始前設(shè)置，番數(shù)取決于玩家最后贏牌時(shí)的牌型，例如清一色、四暗刻等。本文排除臺(tái)灣麻將中的花牌來(lái)簡(jiǎn)化游戲流程，將底分和番型得分分別設(shè)置為1 000 和500，使用2對(duì)2 的形式進(jìn)行3 000 場(chǎng)4 人臺(tái)灣麻將比賽。在對(duì)局中，采用兩個(gè)算法為基準(zhǔn)算法，另外兩個(gè)算法為實(shí)驗(yàn)算法，同時(shí)輪流交換不同玩家的相對(duì)位置以確保游戲的公平性。將不同實(shí)驗(yàn)?zāi)Ｐ团c基準(zhǔn)模型進(jìn)行對(duì)比來(lái)分析其優(yōu)劣性。

本文實(shí)驗(yàn)使用Expectimax搜索算法作為基準(zhǔn)算法，上述不同算法的實(shí)驗(yàn)結(jié)果如表4 所示。可以看出本文算法在對(duì)比實(shí)驗(yàn)中表現(xiàn)最佳。對(duì)比ResNet-1001 和其他監(jiān)督學(xué)習(xí)模型可知，隨著模型復(fù)雜度的提高，監(jiān)督學(xué)習(xí)模型決策水平也相應(yīng)提升。但是橫向比較后發(fā)現(xiàn)，監(jiān)督學(xué)習(xí)算法不如強(qiáng)化學(xué)習(xí)算法和Expectimax 搜索算法，這是因?yàn)楸O(jiān)督學(xué)習(xí)算法的網(wǎng)絡(luò)模型是通過收集用戶數(shù)據(jù)進(jìn)行訓(xùn)練，盡管已設(shè)置標(biāo)準(zhǔn)來(lái)篩選高水平玩家的游戲數(shù)據(jù)，但仍然無(wú)法保證數(shù)據(jù)質(zhì)量，而強(qiáng)化學(xué)習(xí)算法和Expectimax 搜索算法的網(wǎng)絡(luò)模型無(wú)需用戶游戲數(shù)據(jù)進(jìn)行訓(xùn)練，可避免人類先驗(yàn)知識(shí)造成的偏誤。

表4 不同算法的實(shí)驗(yàn)結(jié)果Table 4 Experimental results of different algorithms

由表4 還可以看出：Double DQN 算法的性能優(yōu)于DQN 算法，這是因?yàn)镈ouble DQN 算法改善了DQN 算法的過估計(jì)問題；本文算法比Expectimax 搜索+DQN 算法的表現(xiàn)更好；本文算法的勝率比Expectimax 搜索算法高出2.26 個(gè)百分點(diǎn)，平均每局得分多185.097 分，這是因?yàn)楸疚乃惴▽xpectimax搜索算法與強(qiáng)化學(xué)習(xí)算法Double DQN 相結(jié)合，在游戲訓(xùn)練過程中不斷迭代優(yōu)化，從而提高勝率和得分。

3.3 參數(shù)α 的設(shè)置對(duì)模型的影響

本文在3.1節(jié)提出根據(jù)k值對(duì)搜索樹進(jìn)行剪枝的策略，由式（7）可知k值取決于參數(shù)α的設(shè)置。以下分別從耗時(shí)、勝率和得分討論參數(shù)α對(duì)本文算法的影響。

將參數(shù)α分別設(shè)置為0.2、0.4、0.6、0.8 和1.0，搜索樹限定層數(shù)分別設(shè)置為1 層和2 層，比較不同搜索層數(shù)下α值大小對(duì)本文算法的耗時(shí)、勝率和得分3 個(gè)方面的影響，結(jié)果如表5～表7 所示。

表5 參數(shù)α 對(duì)算法耗時(shí)的影響Table 5 Influence of parameter α on the time consumption of the algorithms

表6 參數(shù)α 對(duì)算法勝率的影響Table 6 Influence of parameter α on the winning rate of the algorithm%

表7 參數(shù)α 對(duì)算法得分的影響Table 7 Influence of parameter α on the score of the algorithm

在表5 中，當(dāng)參數(shù)α設(shè)置為1.0 時(shí)，相當(dāng)于完全展開整個(gè)搜索樹，此時(shí)算法在搜索層數(shù)為1 和2 時(shí)決策時(shí)間分別為0.068 s 和6.778 s?？梢钥闯觯绻恍藜羲阉鳂?，則決策時(shí)間會(huì)呈現(xiàn)指數(shù)級(jí)增長(zhǎng)，因此，需要合理地對(duì)搜索樹進(jìn)行剪枝從而減少算法耗時(shí)。由表5 還可以看出，隨著α值的減小，算法在不同搜索層數(shù)下決策時(shí)間不斷減少。由表6 和表7 可以看出，隨著搜索層數(shù)的增加，本文算法的勝率和得分相應(yīng)增加，而結(jié)合表5 可知算法的耗時(shí)隨著搜索層數(shù)增加也在增長(zhǎng)。因此，為使算法在3 s 內(nèi)做出響應(yīng)，本文算法選取α=0.6 且搜索層數(shù)為2。

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

麻將作為典型的非完備信息博弈游戲，主要通過Expectimax 搜索算法實(shí)現(xiàn)，而該算法中剪枝策略與估值函數(shù)基于人工先驗(yàn)知識(shí)而設(shè)計(jì)，存在不合理的假設(shè)。本文提出一種結(jié)合Expectimax搜索與Double DQN 的非完備信息博弈算法。利用Double DQN 強(qiáng)化學(xué)習(xí)算法改進(jìn)Expectimax 搜索樹的剪枝策略和估值函數(shù)，并通過Expectimax 搜索改進(jìn)Double DQN 模型探索策略與獎(jiǎng)勵(lì)函數(shù)。實(shí)驗(yàn)結(jié)果表明，與Expectimax 搜索算法相比，該算法在麻將游戲上勝率提高2.26 個(gè)百分點(diǎn)，平均每局得分增加185.097 分。由于本文算法剪枝策略中參數(shù)α需借助人工先驗(yàn)知識(shí)來(lái)選擇，因此后續(xù)將使用自適應(yīng)方法進(jìn)行改進(jìn)，以提高算法的準(zhǔn)確性。