網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150326.1020.008.html

六子棋中基于局部“路”掃描方式的博弈樹生成算法

李學俊1,2，王小龍1，吳蕾1，劉慧婷1

(1.安徽大學 計算機科學與技術(shù)學院,安徽 合肥 230601； 2.安徽大學 計算智能與信號處理重點實驗室，安徽 合肥 230039)

摘要：針對六子棋博弈比賽中基于“路”的全局掃描方式的博弈樹生成算法效率較低問題，首先分析了基于“路”的全局掃描方式的計算規(guī)則和估值分析，然后將博弈樹生成算法中的全局掃描方式改進為局部掃描方式，并給出其計算規(guī)則和估值分析，接著設(shè)計了基于局部掃描方式的博弈樹生成算法，并集成到Alpha-Beta剪枝算法中。最后從搜索效率和博弈水平2個角度對全局掃描和局部掃描進行實驗，實驗結(jié)果表明，局部掃描方式在比賽時間要求的情況下，能夠大幅度提高搜索效率，并且博弈水平顯著優(yōu)于全局掃描方式。

關(guān)鍵詞：機器博弈；六子棋；路；局部掃描；博弈樹；剪枝算法；估值

DOI:10.3969/j.issn.1673-4785.201401022

中圖分類號：TP31文獻標志碼：A

收稿日期：2014-01-09. 網(wǎng)絡(luò)出版日期：2015-03-26.

基金項目：國家自然科學基金資助項目(61202227).

作者簡介：

中文引用格式：李學俊，王小龍，吳蕾,等. 六子棋中基于局部“路”掃描方式的博弈樹生成算法[J]. 智能系統(tǒng)學報， 2015, 10(2): 267-272.

英文引用格式：LI Xuejun, WANG Xiaolong, WU Lei， et al. Game tree generation algorithm based on local-road scanning method for connect 6[J]. CAAI Transactions on Intelligent Systems, 2015, 10(2): 267-272.

Game tree generation algorithm

based on local-road scanning method for connect 6

LI Xuejun1,2, WANG Xiaolong1, WU Lei1, LIU Huiting1

(1.School of Computer Science and Technology, Anhui University, Hefei 230601, China; 2.Intelligent Computing and Signal Processing Laboratory, Anhui University, Hefei 230039, China)

Abstract：Aiming at the problem that the game-tree generation algorithm generated by global scanning method is low in efficiency in the connect 6, this paper analyzes the calculation rules and valuation analysis of the global scanning method based on "road". Secondly, it develops the global scanning method of the game-tree generation algorithm into local scanning method, and introduces the calculation rules and valuation analysis. The game-tree generation algorithm is a local scanning method designed and integrated into the alpha-beta pruning search. Finally, the global and local scanning experiments are carried out from the two perspectives of search efficiency and playing skill. The experimental results showed that local scanning could greatly improve search efficiency within the competition time. The game ability is superior to that of the global scanning method.

Keywords：computer game; connect 6; road; local scanning; game tree; pruning algorithm; evaluation

通信作者：李學俊.E-mail:xjli@ahu.edu.cn.

機器博弈(即計算機博弈)是人工智能領(lǐng)域的分支，同時也是該領(lǐng)域公認的最具挑戰(zhàn)性的研究課題之一。棋類博弈是人類所能從事的智能活動之一，如果可以掌握博弈的本質(zhì)，也就說明可以幫助人類從事智能活動。因為存在于棋類博弈的原則或許就存在于人類的智能活動中[1]。近年來，國內(nèi)外計算機博弈比賽，極大地推動了計算機博弈問題的研究，促進了計算機博弈理論和技術(shù)的發(fā)展。

棋類計算機博弈涉及的棋種較多，六子棋就是其中之一，它由臺灣國立交通大學吳毅成教授發(fā)明。六子棋競賽規(guī)則很簡單，對弈雙方分別執(zhí)黑子和白子，在19×19的方格棋盤上，除了黑子先手第1步落一顆子外，雙方輪流落2顆子，先在水平、垂直或?qū)蔷€上形成連續(xù)的6子(或6子以上)的一方為勝[2]。六子棋由五子棋改良而來，但是其復(fù)雜度卻遠大于五子棋[3]，其中博弈樹復(fù)雜度達到10140，狀態(tài)空間復(fù)雜度達到10172，僅次于圍棋，與象棋相當或略高[4]。

