一種多重優(yōu)先經(jīng)驗(yàn)回放的麻將游戲數(shù)據(jù)利用方法

李淑琴，李 奕

(1.北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院， 北京 100101； 2.感知與計(jì)算智能聯(lián)合實(shí)驗(yàn)室， 北京 100101)

0 引言

計(jì)算機(jī)博弈一直是驗(yàn)證人工智能理論的試金石，也是人工智能最活躍的研究領(lǐng)域之一。計(jì)算機(jī)博弈相關(guān)理論和技術(shù)被廣泛應(yīng)用于金融、交通、軍事等領(lǐng)域。計(jì)算機(jī)博弈通常包括完全信息博弈[1]和非完全信息博弈[2]。非完全信息博弈問(wèn)題相對(duì)于完全信息博弈，其研究更為困難也更加具有挑戰(zhàn)性。深度強(qiáng)化學(xué)習(xí)憑借深度學(xué)習(xí)的感知能力與強(qiáng)化學(xué)習(xí)的決策能力成為解決非完全信息博弈問(wèn)題的主流方法[3-5]，目前深度強(qiáng)化學(xué)習(xí)的研究點(diǎn)主要集中在樣本利用效率，獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)以及決策方法上。

在樣本利用方面，以往的經(jīng)驗(yàn)回放機(jī)制中最早采用的隨機(jī)經(jīng)驗(yàn)回放，即將多條經(jīng)驗(yàn)樣本存儲(chǔ)在經(jīng)驗(yàn)池中，然后隨機(jī)采樣更新深度神經(jīng)網(wǎng)絡(luò)，以便克服數(shù)據(jù)之間的相關(guān)性，這在一定程度上提高了數(shù)據(jù)利用率，但不符合人的學(xué)習(xí)習(xí)慣。人們?cè)谌粘５膶W(xué)習(xí)中，往往對(duì)一些重要的經(jīng)驗(yàn)記憶深刻，而忽略那些不重要的經(jīng)驗(yàn)。文獻(xiàn)[6]首次提出了優(yōu)先經(jīng)驗(yàn)回放機(jī)制，對(duì)于經(jīng)驗(yàn)池中的樣本，根據(jù)經(jīng)驗(yàn)重要性賦予不同的優(yōu)先級(jí)，樣本優(yōu)先級(jí)越大則其被采樣到的概率就越高，即希望越重要的經(jīng)驗(yàn)使用次數(shù)越多，從而增加學(xué)習(xí)效率。文獻(xiàn)[7]提出根據(jù)經(jīng)驗(yàn)樣本的時(shí)序差分誤差(temporal-difference)的不同，賦予每個(gè)樣本不同的優(yōu)先概率，誤差值越高，表明模型評(píng)估的差異越大，越需要訓(xùn)練，重要性越大。文獻(xiàn)[8]不僅考慮時(shí)序拆分誤差，還引入了Q值作為劃分標(biāo)準(zhǔn)。文獻(xiàn)[9]采用了回合平均獎(jiǎng)勵(lì)作為優(yōu)先級(jí)進(jìn)行樣本選取。可見(jiàn)優(yōu)先經(jīng)驗(yàn)回放機(jī)制中對(duì)經(jīng)驗(yàn)樣本的劃分方法并不統(tǒng)一，一般與具體領(lǐng)域有關(guān)。

本文從提高大眾麻將AI訓(xùn)練樣本利用率角度出發(fā)，通過(guò)改進(jìn)強(qiáng)化學(xué)習(xí)算法中樣本利用方法，以便提升麻將AI的訓(xùn)練速度。

1 大眾麻將游戲術(shù)語(yǔ)及規(guī)則

麻將是中國(guó)古代發(fā)明的一種不完全信息博弈游戲，在中國(guó)各地區(qū)都十分流行，不同地區(qū)有著不同的玩法。本文針對(duì)2021年中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽中大眾麻將[10-11]進(jìn)行研究，大眾麻將游戲基本術(shù)語(yǔ)及規(guī)則如下：

玩家：大眾麻將游戲由4名玩家組成。

牌庫(kù)：牌的總張數(shù)。大眾麻將分為條、筒、萬(wàn)三門(mén)，共計(jì)108張。

