（韶關(guān)學(xué)院計算機科學(xué)學(xué)院，廣東韶關(guān)512005）

六子棋博弈系統(tǒng)中機器學(xué)習(xí)算法設(shè)計與研究

于江明，袁斌杰，何燦輝，段琢華

（韶關(guān)學(xué)院計算機科學(xué)學(xué)院，廣東韶關(guān)512005）

本文針對我校參加全國大學(xué)生博弈大賽完成的六子棋博弈系統(tǒng)，首先簡要介紹本系統(tǒng)的一些關(guān)鍵構(gòu)成.并重點論述了對現(xiàn)有的六子棋系統(tǒng)一個更進一步的優(yōu)化，在MTD(f)算法上增加自適應(yīng)寬度調(diào)整和在評估函數(shù)上增加TD_BP算法自我學(xué)習(xí)方法，使系統(tǒng)“思考”性的能力更加強.

六子棋；計算機博弈；評估函數(shù)；開局庫；TD_BP算法

六子棋是一種黑白棋游戲，是一種雙人對弈的游戲，對戰(zhàn)雙方各執(zhí)一種顏色的棋子，對弈過程中，一方先于另外一方先連成六顆子獲勝，所以叫六子棋，六子棋的棋盤有的大小可以是無限大，但一般都以19乘以19的方格作為棋盤.現(xiàn)在研究六子棋的領(lǐng)域越發(fā)成熟，在網(wǎng)絡(luò)上出現(xiàn)好多六子棋博弈的系統(tǒng)，例如文獻［1］提到的深思、文獻［2］提到的深藍、網(wǎng)絡(luò)上的X6等，這些系統(tǒng)都有自己的特色，它們的構(gòu)成都大同小異，但他們都沒有使用自我學(xué)習(xí)的算法.本文主要簡單論述以下六子棋系統(tǒng)的構(gòu)成，然后針對六子棋博弈系統(tǒng)增加自我寬度調(diào)整和自我學(xué)習(xí)進行一個比較詳細的論述.

1 六子棋系統(tǒng)構(gòu)成

1.1 棋盤和棋局的表示

在六子棋計算機博弈系統(tǒng)中，只有黑白兩種顏色的棋子，棋盤的表示有數(shù)組棋盤和比特棋盤，但由于六子棋的棋盤比較大，而且棋類沒西洋跳棋、中國象棋那么復(fù)雜，所以采用了數(shù)組棋盤.六子棋的棋盤看起來像一個二維數(shù)組，因此用一個二維數(shù)組表示六子棋棋盤.如代碼1所示，首先枚舉棋子的類型，分別是黑棋、白棋、空子，這樣就可以用不同的數(shù)值表示棋盤上的棋子狀態(tài)，然后定義一個1919的六子棋棋盤，關(guān)鍵代碼為：

typedef CellType Board［ROW_MAX］［COL_MAX］;//定義的二維數(shù)組棋盤.

1.2 著法生成

著法生成是指根據(jù)當前棋局產(chǎn)生所有有效的著法.本六子棋采取常用的棋盤掃描法，在六子棋的規(guī)則內(nèi)和棋盤范圍內(nèi)，進行不斷的掃描，從而約束條件和下子情況.

1.3 MTD（f）算法

MTD(f)算法代碼如代碼2所示，該算法在文獻［2］里面負極大值算法（Negamax）的基礎(chǔ)上設(shè)定了搜索的邊界，一個是上邊界，另外一個是下邊界，還設(shè)置了一個猜測值.文獻［3］提到過MTD(f)算法的效率主要是來自于空窗搜索的高剪枝率，目的是通過猜測值修改上下邊界來逼近真實值，當下邊界的值大于或等于上邊界時，就可以結(jié)束搜索返回了.如果猜測值跟真實值越接近，那么搜索的次數(shù)越小，最好的情況是剛開始的猜測值就是真實值，進行兩次的空窗搜索兩個邊界相等就能結(jié)束搜索了.因為MTD(f)算法搜索過程中可能會重復(fù)一些節(jié)點，因此結(jié)合置換表使用的話更高效率.MTD(f)算法可以調(diào)整精度，增加一個步進值使搜索的幅度增大，這個步進值可以是固定值，也可以是一個動態(tài)值，這個值要根據(jù)博弈系統(tǒng)的評估函數(shù)來調(diào)整，關(guān)鍵代碼為：

