姬 波，尤惠彬,盧紅星，田 欣，2，柳宏川

1(鄭州大學(xué) 信息工程學(xué)院,鄭州 450001) 2(鄭州大學(xué) 產(chǎn)業(yè)技術(shù)研究所第4代工業(yè)研究所,鄭州 450001)

1 引 言

計算機(jī)棋類游戲被認(rèn)為是人工智能領(lǐng)域的“果蠅”，對該領(lǐng)域的深入研究有助于理解機(jī)器智能中許多基礎(chǔ)問題.在計算機(jī)棋類游戲中有3個重要里程碑：Chinook、深藍(lán)和AlphaZero，它們分別在西洋跳棋、國際象棋和圍棋比賽中取得戰(zhàn)勝人類選手的成績[1]，這對投身該領(lǐng)域研究人員的研究熱情起到極大鼓舞作用.

1994年的Chinook基于進(jìn)化論思想，采用種群中互相博弈和遺傳變異的知識傳遞方式，最終篩選出種群中的最優(yōu)選手作為優(yōu)勝者；1997年的深藍(lán)基于向人類專家學(xué)習(xí)知識的理念構(gòu)造專家知識庫，同時結(jié)合α-β剪枝和蒙特卡洛搜索算法解決無法在有限時間內(nèi)窮舉所有可能的國際象棋棋局的問題[2]；2016年的AlphaGo在設(shè)計思路上與深藍(lán)極為相似，只不過是從國際象棋轉(zhuǎn)為更復(fù)雜的圍棋[3]，在很大程度上可認(rèn)為相較于深藍(lán)，AlphaGo僅僅在計算能力(主要指計算速度)上有所提高；至于AlphaZero則著重強(qiáng)調(diào)自學(xué)習(xí)的概念，強(qiáng)調(diào)除下棋規(guī)則外沒有任何其他領(lǐng)域知識，全程無人工指導(dǎo)[4].

上述3個里程碑從不同角度對“果蠅”進(jìn)行詳細(xì)解剖分析，但它們都基于完全一致的認(rèn)知基礎(chǔ)，包括有：

1)承認(rèn)目前計算機(jī)硬件的計算能力有限，無法做到窮舉復(fù)雜棋局游戲的所有局面.

2)認(rèn)為人類棋局專家無法表達(dá)所有棋局知識，通過建立專家知識庫的方式無法解決行棋問題.

3)選用神經(jīng)網(wǎng)絡(luò)作為棋類知識的載體(已經(jīng)證明具有3個隱藏層和足夠節(jié)點數(shù)的神經(jīng)網(wǎng)絡(luò)可以模擬任意復(fù)雜函數(shù))[5].

4)在訓(xùn)練人工智能選手學(xué)習(xí)上，通過產(chǎn)生有限學(xué)習(xí)樣例和調(diào)整神經(jīng)網(wǎng)絡(luò)權(quán)重的方法，能夠達(dá)到準(zhǔn)確判斷棋局形式的目的.

5)有限的學(xué)習(xí)樣例對所有棋局局面的代表程度，很大程度上決定了人工智能選手的智力高低.

目前即使人工智能選手已經(jīng)能夠戰(zhàn)勝人類選手，但棋類人工智能選手身上仍存在很多未能研究透徹的問題.其中一個關(guān)鍵問題是，如何在有限的時間和空間內(nèi)盡可能產(chǎn)生更多高質(zhì)量的學(xué)習(xí)樣例.

學(xué)習(xí)樣例生成方式可分為3類：基于已有棋局的專家知識庫；基于多選手對弈的遺傳變異進(jìn)化篩選；基于自對弈的蒙特卡洛隨機(jī)仿真[6].其中，采用依賴專家知識庫的方法代價高昂且不宜實現(xiàn)，而采用讓人工智能選手間彼此博弈的方法獲得學(xué)習(xí)樣例成本低且易于實現(xiàn).

但目前研究尚且缺乏對于學(xué)習(xí)樣例生成方法和質(zhì)量評價方法的針對性研究，其主要原因如下：