牌墻：開(kāi)局發(fā)完初始手牌后，剩下的牌為牌墻，共55張。

局面：某位玩家在某一個(gè)時(shí)刻可以觀察到的所有信息。

條：條子牌共有9種，由序數(shù)牌一條至九條組成，每一種都有4張，共有36張。

筒：筒子牌共有9種，由序數(shù)牌一筒至九筒組成，每一種都有4張，共有36張。

萬(wàn)：萬(wàn)字牌共有9種，由序數(shù)牌一萬(wàn)至九萬(wàn)組成，每一種都有4張，共有36張。

順子：指同一花色中，順序相連的3張牌，如“一萬(wàn)二萬(wàn)三萬(wàn)”。

刻子：指同一花色中，3張相同的牌，如“一萬(wàn)一萬(wàn)一萬(wàn)”。

對(duì)子：指同一花色中，2張相同的牌，如“一萬(wàn)一萬(wàn)”。

摸牌：玩家從牌墻中摸1張牌。

出牌：玩家從手牌中選擇1張打出。

吃牌：當(dāng)上家打出的1張牌和自己手牌中的2張牌構(gòu)成順子時(shí)，則可進(jìn)行吃牌操作。

碰牌：其他玩家打出的1張牌和自己手牌中的2張牌相同，則可以進(jìn)行碰牌操作。

明杠：指其他玩家打出的1張牌和自己手牌中的3張牌相同，則可以進(jìn)行明杠操作。

暗杠：指自己手中有4張相同的牌，則可以進(jìn)行暗杠操作。

補(bǔ)杠：指自己手牌中有1張和自己已經(jīng)碰過(guò)的牌相同，則可以進(jìn)行補(bǔ)杠操作。當(dāng)牌墻中有剩余牌時(shí)玩家可以進(jìn)行杠牌，玩家摸完牌墻最后1張牌不能杠牌。

和牌：分為點(diǎn)炮、自摸、和搶杠胡，點(diǎn)炮是指其他玩家打出某張牌結(jié)合我方的手牌組成和牌牌型，自摸是指自己摸牌后的牌型為和牌牌型，搶杠胡是指其他玩家補(bǔ)杠的某張牌結(jié)合我方手牌組成和牌牌型，和牌牌型通常是An+B的格式，A為順子或刻子，B為對(duì)子，此外還包括七對(duì)(7個(gè)對(duì)子)和牌方式。

聽(tīng)牌：當(dāng)玩家手牌打出某張牌后，還差1張牌就可以和牌時(shí)，此時(shí)的手牌是聽(tīng)牌狀態(tài)。玩家可選擇是否進(jìn)行報(bào)聽(tīng)操作。報(bào)聽(tīng)后，雖然可以直接獲得分?jǐn)?shù)獎(jiǎng)勵(lì)，但是此后不可吃、碰操作，后續(xù)摸什么牌就打什么牌，直到場(chǎng)上胡的那張牌出現(xiàn)，才可進(jìn)行和牌操作。且在不影響原來(lái)聽(tīng)的牌的情況下，當(dāng)場(chǎng)上有合法的杠牌出現(xiàn)時(shí)，可以選擇進(jìn)行杠牌操作。

開(kāi)局時(shí)4位玩家分東南西北入座，每人起手摸13張牌，莊(東風(fēng)位置)玩家起手多摸1張牌，共計(jì)14張。之后由莊家位玩家開(kāi)始按逆時(shí)針出牌操作，行牌過(guò)程中可進(jìn)行摸牌、出牌、吃牌、碰牌、杠牌、報(bào)聽(tīng)和和牌操作。其中，吃牌、碰牌、杠牌、報(bào)聽(tīng)和和牌都可獲得直接收益。且同一時(shí)刻可能會(huì)出現(xiàn)多種決策動(dòng)作，各動(dòng)作的優(yōu)先級(jí)為：和牌>杠牌>碰牌>吃牌。當(dāng)有玩家成功和牌或牌墻中的牌出完時(shí)，牌局結(jié)束，根據(jù)玩家動(dòng)作以及和牌牌型的番種，統(tǒng)計(jì)各玩家的總分，麻將游戲番種如表1所示。

表1 麻將游戲番種

2 多重優(yōu)先經(jīng)驗(yàn)值的設(shè)計(jì)