1.4 評估函數(shù)

上述的算法里面，都有用到評估函數(shù)值，評估函數(shù)對于一個博弈系統(tǒng)來說占了一比較重要的地位，評估函數(shù)的值可以決定所選擇著法的優(yōu)劣程度.現(xiàn)在博弈系統(tǒng)一般取用的是靜態(tài)評估函數(shù)，因為靜態(tài)評估函數(shù)是比較容易實現(xiàn)，而且根據(jù)各種文獻［4］的經(jīng)驗可以很快的調(diào)整它值.評估函數(shù)表示了己方的有利程度的有利成度，對一般的，取勝局面的評估函數(shù)的值為+∞，失敗局面的評估函數(shù)值-∞.評估函數(shù)值的大小對取勝的影響很大.參考文獻［5］的評估函數(shù)中棋型的分類內(nèi)容本系統(tǒng)的分為C6、DW、L5、D5、L4、D4、L3、S3、D3、L2、D2、L1、D1、V14種棋型，這樣就可以根據(jù)棋局算出評估函數(shù)值，而且根據(jù)評估函數(shù)值我們可以大概看到當前的棋局對己方是否有利.本系統(tǒng)采用數(shù)據(jù)匹配的方式，把各種棋型的評估值放到txt文件里面，運行時，會在系統(tǒng)中把數(shù)據(jù)存到一個表上面去，利用二進制進行一個匹配棋型，不論是白起還是黑棋都一樣.因為是一文件的方式讀入，所以維護里面的參數(shù)也比較方便，通過實際的對弈可以進行人工的修改.

還有一種靜態(tài)評估方法是基于文獻［4］所提出的“路”，把它做成Segment表，連續(xù)六格表示一個棋型，表中有六種情況，所以這個靜態(tài)評估值有六種值，跟第一種評估函數(shù)不一樣.假設(shè)第一種評估的為Evalua-tor，第二種為segmentScore，那么總的靜態(tài)評估值val可以表示成公式：

公式（1）中A和B的值是兩種評估函數(shù)在博弈系統(tǒng)中所占的比重，也就是權(quán)重，我們設(shè)置它們的值都為1.也就是說兩種評估都占了相同的地位.

2 六子棋的優(yōu)化方法

2.1 開局庫的引用

文獻［2］提到常用的定式是一些常用的，但這些遠遠不夠用，有些好的棋局需要計算機算上好長一段時間，幾小時或者幾天都有可能.利用開局庫來存儲這個好的定式.如果當前棋局的局面在開局庫有的話，就可以直接提取出來而不用搜索引擎進行樹的搜索,這樣可以避免由于深度不夠造成下子的失誤,同時也增加了搜索的效率.

本博弈系統(tǒng)采用數(shù)據(jù)庫的形式，使用了SQL的開放數(shù)據(jù)庫互連（ODBC）.開局庫存儲的內(nèi)容是棋局的棋子坐標.對于當前局面，首先連接數(shù)據(jù)庫，然后向數(shù)據(jù)庫發(fā)送語句查詢信號，查詢數(shù)據(jù)庫中有沒有對應(yīng)的開局，有的就返回對應(yīng)著法數(shù)據(jù)，對數(shù)據(jù)轉(zhuǎn)換成坐標.

在數(shù)據(jù)庫中創(chuàng)建兩個表，一個是黑棋著法的數(shù)據(jù)庫，另一個是白棋著法的數(shù)據(jù)庫，兩個表內(nèi)存的定石除了一些文獻［2］說到常用的開局，還有通過自己跟別人對弈得到的一些比較好的棋局.黑棋跟白棋都可以算到第六手.

2.2 自適應(yīng)確定寬度值

