計(jì)算機(jī)博弈算法在黑白棋中的應(yīng)用

摘? 要：計(jì)算機(jī)博弈是人工智能的重要分支之一，文章對(duì)人工智能算法黑白棋中的應(yīng)用進(jìn)行了研究。首先介紹了計(jì)算機(jī)博弈中的經(jīng)典黑白棋算法，然后介紹深度強(qiáng)化學(xué)習(xí)中兩種典型的時(shí)間差分算法的定義和實(shí)現(xiàn)過(guò)程，以及兩者的區(qū)別和聯(lián)系。最后評(píng)測(cè)蒙特卡洛樹(shù)搜索算法、Q學(xué)習(xí)算法和SARSA算法三種算法在黑白棋實(shí)際應(yīng)用的表現(xiàn)，以及后續(xù)改進(jìn)的方向。

關(guān)鍵詞：蒙特卡洛樹(shù)搜索;深度強(qiáng)化學(xué)習(xí);馬爾科夫決策過(guò)程;Q學(xué)習(xí);SARSA

中圖分類(lèi)號(hào)：TP181? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2021）17-0073-06

Abstract： Computer game is one of the important branches of artificial intelligence. This paper studies the application of artificial intelligence algorithm in black and white chess. This paper first introduces the classical black and white chess algorithm in computer game， and then introduces the definition and implementation process of two typical time difference algorithms in deep reinforcement learning， as well as their differences and relations. Finally， evaluate the performance of MCTS algorithm， Q learning algorithm and SARSA algorithm in the practical application of black and white chess， as well as the direction of subsequent improvement.

Keywords： MCTS; deep reinforcement learning; Markov decision process; Q learning; SARSA

0? 引? 言

計(jì)算機(jī)博弈是人工智能的分支領(lǐng)域之一。它結(jié)合了計(jì)算機(jī)算法與博弈論，成為人工智能算法應(yīng)用在其他領(lǐng)域前的最佳驗(yàn)證領(lǐng)域，被譽(yù)為是人工智能的果蠅[1]。傳統(tǒng)的計(jì)算機(jī)博弈算法一般基于樹(shù)搜索算法。它是一種窮舉算法，采用深度優(yōu)先的方式搜索整棵多叉樹(shù)。假定樹(shù)的分支（也稱(chēng)為寬度）是w，深度是d，那么它的時(shí)間復(fù)雜度為wd。指數(shù)級(jí)別的復(fù)雜度在實(shí)踐中由于計(jì)算結(jié)果的時(shí)間可能達(dá)到好幾天甚至好幾個(gè)月，很難得到應(yīng)用。

科學(xué)家針對(duì)如何在寬度和深度這兩方面去減少搜索時(shí)間這一問(wèn)題提出了很多有效的解決方案。第一種是減少搜索寬度。信息論之父香農(nóng)（Claude shannon）于1950年提出的策略為有選擇性地遍歷樹(shù)的分支。它可以顯著地減少搜索次數(shù)，副作用是會(huì)丟失有效的分支路線。

1958年Newell等提出了一種可有效減少搜索寬度的算法：α-β剪枝（alpha-beta pruning）算法。相比香農(nóng)教授的隨機(jī)選擇分支算法，α-β剪枝算法是一種無(wú)損選擇算法。

第二種有效減少搜索深度。普遍采用的策略是棋局評(píng)估函數(shù)。所謂評(píng)估函數(shù)就是一種判斷當(dāng)面局面哪一方領(lǐng)先以及具體領(lǐng)先多少的函數(shù)[2]。

這兩項(xiàng)技術(shù)的組合成為了計(jì)算機(jī)博弈游戲人工智能的兩大支柱。在目前計(jì)算機(jī)圍棋的最強(qiáng)者、谷歌旗下開(kāi)發(fā)的軟件產(chǎn)品AlphaGo在下棋時(shí)就配置兩臺(tái)計(jì)算機(jī)，一臺(tái)用于α-β剪枝，一臺(tái)用于棋局評(píng)估。

