基于Expectimax 搜索與Double DQN 的非完備信息博弈算法

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

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

0 概述

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

近年來，關(guān)于完備信息博弈和非完備信息博弈的研究在多個應(yīng)用領(lǐng)域取得突破性進(jìn)展。在圍棋應(yīng)用方面，Google 公司DeepMind 團(tuán)隊開發(fā)出AlphaGo、AlphaGoZero 和AlphaZero 等系列圍棋博弈程序，并結(jié)合蒙特卡洛樹搜索與深度強(qiáng)化學(xué)習(xí)算法［5-7］進(jìn)行實現(xiàn)。2016 年，AlphaGo 以4∶1 擊敗韓國專業(yè)圍棋選手李世石引發(fā)社會關(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］解決了德州撲克一對一無限注博弈問題。此外，人們還對《星際爭霸II》等多人非合作游戲進(jìn)行研究，取得眾多研究成果［10-12］。

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

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

1 相關(guān)理論

1.1 Expectimax 搜索算法

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

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

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

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

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

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

2 本文算法

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

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

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

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

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

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

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

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

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

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

在有限時間內(nèi)通常無法完全搜索整個游戲樹，為使算法能在限定時間內(nèi)響應(yīng)，主要采取兩種方法：1）限制搜索樹深度并用估值函數(shù)評估當(dāng)前節(jié)點的值；2）設(shè)計一種合理的剪枝策略對游戲樹進(jìn)行剪枝。由于Expectimax 搜索算法的估值函數(shù)與剪枝策略均基于人工先驗知識而設(shè)計，因此該算法的決策水平在很大程度上取決于設(shè)計者對麻將的理解。為擺脫人工先驗知識的局限性，進(jìn)一步提高算法決策水平，本文結(jié)合Double DQN 算法對傳統(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ò)的輸出是一個34 維的數(shù)據(jù)，表示34 種出牌對應(yīng)的分?jǐn)?shù)（Q值）。

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

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

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

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

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

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

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

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

2.2.1 基于麻將先驗知識的特征編碼

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

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

表1 基于麻將先驗知識的特征編碼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ù)、牌庫剩余牌數(shù)等全部可見信息。

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

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

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

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

6）根據(jù)執(zhí)行動作、獎勵分?jǐn)?shù)、當(dāng)前游戲狀態(tài)信息和下一個游戲狀態(tài)信息，結(jié)合梯度下降算法對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)行計算。

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

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

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

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

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

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

將本文算法與其他監(jiān)督學(xué)習(xí)算法進(jìn)行對比，并討論參數(shù)α的設(shè)置對模型的影響。實驗環(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 場比賽）對監(jiān)督學(xué)習(xí)算法的網(wǎng)絡(luò)模型進(jìn)行訓(xùn)練，共篩選出360 萬條游戲數(shù)據(jù)，按照數(shù)量比例3∶1∶1 將數(shù)據(jù)分為訓(xùn)練集、測試集和驗證集，并根據(jù)表1 中特征編碼處理數(shù)據(jù)。值得注意的是，對于CNN、DenseNet 和ResNet 等具有卷積層結(jié)構(gòu)的網(wǎng)絡(luò)模型，需采用填零的方式將特征轉(zhuǎn)換為19×19 的二維矩陣。

3.2 對比實驗

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

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

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

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

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

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

本文實驗使用Expectimax搜索算法作為基準(zhǔn)算法，上述不同算法的實驗結(jié)果如表4 所示?？梢钥闯霰疚乃惴ㄔ趯Ρ葘嶒炛斜憩F(xiàn)最佳。對比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 搜索算法，這是因為監(jiān)督學(xué)習(xí)算法的網(wǎng)絡(luò)模型是通過收集用戶數(shù)據(jù)進(jìn)行訓(xùn)練，盡管已設(shè)置標(biāo)準(zhǔn)來篩選高水平玩家的游戲數(shù)據(jù)，但仍然無法保證數(shù)據(jù)質(zhì)量，而強(qiáng)化學(xué)習(xí)算法和Expectimax 搜索算法的網(wǎng)絡(luò)模型無需用戶游戲數(shù)據(jù)進(jìn)行訓(xùn)練，可避免人類先驗知識造成的偏誤。

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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