開局庫在點格棋計算機博弈系統(tǒng)中的應(yīng)用

北京信息科技大學(xué)計算機學(xué)院 靳淑嫻 高銘 王修鍇

計算機博弈，是人工智能領(lǐng)域的一個重要研究方向。在點格棋計算機博弈的過程中，由于開局可能著法較多、計算量巨大，在開局階段往往會花費大量的時間，為了解決這一問題，我們將開局庫技術(shù)應(yīng)用到點格棋的計算機博弈中。利用對局數(shù)據(jù)庫生成方法，在UCT算法的基礎(chǔ)上，我們生成了點格棋的開局庫，與未采用開局庫策略的點格棋博弈程序?qū)暮螅〉昧嗣黠@的優(yōu)勢。實驗結(jié)果表明，應(yīng)用了開局庫策略的點格棋博弈程序具有較強的棋力和較高的計算效率。

開局庫是棋類軟件的組件之一，其中包括著與開局有關(guān)的數(shù)據(jù)庫。開局庫相關(guān)技術(shù)主要應(yīng)用在象棋計算機博弈系統(tǒng)中，目前已經(jīng)建立了基于SQL Server數(shù)據(jù)庫技術(shù)的中國象棋開局庫[1]，在四國軍棋的計算機博弈領(lǐng)域也有著定式庫的相關(guān)應(yīng)用[2]。在點格棋計算機博弈的過程中，由于開局可能著法較多、計算量巨大，在開局階段往往會花費大量的時間，開局庫策略有助于改善這一狀況，而在點格棋的計算機博弈領(lǐng)域，目前僅僅存在簡單的鏡像開局庫策略的相關(guān)研究[3]。為了解決這一問題，我們參考中國象棋和國際象棋的成熟的開局庫技術(shù)[4-6]，設(shè)計開發(fā)點格棋博弈系統(tǒng)的開局庫，在點格棋計算機博弈系統(tǒng)中應(yīng)用開局庫技術(shù)。

1 點格棋研究現(xiàn)狀

1.1 點格棋規(guī)則簡介

全國大學(xué)生計算機博弈大賽中規(guī)定了點格棋項目的比賽規(guī)則：

（1）N×N的點格棋的棋盤是由N×N個等距的點陣構(gòu)成的。全國計算機博弈大賽規(guī)定采用6×6的點格棋盤。

（2）博弈雙方通過輪流將橫向或者豎向上相鄰兩點相連來進行占邊操作（不可以跨越點，不可以重復(fù)占邊）。

（3）當某一格子四條邊都被某一方連線后，占領(lǐng)格子最后那一條邊的玩家得到這個格子。

（4）玩家占領(lǐng)格子后，可以繼續(xù)進行一次占邊。

（5）當棋盤上的所有格子都被占領(lǐng)后，則游戲結(jié)束，占領(lǐng)格子數(shù)多者獲得勝利。

由于6×6的點格棋有5×5即25個格子，所以6×6點格棋是一定可以分出勝負的。

一個6×6的點格棋棋盤如圖1所示：

圖1 6×6點格棋棋盤Fig.1 A 6×6 board of dots-and-boxes

1.2 點格棋常用算法

點格棋的博弈系統(tǒng)主要由搜索算法和估值函數(shù)這兩部分組成。點格棋博弈搜索算法主要有alpha-beta剪枝搜索算法、UCT搜索算法等[7-9]。UCT（UCB applied to Tree）搜索算法[10-11]是近幾年來在計算機博弈中采用最多的一種算法，有著搜索效率較高、搜索時間可控的特點。UCT算法是一種將蒙塔卡羅搜索樹（Monte-Carlo Tree Search），簡稱MCTS，方法與UCB公式進行結(jié)合的博弈樹搜索算法。MCTS算法通過大量隨機模擬，建立博弈樹概率模型進行在線搜索，而UCB公式，用來在每個局面狀態(tài)節(jié)點處有傾向地選擇分支節(jié)點。