計(jì)算機(jī)博弈應(yīng)用于黑白棋早在1970年由日本學(xué)者開(kāi)發(fā)出來(lái)。經(jīng)過(guò)幾十年的發(fā)展，目前最好的計(jì)算機(jī)黑白棋程序以WZebra等軟件為代表。它們基于對(duì)游戲的透徹分析，精心打造了一套高水平的規(guī)則，采用非常復(fù)雜的搜索技術(shù)。 這些程序通常結(jié)合使用了強(qiáng)大的經(jīng)過(guò)專(zhuān)家標(biāo)記過(guò)的游戲數(shù)據(jù)集的來(lái)學(xué)習(xí)和進(jìn)化。之前主流的棋局評(píng)估函數(shù)多采用靜態(tài)評(píng)估的方式。直到1990年的計(jì)算機(jī)黑白棋世界冠軍BILL3.0問(wèn)世。它由當(dāng)時(shí)在卡內(nèi)基梅隆大學(xué)的李開(kāi)復(fù)等開(kāi)發(fā)，它開(kāi)創(chuàng)性地采用了基于貝葉斯方法的動(dòng)態(tài)評(píng)估函數(shù)，使得BILL3.0棋力成為當(dāng)時(shí)的世界冠軍[3]。

本論文介紹將深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)相結(jié)合的棋局評(píng)估函數(shù)，主要的策略是通過(guò)分析并優(yōu)化評(píng)估函數(shù)參數(shù)，從而減少搜索深度，提高計(jì)算機(jī)對(duì)整體局面的判斷力，從而在更短的單位時(shí)間內(nèi)做出更有效的決策。

1? 黑白棋簡(jiǎn)介

黑白棋又稱(chēng)奧賽羅棋。它是一種對(duì)弈的棋類(lèi)游戲。采用類(lèi)似于圍棋的棋盤(pán)和棋子。棋盤(pán)大小為8行8列。棋子分為黑白兩色，黑棋先走，棋子放在方格中，輪流走子，每次走子都必須要俘虜并翻轉(zhuǎn)對(duì)方的棋子成為自己方棋子（簡(jiǎn)稱(chēng)吃子），如果輪到己方時(shí)，但是沒(méi)有能吃子的落子點(diǎn)，則要棄權(quán)一次。雙方都沒(méi)有落子點(diǎn)時(shí)則游戲結(jié)束。最后以占據(jù)地盤(pán)多者為勝。

俘虜對(duì)方棋子規(guī)則是指對(duì)方棋子被自己的另外一個(gè)棋子同一條線之間的所有棋子都被俘虜并翻轉(zhuǎn)成為自己的棋子。圖1為起始棋局，X點(diǎn)為黑棋下一步合法的可選落子點(diǎn)，在黑白棋中稱(chēng)為行動(dòng)力。

圖1（b）圖為黑子下在了d3位置后，d4位置的白棋變成了黑棋，因?yàn)閐3和d5的黑棋連成了一條線。這個(gè)連線中間可以間隔1個(gè)或者多個(gè)對(duì)方的連續(xù)棋子，不能有空位。

2? 經(jīng)典黑白棋算法

由于黑白棋的規(guī)則簡(jiǎn)單，算法復(fù)雜度中等，它一直是計(jì)算機(jī)科學(xué)家在人工智能算法中鐘愛(ài)的研究對(duì)象，研究流行度僅次于國(guó)際象棋。計(jì)算機(jī)黑白棋程序中常見(jiàn)的算法是樹(shù)搜索算法。

2.1? 樹(shù)搜索算法

