王鴻菲　王靜文　李媛

摘要：針對(duì)六子棋比賽中基于棋型分析的評(píng)估函數(shù)比較復(fù)雜，因此搜索效率大大降低，六子棋是一種復(fù)雜度與象棋相當(dāng)?shù)牟┺挠螒?。其?fù)雜性主要是平均分枝因子大，導(dǎo)致博弈樹(shù)搜索的深度太淺。本文采用了PVS搜索算法，通過(guò)縮小搜索范圍，從而有效增加剪枝效率，同時(shí)結(jié)合了迭代深化和歷史啟發(fā)增強(qiáng)及置換表和哈希表技術(shù)，極大提高了搜索效率和深度。使用該技術(shù)開(kāi)發(fā)的六子棋系統(tǒng)，其博弈水平得到了有效提高。

關(guān)鍵詞：六子棋;PVS;路;歷史啟發(fā)增強(qiáng);迭代加深;置換表

【Abstract】TheevaluationfunctionbasedonchesstypeanalysisiscomplexinthegameofConnect6，sothesearchefficiencyisgreatlyreduced.Thecomplexityismainlyduetothelargeaveragebranchingfactor，whichleadstotheshallowdepthofgametreesearch.Inthispaper，PVSsearchalgorithmisusedtoreducethesearchscope，soastoeffectivelyincreasethepruningefficiency.Atthesametime，thecombinationofiterativedeepening，historicalheuristicenhancement，replacementtableandHashtabletechnologygreatlyimprovethesearchefficiencyanddepth.ThegamelevelofConnect6systemdevelopedbythistechnologyhasbeeneffectivelyimproved.

【Keywords】Connect6;PVS;road;historicalheuristicenhancement;iterativedeepening;Hash

作者簡(jiǎn)介：王鴻菲（1999-），男，本科生，主要研究方向：計(jì)算機(jī)博弈;王靜文（1965-），男，工程師，主要研究方向：人工智能和信息安全;李媛（1976-），女，博士后，教授，主要研究方向：人工智能和隨機(jī)過(guò)程。

0引言

機(jī)器博弈是人工智能研究中極具挑戰(zhàn)性的重要課題之一，其技術(shù)進(jìn)步則為人工智能領(lǐng)域的研究融匯了為數(shù)可觀的理論和方法，對(duì)社會(huì)及學(xué)術(shù)方面產(chǎn)生了廣泛而深遠(yuǎn)的影響。機(jī)器博弈并不是如人們?cè)O(shè)想的那樣只是人和計(jì)算機(jī)間簡(jiǎn)單的下棋小游戲，而是通過(guò)這種競(jìng)爭(zhēng)性的活動(dòng)來(lái)檢驗(yàn)人工智能成果是否達(dá)到了人的智能水平。在社會(huì)的日常生活中經(jīng)常面臨著決策問(wèn)題，而建立和選擇決策的過(guò)程便是計(jì)算機(jī)博弈研究關(guān)注的內(nèi)容，所以在智能決策、沙盤(pán)推演等場(chǎng)景中均有著現(xiàn)實(shí)應(yīng)用意義。

由于六子棋的棋盤(pán)與圍棋棋盤(pán)相同[1]，并有與圍棋有著相同的狀態(tài)空間復(fù)雜度，吸引了越來(lái)越多的計(jì)算機(jī)博弈愛(ài)好者對(duì)六子棋的關(guān)注。本文擬對(duì)此展開(kāi)研究論述如下。

1六子棋簡(jiǎn)介

六子棋是近些年新興起的棋類(lèi)博弈項(xiàng)目，是國(guó)立交通大學(xué)吳毅成教授提出的“連K”系列棋之一[2]。對(duì)其特點(diǎn)可概述為：

（1）規(guī)則簡(jiǎn)單，六子棋有黑白兩方，黑方先落子。黑方第一步下一顆子，隨后黑白雙方輪流落兩子。連成六子或以上獲勝。沒(méi)有禁手，長(zhǎng)連即連成六子以上也為贏，如果棋盤(pán)被下滿(mǎn)時(shí)仍未分出勝負(fù)則算和棋，若不同意和棋，也可按照存在五連的數(shù)量來(lái)定勝負(fù)，減少和棋局面的出現(xiàn)。六子棋的標(biāo)準(zhǔn)棋盤(pán)如圖1所示。