作為剛興起不久的棋類游戲，六子棋的智能搜索算法研究較少。博弈樹搜索為計算機博弈的基本搜索算法，它是從根節(jié)點向下遞歸搜索而產(chǎn)生的包含雙方所有對弈過程的搜索樹。由于受搜索時間的嚴格約束，博弈樹能夠搜索到的葉子節(jié)點極少屬于末端節(jié)點(即根據(jù)對弈規(guī)則可以判定比賽結(jié)果)，此時需要通過估值函數(shù)對葉子節(jié)點進行量化計算，判斷該葉子節(jié)點所處的棋局狀態(tài)是有利于己方還是對方，且計算其有利程度大小[5]。

在博弈樹的擴展過程中會將雙方可能的對弈過程展示出來，首先對葉子節(jié)點進行估值，再倒推計算根節(jié)點各分支節(jié)點的值，選擇估值最大的分支節(jié)點作為最佳解。但是隨著搜索深度的增加，博弈樹的節(jié)點數(shù)量成指數(shù)性增長。在極大極小值算法的基礎(chǔ)上，Alpha-Beta剪枝技術(shù)在搜索的過程中忽略了無用的節(jié)點，并將其刪除，不對其估值，刪除無用節(jié)點時不會造成信息丟失，不影響根節(jié)點各分支節(jié)點的估值，提高了搜索速度[6]。在深層次的遞歸搜索中廣泛采用Alpha-Beta剪枝算法。為了提高計算速度，本文采用Alpha-Beta剪枝技術(shù)。

由于六子棋對弈規(guī)則的特殊性，如果只考慮單個棋子對棋局的影響進行估值計算，而未考慮棋子間的位置關(guān)系，肯定會影響棋局狀態(tài)的評估效果，由此產(chǎn)生了基于棋形的掃描方式[7-8]。常見的棋形主要分為六連、長連、活五、眠五、死五、活四、眠四、死四、活三、眠三、朦朧三、活二、眠二、朦朧二等[9]。文獻[2]提出基于棋形的數(shù)據(jù)表示方法，數(shù)據(jù)結(jié)構(gòu)依賴于棋形，將棋局的數(shù)據(jù)表示和局面知識結(jié)合起來，提高搜索效率。

基于棋形的掃描方式將棋子間的位置關(guān)系聯(lián)系起來，通過產(chǎn)生某種棋形來表示對整個棋局狀態(tài)的影響程度，更具有直觀性，減少對單個棋子進行估值的不穩(wěn)定性；然而目前棋形是通過經(jīng)驗總結(jié)的，人為因素影響很大，不排除還存在其他種類，這需要通過大量實驗來確定。大部分六子棋的估值計算都是基于棋形的掃描方式，但是由于棋形的判斷要求很高，常見的棋形種類較多，且每種棋形又存在多種落子方式[10]，由此文獻[11]提出“路”的掃描方式。所謂“路”就在棋盤的水平、垂直或?qū)蔷€上出現(xiàn)連續(xù)6點連成一線[11]。

基于“路”掃描方式能有效降低棋形判斷的復(fù)雜度，通過“路”掃描方式的估值相對于通過棋形掃描方式估值較為簡單，實現(xiàn)方面也更加容易，并且搜索時間較短。文獻[12]在傳統(tǒng)的基于“路”的全局掃描方式上采用自學習的方法自動調(diào)整估值函數(shù)的參數(shù)，提高搜索精度。文獻[13]在應(yīng)用Alpha-Beta剪枝搜索時引入并行計算，大幅度提高搜索效率。