樹(shù)搜索算法是一類(lèi)計(jì)算機(jī)中常用的搜索策略，它們采用循環(huán)遍歷可能的決策路徑，并找出最佳的決策路線，其中有幾種比較適合在博弈類(lèi)游戲中應(yīng)用。首先就是一種稱(chēng)為極小極大搜索算法（minimax search algorithm， MIN/MAX）。極小極大搜索算法是在對(duì)弈過(guò)程中假定對(duì)手和我們一樣聰明，采用的策略總是使己方利益最大化，反之對(duì)手利益最小化。該算法非常適合于信息透明的零和游戲。黑白棋的最終目標(biāo)是在64個(gè)棋盤(pán)格子中盡可能使己方棋子數(shù)量最大。所以黑白棋可以應(yīng)用極小極大搜索算法。當(dāng)我們采用某種最優(yōu)策略，假定對(duì)手也采用最優(yōu)的策略去應(yīng)對(duì)。對(duì)于黑白棋類(lèi)游戲，會(huì)產(chǎn)生相應(yīng)的游戲樹(shù)。樹(shù)是具有寬度和深度的二維結(jié)構(gòu)。寬度表示當(dāng)前回合中可下的位置，深度表示當(dāng)前回合某個(gè)可能選擇到最終的游戲狀態(tài)的回合數(shù)量。并且每一個(gè)回合寬度（用w表示）和深度（用d表示）都是會(huì)變化的。游戲中可能對(duì)局的數(shù)量可以用公式wd來(lái)表示。其中的寬度和深度都是平均值。根據(jù)黑白棋規(guī)則限定，每個(gè)落子點(diǎn)都必須要吃子，那么它的平均每回合寬度在一個(gè)合理的范圍，有研究表明，黑白棋到中盤(pán)后平均寬度w約為10[4]。一局棋最多需要32回合結(jié)束，預(yù)估此樹(shù)搜索的最大尺寸1032。而在實(shí)際運(yùn)行中根據(jù)不同的計(jì)算精度需要，采用三個(gè)深度級(jí)別，分別為最小、中等和最大。最小一般預(yù)估6步可以達(dá)到較合理的結(jié)果。中等深度為12步，最大平均深度約為24步。如表1所示，以每秒1千萬(wàn)個(gè)局面的速度進(jìn)行計(jì)算，僅僅計(jì)算中等深度每步需要花費(fèi)166分鐘，沒(méi)有實(shí)戰(zhàn)價(jià)值。由此必須要采用更加有效的搜索算法來(lái)進(jìn)行優(yōu)化。消除樹(shù)的部分分支，這種方式稱(chēng)為剪枝。最有名的剪枝算法稱(chēng)為α-β剪枝算法。

2.2? α-β剪枝算法

采用α-β剪枝算法，可以顯著減少搜索次數(shù)，研究表明中盤(pán)向前搜索12步，平均每步棋的次數(shù)為1億數(shù)量級(jí)，耗時(shí)約10秒。如果減少為搜索10步，則在1秒內(nèi)可以完成搜索。

α-β剪枝算法是基于極小極大化算法（MIN/MAX算法），通過(guò)優(yōu)化來(lái)減少不必要搜索的剪枝方案，它是一種無(wú)損選擇算法。α-β剪枝算法在規(guī)模較大的搜索樹(shù)中效果非常顯著，以井字棋游戲?yàn)槔?，從開(kāi)局到終局進(jìn)行搜索，生成的節(jié)點(diǎn)數(shù)量如表2所示[5]。從表2可以看出，采用α-β剪枝算法產(chǎn)生的節(jié)點(diǎn)數(shù)量約為僅僅使用MIN/MAX算法的1/15，采用優(yōu)化算法后會(huì)有更大的提升。

2.3? 棋局評(píng)估函數(shù)

棋局評(píng)估函數(shù)是根據(jù)當(dāng)前的局面來(lái)進(jìn)行評(píng)估每一個(gè)備選位置的價(jià)值函數(shù)。圖2為wZebra軟件提供的評(píng)估結(jié)果。其中圖2（a）為開(kāi)局。（D3，C4，F(xiàn)5，E6）四個(gè)備選位置價(jià)值相同。圖2（b）為對(duì)白棋的下一步評(píng)估F4為-6表示負(fù)面結(jié)果，如果白下F4，則會(huì)對(duì)對(duì)手黑棋有利，黑棋得利為6，如圖2（c）所示。白棋最佳的選擇是從D6和F6任選一處。

評(píng)估函數(shù)的定義成為要解決的重點(diǎn)。首先采用專(zhuān)家法，根據(jù)世界頂級(jí)人類(lèi)黑白棋棋手的總結(jié)，常見(jiàn)的評(píng)估和判斷局面的幾個(gè)變量為：