由于大眾麻將真人打牌數(shù)據(jù)有限，目前主要采用遷移學(xué)習(xí)[12-13]和深度強(qiáng)化學(xué)習(xí)的方法來(lái)進(jìn)行研究，但在樣本的使用上，存在兩個(gè)問(wèn)題：

1) 經(jīng)驗(yàn)樣本存在時(shí)序相關(guān)的特點(diǎn)，不符合獨(dú)立同分布的假設(shè),因此網(wǎng)絡(luò)模型很難穩(wěn)定地去學(xué)習(xí)。

2) 經(jīng)驗(yàn)樣本被利用一次后就被丟棄，樣本利用率差。

為解決上述問(wèn)題，將經(jīng)驗(yàn)樣本存入經(jīng)驗(yàn)池，從經(jīng)驗(yàn)池取出均勻采樣用于訓(xùn)練的方法，但是這樣做會(huì)導(dǎo)致經(jīng)驗(yàn)樣本浪費(fèi)，效率也低。為了提高經(jīng)驗(yàn)樣本(Si,a,r,Si+1)的利用率，對(duì)重要的經(jīng)驗(yàn)重復(fù)利用，本文綜合考慮經(jīng)驗(yàn)樣本中局面Si的復(fù)雜程度D(Si)、時(shí)間差分誤差δi、動(dòng)作的即時(shí)獎(jiǎng)勵(lì)值ri三個(gè)因素。首先計(jì)算出經(jīng)驗(yàn)樣本中各個(gè)因素的優(yōu)先值概率，然后通過(guò)對(duì)3個(gè)因素的概率值線性加權(quán)，計(jì)算出經(jīng)驗(yàn)樣本的總優(yōu)先概率，概率值越大，被抽取的概率越大。本文通過(guò)提高重要樣本的抽取概率，提高數(shù)據(jù)利用效率，加快網(wǎng)絡(luò)的訓(xùn)練速度。

2.1 基于局面復(fù)雜程度的優(yōu)先級(jí)

結(jié)合大眾麻將游戲的特點(diǎn)，麻將游戲?qū)儆诙嗳瞬┺挠螒颍螒螂[藏信息多，對(duì)手策略隱蔽，出牌不確定性程度高。由于距離和牌近的游戲局面往往比較容易取得勝利，局面相對(duì)簡(jiǎn)單，而距離和牌越遠(yuǎn)的游戲局面不確定性程度大，局面比較復(fù)雜。因此，本文在選擇樣本重要程度時(shí)考慮了不同時(shí)刻局面的復(fù)雜程度，并根據(jù)局面復(fù)雜程度給出優(yōu)先級(jí)。

定義：麻將局面的復(fù)雜程度

一個(gè)局面的復(fù)雜程度為當(dāng)前局面與游戲結(jié)束局面時(shí)的距離。即當(dāng)前麻將局面下玩家替換若干手牌后可以和牌的最小值。

某個(gè)局面Si的復(fù)雜程度D(Si)計(jì)算。本文除了考慮計(jì)算4個(gè)搭子加1個(gè)對(duì)子的所有基本和牌牌型外，還考慮了七對(duì)這種特殊牌型，計(jì)算方法如式(1)所示。

D(Si)=min(D1(Si),D2(Si))

(1)

其中：D1(Si)表示計(jì)算4個(gè)搭子加1個(gè)對(duì)子的基本和牌牌型，計(jì)算方法如式(2)所示。

(2)

其中：m表示手牌中搭子(不相交的刻子數(shù)和順子數(shù))；n表示手牌中不相交的搭子數(shù)(包括兩面搭子、邊張搭子、嵌張搭子和對(duì)子)；p表示除去面子和搭子后手牌中是否還有一對(duì)子。

和牌不僅包括基本胡，還包括七對(duì)這種牌型，計(jì)算如式(3)所示。

D2(Si)=7-q

(3)

其中q表示當(dāng)前局面的手牌中的對(duì)子數(shù)。

樣本中局面復(fù)雜程度的優(yōu)先概率計(jì)算首先通過(guò)式(1)先得到每個(gè)局面復(fù)雜程度大小D(Si)，然后根據(jù)式(5)計(jì)算該時(shí)段局面復(fù)雜程度重要性值Mi，最后通過(guò)式(4)歸一化得出樣本局面復(fù)雜程度的選取概率PD。Mi表示樣本i的復(fù)雜程度對(duì)應(yīng)的數(shù)值大小。相關(guān)定義如下：

(4)

Mi=-e(D(Si)-φ)2+f

(5)

式(5)表示不同時(shí)刻下樣本局面復(fù)雜程度大小，其中，e,φ,f為調(diào)節(jié)參數(shù)，e使得不同復(fù)雜程度優(yōu)先級(jí)間隔平滑，f保證局面復(fù)雜程度對(duì)應(yīng)的重要性值為正，φ使得AI在不同時(shí)間局面復(fù)雜度的優(yōu)先級(jí)不同。起初φ=0，表示局面復(fù)雜程度為0的經(jīng)驗(yàn)樣本概率最大；隨著游戲局?jǐn)?shù)的增加，φ逐漸增大，局面復(fù)雜程度位于(0，φ)之間值的重要性逐漸變小；局面復(fù)雜程度最高為7，所以值位于(φ，7)的樣本重要性逐漸增大，表明隨著學(xué)習(xí)的時(shí)間增加，學(xué)到的局面復(fù)雜程度越來(lái)越大。