“路”掃描方式的引入避免了精確判斷棋形的難題，減少了計算量；同時應(yīng)用面向?qū)ο蟮乃枷?，將“路”的信息抽象成類，易于實現(xiàn)?；凇奥贰?的掃描方式解決了因棋形判斷不準確而影響博弈水平的問題，但是應(yīng)用博弈樹搜索時，在對每個子節(jié)點的擴展時都需要對棋盤進行全局掃描。受博弈競賽時間約束，搜索深度和寬度都有所限制，博弈水平也達不到理想要求。因此本文在博弈樹生成子節(jié)點時將基于“路”的全局掃描方式改進為局部掃描，并設(shè)計基于局部“路”掃描方式的博弈樹生成算法。

1基于“路”的全局掃描方式

1.1計算規(guī)則

K子棋可用connect(m,n,k,p,q)表示[14]，對弈雙方為黑方和白方，黑方先走。connect(m,n,k,p,q)的規(guī)則包括：1)棋盤的方格為m行n列，即含m×n個交叉點；2)對弈時雙方輪流落p顆棋子(根據(jù)六子棋比賽黑方先手規(guī)則，第1次落q顆棋子)；3)在棋盤的水平、垂直或?qū)蔷€上先形成k連獲勝。若在規(guī)定時間內(nèi)雙方均無法獲勝，則判為平局。

K子棋中“路”的計算規(guī)則：1)水平方向：m行×(n-k+1)路/行，如圖1中(a)所示；2)垂直方向：n列×(m-k+1)路/列，類似于水平方向；3)左斜方向：由于k連需要k子連續(xù)相連，在左斜方向前k-1行不可能形成k連，故左斜方向路數(shù)為(m-k+1)行×(n-k+1)路/行，如圖1中(b)；4)右斜方向：(n-k+1)列×(m-k+1)路/列，類似于左斜方向。

六子棋是K子棋的一種[15]，采用19×19方格棋盤，可表示為connect(19,19,6,2,1),總路數(shù)為

(1)

圖1　水平及左斜方向路數(shù)計算示例 Fig.1　Road number of horizontal and left diagonal direction

1.2估值分析

在“路”的信息表示中，設(shè)置n∈{0,1,2,3,4,5,6}表示該路中相同顏色棋子的個數(shù)，設(shè)置c∈{′B′,′W′}表示路中棋子的顏色。若某路中含2種顏色棋子，表示該路不可能成為六連，則初始值不變。

當某路中c為已方棋子顏色時分配不同的價值，計算分配價值公式為

(2)

式中：Vown表示分配的價值，n越大表明己方在該路越容易形成六連，則分配的價值越大。

當某路中c為對方棋子顏色時分配不同的威脅值，計算威脅值公式為

(3)

式中：Vthreat表示分配的威脅值，n越大表明對方在該路越容易形成六連，則分配的威脅值越大。

全局掃描估值可用己方所有“路”的價值之和減去對方所有“路”的威脅值之和表示。全局掃描棋局估值Vtotal可看作是每步落子后對當前棋局的影響程度大小，即落子后棋盤全局掃描估值Vafter減去落子前棋盤全局掃描估值Vpre，可表達為

(4)

2基于“路”的局部掃描方式

應(yīng)用Alpha-Beta剪枝技術(shù)搜索時,效率和精確度是非常重要又相互影響的因素[16]。文獻[2]中指出棋局狀態(tài)的變化均由新增的棋子引起，在棋局中只有新增棋子的水平方向、垂直方向和對角線方向上的棋形發(fā)生變化，對其他位置棋形無影響。在基于“路”的掃描過程中，每步落子對棋局的影響是由該兩落子在水平方向、垂直方向和對角線方向上的“路”所引起，與其他“路”沒有關(guān)系，故本文在博弈樹生成時，優(yōu)化改進“路”的掃描方式。

2.1計算規(guī)則

假設(shè)在棋盤的(3,7)位置模擬一個落子，由圖2可得在水平方向有6路包含該落子，由此可得在局部掃描方式下，每步落子所影響的路數(shù)計算如式(5)所示。

(5)

式中：Npart表示局部掃描每步落子影響的路數(shù)，Ndirect表示每個方向所含的路數(shù)，Nscan表示一個落子所要掃描的方向數(shù)，Nchess表示每步的落子數(shù)。