1)棋類智能研究的目標(biāo)多聚焦于人工智能選手與其他選手的比賽結(jié)果上，尤其是與人類冠軍選手的輸贏上，將戰(zhàn)勝人類選手看作核心研究目標(biāo)，而對學(xué)習(xí)樣例產(chǎn)生方式及質(zhì)量評價方法未能引起足夠重視.

2)因國際象棋、圍棋等眾多棋類游戲復(fù)雜度較高，生成樣例所需的硬件環(huán)境不易獲得，所以大大挫傷了缺乏條件的研究人員的參與積極性.

3)棋類游戲復(fù)雜度高帶來的另一個問題是，注意力會更多集中在并行算法(也包括專用硬件的設(shè)計)上，力保在計算時間有限的條件下得出相應(yīng)結(jié)果.因此，研究人員對于已經(jīng)相當(dāng)成熟的蒙特卡洛仿真或遺傳變異算法難以產(chǎn)生足夠重視.

4)缺乏明確的定量分析指標(biāo)，無法建立相應(yīng)的評價體系.

針對以上問題，本文將研究重心聚焦于學(xué)習(xí)樣例質(zhì)量評價方法，首次提出采用樣本規(guī)模綜合指標(biāo)T決定學(xué)習(xí)樣例大小的樣例質(zhì)量評價方法.并在復(fù)雜度適中的西洋跳棋游戲中進(jìn)行驗證，借助T指標(biāo)的指導(dǎo)可以在不降低學(xué)習(xí)效果的前提下大幅減少學(xué)習(xí)樣例產(chǎn)生的計算成本.

2 博弈樹

在博弈類程序設(shè)計中，博弈樹常作為記錄行棋信息的載體，用于記錄下棋步驟和棋局信息.為使行棋方在規(guī)定時間內(nèi)搜索到最佳走子方式，采用窮舉搜索方法顯然不合理，需結(jié)合極大極小算法、α-β剪枝算法和蒙特卡洛搜索算法解決該問題[7].

2.1 極大極小算法

Minimax算法又名極小化極大算法，該算法是一個零總和算法，一方選擇令自己優(yōu)勢達(dá)到最大化的選項，另一方選擇令對手優(yōu)勢最小化的選項[8].

本文將“1”看作我方選手，“-1”看作對方選手.因井字棋整棵博弈樹無法完整呈現(xiàn)，故只展示博弈樹中某一分支，具體搜索過程如圖1所示.

根據(jù)圖1所示的博弈樹分支可推斷出，在可窮舉的情況下采用Minimax算法遍歷整棵博弈樹，可得到根節(jié)點的值，換句話說就是可以找到對當(dāng)前棋局最有利的情況.

2.2 α-β剪枝算法

在生成博弈樹過程中會產(chǎn)生諸多節(jié)點，且在實際下棋過程中每步行棋都要在一定時間內(nèi)完成，因此無法對每個分支都進(jìn)行訪問，可利用α-β剪枝算法解決該問題，通過裁剪搜索樹中無意義分支來提高搜索效率.

圖1 井字棋整棵博弈樹中的某一分支Fig.1 A branch of the whole game tree of TicTacToe

對每個節(jié)點來說，假設(shè)α為下界，β為上界.任意節(jié)點分值N的取值范圍為α≤N≤β，α≤β代表N有解；α>β代表N無解.本文規(guī)定正方形為我方選手，圓形為對方選手，將極大極小值算法和α-β剪枝算法結(jié)合起來，通過不斷修改α和β的值判定在何處進(jìn)行剪枝，某一博弈樹剪枝后的最終結(jié)果如圖2所示.

圖2 α-β剪枝結(jié)果圖Fig.2 Results of α-β pruning

2.3 蒙特卡洛搜索算法

僅使用Minimax算法和α-β剪枝算法無法模擬整個博弈過程，針對無法窮舉的情況需結(jié)合蒙特卡洛樹搜索算法(Monte Carlo Tree Search)，將當(dāng)前棋局的最優(yōu)走子方法以一種新穎的方式計算出來[9].即在走子時多次模擬博弈過程，并嘗試根據(jù)模擬結(jié)果預(yù)測出一種最優(yōu)走子策略.