（2）變化復(fù)雜。對(duì)于機(jī)器博弈來(lái)說(shuō)，一般采用狀態(tài)空間復(fù)雜度和博弈樹(shù)復(fù)雜度來(lái)衡量某種博弈游戲的復(fù)雜程度。狀態(tài)空間復(fù)雜度，指的是從游戲最開(kāi)始的狀態(tài)可以變化出的符合規(guī)則的狀態(tài)的數(shù)量[3]。在六子棋的對(duì)弈過(guò)程中的每一個(gè)局面都對(duì)應(yīng)一個(gè)節(jié)點(diǎn)，而一個(gè)節(jié)點(diǎn)下面又有很多子節(jié)點(diǎn)，所以不斷地向下推演就可以建立整個(gè)博弈樹(shù)，直至得到博弈結(jié)果。但得到的博弈樹(shù)是巨大的，隨著不斷地加深，子節(jié)點(diǎn)將以幾何方式上升。常見(jiàn)棋類(lèi)的復(fù)雜度對(duì)比見(jiàn)表1。

從表1中可以看到，六子棋比五子棋的復(fù)雜度高[4-5]，和象棋差不多或略高一點(diǎn)。

（3）游戲公平。由于各方每次下完一手后，盤(pán)面都比對(duì)方多一子，因此賽局自然達(dá)成平衡的狀態(tài)，這大大提升了六子棋的公平性。不像許多棋種、如五子棋、象棋、國(guó)際象棋，先下者會(huì)占據(jù)一些優(yōu)勢(shì)。

2六子棋博弈系統(tǒng)

計(jì)算機(jī)博弈游戲的核心由搜索和估值兩部分組成。其中，估值是用于準(zhǔn)確地評(píng)價(jià)當(dāng)前局面，而搜索則是根據(jù)當(dāng)前局面獲得最佳下法。這里將給出探討分述如下。

2.1估值函數(shù)

在博弈比賽的對(duì)弈中，如果將棋局的所有狀態(tài)都列舉出來(lái)，就一定可找到最佳的走法，但是對(duì)于博弈來(lái)說(shuō)，這種做法不僅是無(wú)意義的，對(duì)于大部分棋種也是不可行的。因此對(duì)博弈樹(shù)的窮舉搜索必須適可而止，由此可知研究中搜索的深度是有限的，即可根據(jù)在一定深度處的節(jié)點(diǎn)的估計(jì)值來(lái)評(píng)分，就是估計(jì)值代替實(shí)際的搜索，這就叫做估值函數(shù)。不管對(duì)黑方、還是白方，都是利于對(duì)博弈樹(shù)進(jìn)行捜索找到最佳走法的。如果不能窮舉所有走法，就只能在搜索到一定層后，根據(jù)對(duì)局面的估值來(lái)判斷路徑的好壞，此時(shí)就要設(shè)計(jì)出評(píng)估函數(shù)來(lái)對(duì)局面進(jìn)行估值。估值方法往往和具體的棋類(lèi)規(guī)則結(jié)合緊密，這在很大程度上決定了博弈程序的棋力高低[6]。研究時(shí)，既可以向估值函數(shù)寫(xiě)入棋類(lèi)知識(shí)，使程序?qū)τ诰置娴脑u(píng)估更為精確，也可以寫(xiě)出簡(jiǎn)化的估值函數(shù)，使估值的過(guò)程簡(jiǎn)捷、且節(jié)省運(yùn)算時(shí)間，期望通過(guò)更深的搜索提高棋力。

目前，六子棋普遍采用2種估值方式。一種是基于“路”的方式進(jìn)行估值，另一種就是基于“棋型”的方式進(jìn)行估值。這里，基于“路”或基于“棋型”，則是指根據(jù)路或棋型的方式對(duì)棋盤(pán)進(jìn)行掃描。

需要指出的是，在基于棋型的估值中，由于目前常見(jiàn)的10種棋型都是通過(guò)經(jīng)驗(yàn)總結(jié)的，主觀因素影響較大，可能存在未定義的其他棋型。同時(shí)因?yàn)橥环N棋型也有多種可下位置。