2.2 基于立即回報(bào)的優(yōu)先級(jí)

在麻將游戲?qū)謺r(shí)刻t，對(duì)于狀態(tài)St做出了動(dòng)作a，并轉(zhuǎn)移到下一個(gè)狀態(tài)St+1時(shí)，會(huì)獲得的立即回報(bào)為r。回報(bào)的絕對(duì)值大的樣本往往反應(yīng)映AI動(dòng)作過(guò)好或者過(guò)壞，重要程度較高。因此，在選擇樣本重要程度時(shí)考慮動(dòng)作的立即回報(bào)。立即回報(bào)選擇概率如式(6)所示。

(6)

其中：i表示為經(jīng)驗(yàn)樣本中即時(shí)獎(jiǎng)勵(lì)的下標(biāo)；ε是一個(gè)很小的常數(shù)，防止即時(shí)獎(jiǎng)勵(lì)為0的經(jīng)驗(yàn)被抽取到的概率為0。

2.3 基于時(shí)間差分誤差的優(yōu)先級(jí)

在t時(shí)刻，狀態(tài)為St，動(dòng)作為at, AI的狀態(tài)動(dòng)作價(jià)值函數(shù)Q(St,at)與事先預(yù)估的狀態(tài)動(dòng)作價(jià)值函數(shù)Q(St+1,at+1)的差值稱(chēng)為時(shí)間差分誤差。時(shí)間差分誤差越大，表明AI對(duì)該局面動(dòng)作選取越差，越需要學(xué)習(xí)更新。因此，在選擇樣本重要程度時(shí)考慮了樣本時(shí)序差分誤差。時(shí)序差分選擇概率如式(7)—(9)所示。

δt=r+λQ(St+1,at+1)-Q(St,at)

(7)

pi=|δi|+ε

(8)

(9)

其中：λ為衰減率；ε是一個(gè)很小的常數(shù)，防止時(shí)序差分誤差為0的經(jīng)驗(yàn)被抽取到的概率為0。

2.4 樣本多重優(yōu)先級(jí)的計(jì)算方法

綜合考慮局面的復(fù)雜程度、動(dòng)作即時(shí)獎(jiǎng)勵(lì)以及時(shí)間差分誤差，采用線性加權(quán)的方式計(jì)算樣本總優(yōu)先概率值，多重優(yōu)先級(jí)計(jì)算方法如式(10)(11)所示。

(10)

(11)

其中：PTD(i)，PR(i)，PD(i)分別表示第i條經(jīng)驗(yàn)樣本的時(shí)序差分誤差、獎(jiǎng)勵(lì)、復(fù)雜程度概率；a∈[0,1],b∈[0,1],c∈[0,1]為三者的權(quán)重，它們的大小隨時(shí)間的增加而減小。隨著游戲?qū)值脑黾樱珹I對(duì)經(jīng)驗(yàn)的學(xué)習(xí)越來(lái)越不依賴(lài)于這些優(yōu)先經(jīng)驗(yàn)，當(dāng)對(duì)局?jǐn)?shù)目增大時(shí)μj減小。