MCTS算法核心思想是從當(dāng)前棋盤一路向下進(jìn)行一組隨機(jī)遍歷[10]，其中每次模擬博弈時都需要經(jīng)過博弈樹搜索、節(jié)點擴(kuò)展、隨機(jī)模擬和反向傳播4個步驟.針對博弈樹搜索和節(jié)點擴(kuò)展兩個重要步驟，畫出如圖3所示的流程圖.

3 學(xué)習(xí)樣例質(zhì)量的定量評價指標(biāo)

3.1 西洋跳棋簡介

西洋跳棋是一種下棋規(guī)則復(fù)雜的智力游戲，傳統(tǒng)西洋跳棋在8×8的棋盤上進(jìn)行，其中棋盤上有黑白兩種顏色的方塊(黑色表示不能放置任何棋子，白色反之)，棋盤左上角為黑色方塊且相鄰方塊不能為同種顏色[11].游戲玩家包括紅方選手和藍(lán)方選手，對弈雙方各持12個相同顏色的棋子，分別占據(jù)棋盤上下兩邊，如圖4所示.

圖3 MCTS算法模擬博弈流程圖Fig.3 MCTS algorithm simulation game flow chart

圖4 西洋跳棋64格棋盤Fig.4 Checkers 64 board

本文規(guī)定紅方選手為先手，雙方輪流下棋.“未成王”棋子只能向?qū)Ψ椒较驘o人占據(jù)的斜線空格位置行棋，當(dāng)棋子到達(dá)對方底線時變成“王棋”，隨后可向4個斜線方向中任一方向移動.普通棋子在“成王”后不能馬上繼續(xù)吃棋，須等下一回合才可移動.在行棋過程中吃子優(yōu)先級高于走子，出現(xiàn)連吃情況時連吃優(yōu)先級高于吃子.

出現(xiàn)下述情況判定該局游戲結(jié)束：

1)任意一方玩家的棋子被全部吃完，判定留在棋局上的玩家為獲勝方.

2)當(dāng)棋局上留有雙方棋子，但雙方選手均無法移動，判定紅藍(lán)雙方平局.

3)移動步數(shù)超過最大限度且仍未分出勝負(fù)，判定紅藍(lán)雙方平局.

3.2 棋盤表示

西洋跳棋在程序中常用表示方法有兩種：一種是用二維數(shù)組表示棋盤，另一種是用一維數(shù)組表示棋盤.由于二維數(shù)組表示棋盤更加直觀易于分析，綜合考慮后認(rèn)為采用二維數(shù)組表示西洋跳棋棋盤更合理.

如圖4所示，棋盤位置與二維數(shù)組中元素成一一對應(yīng)關(guān)系，例如西洋跳棋棋盤中位置6相當(dāng)于二維數(shù)組中的[1][2]元素.數(shù)組元素由{-2，-1，0，+1，+2}組成，以正負(fù)號區(qū)分紅方選手和藍(lán)方選手[12]，其中-2表示藍(lán)王棋、-1表示普通藍(lán)棋、0表示空格(無棋子)、+1表示普通紅棋、+2表示紅王棋.當(dāng)普通棋子“成王”后，棋子圖像由圓形變?yōu)闃?biāo)有“王”字樣的圓形，以此來區(qū)分普通棋子與王棋.

3.3 棋局學(xué)習(xí)樣例生成

博弈樹作為記錄信息的載體用于記錄行棋信息，將博弈樹節(jié)點看作是一個棋局狀態(tài)，博弈樹每層均可看作某步行棋后所面臨的全部情況[13].

西洋跳棋學(xué)習(xí)樣例生成過程包括棋盤表示、雙方迭代自對弈和優(yōu)化神經(jīng)網(wǎng)絡(luò)，一次迭代的整體流程如圖5所示.

圖5 迭代整體流程圖Fig.5 Return to the overall flowchart