所以棋形判斷的復(fù)雜度高，計(jì)算量大，受計(jì)算機(jī)博弈比賽中六子棋博弈時(shí)間的約束，搜索的深度和寬度都會(huì)受到限制。故而本文提出基于路的估值方法，相對(duì)于基于棋型的估值較為簡(jiǎn)單，實(shí)現(xiàn)上較為容易，搜索時(shí)間也較短，更適合在在博弈比賽中付諸應(yīng)用。

基于路的估值，在一個(gè)棋盤(pán)中，將路分為6種，掃描連續(xù)的同一條直線上的6個(gè)不同的位置，再對(duì)同一個(gè)顏色的棋子進(jìn)行計(jì)數(shù)，從而判斷為幾路。因此可以計(jì)算出一個(gè)棋盤(pán)有：水平方向?yàn)?9×14=266;豎直方向?yàn)?9×14=266;

左斜方向14×14=196;右斜方向14×14=196，所以一共有294路。本文采用了4個(gè)方向的函數(shù)實(shí)現(xiàn)路的掃描。研究后推得AnalysisRight主要偽碼可表示如下：

IntAnalysisRight（charposition[19]，inti，intj）{

chartempArray[19];

intx;

inty;

intrealnum;

if（18-j

y=18;

x=j-18+i;

}

else{

x=0;

y=i+j;

}

intg=0;

for（intk=0;k<19;k++）{

if（x+k>18||y-k<0）{

break;

}

tempArray[k]=position[x+k][y-k];

g++;

}

AnalysisLine（tempArray，g，y-j）;

for（ints=0;s

if（m_LineRecord[s]！=WEIFANGWEN）{

TypeRecord[x+s][y-s][3]=

m_LineRecord[s];

}

}

returnTypeRecord[i][j][3];

}

其它各個(gè)方向上的計(jì)算方法和上述偽碼的計(jì)算方法相同。文中不再做過(guò)多贅述。

2.2基于PVS的搜索算法

六子棋的復(fù)雜度高，一般的搜索算法難以達(dá)到較高的搜索效率。目前，常用的方法有alpha-beta算法、UCTS算法等[7]。其中，alpha-beta算法在經(jīng)過(guò)剪枝處理后，卻仍然還是存在大量的節(jié)點(diǎn)需要去遍歷，搜索效率較低;UCTS算法可以達(dá)到較好的搜索深度，但得到的估值準(zhǔn)確性較低。

本文的搜索算法是基于PVS算法。PVS算法，也稱(chēng)最小窗口搜索算法，是由alpha-beta變形而來(lái)。兩者間的主要區(qū)別就在于：除了主變量外的其它節(jié)點(diǎn)都進(jìn)行零窗口搜索，并且把α的值復(fù)制為β的值，通常情況下都是把每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)進(jìn)行排序，同時(shí)假設(shè)第一個(gè)節(jié)點(diǎn)是最好的，作為主變量，進(jìn)行全窗口搜索。通過(guò)零窗口搜索，判斷是否存在αβ的值，在此基礎(chǔ)上進(jìn)行博弈樹(shù)的剪枝。其中，對(duì)節(jié)點(diǎn)進(jìn)行排序是該算法至為關(guān)鍵的一步，這樣大大提高了搜索效率。所以本文采用了置換表和哈希表、歷史啟發(fā)增強(qiáng)、迭代深化等方法，極大地提高了算法的搜索效率[8]。

在搜索過(guò)程中，還增加了置換表和哈希表，如果計(jì)算過(guò)的價(jià)值，將會(huì)加入Hash表，并通過(guò)查找的方法判斷是否存在，如果存在就直接調(diào)用價(jià)值，這樣也大大加快了搜索過(guò)程;采用了歷史啟發(fā)方法增強(qiáng)通過(guò)已有的節(jié)點(diǎn)評(píng)分可更好地進(jìn)行排序[9]，價(jià)值高的節(jié)點(diǎn)排在前面，極大提高了搜索效率;與此同時(shí)，還通過(guò)迭代深化來(lái)加快節(jié)點(diǎn)排序的過(guò)程，過(guò)程中也一并進(jìn)行時(shí)間的控制。在此基礎(chǔ)上，改進(jìn)的PVS算法的偽碼參見(jiàn)如下。