（1）行動(dòng)力（MOBILITY）：由于黑白棋的規(guī)則要求每一步都必須吃掉對(duì)方的至少1個(gè)子，否則棄權(quán)1次。所以當(dāng)前可選的位置是很容易計(jì)算的。圖2中3個(gè)局面的行動(dòng)力就分別是4（黑棋），3（白棋），5（黑棋）。

（2）潛在行動(dòng)力（Potential MOBILITY）：所謂潛在行動(dòng)力是指緊鄰對(duì)手的空白位置的數(shù)量。圖2中3個(gè)局面的潛在行動(dòng)力就分別是10（黑棋），13（白棋），9（黑棋）。潛在行動(dòng)力可能轉(zhuǎn)換成行動(dòng)力，并且包含了所有的行動(dòng)力。它的影響因子要小于行動(dòng)力。

（3）穩(wěn)定子與邊緣子：首先是穩(wěn)定子的概念。位于角的棋子不可能被翻轉(zhuǎn)，因?yàn)樗肋h(yuǎn)也不會(huì)被對(duì)手的兩個(gè)棋子夾住，那么四個(gè)角就是典型的穩(wěn)定子[6]。除此之外，一旦有棋子占角，相鄰的同色棋子通常也變成了穩(wěn)定子。然后有邊緣子集合的概念。由于每步棋都必須至少翻轉(zhuǎn)對(duì)手一個(gè)棋子，因此對(duì)手與空位相鄰的棋子越多，你可下的棋就越多，因此你的行動(dòng)力也就越好。相反地，如果己方棋子很少與空位相鄰，那么你的對(duì)手就只有很少的棋可下。與空位相鄰的棋子就叫作邊緣子（frontier disc）。邊緣子的集合就叫作邊界（frontier）。由以上分析，要盡量增加穩(wěn)定子，減少邊緣子的數(shù)量。

根據(jù)以上的概念，綜合使用參數(shù)可以使用加權(quán)線性和，用來(lái)評(píng)估每個(gè)位置的價(jià)值。

可以使用如下的第一種評(píng)價(jià)函數(shù)：

f1=（a-b）w+S1-S2

以上公式a表示自己的行動(dòng)力，b表示對(duì)方的行動(dòng)力，w表示權(quán)重，S1表示自己的穩(wěn)定子的數(shù)量，S2表示對(duì)方的穩(wěn)定子數(shù)量。作為對(duì)比，我們采用第二種評(píng)價(jià)函數(shù)：

f2=（a-b）w+C1-C2

其中C1表示自己的棋子數(shù)，C2表示對(duì)手的棋子數(shù)。這兩種評(píng)價(jià)函數(shù)經(jīng)過(guò)測(cè)試f1函數(shù)的勝率表現(xiàn)要明顯好于f2。并且f1的水平已經(jīng)可以達(dá)到相當(dāng)高的水準(zhǔn)。

2.4? 蒙特卡洛樹(shù)搜索

蒙特卡洛樹(shù)搜索（Monte carlo Tree Search，MCTS）是蒙特卡洛算法族的一個(gè)，蒙特卡洛算法可以利用隨機(jī)性來(lái)分析極其復(fù)雜的情況。蒙特卡洛樹(shù)搜索算法是通過(guò)將蒙特卡洛方法與多叉樹(shù)搜索進(jìn)行結(jié)合的算法，兼顧了蒙特卡洛方法隨機(jī)模擬的通用性以及多叉樹(shù)的廣度和深度搜索，能夠有效解決決策優(yōu)化問(wèn)題[7]。蒙特卡洛搜索樹(shù)是基于蒙特卡洛方法且通過(guò)不斷模擬迭代所建立的一顆搜索樹(shù)，迭代的終止條件通常是預(yù)先設(shè)定的時(shí)間或者條件約束。得到最佳的搜索結(jié)果后搜索就會(huì)停止，搜索樹(shù)中的每個(gè)終止節(jié)點(diǎn)就是達(dá)到最佳決策過(guò)程中的每個(gè)狀態(tài)[8]。MCTS要評(píng)估某個(gè)位置價(jià)值，采用隨機(jī)對(duì)弈來(lái)推演最后得出當(dāng)前這個(gè)位置是否有利。黑白棋的每輪的合法位置就是等價(jià)與它的行動(dòng)力。MCTS算法的每一回合的計(jì)算包含如下3個(gè)步驟：