每次迭代雙方需進(jìn)行多局自對弈，每局均默認(rèn)紅方先行，且紅方選手權(quán)重獲取方式為文件讀取，藍(lán)方選手獲取權(quán)重方式為隨機(jī)獲得.由于初始局紅方無較好的神經(jīng)網(wǎng)絡(luò)作為開局選手，因此需根據(jù)下述操作獲得紅方下次迭代的權(quán)重信息：在第1次迭代過程中，保存所有紅方勝n子(即本局結(jié)束后紅方獲勝，且盤面上紅方剩余棋子個數(shù)比藍(lán)方剩余棋子個數(shù)多n個及以上)的權(quán)重信息，在紅方勝n子的棋局中隨機(jī)選取一局，作為紅方本次迭代的最優(yōu)訓(xùn)練結(jié)果.

從第2次迭代開始，紅方選手讀取上次迭代訓(xùn)練完成后存入txt文件的權(quán)重信息，將其作為本次自對弈下棋的選手，藍(lán)方選手仍以隨機(jī)獲取權(quán)重的方式進(jìn)行自對弈下棋，值得注意的是每次迭代結(jié)束前，紅方選手能力(即權(quán)重信息)不再發(fā)生變化.本次迭代完成后雙方對戰(zhàn)輸贏結(jié)果一目了然，本文規(guī)定紅方向藍(lán)方學(xué)習(xí)，故保留所有藍(lán)方勝n子棋局的詳細(xì)下棋步驟及權(quán)重信息作為學(xué)習(xí)樣例.之所以保存藍(lán)方勝n子的棋局信息，是因為對于那些“僥幸獲勝”的藍(lán)方棋局(即沒有勝出n子的情況)，本文認(rèn)為沒有太多學(xué)習(xí)價值，考慮到時間成本問題，決定只保留藍(lán)方勝n(n=6)子的情況.

一次迭代完成后讓紅方選手向本次迭代中收集到的所有藍(lán)方勝n子棋局學(xué)習(xí)，并通過不斷學(xué)習(xí)更新自身權(quán)重，具體訓(xùn)練過程在3.4小節(jié)進(jìn)行詳細(xì)介紹.訓(xùn)練完成后將紅方選手的權(quán)重信息存入文件中，作為下次迭代的開局選手.

重復(fù)迭代上述步驟，以此生成更多高質(zhì)量的學(xué)習(xí)樣例，同時提升紅方選手，整體來看紅方選手相較于學(xué)習(xí)前會有一定程度提升.

3.4 局勢評估機(jī)制

局勢評估機(jī)制主要包括評估函數(shù)和調(diào)整權(quán)值兩大部分.多方參考資料確定影響棋力因素，得到評估函數(shù)[14]，并在此基礎(chǔ)上生成訓(xùn)練樣例，結(jié)合函數(shù)逼近算法更新紅方權(quán)重，以此優(yōu)化紅方選手下棋方式.

3.4.1 評估函數(shù)

在計算機(jī)博弈問題中，評估函數(shù)占有重要地位.評估函數(shù)確定搜索到的棋局估值大小，估值越大表示對我方棋類選手越有利[15].從當(dāng)前面臨的棋局考慮，為確定下一步棋子走向，需通過評估函數(shù)得到下一步所有棋局估值，根據(jù)估值大小選擇最有利于自己的棋子走向.

西洋跳棋棋盤狀態(tài)考慮的影響因素包括紅藍(lán)雙方普通棋子、王棋和空格的位置.每個棋盤狀態(tài)用一個二維數(shù)組表示，根據(jù)本文設(shè)定的棋盤表示方法，用二維數(shù)組的32個元素(x01、x03、x05、x07、x10、x12,…,x72、x74、x76)代表棋盤上32個可走空格狀態(tài)，其他32個不可走子空格本文不予表示.

本文以藍(lán)方勝局作為紅方的學(xué)習(xí)對象，即用紅方下一步面臨的棋局狀態(tài)(藍(lán)方棋局)和紅方權(quán)值計算出紅方的學(xué)習(xí)目標(biāo).結(jié)合棋力影響因素確定原始值和目標(biāo)值，下列式(1)和式(2)為估值法則：

Score_original=Red_status*w_Red

(1)

Score_goal=Blue_status*w_Red

(2)

式(1)中Score_original表示紅方本步棋盤狀態(tài)原始值，Red_status表示紅方本步面臨的棋局狀態(tài)；式(2)中Score_goal表示紅方本步棋盤狀態(tài)目標(biāo)值，Blue_status表示紅方下一步面臨的棋局狀態(tài)(藍(lán)方棋局)；w_Red表示紅方本局權(quán)重.