FunctionPVS（intdepth，intalpha，intbeta）{

if（depth<=0）

returnvalue（）

generateAllMove（）

sort（）

makeMove（）

best=-PVS（depth-1，-beta，-alpha）

unMakeMove（）

for（movei=1tomove.size（））

if（best

if（best>alpha）

alpha=best

makeMove（）

v=-PVS（depth-1，-alpha-1，-alpha）

if（valpha）

best=-PVS（depth-1，-beta，-v）

if（v>best）

best=v

unMakeMove（）

returnbest

}

3實(shí)驗(yàn)與結(jié)果

針對(duì)六子棋的估值設(shè)計(jì)和搜索算法，分別設(shè)計(jì)針對(duì)估值方法的對(duì)比和針對(duì)搜索方法的對(duì)比實(shí)驗(yàn)。并分別使用先手和后手進(jìn)行測(cè)試。

針對(duì)評(píng)估函數(shù)，主要比較了基于“路”的評(píng)估方法和基于棋型的評(píng)估方法，其對(duì)比結(jié)果見(jiàn)表2。

由表2可以看出，在相同的對(duì)弈時(shí)間下，基于路的估值方法與基于棋型的估值方法相比較來(lái)說(shuō)具有明顯的優(yōu)勢(shì)。

PVS算法與alpha-beta算法的對(duì)比結(jié)果見(jiàn)表3。

PVS算法與UCTS算法的對(duì)比結(jié)果見(jiàn)表4。

由表3和4可知，與alpha-beta算法和UCTS算法相比，PVS算法在棋力上占有一定的優(yōu)勢(shì)，無(wú)論是先手、還是后手，PVS的勝率都在85%以上。同時(shí)，因?yàn)殡p方都使用相同的估值函數(shù)，從棋力方面說(shuō)明PVS算法更適合六子棋。

4結(jié)束語(yǔ)

本文針對(duì)PVS算法與alpha-beta算法和UCTS算法的對(duì)弈比較進(jìn)行研究，結(jié)果表明PVS算法相較另外兩種算法在公平條件下有更好的搜索效率，在限制時(shí)間的博弈比賽中有更好的優(yōu)勢(shì)。同時(shí)，加入置換表和哈希表、歷史啟發(fā)增強(qiáng)、迭代深化等方法提高了PVS算法的搜索效率，而結(jié)合基于路的估值函數(shù)則極大地提高了分支的選擇效率。利用本文提出的算法開(kāi)發(fā)的六子棋博弈程序獲得了2020年遼寧省大學(xué)生計(jì)算機(jī)博弈競(jìng)賽六子棋項(xiàng)目冠軍，進(jìn)一步驗(yàn)證了該算法的有效性。

參考文獻(xiàn)

[1]鄧超.計(jì)算機(jī)圍棋中的搜索算法研究[D].昆明：昆明理工大學(xué)，2013.

[2]WUIC，YENSJ.NCTU6winsConnect6tournament[J].InternationalClassicGuitarAssociation（ICGA）Journal，2006（3）：157-158.

[3]王靜文，吳曉藝.全國(guó)大學(xué)生計(jì)算機(jī)博弈大賽培訓(xùn)教程[M].北京：清華大學(xué)出版社，2013.

[4]王亞杰，邱虹坤，吳燕燕，等.計(jì)算機(jī)博弈的研究與發(fā)展[J].智能系統(tǒng)學(xué)報(bào)，2016，11（6）：788-798.

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

[6]何軒，洪迎偉，王開(kāi)譯，等.機(jī)器博弈中搜索策略和估值函數(shù)的設(shè)計(jì)—以六子棋為例[J].電腦知識(shí)與技術(shù)，2019，15（34）：53-54，61.

[7]李學(xué)俊，王小龍，吳蕾，等.六子棋中基于局部“路”掃描方式的博弈樹(shù)生成算法[J].智能系統(tǒng)學(xué)報(bào)，2015，10（2）：267-272.

[8]徐長(zhǎng)明，馬宗民，徐心和.一種新的連珠棋局面表示法及其在六子棋中的應(yīng)用[J].東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，30（4）：514-517.

[9]YANGXue，LIHuayu，JIANGTianbo.Alpha-Beta-TSSinConnect6[C]//第27屆中國(guó)控制與決策會(huì)議.中國(guó)，青島：《控制與決策》編輯部，2015：746-751.