（1）將新的棋局添加到MCTS樹(shù)中。

（2）從這個(gè)棋局開(kāi)始模擬從可選合法位置中隨機(jī)選一個(gè)位置對(duì)局。

（3）根據(jù)對(duì)局結(jié)果更新樹(shù)節(jié)點(diǎn)的統(tǒng)計(jì)數(shù)據(jù)。

在一定的時(shí)間內(nèi)重復(fù)這個(gè)計(jì)算過(guò)程，最后根據(jù)統(tǒng)計(jì)數(shù)據(jù)得到最優(yōu)結(jié)果動(dòng)作。

在每個(gè)回合中可使用的時(shí)間是有限的，針對(duì)如何在有限的時(shí)間內(nèi)分配有限的預(yù)算這一問(wèn)題，比較好的策略稱(chēng)為搜索樹(shù)置信區(qū)間上界公式（upper confidence bound for trees，UCT）[9]。

該公式定義為：

UCT=w+c

其中w是計(jì)算獲勝百分率，N表示推演的總數(shù)。n表示當(dāng)前節(jié)點(diǎn)開(kāi)始的所有推演數(shù)。參數(shù)c表示權(quán)衡深入探索和廣泛探索時(shí)之間的權(quán)重。UCT公式為每一個(gè)節(jié)點(diǎn)提供分?jǐn)?shù)，具有最高UCT分?jǐn)?shù)的節(jié)點(diǎn)，可以作為下一次推演的開(kāi)始點(diǎn)。

3? 深度強(qiáng)化學(xué)習(xí)的應(yīng)用

深度強(qiáng)化學(xué)習(xí)（deep reinforcement learning， DRL）是一種結(jié)合深度神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)兩種方法的融合算法。

深度學(xué)習(xí)利用深度神經(jīng)網(wǎng)絡(luò)的優(yōu)勢(shì)，對(duì)輸入數(shù)據(jù)具有良好的感知能力，但是決策能力不足。而強(qiáng)化學(xué)習(xí)感知能力不足但具有良好的決策能力，由此將兩者優(yōu)勢(shì)結(jié)合可以用于解決智能體在復(fù)雜高維狀態(tài)空間中的感知決策問(wèn)題[10]。

強(qiáng)化學(xué)習(xí)是心理學(xué)和行為學(xué)家通過(guò)研究發(fā)現(xiàn)自然界生物體（包括人類(lèi)）能夠通過(guò)不斷地試錯(cuò)從而能適應(yīng)環(huán)境的變化。通過(guò)最大化累積獎(jiǎng)勵(lì)的方式來(lái)學(xué)習(xí)到最優(yōu)策略。

強(qiáng)化學(xué)習(xí)是學(xué)習(xí)器（又稱(chēng)為代理，agent）學(xué)習(xí)如何在環(huán)境中動(dòng)作（action），環(huán)境中僅有的反饋由獎(jiǎng)勵(lì)信號(hào)組成。代理的目標(biāo)是長(zhǎng)期最大化從環(huán)境獲得的獎(jiǎng)勵(lì)信號(hào)。

強(qiáng)化學(xué)習(xí)問(wèn)題可以通過(guò)馬爾科夫決策過(guò)程（Markov Decision Processes， MDP）的框架來(lái)描述。

3.1? 馬爾科夫決策過(guò)程

MDP是決策理論規(guī)劃、強(qiáng)化學(xué)習(xí)及隨機(jī)過(guò)程中一種直觀和基本的構(gòu)造模型。一個(gè)馬爾科夫決策過(guò)程包括狀態(tài)、動(dòng)作、轉(zhuǎn)換函數(shù)、獎(jiǎng)勵(lì)方程等。

