計算機博弈算法在黑白棋中的應用

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

關鍵詞：蒙特卡洛樹搜索;深度強化學習;馬爾科夫決策過程;Q學習;SARSA

中圖分類號：TP181? ? 文獻標識碼：A 文章編號：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? 引? 言

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

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

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

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

這兩項技術的組合成為了計算機博弈游戲人工智能的兩大支柱。在目前計算機圍棋的最強者、谷歌旗下開發(fā)的軟件產品AlphaGo在下棋時就配置兩臺計算機，一臺用于α-β剪枝，一臺用于棋局評估。

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

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

1? 黑白棋簡介

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

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

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

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

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

2.1? 樹搜索算法

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

2.2? α-β剪枝算法

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

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

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

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

評估函數(shù)的定義成為要解決的重點。首先采用專家法，根據(jù)世界頂級人類黑白棋棋手的總結，常見的評估和判斷局面的幾個變量為：

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

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

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

根據(jù)以上的概念，綜合使用參數(shù)可以使用加權線性和，用來評估每個位置的價值。

可以使用如下的第一種評價函數(shù)：

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

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

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

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

2.4? 蒙特卡洛樹搜索

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

（1）將新的棋局添加到MCTS樹中。

（2）從這個棋局開始模擬從可選合法位置中隨機選一個位置對局。

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

在一定的時間內重復這個計算過程，最后根據(jù)統(tǒng)計數(shù)據(jù)得到最優(yōu)結果動作。

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

該公式定義為：

UCT=w+c

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

3? 深度強化學習的應用

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

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

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

強化學習是學習器（又稱為代理，agent）學習如何在環(huán)境中動作（action），環(huán)境中僅有的反饋由獎勵信號組成。代理的目標是長期最大化從環(huán)境獲得的獎勵信號。

強化學習問題可以通過馬爾科夫決策過程（Markov Decision Processes， MDP）的框架來描述。

3.1? 馬爾科夫決策過程

MDP是決策理論規(guī)劃、強化學習及隨機過程中一種直觀和基本的構造模型。一個馬爾科夫決策過程包括狀態(tài)、動作、轉換函數(shù)、獎勵方程等。

3.1.1? 狀態(tài)

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

3.1.2? 動作

動作集合A通過有限集合{a1，…，AK}來定義大小為K的動作空間。默認所有動作都能對應于一個狀態(tài)，對于s∈S，A（s）=A。

3.1.3? 轉換函數(shù)

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

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

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

3.1.4? 獎勵方程

獎勵方程式指在一個狀態(tài)中完成一個動作后的獎勵。狀態(tài)獎勵方程可以定義為R：S→R。獎勵方程是馬爾科夫決策過程中最重要的部分，因為獎勵方程定義了學習的最終目標[11]。在黑白棋游戲中，獎勵值可以定義成最終獲得比對手多的棋子數(shù)量。

價值函數(shù)用來估計在某個特定的狀態(tài)下執(zhí)行某個動作所能獲得的收益值。

在策略π下的狀態(tài)S的值，表示為V π（S），是預期收益。可以表示為如下公式：

3.2? 時間差分學習算法

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

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

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

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

AlphaOthello是一個使用MCTS算法、Q學習算法和SRASA算法的實現(xiàn)人機對弈軟件。其中Q學習算法和SRASA算法采用了Keras框架。它是一個基于深度學習的框架。

Keras框架中可以采用函數(shù)式API來定義神經(jīng)網(wǎng)絡。函數(shù)式API的優(yōu)勢在于可以更加靈活地定義多個輸入、輸出或者更復雜的連接方式，神經(jīng)網(wǎng)絡函數(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學習算法主要代碼為：

class QAgent（Agent）：

#訓練算法

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）

#價值排序，貪婪策略

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]

...

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

為了測試算法的性能，將算法生成的下一步策略和WZebra軟件進行對弈。

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

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

5? 結? 論

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

（1）收集更多高質量的對弈樣本數(shù)據(jù)集，用來訓練神經(jīng)網(wǎng)絡。

（2）通過對神經(jīng)網(wǎng)絡算法中的超參數(shù)調試，來達到更好的效果。

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

參考文獻：

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

[2] 帕佩拉，費格森.深度學習與圍棋 [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游戲開發(fā)和深度學習進階[M].北京：機械工業(yè)出版社，2021.

[6] LAZARD E.黑白棋戰(zhàn)術指南 [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] 紀嘉偉.基于蒙特卡洛樹搜索的混合激活函數(shù)研究 [D].蘭州：蘭州大學，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] 劉全，翟建偉，章宗長，等.深度強化學習綜述 [J].計算機學報，2018，41（1）：1-27.

[11] WIERING M，OTTERLO M V.強化學習 [M].趙地，等譯.北京：機械工業(yè)出版社，2018.

[12] RAVICHANDIRAN S.Python強化學習實戰(zhàn) [M].連曉峰，等譯.北京：機械工業(yè)出版社，2019.

[13] 唐振韜，邵坤，趙冬斌，等.深度強化學習進展：從AlphaGo到AlphaGo Zero [J].控制理論與應用，2017，34（12）：1529-1546.

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