UCT算法的搜索過程，如圖2所示，共分為四個階段，即選擇（Selection）、拓展（Expansion）、模擬（Simulation）和回溯（Backpropagation）。

圖2 UCT的搜索過程：選擇、拓展、模擬、回溯Fig.2 The search process of UCT: selection, expansion, simulation, backpropagation

（1）選擇：根據(jù)UCB公式，通過遞歸的方式對不同分支進行選擇，一直到達博弈樹的葉子節(jié)點。UCB公式如公式（1）所示。

其中，wi表示特定局面下第i個分支所有模擬中當前玩家的勝利次數(shù)，ni表示特定局面下第i個分支模擬的總次數(shù)，N表示特定局面下所有分支的模擬總次數(shù)，c表示探索的傾向參數(shù)，通常被設(shè)置為。

（2）拓展：當?shù)竭_葉節(jié)點之后，以此局面為基礎(chǔ)，計算該葉子節(jié)點所代表局面下的所有的合法動作，選擇其中的一個節(jié)點進行拓展，生成該節(jié)點的子節(jié)點，并將其添加到搜索樹中。

（3）模擬：從新擴展的節(jié)點處開始模擬博弈的過程，直到博弈結(jié)束為止，記錄博弈的結(jié)果。

（4）回溯：模擬結(jié)束后，根據(jù)模擬的博弈結(jié)果向上回溯并更新該路徑上所有節(jié)點的訪問次數(shù)和收益情況信息。

2 開局庫研究現(xiàn)狀

點格棋的博弈過程一般可以分為開局、中局和殘局三個階段[12]。開局庫是存儲開局著法的數(shù)據(jù)文件或者數(shù)據(jù)庫。通過開局庫，可以把一些比較好的開局存儲起來，在開局時，用查詢數(shù)據(jù)庫的方法來代替搜索和評估，可以提高計算機在開局時的對弈水平并減少運算時間。優(yōu)秀的棋類博弈系統(tǒng)，基本上都擁有自己的開局庫。

2.1 由脫離棋譜的拓展自動生成

脫離棋譜的拓展[4]即DOE（Drop-out Expansion）是由Thomas Lincke發(fā)明的，在西洋跳棋中取得了比較大的成功。該方法在建立開局庫時，對于一些好的著法進行擴展，然后在擴展后的局面繼續(xù)，通過擴展后的局面來判斷先前著法的優(yōu)劣。該方法會有一個優(yōu)先函數(shù)，對每個可能的路徑給出優(yōu)先值，對優(yōu)先值較高的路徑的葉子節(jié)點進行擴展。采用這種開局庫的程序一般只會走開局庫中好的著法，所以當在遇到不恰當?shù)木置鏁r往往表現(xiàn)很糟糕。

2.2 由對局數(shù)據(jù)庫生成

生成開局庫最簡單的方法就是找到或者創(chuàng)建一個對局數(shù)據(jù)庫，根據(jù)對局數(shù)據(jù)庫中對局的最終結(jié)果選擇比較可靠的著法。對于每個局面，可以生成所有著法的統(tǒng)計數(shù)字，例如，采用這步著法的最終勝率，使用開局庫時可以根據(jù)數(shù)據(jù)來選擇最佳著法。對于人類非常精通的棋類,例如，中國象棋、國際象棋等，可以手工整理高質(zhì)量的高手對弈的棋譜收錄到開局庫中，而點格棋目前還不存在現(xiàn)有的高質(zhì)量開局庫，所以需要利用數(shù)據(jù)庫自動生成。

2.3 鏡像開局庫策略

鏡像開局庫策略[3]是一種較為特殊的開局庫策略，它通過模擬對方的落子，將對方落子進行鏡像，重現(xiàn)對方的開局。這種策略在面對實力較強的對手時，可以學(xué)習(xí)對手的開局來增加自己的開局信息，避免在前中期開局不利的情況。

3 點格棋開局庫的設(shè)計與實現(xiàn)