3.1.1? 狀態(tài)

對(duì)于建立模型的問(wèn)題來(lái)說(shuō)，狀態(tài)是所有信息的唯一特征。例如，在黑白棋中一個(gè)完整的棋盤(pán)由8行8列的64個(gè)方格組成，這是其中一種狀態(tài)。集合S可以用{s1，…，SN}來(lái)定義一個(gè)規(guī)模為N的有限集合。

3.1.2? 動(dòng)作

動(dòng)作集合A通過(guò)有限集合{a1，…，AK}來(lái)定義大小為K的動(dòng)作空間。默認(rèn)所有動(dòng)作都能對(duì)應(yīng)于一個(gè)狀態(tài)，對(duì)于s∈S，A（s）=A。

3.1.3? 轉(zhuǎn)換函數(shù)

通過(guò)將動(dòng)作a∈A運(yùn)用于狀態(tài)s∈S，可以得到一個(gè)轉(zhuǎn)換集合的概率分布，學(xué)習(xí)系統(tǒng)就能完成從當(dāng)前狀態(tài)s到下一個(gè)狀態(tài)s'的轉(zhuǎn)換，轉(zhuǎn)換函數(shù)T的定義為S×A×S→[0，1]。表示含義為當(dāng)作用于狀態(tài)s的動(dòng)作執(zhí)行后，它的概率為T(mén)（s，a，s'）。如果一個(gè)動(dòng)作的結(jié)果不依賴(lài)以前的動(dòng)作和狀態(tài)，而僅僅由當(dāng)前的狀態(tài)決定，那么這個(gè)系統(tǒng)就具有馬爾科夫特性。它可以用以下公式表示：

P（St+1|st，at，st-1，at-1，…）=P（St+1|st，at）=T（st，at，st+1）

馬爾科夫動(dòng)態(tài)的核心思想是當(dāng)前的狀態(tài)s可以提供所有的信息來(lái)為將來(lái)做出最優(yōu)決策。

3.1.4? 獎(jiǎng)勵(lì)方程

獎(jiǎng)勵(lì)方程式指在一個(gè)狀態(tài)中完成一個(gè)動(dòng)作后的獎(jiǎng)勵(lì)。狀態(tài)獎(jiǎng)勵(lì)方程可以定義為R：S→R。獎(jiǎng)勵(lì)方程是馬爾科夫決策過(guò)程中最重要的部分，因?yàn)楠?jiǎng)勵(lì)方程定義了學(xué)習(xí)的最終目標(biāo)[11]。在黑白棋游戲中，獎(jiǎng)勵(lì)值可以定義成最終獲得比對(duì)手多的棋子數(shù)量。

價(jià)值函數(shù)用來(lái)估計(jì)在某個(gè)特定的狀態(tài)下執(zhí)行某個(gè)動(dòng)作所能獲得的收益值。

在策略π下的狀態(tài)S的值，表示為V π（S），是預(yù)期收益?？梢员硎緸槿缦鹿剑?/p>

3.2? 時(shí)間差分學(xué)習(xí)算法

Q學(xué)習(xí)是基于離線策略的時(shí)間差分算法，時(shí)間差分算法是Sutton在1988年提出的，該算法綜合了蒙特卡洛算法算和動(dòng)態(tài)規(guī)劃算法的優(yōu)點(diǎn)。該算法有兩個(gè)優(yōu)點(diǎn)，一是可以無(wú)須已知模型動(dòng)態(tài)，第二是無(wú)須等到情景結(jié)束是才能估計(jì)值函數(shù)[12]。

狀態(tài)-行為-獎(jiǎng)勵(lì)-狀態(tài)-行為（SARSA）是一種在線時(shí)間差分控制算法。根據(jù)下面的公式來(lái)更新值：

這個(gè)公式看起來(lái)和Q學(xué)習(xí)公式非常相似，它們都是通過(guò)貪婪策略來(lái)選擇行為，主要的區(qū)別在于更新Q值時(shí)，Q學(xué)習(xí)只簡(jiǎn)單地選取具有最大值的行為，而在SARSA算法中更新Q值時(shí)，它也采用貪婪策略來(lái)選取行為[13]。