原始值與目標(biāo)值的計算均以當(dāng)前棋盤32個有效位置作為輸入，權(quán)重和偏差的初始值通過在[-0.2,0.2]上均勻分布采樣產(chǎn)生，以BP神經(jīng)網(wǎng)絡(luò)輸出標(biāo)量值作為唯一輸出，輸出值表示當(dāng)前棋局狀態(tài)分值.

本文設(shè)置神經(jīng)網(wǎng)絡(luò)的第1個隱藏層有5個節(jié)點，第2個隱藏層3個節(jié)點.以第1個隱藏層節(jié)點值的計算方法為例，描述計算過程：

第i個神經(jīng)元的凈輸入值Si，由32個輸入值分別同到該節(jié)點的權(quán)重累積和，加上該節(jié)點本身閾值得到，公式如式(3)所示.此時凈輸入值Si經(jīng)過激活函數(shù)f(x)變換后作為該節(jié)點的輸出yj，公式如式(4)所示.

(3)

(4)

其余節(jié)點均采用同樣計算方法獲得輸出值，本文不再一一贅述，直到獲得輸出標(biāo)量值為止.

3.4.2 調(diào)整權(quán)值

學(xué)習(xí)目標(biāo)函數(shù)的過程被稱為函數(shù)逼近，調(diào)整權(quán)值是其中一個非常重要的環(huán)節(jié).以棋盤狀態(tài)、原始值和目標(biāo)值的估值為訓(xùn)練樣例，通過BP神經(jīng)網(wǎng)絡(luò)的逆向反饋調(diào)整權(quán)值[16].

BP算法是一個迭代算法，它的基本思想為：

1)計算每層節(jié)點分值和激活值，直至輸出層(即信號前向傳播)；

2)計算每層節(jié)點誤差，誤差的計算過程是從輸出層依次向前推進(jìn)的(即信號反向傳播)；

3)更新參數(shù)(其目標(biāo)為使誤差減小).迭代步驟1)和步驟2)，直至滿足停止準(zhǔn)則終止參數(shù)更新(如相鄰兩次迭代的誤差差別很小).

某一訓(xùn)練數(shù)據(jù)(xi，yi)的代價函數(shù)如式(5)所示：

Ei=‖yi-oi‖=∑i(yi-oiL)2

(5)

式中：yi為目標(biāo)值，oi為神經(jīng)網(wǎng)絡(luò)對輸入xi產(chǎn)生的原始值(即實際輸出)，L為神經(jīng)元層數(shù)，i為第i個神經(jīng)元.

代價函數(shù)僅與權(quán)值矩陣和偏置向量有關(guān)，通過BP算法反向傳播調(diào)整參數(shù)，使總體代價(即誤差)變小.過程大致如下：計算神經(jīng)網(wǎng)絡(luò)最后一層輸出值誤差，從后往前反向計算神經(jīng)網(wǎng)絡(luò)每層的錯誤，并計算權(quán)值和偏置項的梯度.當(dāng)多次迭代后達(dá)到預(yù)設(shè)代價函數(shù)最小值時，對應(yīng)的各個神經(jīng)元參數(shù)(即權(quán)值和偏置項)即為本次訓(xùn)練最終參數(shù).

3.5 樣本規(guī)模綜合指標(biāo)

與學(xué)習(xí)樣本產(chǎn)生規(guī)模直接相關(guān)的兩個定量指標(biāo)分別是：樣例總個數(shù)s和重復(fù)樣本率x=r/s.其中，r為重復(fù)樣本個數(shù)，其統(tǒng)計方法是將棋盤狀態(tài)完全一致(盤面評分未必相同)的學(xué)習(xí)樣例計數(shù)為重復(fù)樣本.

y增大時會有助提高學(xué)習(xí)樣例質(zhì)量；而x增加會降低學(xué)習(xí)效果.因此，本文給出了結(jié)合兩者的樣本規(guī)模綜合指標(biāo)T，如式(6)所示：

T=α*y-(1-α)*x

(6)

其中，x=r/s；y=tanh(logs)；α為平衡因子且α∈[0,1].