3.1 開局庫生成策略

我們選擇利用對局數(shù)據(jù)庫的方法來生成點格棋的開局庫。可以用來判斷著法優(yōu)劣的相關(guān)標準有：

（1）一個著法被人采用的次數(shù)越多，著法就越好。

（2）棋力較高的棋手/博弈程序的著法更好。

（3）通過對局結(jié)果獲勝的一方著法更好。

結(jié)合以上因素，我們選擇將勝率作為判斷著法優(yōu)劣的標準。由于空間有限，且勝率較小的局面存儲價值不大，所以我們通過設(shè)置勝率的閾值來篩選錄入開局庫的局面。為了開局庫的生成與局面的查詢與匹配，我們將開局庫分為先手開局庫與后手開局庫。在實際實驗中，我們選取了1000個對局棋譜，設(shè)定第1～10步為開局階段，則產(chǎn)生10×1000=10000個（包含重復(fù)局面）局面，分別為先手局面5000個，后手局面5000個，設(shè)置勝率閾值為40%，通過計算不同局面的勝率，對局面篩選并去重，我們得到最終的開局庫。

3.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計

由于開局僅為棋局的前10步，如果記錄所有邊的被占有信息時沒有必要的，所以我們選擇按照從左到右、從上到下的順序，記錄被占領(lǐng)的邊的信息來表示局面。我們假設(shè)開局時沒有格子被占領(lǐng)的（通常在開局中是沒有格子被占領(lǐng)的），而邊被占有后是屬于共有的邊，所以我們不記錄某邊是被博弈的哪一方所占領(lǐng)。而某一條被占邊的信息我們用三個連續(xù)的數(shù)字表示，即公式（2）所示。

其中，Direction代表該邊方向（0為橫向，1為豎向），X代表該邊所在橫坐標（1～6），Y代表該邊所在豎坐標（1～6）。

4 實驗結(jié)果與分析

為了驗證本文研究的開局庫策略的有效性，將該策略與不采用開局庫策略的蒙特卡洛算法進行博弈測試，棋盤大小為6×6，采用前面提到的點格棋項目規(guī)則，計時方式為包干計時15分鐘。6×6的點格棋棋盤共有60條邊，我們假設(shè)一方走三十步（可能有一方得到棋子后連走的情況，所以實際上的走棋一般達不到30步），所以將單步時限設(shè)為15分鐘/30步，即單步時限為30秒。由于開局庫查詢所需時間較少，所以對于采用開局庫策略的程序，我們將開局后的單步時限調(diào)整為35秒。該測試硬件環(huán)境為：Intel Core i7-1165G7，主頻2.80GHz。測試結(jié)果如表1，表2，表3所示。

表1 采用開局庫策略先手Tab.1 Use-opening-book first

表2 不采用開局庫策略先手Tab.2 Nonuse-opening-book first

表3 總對弈結(jié)果Tab.3 The total result

由表1、表2、表3可以得出，采用開局庫策略的程序的勝率明顯比未采用的程序更高。

5 結(jié)語

計算機博弈是一個復(fù)雜又具有挑戰(zhàn)性的課題，對于博弈論的學(xué)習(xí)和研究具有很深遠的意義。本文在點格棋蒙塔卡羅搜索樹算法的基礎(chǔ)上，運用了開局庫策略，創(chuàng)建了點格棋的開局庫并與未采用開局庫策略的點格棋博弈程序進行對弈，由實驗結(jié)果，我們可以看出，開局庫策略取得了一定的效果。

此次研究雖然小有成果，但開局庫在點格棋方面運用的經(jīng)驗與知識與中國象棋、國際象棋等棋類相比十分缺少，我們通過對其他棋類開局庫研究的借鑒與自己的探索，對點格棋的開局庫策略有了初步的研究成果，但仍存在一些不足有待進一步的改進和研究，受各種條件限制，所建立的開局也并不完整，期待日后能夠進一步研究，盡量開發(fā)出更加精確和完善的開局庫。