2.5 降低學(xué)習(xí)率方法

提出的多重優(yōu)先級(jí)回放方法改變了經(jīng)驗(yàn)的抽樣方式，但是它引入了偏差，不利于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練。為此，通過(guò)使用重要性抽樣(importing sample)對(duì)高概率樣本降低學(xué)習(xí)率，以防止過(guò)擬合。

重要性采樣權(quán)重如式(12)所示：

(12)

其中β∈ [0,1]，網(wǎng)絡(luò)剛開(kāi)始訓(xùn)練時(shí)，β設(shè)置較小，隨著網(wǎng)絡(luò)訓(xùn)練β值逐漸增加至1。

2.6 優(yōu)先級(jí)計(jì)算優(yōu)化方法

相比于隨機(jī)經(jīng)驗(yàn)回放，優(yōu)先經(jīng)驗(yàn)回放在計(jì)算經(jīng)驗(yàn)樣本的優(yōu)先級(jí)上需要額外的時(shí)間。所以，本文在經(jīng)驗(yàn)樣本優(yōu)先級(jí)的計(jì)算以及經(jīng)驗(yàn)樣本的抽取上進(jìn)行了時(shí)間優(yōu)化。主要方法包括：

1)當(dāng)一條新經(jīng)驗(yàn)樣本覆蓋經(jīng)驗(yàn)庫(kù)時(shí)，需要重新計(jì)算經(jīng)驗(yàn)庫(kù)中每條經(jīng)驗(yàn)樣本的優(yōu)先級(jí)，此時(shí)經(jīng)驗(yàn)庫(kù)中總局面復(fù)雜程度、總即時(shí)獎(jiǎng)勵(lì)以及總時(shí)序差分誤差不必重新累加，優(yōu)化方法如式(13)所示，其中W表示經(jīng)驗(yàn)庫(kù)中局面復(fù)雜程度、即時(shí)獎(jiǎng)勵(lì)或時(shí)序差分誤差：

W總=W總+W移入-W移除

(13)

2) 當(dāng)計(jì)算出個(gè)樣本的總優(yōu)先級(jí)值時(shí)，常用做法是對(duì)樣本排序后按概率進(jìn)行抽取，這種做法的平均時(shí)間復(fù)雜度為nlog2(n),本文通過(guò)構(gòu)建sum-tree進(jìn)行經(jīng)驗(yàn)樣本的抽取，時(shí)間復(fù)雜度為log2(n),如圖1所示。

圖1 sum-tree示意圖

葉子節(jié)點(diǎn)表示經(jīng)驗(yàn)庫(kù)中樣本的總優(yōu)先級(jí)值，父節(jié)點(diǎn)為子節(jié)點(diǎn)之和，構(gòu)建sum-tree時(shí)，當(dāng)葉子節(jié)點(diǎn)不為2n時(shí)，用0節(jié)點(diǎn)補(bǔ)至2n，自下而上構(gòu)建整棵樹(shù)。節(jié)點(diǎn)旁紅色數(shù)字為節(jié)點(diǎn)標(biāo)號(hào)，葉子結(jié)點(diǎn)下面是他們各自對(duì)應(yīng)的數(shù)值區(qū)間，葉子結(jié)點(diǎn)數(shù)值越大(優(yōu)先級(jí)越高)其區(qū)間長(zhǎng)度就越大，因此從0～11中均勻抽樣一個(gè)數(shù)據(jù)落到這個(gè)區(qū)間內(nèi)的概率也就越大，這就是按照優(yōu)先級(jí)進(jìn)行抽樣的原理，具體抽樣過(guò)程如下:

a) 給定0～根節(jié)點(diǎn)范圍隨機(jī)數(shù)s將根結(jié)點(diǎn)作為父親結(jié)點(diǎn)，遍歷其子節(jié)點(diǎn)；

b) 如果左子節(jié)點(diǎn)大于s，將左子節(jié)點(diǎn)作為父親結(jié)點(diǎn)，遍歷其子節(jié)點(diǎn)；

c) 如果左子結(jié)點(diǎn)數(shù)值小于s，將s減去左子結(jié)點(diǎn)的數(shù)值，選擇右子結(jié)點(diǎn)作為父親結(jié)點(diǎn)，遍歷其子節(jié)點(diǎn)；