4? 模型代碼實(shí)現(xiàn)與測(cè)試

AlphaOthello是一個(gè)使用MCTS算法、Q學(xué)習(xí)算法和SRASA算法的實(shí)現(xiàn)人機(jī)對(duì)弈軟件。其中Q學(xué)習(xí)算法和SRASA算法采用了Keras框架。它是一個(gè)基于深度學(xué)習(xí)的框架。

Keras框架中可以采用函數(shù)式API來(lái)定義神經(jīng)網(wǎng)絡(luò)。函數(shù)式API的優(yōu)勢(shì)在于可以更加靈活地定義多個(gè)輸入、輸出或者更復(fù)雜的連接方式，神經(jīng)網(wǎng)絡(luò)函數(shù)式API創(chuàng)建模型代碼為：

from keras.models import Model

from keras.layers import Dense，Input

model_input=Input（shape=（8，8）

hidden_layer=Dense（32）（ model_input）

output_layer=Dense（24）（hidden_layer）

model=Model（inputs=[model_input]，outputs=[output_layer]

Q學(xué)習(xí)算法主要代碼為：

class QAgent（Agent）：

#訓(xùn)練算法

def train（self，exper，lr=0.1，batch_size=128）：

opt=SGD（lr=lr）

self.model.compile（loss=mse，optimizer=opt）

n=exper.states.shape[0]

num_moves=self.encoder.num_points（）

y=np.zeros（（n，））

actions=np.zeros（（n，num_moves））

for i in range（n）：

action=exper.actions[i]

reward=exper.rewards[i]

actions[i][action]=1

y[i]=reward

self.model.fit（[exper.staes，actions]，y，batch_size=batch_size，epochs=1）

#價(jià)值排序，貪婪策略

def rank_moves_eps_greedy（self，values）：

if np.random.random（）

values=np.random.random（values.shape）

ranked_moves=np.argsort（values）

return ranked_moves[：：-1]

...

以上算法代碼中，使用隨機(jī)梯度下降法（stochastic gradient descent， SGD）來(lái)更新神經(jīng)網(wǎng)絡(luò)的參數(shù)，并且使用均值平方差（Mean square differencemse， MSE）做為損失函數(shù)。

為了測(cè)試算法的性能，將算法生成的下一步策略和WZebra軟件進(jìn)行對(duì)弈。

wZebra軟件是目前黑白棋AI頂級(jí)棋手。在測(cè)試中wZebra的對(duì)局設(shè)置搜索深度采用8步+16步完美，對(duì)局時(shí)限為30分鐘。每種算法對(duì)局100局后統(tǒng)計(jì)平均表現(xiàn)，wZebra執(zhí)黑棋，AlphaOthello執(zhí)白棋。

圖4為以wZebra執(zhí)黑子視角展示對(duì)局過(guò)程估值圖。mcts算法經(jīng)過(guò)調(diào)校，總體水平與wZebra低級(jí)水平相當(dāng)，由于實(shí)驗(yàn)硬件采用CPU來(lái)實(shí)現(xiàn)神經(jīng)網(wǎng)絡(luò)的計(jì)算過(guò)程，總體未能戰(zhàn)勝wZebra。本實(shí)驗(yàn)采用樣本數(shù)據(jù)集為www.skatgame.net GGS 2010數(shù)據(jù)集，由于數(shù)據(jù)集數(shù)量為15個(gè)，數(shù)據(jù)集數(shù)量太少導(dǎo)致學(xué)習(xí)率不足，導(dǎo)致無(wú)法戰(zhàn)勝wZebra軟件。從曲線圖可以看出Q學(xué)習(xí)算法白棋在中盤(pán)30～40步表現(xiàn)一度接近wZebra。而SARSA算法則在局面的中后盤(pán)40～50步表現(xiàn)較好。

5? 結(jié)? 論