圖2　局部掃描水平方向路數(shù)計算示例 Fig.2　Road number of horizontal direction by the local-road scanning method

(6)

2.2估值分析

局部掃描方式本質(zhì)上和全局掃描方式的不同在于對每個子節(jié)點進行擴展時都要應(yīng)用“路”進行局部掃描而不是全局掃描，它們的估值存在一定的聯(lián)系。

(7)

(8)

3)由于每步落子不會對局部掃描以外的“路”估值產(chǎn)生影響，即落子后除局部掃描以外的“路”估值V″after等于落子前除局部掃描以外的“路”估值V″pre，表達為

(9)

所以，局部掃描的棋局估值為

(10)

由式(10)可以看出，局部掃描方式和全局掃描方式的棋盤估值相同，并沒有降低精確度，因此在博弈樹生成時，本文將棋盤掃描方式由全局掃描改進為局部掃描，忽略無用掃描，以提高搜索速度。

3局部掃描方式的博弈樹生成算法

局部掃描方式的博弈樹生成算法主要用于子節(jié)點的擴展過程。因為搜索的寬度是有限的，根節(jié)點遞歸向下搜索時，先采用局部掃描方式擴展子節(jié)點并進行估值，并通過排序選擇估值排名靠前的Width個節(jié)點繼續(xù)遞歸向下搜索，刪除其他不進行遞歸搜索的節(jié)點。為了更方便地應(yīng)用博弈搜索策略，將“2步”落子并作“一步”，對模擬的2步落子進行綜合估值，保證搜索效率和博弈水平?；诰植繏呙璺绞降牟┺臉渖伤惴▊未a如下。

基于局部掃描的博弈樹生成算法中，輸入模擬落子的棋子顏色Color及搜索寬度Width，輸出估值排名前Width的落子組合點。

本文的六子棋搜索算法采用Alpha-Beta剪枝技術(shù)實現(xiàn)，設(shè)置深度為Depth，寬度為Width。對弈過程中，根據(jù)當前棋局狀態(tài)擴展子節(jié)點時，采用基于局部掃描的博弈樹生成算法對所有可以進行擴展的子節(jié)點進行估值，選擇估值為前Width名的子節(jié)點繼續(xù)擴展，直至擴展深度為Depth為止。通過對葉子節(jié)點估值，倒推計算根部各分支節(jié)點的估值，選擇最大值節(jié)點對應(yīng)的落子方式為最佳解。

/*Input:Color,Width Output:listWay(估值排名前Width的2步落子組合)*/

1) Localscanning(int Color,int Width){

2)AddMovePoints(ListPoints);//計算模擬移動的落子位置

3)for(i=0;i

4)for(j=i+1;j

5)scanPart(ListPoints[i].Point,ListPoints[j].Point);//落子前局部掃描

6)Part_preValue=Caculate();//計算模擬落子前局部掃描估值

7)SimulateMove();//模擬落子

8)scanPart(ListPoints[i].Point,ListPoints[j].Point);//落子后局部掃描

9)Part_afterValue=Caculate();//計算模擬落子后局部掃描估值

10)Value=Part_afterValue-Part_preValue;

11)RestoreMove();//撤銷落子

12)AddListWay(ListPoints[i].Point,ListPoints[j].Point,Value);

13)}

14)GetListWay(ListWay,Width);

4實驗

4.1實驗環(huán)境

基于上述六子棋搜索策略，本文設(shè)計并實現(xiàn)了六子棋博弈系統(tǒng)DragonWorld(龍行天下)-人機對弈平臺。該系統(tǒng)采用C#語言開發(fā)，操作系統(tǒng)為Windows 7，硬件環(huán)境為聯(lián)想(G490) CPU、2.60GHZ的Inter處理器和4G內(nèi)存。

4.2實驗與分析

為比較不同的掃描方式，本文從搜索效率和博弈水平2個角度進行實驗對比。通過搜索效率的實驗，分析不同深度和寬度對搜索效率的影響。通過博弈水平的實驗，在嚴格遵循競賽時間要求的前提下，分析同等條件下不同搜索深度和寬度對博弈水平的影響。實驗中每局對弈時間不超過15min。