d) 直到遍歷的葉子結(jié)點(diǎn)，該葉子結(jié)點(diǎn)的數(shù)值就是優(yōu)先級(jí)，下標(biāo)對(duì)應(yīng)的數(shù)值下標(biāo)，可以從經(jīng)驗(yàn)庫(kù)中找到對(duì)應(yīng)的數(shù)值。

例如，圖1給出隨機(jī)數(shù)8.5，選擇節(jié)點(diǎn)0作為父節(jié)點(diǎn)。8.5與節(jié)點(diǎn)1比較，8小于8.5，得到結(jié)果0.5，將節(jié)點(diǎn)2作為父節(jié)點(diǎn)， 0.5與節(jié)點(diǎn)5比較，0.5小于1，選擇節(jié)點(diǎn)5，所以抽取節(jié)點(diǎn)5代表的經(jīng)驗(yàn)樣本。

3 基于多重優(yōu)先經(jīng)驗(yàn)值的大眾麻將博弈算法實(shí)現(xiàn)

強(qiáng)化學(xué)習(xí)就是一個(gè)智能體(Agent)在狀態(tài)(State)采取行動(dòng)(Action)獲得獎(jiǎng)勵(lì)(Reward)與環(huán)境(Environment)發(fā)生交互并更新的自身循環(huán)過(guò)程。

對(duì)于大眾麻將游戲而言，要訓(xùn)練的AI可以看作一個(gè)智能體，博弈信息可以看作是環(huán)境狀態(tài)，吃、碰、杠、聽(tīng)、胡、棄牌可以看作是行動(dòng)，是否獲勝，以及獲勝的番種可以看作為獎(jiǎng)勵(lì)。博弈過(guò)程會(huì)隨著智能體根據(jù)博弈信息做出策略，而轉(zhuǎn)移到下一個(gè)狀態(tài)，并獲得一定獎(jiǎng)勵(lì)。麻將是一個(gè)四人博弈游戲，在一個(gè)智能體做完動(dòng)作后，需要等其余3名玩家做出回應(yīng)后才能使得環(huán)境狀態(tài)進(jìn)行轉(zhuǎn)移。因此，本文將其他3個(gè)玩家設(shè)置為環(huán)境一部分。采用DDQN(double deep Q-learning)方法結(jié)合優(yōu)先經(jīng)驗(yàn)回放進(jìn)行麻將AI訓(xùn)練。由于麻將數(shù)據(jù)離散，需要對(duì)麻將牌面進(jìn)行表示，以供神經(jīng)網(wǎng)絡(luò)的輸入，牌面表示如圖2所示。訓(xùn)練流程如圖3所示，其中紅色虛線框中多重經(jīng)驗(yàn)回放機(jī)制部分是本文重難點(diǎn)研究的內(nèi)容。算法主要流程見(jiàn)算法1所示。

圖2 牌面表示示意圖

圖3 DDQN算法訓(xùn)練流程框圖

算法1:MPER-DDQN

1 輸入：minibatch大小為k學(xué)習(xí)率為α，折扣系數(shù)γ，回放周期為K，存儲(chǔ)數(shù)據(jù)大小為N，對(duì)局輪數(shù)M，單局對(duì)局時(shí)間T,探索率ε

2 輸出：預(yù)測(cè)網(wǎng)絡(luò)Q參數(shù)ε

4 for episode = 1 toMdo

5 fort= 1 toTdo

觀察初始狀態(tài)S0, 生成隨機(jī)數(shù)n,n∈[0,1];

6 ifn<ε

選擇隨機(jī)動(dòng)作at

7 else

at=maxaQ*(St,a;θ)

8 end

9 得到該動(dòng)作獎(jiǎng)勵(lì)rt,以及下一狀態(tài)St+1，并將經(jīng)驗(yàn)樣本(St,at,rt,St+1)存儲(chǔ)在經(jīng)驗(yàn)庫(kù)H中;

10 forj= 1 toNdo

11 令yj=

//a為動(dòng)作集，t′為時(shí)間步

12 計(jì)算δj=yj-Q(St′-at′);

13 計(jì)算P(j)D,P(j)r,P(j)TD;