圖6 y值隨s的變化示意圖Fig.6 y value as a function of s

可以看到，T是x和y的線性組合.其中，由于s∈[0,+∞]，故文本對其作了兩次變換，首先通過對數(shù)log變換降低其數(shù)值域，而后通過雙曲正切函數(shù)tanh變換將值域限定到[0,1].因此，樣本規(guī)模綜合指標(biāo)T的值域范圍為[0,1].其中，y值隨s的變化示意如圖6所示.

4 實驗結(jié)果

為驗證T指標(biāo)對學(xué)習(xí)樣例質(zhì)量的影響，實驗中通過設(shè)定迭代次數(shù)和每次迭代局?jǐn)?shù)兩個變量來人為控制棋局規(guī)模.

實驗1.設(shè)定迭代次數(shù)和每次迭代局?jǐn)?shù)分別為(100,300)，(300,100)，(100,500)，(500,100)等，其中迭代次數(shù)的值為逗號前面的數(shù)值；每局迭代局?jǐn)?shù)的值為逗號后面的數(shù)值.

表1 不同迭代次數(shù)和每次迭代局?jǐn)?shù)下的 樣例總個數(shù)和重復(fù)樣本率對比表Table 1 Comparison Table of total number of samples and repeated sample rate under different iterations and rounds per iteration

生成樣例中的樣例總個數(shù)s和重復(fù)樣本率x如表1所示.

從表1中可得出兩個結(jié)論：

1)隨著整體棋局個數(shù)(即迭代次數(shù)與每次迭代局?jǐn)?shù)的乘積)的增加，s值也會增加.

2)隨著s值增加，x的值雖有小幅度變化，但總體穩(wěn)定在2%以內(nèi).

實驗2.設(shè)定迭代次數(shù)和每次迭代局?jǐn)?shù)分別為(500,1000)，(1000,500)，(2000,300)等，本文給出了每組參數(shù)下生成樣例中的樣例總個數(shù)s、重復(fù)樣本率x、指標(biāo)值T(a取值為0.8)和用該學(xué)習(xí)樣例數(shù)據(jù)集訓(xùn)練后的紅方AI的勝率情況，如表2所示：

表2 雙方自對弈實驗結(jié)果Table 2 Result of the game experiment

根據(jù)表2中數(shù)據(jù)繪制T值與紅方勝率變化組合圖，如圖7所示.

圖7 T值與紅方勝率變化圖Fig.7 T value and red square win rate change chart

圖7中橫坐標(biāo)代表迭代次數(shù)和每次迭代局?jǐn)?shù)的具體組合情況，左側(cè)數(shù)值代表紅方勝率，右側(cè)數(shù)值代表T值，折線代表紅方勝率，長方體代表T值大小.

從表2和圖7可得出下列3個結(jié)論：

1)迭代次數(shù)和每次迭代局?jǐn)?shù)分別為(2000，300)時紅方勝率最高，而后隨著自對弈次數(shù)增加，學(xué)習(xí)效果反而較差；

2)在平衡參數(shù)a取值為0.8時，T值的大小和紅方訓(xùn)練后的勝率變化規(guī)律一致，這說明在西洋跳棋游戲中T值是一個可以反映學(xué)習(xí)樣例質(zhì)量的合理指標(biāo)；

3)采用樣本規(guī)模綜合指標(biāo)T來決定學(xué)習(xí)樣例大小，可以控制樣本規(guī)模和學(xué)習(xí)時間，降低學(xué)習(xí)成本.

5 結(jié)束語

為了在不降低學(xué)習(xí)效果的前提下大幅降低學(xué)習(xí)樣例產(chǎn)生的計算成本，本文在分析棋盤狀態(tài)評分方法的基礎(chǔ)上，提出采用樣本規(guī)模綜合指標(biāo)T評價學(xué)習(xí)樣例質(zhì)量，并在西洋跳棋游戲上進(jìn)行了驗證.

下一步工作包括：驗證該指標(biāo)在其他自對弈棋類游戲?qū)W習(xí)的指導(dǎo)效果；通過改良實驗中的AI選手的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)來提高學(xué)習(xí)后的勝率等.