表1價值與威脅值分配

Table 1The distribution of the value and threat value

路數(shù)己方路的價值對方路的威脅值6路100000010000005路20060004路20060003路40502路20251路11

4.2.1搜索效率實驗

搜索效率包括深度和寬度2個方面。通過深度實驗，分析同等寬度情況下不同搜索深度對搜索效率的影響；通過寬度實驗，分析同等深度情況下不同搜索寬度對搜索效率的影響。

設(shè)置Width=10，采用深度為3、4、5時，全局掃描和局部掃描時間進行對比實驗，各對弈100局，每步的平均搜索時間如圖3所示。由圖3可得，隨著步數(shù)的增加，全局掃描的搜索時間明顯增加，局部掃描卻無明顯變化。隨著搜索深度的增加，局部掃描的搜索效率優(yōu)化愈加明顯。對于第9步，在深度為3、4、5時，全局掃描搜索時間分別為23.030、269.902、640.780s；而局部掃描搜索時間分別為2.010、31.855、36.301s。

圖3　2種掃描方式不同深度的搜索時間對比 Fig.3　Search time two scanning method with different depths

4.2.2博弈水平實驗

設(shè)置Depth=3，全局掃描和局部掃描采用不同寬度對弈，每個寬度對弈100局，博弈水平如圖4所示。局部掃描顯著優(yōu)于全局掃描，Width=20時，局部掃描和全局掃描的對弈勝率是96：4。設(shè)置Width=10，全局掃描和局部掃描采用不同深度對弈，各深度對弈100局博弈水平如圖6所示。在同等條件下，局部掃描的搜索深度增加，博弈水平遠遠超過全局掃描。在Depth=5時，局部掃描和全局掃描的對弈勝率是95：5。因為隨著深度增加，搜索層次越大，葉子節(jié)點越接近末端節(jié)點，越提高獲勝幾率。

圖4　2種掃描方式在不同寬度的博弈結(jié)果 Fig.4　Game results with different widths

圖5　2種掃描方式在不同深度的博弈結(jié)果 Fig.5　Game results with different depths

5結(jié)束語

本文將優(yōu)化后的掃描方式應(yīng)用到六子棋博弈中，從搜索效率和博弈水平2個角度評價，相對于全局掃描，局部掃描大幅度提高搜索效率，博弈水平也有明顯提高。本文僅在開局和中局采用局部掃描方式，提高搜索效率，如何在殘局階段改進估值提高效率，有待進一步研究。博弈樹生成算法仍存在改進之處，例如估值方法中對于己方“路”的價值和對方“路”的威脅值的分配仍需手動調(diào)整，搜索深度僅到5層，依然未達到理想要求。

參考文獻:

[1]張利群.五道棋計算機博弈程序的設(shè)計與實現(xiàn)[J]. 計算機工程, 2010(10): 227-228, 231.

ZHANG Liqun. Design and realization of Wudao chess computer game program[J]. Computer Engineering, 2010(10): 227-228, 231.

[2]徐長明,馬宗民,徐心和.一種新的連珠棋局面表示法及其在六子棋中的應(yīng)用[J].東北大學學報:自然科學版, 2009(4): 60-63.

XU Changming, MA Zongmin, XU Xinhe. A new board representation method for k-in-a-row games with its application to connect 6[J].Journal Northeastern University: Natural Science, 2009(4): 60-63.

[3]QIAO Zhihua, YANG Ming, WANG Zijuan. Technologies analysis of connect6 computer game[J]. Advanced Materials Research, 2011, 1077 (171) : 679-682.

[4]ZHANG Ruimei, LIU Changcheng, WANG Chuandui. Research on connect 6 programming based on mtd(f) and deeper-always transposition table[C]//2012 IEEE 2nd International Conference on Cloud Computing and Intelligence Systems. [S.l.], 2012: 254-255.

[5]徐長明.基于連珠模式的六子棋機器博弈關(guān)鍵技術(shù)研究[D]. 沈陽: 東北大學, 2010: 15-36.