本文討論了從經(jīng)典搜索算法到基于人工神經(jīng)網(wǎng)絡(luò)和深度強(qiáng)化學(xué)習(xí)三類(lèi)算法在人機(jī)對(duì)弈方面的應(yīng)用。經(jīng)典搜索算法經(jīng)過(guò)幾十年的優(yōu)化，已經(jīng)達(dá)到了人類(lèi)一流棋手的水平。而使用人工神經(jīng)網(wǎng)絡(luò)和深度強(qiáng)化學(xué)習(xí)的Q學(xué)習(xí)算法和SARSA算法要想達(dá)到優(yōu)異地性能表現(xiàn)，依賴(lài)于兩點(diǎn)：一是高質(zhì)量的對(duì)局樣本、二是強(qiáng)大的計(jì)算能力。后續(xù)要提高深度強(qiáng)化學(xué)習(xí)類(lèi)算法的表現(xiàn)，可以從三個(gè)方面來(lái)優(yōu)化：

（1）收集更多高質(zhì)量的對(duì)弈樣本數(shù)據(jù)集，用來(lái)訓(xùn)練神經(jīng)網(wǎng)絡(luò)。

（2）通過(guò)對(duì)神經(jīng)網(wǎng)絡(luò)算法中的超參數(shù)調(diào)試，來(lái)達(dá)到更好的效果。

（3）采用GPU來(lái)完成神經(jīng)網(wǎng)絡(luò)的計(jì)算，提高算法能力。

參考文獻(xiàn)：

[1] 徐心和，鄧志立，王驕，等.機(jī)器博弈研究面臨的各種挑戰(zhàn) [J].智能系統(tǒng)學(xué)報(bào)，2008（4）：288-293.

[2] 帕佩拉，費(fèi)格森.深度學(xué)習(xí)與圍棋 [M].趙普明，譯.北京：人民郵電出版社，2021.

[3] LEE K F，MAHAJAN S.The development of a world class Othello program [J].Artificial Intelligence，1990，43（1）：21-36.

[4] ALLIS L V.Searching for Solutions in Games and Artificial Intelligence [D].Maastricht：University of Limburg，1994.

[5] 伊庭齊志著.曹旸，譯.AI游戲開(kāi)發(fā)和深度學(xué)習(xí)進(jìn)階[M].北京：機(jī)械工業(yè)出版社，2021.

[6] LAZARD E.黑白棋戰(zhàn)術(shù)指南 [M].Paris：FEDERATION FRANCAISE D'OTHELLO，1993.

[7] SCHAEFFER J，HLYNKA M，JUSSILA V. Temporal Difference Learning Applied to a High-Performance Game-Playing Program [J].Theoretical Computer Science，2001，252（1-2）：105-119.

[8] 紀(jì)嘉偉.基于蒙特卡洛樹(shù)搜索的混合激活函數(shù)研究 [D].蘭州：蘭州大學(xué)，2021.

[9] WANG Y ，GELLY S .Modifications of UCT and sequence-like simulations for Monte-Carlo Go [C]//IEEE Symposium on Computational Intelligence & Games.Honolulu：IEEE，2007.

[10] 劉全，翟建偉，章宗長(zhǎng)，等.深度強(qiáng)化學(xué)習(xí)綜述 [J].計(jì)算機(jī)學(xué)報(bào)，2018，41（1）：1-27.

[11] WIERING M，OTTERLO M V.強(qiáng)化學(xué)習(xí) [M].趙地，等譯.北京：機(jī)械工業(yè)出版社，2018.

[12] RAVICHANDIRAN S.Python強(qiáng)化學(xué)習(xí)實(shí)戰(zhàn) [M].連曉峰，等譯.北京：機(jī)械工業(yè)出版社，2019.

[13] 唐振韜，邵坤，趙冬斌，等.深度強(qiáng)化學(xué)習(xí)進(jìn)展：從AlphaGo到AlphaGo Zero [J].控制理論與應(yīng)用，2017，34（12）：1529-1546.

作者簡(jiǎn)介：彭之軍（1978—），男，漢族，湖北潛江人，高級(jí)工程師，碩士，研究方向：軟件工程、人工智能技術(shù)、移動(dòng)互聯(lián)網(wǎng)技術(shù)。