開局庫在點格棋計算機博弈系統中的應用

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

計算機博弈，是人工智能領域的一個重要研究方向。在點格棋計算機博弈的過程中，由于開局可能著法較多、計算量巨大，在開局階段往往會花費大量的時間，為了解決這一問題，我們將開局庫技術應用到點格棋的計算機博弈中。利用對局數據庫生成方法，在UCT算法的基礎上，我們生成了點格棋的開局庫，與未采用開局庫策略的點格棋博弈程序對弈后，取得了明顯的優勢。實驗結果表明，應用了開局庫策略的點格棋博弈程序具有較強的棋力和較高的計算效率。

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

1 點格棋研究現狀

1.1 點格棋規則簡介

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

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

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

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

（4）玩家占領格子后，可以繼續進行一次占邊。

（5）當棋盤上的所有格子都被占領后，則游戲結束，占領格子數多者獲得勝利。

由于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 點格棋常用算法

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

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

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

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

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

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

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

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

2 開局庫研究現狀

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

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

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

2.2 由對局數據庫生成

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

2.3 鏡像開局庫策略

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

3 點格棋開局庫的設計與實現

3.1 開局庫生成策略

我們選擇利用對局數據庫的方法來生成點格棋的開局庫。可以用來判斷著法優劣的相關標準有：

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

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

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

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

3.2 數據結構設計

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

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

4 實驗結果與分析

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

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

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

表3 總對弈結果Tab.3 The total result

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

5 結語

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

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