XU Changming. Research on key technologies of connection-pattern based computer connect 6[D]. Shenyang: Northeastern University, 2010: 15-36.

[6]KNUTH D E, MOORE R W. An analysis of alpha-beta pruning[J]. Artificial Intelligence, 1975, 6(4): 293-326.

[7]李翠珠.六子棋計算機博弈系統(tǒng)的研究與實現(xiàn)[D]. 重慶: 重慶理工大學, 2010: 43-46.

LI Cuizhu. Research and Implementation of the system of connect 6 game[D]. Chongqing: Chongqing University of Technology, 2010: 43-46.

[8]張穎.六子棋啟發(fā)式搜索算法的優(yōu)化與設(shè)計[J]. 西北師范大學學報: 自然科學版, 2008(4): 31-36, 58.

ZHANG Ying. Optimization and design of connect6 heuristic searching algorithm[J]. Journal of Northwest Normal University: Natural Science, 2008(4): 31-36, 58.

[9]黃繼平,苗華,張棟.用遺傳算法實現(xiàn)六子棋評估函數(shù)參數(shù)優(yōu)化[J]. 重慶工學院學報: 自然科學版, 2009(11): 91-95.

HUANG Jiping, MIAO Hua, ZHANG Dong. Optimizing the evaluation function parameters of connect6 with genetic algorithms[J].Journal of Chongqing Institute of Technology: Natural Science, 2009(11): 91-95.

[10]陳光年.基于智能算法的六子棋博弈行為選擇的應(yīng)用研究[D]. 重慶: 重慶理工大學, 2010: 20-25.

CHEN Guangnian. The research and application on the behavior election of connect 6 based on intelligent algorithms[D]. Chongqing: Chongqing University of Technology, 2010: 20-25.

[11]張小川, 陳光年, 張世強, 等.六子棋博弈的評估函數(shù)[J]. 重慶理工大學學報: 自然科學版, 2010(2): 68-72.

ZHANG Xiaochuan, CHEN Guangnian, ZHANG Shiqiang. Research on evaluation functions for computer game of connect6[J]. Journal of Chongqing University of Technology: Natural Science, 2010(2): 68-72.

[12]徐長明, 馬宗民, 徐心和, 等. 面向機器博弈的即時差分學習研究[J]. 計算機科學, 2010(8): 225-229.

XU Changming, MA Zongmin, XU Xinhe. Study of temporal difference learning in computer games[J]. Computer Science, 2010(8): 225-229.

[13]徐心和, 鄧志立, 王驕, 等.機器博弈研究面臨的各種挑戰(zhàn)[J]. 智能系統(tǒng)學報, 2008, 3(4): 10-15.

XU Xinhe, DENG Zhili, WANG Jiao， et al. Challenging issues facing computer game research[J]. CAAI Transactions on Intelligent Systems, 2008, 3(4): 10-15.

[14]閔文杰. 六子棋計算機博弈關(guān)鍵技術(shù)研究[D]. 重慶:重慶交通大學, 2010: 12-18.

MIN Wenjie. Research on the key technologies of the connect 6 computer game[D]. Chongqing: Chongqing Jiaotong University, 2010: 12-18.

[15]MARTIN K, SVEN S, RAINER H. Improved tree-based strategies for a connect 6 threat-based hardware design[C]//2013 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM). [S.l.], 2013: 32-36.

[16]張明亮,吳俊,李凡長.五子棋機器博弈系統(tǒng)評估函數(shù)的設(shè)計[J]. 計算機應(yīng)用, 2012(7): 189-192, 210.

ZHANG Mingliang, WU Jun, LI Fanchang. Design of evaluation function for computer gobang game system[J]. Journal of Computer Applications, 2012(7): 189-192, 210.

李學俊，男，1976年生，副教授，中國人工智能學會機器博弈專業(yè)委員會理事，主要研究方向為智能軟件、云工作流。

王小龍，男，1989年生，碩士，主要研究方向為機器博弈。

吳蕾，女，1978年生，講師，博士研究生，中國人工智能學會機器博弈專業(yè)委員會理事，主要研究方向為機器博弈，軟件測試。