14 計(jì)算優(yōu)先級(jí)

15 iftmodK== 0 then

//間隔K步回放一次

fori= 1 tokdo

損失函數(shù)Loss:

計(jì)算樣本的重要性權(quán)重ωj;

計(jì)算權(quán)重Δ←Δ+ωj·δj▽?duì)?St″,at″)

16 end for

17 更新預(yù)測(cè)網(wǎng)絡(luò)參數(shù)θ←θ+α·Δ

18 更新有先經(jīng)驗(yàn)權(quán)重系數(shù)μi=μi*μ

19 一段時(shí)間θ-←θ;

20 end if

21 end for

22 end for

23end for

在訓(xùn)練過(guò)程中，DDQN使用預(yù)測(cè)網(wǎng)絡(luò)計(jì)算下一個(gè)狀態(tài)下的對(duì)應(yīng)各個(gè)打牌動(dòng)作的Q值，并記錄其下標(biāo)，然后使用目標(biāo)網(wǎng)絡(luò)計(jì)算下一個(gè)狀態(tài)里面的對(duì)應(yīng)各個(gè)打牌動(dòng)作，將預(yù)測(cè)網(wǎng)絡(luò)預(yù)測(cè)的打牌動(dòng)作索引對(duì)應(yīng)的Q值作為目標(biāo)Q值，避免了選取預(yù)測(cè)網(wǎng)絡(luò)最大Q值的過(guò)程，從而一定程度上避免了對(duì)當(dāng)前牌局下，對(duì)某個(gè)打牌動(dòng)作過(guò)高Q值估計(jì)的問(wèn)題，提高了訓(xùn)練的穩(wěn)定性。Double DQN與DQN相同的是他們都有被稱(chēng)之為預(yù)測(cè)網(wǎng)絡(luò)與目標(biāo)網(wǎng)絡(luò)的兩個(gè)網(wǎng)絡(luò)，只是在實(shí)作過(guò)程中，標(biāo)簽的計(jì)算過(guò)程做了修正，如式(14)。

(14)

yj表示模型訓(xùn)練時(shí)得到的Q值。如果當(dāng)前一輪游戲結(jié)束，則rj值為最終Q值；否則，Q值不僅包含即時(shí)獎(jiǎng)勵(lì)rj，也包含預(yù)測(cè)網(wǎng)絡(luò)對(duì)下一牌局狀態(tài)預(yù)測(cè)的最大Q值。

與深度學(xué)習(xí)不同的是，DDQN輸出的不再是預(yù)測(cè)出牌的概率，而是對(duì)于當(dāng)前狀態(tài)下每個(gè)動(dòng)作的Q值，選取Q值最大的動(dòng)作進(jìn)行執(zhí)行，進(jìn)而利用eval網(wǎng)絡(luò)得到最大Q值打牌策略的下標(biāo)，然后利用target網(wǎng)絡(luò)計(jì)算下一狀態(tài)下執(zhí)行該動(dòng)作的實(shí)際Q值，進(jìn)而計(jì)算當(dāng)前局面下，執(zhí)行該打牌動(dòng)作后的收益，與預(yù)估收益的均方誤差，作為DDQN的損失函數(shù)為：

(15)

4 實(shí)驗(yàn)平臺(tái)搭建及實(shí)驗(yàn)結(jié)果

4.1 實(shí)驗(yàn)平臺(tái)的搭建

在對(duì)智能體交互的環(huán)境進(jìn)行搭建的文獻(xiàn)中，OpenAI的gym[14]以及RLcard[15]給出了很好的范例，因此，本文借鑒其對(duì)智能體環(huán)境的搭建方式，并結(jié)合大眾游戲自身的特點(diǎn)，建立一套大眾麻將自博弈環(huán)境。其自博弈流程如下：

算法2大眾麻將自博弈流程

1 輸入：初始化玩家手牌hand，莊家位置dealer，該回合玩家p

2 輸出：博弈結(jié)果

3p= 莊家；

4 while True do

5 ifp已經(jīng)聽(tīng)牌 then

6 ifp和牌合法

7 直接胡

8 else ifp杠牌合法 then

9 獲取p的動(dòng)作內(nèi)容

10 else

11 打出剛摸得牌

12 end if