上述的MTD（f）算法，利用迭代深化，用一個時間的限制來規(guī)定搜索引擎搜索的深度，在時間內(nèi)搜到好的棋局就回返回，搜不到好的棋局就會一直搜到時間限制的結(jié)束再從搜出的這么多節(jié)點當中挑出最好的那個返回.算法里面還設(shè)置了一個步進值，例如下述代碼所示這個步進值是修改搜索上下邊界的寬度，這個值是協(xié)同評估函數(shù)值的，精度高的評估函數(shù)，顆粒小的話需要多次搜索才會接近真實值.設(shè)置步進值可以適當減少搜索次數(shù)，這樣使搜索的效率更高一些，關(guān)鍵代碼為：

int MTDf(int原始猜測值,int深度)

{

While(深度＜最大深度||時間＞最大時間){

int真實值,猜測值=原始猜測值;

int上邊界=正無窮;int下邊界=負無窮;

int步進值=設(shè)定固定值；

While(深度＜最大深度){

while(下邊界＜上邊界)

{步進值=上一輪搜索中最好的評估值;

if(猜測值==下邊界)

窗口值=猜測值+1+步進值;

else

窗口值=猜測值-步進值;

猜測值=負極大值算法(窗口值-1,窗口值,深度);

if(猜測值＜窗口值)

上邊界=猜測值;

else

下邊界=猜測值;

return猜測值;}.

2.3 自適應(yīng)寬度的調(diào)整的取值分析

自適應(yīng)確定寬度值的取值怎么取呢？在本博弈樹中，我們利用一個比較大的數(shù)1 000 000 000代表∞，這個也是評估函數(shù)的極限值，因此step值的取值范圍是0～1 000 000 000,但這個step值不能取太小，太小的話搜索引擎需要搜索多次，太大的話雖然搜索很快，但可能會錯過了一次比較好的著法，因此效率和著法質(zhì)量是一個反比的關(guān)系.取寬度值為0、150 000和動態(tài)值三個值進行多次測試，整理數(shù)據(jù)分析得出，當step值為0時，搜索的次數(shù)明顯要給step的值為固定值或動態(tài)值的要多.Step值為動態(tài)值的時候，搜索的次數(shù)大部分是給step值為0或固定值小.

3 TD_BP自我學(xué)習(xí)評估

3.1 TD_BP自我學(xué)習(xí)的介紹

傳統(tǒng)的搜索算法一般是采用靜態(tài)評估函數(shù)結(jié)合的博弈系統(tǒng)，為了改進系統(tǒng)，增加TD_BP自我學(xué)習(xí)系統(tǒng)，這是一個增強學(xué)習(xí)的系統(tǒng)，文獻［6］所提出的BP算法分為有導(dǎo)師和無導(dǎo)師的的學(xué)習(xí)方法，如果要采用導(dǎo)師學(xué)習(xí)的方法，需要手工輸入棋局和對弈結(jié)果，需要費很大的人力，所以是不合理的.所以本系統(tǒng)采用無導(dǎo)師的非監(jiān)督的學(xué)習(xí)方法，它能從環(huán)境的反饋學(xué)習(xí)，不斷嘗試進行動作選擇，并從環(huán)境的反饋結(jié)果調(diào)整評估值，等到最優(yōu)策略.

3.2 評估函數(shù)P(s，a)

對于前面提到過的靜態(tài)評估，參考文獻［6］對于局面P的估值過程都可以形式上的描述為一個線性的函數(shù)V（p）:

其中，W是常量分量構(gòu)成的權(quán)重向量＜w1,w2,w3,...,wn＞，f是由特征值構(gòu)成的n維特征向量＜f1,f2, f3,...,fn＞.對于上述的靜態(tài)評估權(quán)重向量的取值都是1.

而對于自我學(xué)習(xí)系統(tǒng)的評估函數(shù)遞歸公式為P(s,a)：

上式s為每個局面的狀態(tài)，a為動作，P(s,a)為評估值.

由公式（3）P值函數(shù)可以被看做是基于單步前瞻的訓(xùn)練值，可變?yōu)椋?/p>

基于n步前瞻的回報P(n)(st,at)：

在公式（3）上增加一個0≤λ≤1合并不同前瞻距離的評估值P(st,at)：個隱藏層的節(jié)點數(shù)很多時，往往網(wǎng)絡(luò)性能還得不到很好的改善，就會再增加一個隱藏層.本系統(tǒng)采用輸入層，隱藏層，輸出層3層的網(wǎng)絡(luò)結(jié)構(gòu).

自我學(xué)習(xí)算法TD(λ)=Pλ(st,at)，對于博系統(tǒng)，上式（6）中，當λ=0時，P(1),只考慮單步差異的話，對估值沒什么影響，需要考慮更遠的前瞻，這樣對當前的估計更準確，訓(xùn)練更好.

3.3 BP網(wǎng)絡(luò)的結(jié)構(gòu)設(shè)計與神經(jīng)元網(wǎng)絡(luò)的參數(shù)選擇

映射所有連續(xù)函數(shù)的可以采用單隱藏層的前饋網(wǎng)絡(luò)，不連續(xù)函數(shù)的學(xué)習(xí)時需要兩個隱藏層，設(shè)計中一

用三層的神經(jīng)網(wǎng)絡(luò)作為六子棋的評估函數(shù)，網(wǎng)絡(luò)相鄰之間的傳輸函數(shù)對網(wǎng)絡(luò)的的擬合性能影響很大.轉(zhuǎn)換函數(shù)可以選線性函數(shù)或非線性函數(shù).使用線性函數(shù)的話，評估函數(shù)會存在很大的不足，是因為六子棋的局面錯綜復(fù)雜.因此構(gòu)造網(wǎng)絡(luò)采用非線性函數(shù)S型sigmoid函數(shù).任意逼近任何連續(xù)函數(shù)需用兩層sigmoid函數(shù)，反向傳播誤差時更容易.

本博弈系統(tǒng)中應(yīng)用神經(jīng)元網(wǎng)絡(luò)必須提取棋局的的局面特征作為神經(jīng)元網(wǎng)絡(luò)的輸入，所選的棋型特征必須符合以下原則：

（1）對結(jié)果影響比較大而且方便取出的的局面特征.

（2）特征之間互不影響或影響性很小.

上述的靜態(tài)評估中已經(jīng)提到過把六子棋的棋型分為C6、DW、L5、D5、L4、D4、L3、S3、D3、L2、D2、L1、D1、V共14種，但對于特征原則的選取，只需要其中的8種，對于神經(jīng)元的輸入，必須要對棋局特征進行一個編碼.例如局面中的‘L3’棋型用4個輸入單元表述，4個輸入單元取值用4維向量表示，（1,0，0，0）表示黑方‘L3’棋型的個數(shù)為0個時；（0,1，0，0）表示黑方‘L3’棋型的個數(shù)為1個時；（0,0，1，0）表示黑方‘L3’棋型的個數(shù)為2個時；（0,0，0,1）表示黑方‘L3’棋型的個數(shù)為3個或3個以上時；類似的，要描述黑棋需要32個輸入單元，一個局面總共需要64個輸入單元.

神經(jīng)元網(wǎng)絡(luò)有一個輸出單元，表示當前局面的估值，輸出越越向1，局勢越對黑方有利，輸出越越向0，局勢對白方有利.根據(jù)得到的輸出單元的值進行選擇著法，生成最優(yōu)著法.

3.4 隱藏層節(jié)點數(shù)的選取

隱藏層節(jié)點的數(shù)目會影響到神經(jīng)網(wǎng)絡(luò).隱藏層節(jié)點過少，學(xué)習(xí)就會受到限制，這樣就看不出規(guī)律來了；隱藏層節(jié)點過多，會使訓(xùn)練時間增加，而且可能會將樣本中非規(guī)律行的內(nèi)容存儲進去，降低了學(xué)習(xí)的能力.本博弈系統(tǒng)選取了18個隱藏單元.最終確定本系統(tǒng)BP神經(jīng)元網(wǎng)絡(luò)（見圖1）輸入層為64個單元，輸出層為1個單元，隱藏層為18個單元.

圖1 BP神經(jīng)元網(wǎng)絡(luò)的結(jié)構(gòu)設(shè)計

3.5 神經(jīng)網(wǎng)絡(luò)權(quán)值W的修改和參數(shù)a和設(shè)置對系統(tǒng)的影響

在神經(jīng)網(wǎng)中主要是通過網(wǎng)絡(luò)權(quán)值W的修改達到學(xué)習(xí)的目的，因為本系統(tǒng)采用的是無監(jiān)督學(xué)習(xí)方法，所以不要輸入樣本和輸出數(shù)據(jù)，因此W權(quán)值修改的公式可以表示為：

式（7）中λ為衰減因子，a是學(xué)習(xí)速率，Pt+1-Pt是相鄰的兩個預(yù)測值，犖wPt是Pt對w每個分量的偏導(dǎo)數(shù).

在TD_BP算法中，a和是常量，a是神經(jīng)元反向傳遞學(xué)習(xí)的學(xué)習(xí)速率，a∈［0,1］，a的值過小，神經(jīng)元的學(xué)習(xí)就會過于緩慢，很難得到提升到最大的性能，a的值過大.盡管學(xué)習(xí)速度好快，但卻降低網(wǎng)絡(luò)的最大性能，難于擬合到真實的局面估值函數(shù).是神經(jīng)網(wǎng)絡(luò)的衰減因子，λ∈［0,1］，λ的值越接近0，表示越遠離當前時刻t的預(yù)測，對時刻t的預(yù)測的影響就越小.因此對于參數(shù)a和λ的取值要經(jīng)過測試取適當?shù)闹?各自取不同的值進行測試，參數(shù)a=0.3和λ=0.7時勝率提高比其他參數(shù)好.

增加TD_BP算法的本系統(tǒng)通過不斷的跟其他六子棋系統(tǒng)不斷的對弈進行自我反饋，動態(tài)調(diào)整評估函數(shù)使搜索引擎有更好的尋優(yōu)，相對于沒有增加TD_BP算法的本系統(tǒng)勝率會更高.

4 結(jié)語

闡述了六子棋博弈系統(tǒng)的幾個核心部分：棋局表示、著法生成、搜索引擎、評估函數(shù).搜索引擎使用了MTD（f）算法，在MTD（f）算法的基礎(chǔ)上加入自適應(yīng)寬度的調(diào)整，有效地減少搜索時間，進一步提高搜索效率.在評估函數(shù)的基礎(chǔ)上加入TD_BP的自我學(xué)習(xí)評估.增強系統(tǒng)“思考”的能力，能更好的提高棋子的棋力.

［1］李果.基于遺傳算法的六子棋博弈評估函數(shù)參數(shù)優(yōu)化［J］.西南大學(xué)學(xué)報：自然科學(xué)版，2007，29(11)：138-142.

［2］閔文杰.六子棋計算機博弈關(guān)鍵技術(shù)研究［D］.重慶：重慶交通大學(xué)，2010.

［3］陳其.PC游戲編程－人機博弈［M］.重慶：重慶大學(xué)出版社，2002.

［4］陳光年.基于智能算法的六子棋博弈行為選擇的應(yīng)用研究［D］.重慶：重慶理工大學(xué)，2011.

［5］徐長明.基于連珠模式的六子棋機器博弈關(guān)鍵技術(shù)研究［D］.沈陽：東北大學(xué)，2010.

［6］李新星.六子棋中基于BP_TD學(xué)習(xí)的局面估值方法研究［D］.沈陽：東北大學(xué)，2009.

Machine learning research and design of algorithm Connect6 game system

YU Jiang-ming,YUAN Bin-jie,HE Can-hui,DUAN Zhuo-hua
（Institute of Computer Science,Shaoguan university,Shaoguan 512005,Guangdong,China)

This article is aimed to analyze Shaoguan University′s students who participatd in the national Computer Games finished.It briefly analyzed the system structure and some key opponents with a focus on the Connect6 for a further optimization.It also increases adaptive width adjustment on the MTD(f)algorithm and evaluation function to increase TD_BP on self-learning algorithm which would strengthen system′s"thinking" ability.

Connect6；computer game；evaluation function；opening data；TD_BP algorithm

TP312；TP183

：A

：1007-5348（2014）10-0017-06

（責任編輯：歐愷）

2014-06-11

韶關(guān)學(xué)院大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃國家級立項建設(shè)項目（201310576-007）.

于江明（1963-），男，湖南邵陽人，韶關(guān)學(xué)院計算機科學(xué)學(xué)院副教授，主要從事知陣論及計算機算法研究.