13 else

14 驗(yàn)證p動(dòng)作action合法性；

15 if action == 和牌 then

16 游戲結(jié)束計(jì)算得分

17 else if action == 杠牌 then

18 if 補(bǔ)杠 then

19 if 搶杠胡(判定動(dòng)作是否合法)then

20 游戲結(jié)束

21 end if

22 end if

23 else if action == 棄牌 or 聽(tīng)牌 then

24 獲取可行動(dòng)作玩家動(dòng)作；

25 判定優(yōu)先級(jí)

26 Continue;

27 if 剩余牌數(shù)目大于0 then

28 摸一張(吃碰后不能摸);

29 else

30 游戲結(jié)束

31 end if

32 end if

33end if

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

在2080Ti服務(wù)器進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)的軟件環(huán)境配置為：Windows 10，python 3.7，pytorch 1.4等，實(shí)驗(yàn)超參數(shù)如表2所示。

表2 超參數(shù)設(shè)置

為了驗(yàn)證本文方法的有效性，將提出的多重優(yōu)先經(jīng)驗(yàn)回放大眾麻將程序 MPER-DDQN與基于隨機(jī)經(jīng)驗(yàn)回放麻將程序ER-DDQN各自博弈8萬(wàn)局，設(shè)置的對(duì)手麻將AI均為采用深度學(xué)習(xí)編寫(xiě)的2020年亞軍程序[16]。由于麻將游戲?qū)殖跏际峙撇煌烤钟螒蚶塾?jì)回報(bào)差異較大，故統(tǒng)計(jì)了每百輪平均獎(jiǎng)勵(lì)作為AI對(duì)局中的表現(xiàn)。實(shí)驗(yàn)過(guò)程中2個(gè)麻將AI程序?qū)种蝎@得的累計(jì)回報(bào)如圖4所示，橫坐標(biāo)為AI對(duì)局輪數(shù)，縱坐標(biāo)為對(duì)局中獲得的累計(jì)獎(jiǎng)勵(lì)。AI對(duì)局消耗的時(shí)間如圖5所示，其中橫坐標(biāo)表現(xiàn)對(duì)局時(shí)間，縱坐標(biāo)為對(duì)局所用時(shí)間。

圖4 2種方法AI對(duì)局中累計(jì)回報(bào)

圖5 2種方法AI對(duì)局中消耗的時(shí)間

從圖4中可以看出，采用本文多重優(yōu)先經(jīng)驗(yàn)回放的方法AI在39 000輪對(duì)局可以達(dá)到收斂，而隨機(jī)經(jīng)驗(yàn)回放則大約需要61 000局。從圖5可以看出，優(yōu)先經(jīng)驗(yàn)回放方法在8萬(wàn)個(gè)對(duì)局中總用時(shí)高于隨機(jī)經(jīng)驗(yàn)回放，分析其原因?yàn)橛?jì)算優(yōu)先級(jí)需要花費(fèi)額外的時(shí)間。從實(shí)驗(yàn)數(shù)據(jù)得出，優(yōu)先經(jīng)驗(yàn)回放對(duì)局39 000輪收斂大約需要615 min，而隨機(jī)經(jīng)驗(yàn)回放則需要794 min。由此得出，本文所提出的方法將麻將AI的訓(xùn)練速度上提升了22.5%。

5 結(jié)論

通過(guò)分析麻將游戲的特點(diǎn)，提出了多重優(yōu)先經(jīng)驗(yàn)回放機(jī)制，給出了麻將游戲局面復(fù)雜程度的定義，通過(guò)時(shí)序差分誤差、獎(jiǎng)勵(lì)以及局面復(fù)雜程度3個(gè)標(biāo)準(zhǔn)對(duì)經(jīng)驗(yàn)樣本優(yōu)先值進(jìn)行計(jì)算，并在筆者搭建的麻將自博弈平臺(tái)進(jìn)行對(duì)比實(shí)驗(yàn)。與傳統(tǒng)的隨機(jī)經(jīng)驗(yàn)回放算法相比，麻將AI訓(xùn)練速度與穩(wěn)定性大幅度提升。下一步，將在改進(jìn)模型訓(xùn)練速度的基礎(chǔ)上研究將麻將AI決策水平進(jìn)一步提高。