倪錦園 張建勛

DOI：10.19850/j.cnki.2096-4706.2021.09.021

摘? 要：計算機(jī)博弈是當(dāng)前人工智能領(lǐng)域的主要研究方向。在點格棋計算機(jī)博弈的過程中，搜索引擎在開局階段會花費大量的時間，搜索出來的節(jié)點不夠優(yōu)秀，由此造成整體棋力不夠強(qiáng)。為了解決此問題，該文設(shè)計了一種結(jié)合開局庫策略的MiniMax算法，并將此算法作為整顆博弈樹的搜索引擎，以強(qiáng)化計算機(jī)的算力，提高程序的整體效率。實驗結(jié)果表明，該文提出的搜索引擎具有更高的準(zhǔn)確率和更好的魯棒性。

關(guān)鍵詞：計算機(jī)博弈;蒙特卡洛;開局庫;MiniMax

中圖分類號：TP311.5 文獻(xiàn)標(biāo)識碼：A 文章編號：2096-4706（2021）09-0078-05

Design and Implementation of Dots and Boxes Computer Gaming System

NI Jinyuan，ZHANG Jianxun

（School of Computer Science and Engineering，Chongqing University of Technology，Chongqing? 400054，China）

Abstract：Computer gaming is the main research direction in the field of artificial intelligence at present. In the process of dots and boxes computer gaming，the search engine will spend a lot of time in the opening stage，and the searched nodes are not good enough，resulting in the overall chess power is not strong enough. In order to solve this problem，this paper designs a MiniMax algorithm combined with opening library strategies，and uses this algorithm as the search engine of the whole gaming tree，so as to strengthen the computing power of the computer and improve the overall efficiency of the program. Experimental results show that the proposed search engine in this paper has higher accuracy and better robustness.

Keywords：computer gaming;Monte Carlo;opening library;MiniMax

0? 引? 言

計算機(jī)博弈是一個充滿著智慧和無限挑戰(zhàn)的科學(xué)領(lǐng)域^[1-3]，它主要研究的是讓機(jī)器模擬人類思考的過程，并通過更加強(qiáng)大的計算能力來獲得更好的運算結(jié)果。筆者曾參加全國大學(xué)生計算機(jī)博弈大賽，獨立設(shè)計并開發(fā)了點格棋計算機(jī)博弈系統(tǒng)，并于比賽中取得二等獎的成績。在計算機(jī)博弈領(lǐng)域中，點格棋屬于零和完全信息博弈^[4]，由11×11大小的棋盤組成。對于計算機(jī)的搜索計算量，這個數(shù)據(jù)量非常龐大，構(gòu)造一顆完整的博弈樹，則需要1111數(shù)量級的空間大小，這對計算機(jī)的空間要求是十分高的。因此在點格棋博弈項目上探索一種好的搜索引擎是非常困難的。目前對于點格棋博弈研究主要用蒙特卡洛算法配合估值函數(shù)作為搜索引擎，但由于在前中期搜索節(jié)點會花費大量的時間，且搜索出來的節(jié)點不是很好，導(dǎo)致點格棋的棋力難以得到較大提升^[5-7]。

針對以上問題，該文設(shè)計了一種結(jié)合開局庫策略的MiniMax算法作為搜索引擎，通過不同的開局庫策略讓己方棋子在博弈開局階段處于優(yōu)勢地位，在中期階段通過MiniMax算法和經(jīng)驗搜索布局來進(jìn)行落子，在博弈雙方進(jìn)入終局階段后，如果雙方的棋局進(jìn)入我方終局必贏策略，此時程序?qū)⒅苯诱{(diào)用終局庫，勝率會達(dá)到100%。

1? 點格棋計算機(jī)博弈規(guī)則

點格棋計算機(jī)博弈系統(tǒng)的規(guī)則是根據(jù)全國大學(xué)生計算機(jī)博弈大賽的規(guī)則制定的，詳細(xì)的規(guī)則為：

（1）雙方輪流將兩個相鄰的點連接成一條邊，不可以超越兩個臨近點，不可以填充重復(fù)的邊，不可以連接一個格子的對角線。

（2）邊屬于雙方共有，只討論格子的所屬。

（3）當(dāng)某一個格子的四條邊都被連成線時，占領(lǐng)最后一條邊的玩家擁有這個格子。

（4）占領(lǐng)格子后有一個獎勵邊，該玩家必須再下一步。

（5）格子全部圍成后，博弈結(jié)束，占領(lǐng)格子較多的一方為獲勝方。

一個11×11點格棋棋盤如圖1所示。

2? 算法介紹

2.1? MiniMax算法設(shè)計

對于很多十分復(fù)雜的棋局，有一個好的搜索算法和一個完善的估值函數(shù)可以很大程度上搜索到當(dāng)前局面的最佳走步。MiniMax算法就是一種可以找出最優(yōu)解的算法，屬于零和博弈的一種。目的是讓己方以優(yōu)勢最大的方式去落子，讓對方以優(yōu)勢最小的方式去落子，其總和為0，如同此消彼長的能量守恒。更進(jìn)一步解釋，博弈樹的層次也分為奇偶層，對于落子的一方來說，其中的最優(yōu)走步就是在他下一層節(jié)點的最優(yōu)來選擇，如果這個估值的選擇上我方可以得到最大的收益的話，這個搜索就為“Max搜索”，同時這個估值對于對方來說是最小收益的話，這個搜索就是“Min搜索”^[8]。

對于不同局面時，都能夠以當(dāng)前局面作為根節(jié)點，然后以該根節(jié)點建立一顆深度固定的博弈搜索樹，博弈樹出度為0的位置作為葉子節(jié)點，葉子節(jié)點的位置也就是當(dāng)前落子的位置，但由于計算機(jī)內(nèi)存硬件有限，在博弈前中期搜索過程中很難搜索到葉子節(jié)點，一般通過人為設(shè)置每步落子的搜索時間或者博弈樹迭代深度來控制落子。

極大極小算法的偽代碼示例程序為：

01 maxmin（player， cur_node）

02? ? ?if depth = 0 or node is a terminal node

03? ? ? ? ?return the heuristic value of nod

04? ? ?if maxPlayer

05? ? ? ? ?bestValue ：= -∞

06? ? ? ? ?for each child of node

07? ? ? ? ? ? ?v ：= minimax（child， depth - 1， FALSE）

08? ? ? ? ? ? ?bestValue ：= max（bestValue， v）

09? ? ? ? ?return bestValue

10? ? ?else miniPlayer

11? ? ? ? ?bestValue ：= +∞

12? ? ? ? ?for each child of node

13? ? ? ? ? ? ?v ：= minimax（child， depth - 1， TRUE）

14? ? ? ? ? ? ?bestValue ：= min（bestValue， v）

15? ? ? ? ?return bestValue

在棋盤大小為11×11的點格棋博弈過程中，由于需要1111數(shù)量級的空間大小，一般計算機(jī)難以達(dá)到這個量級的搜索量，所以通過限制搜索層數(shù)或者限制搜索時間，利用MiniMax算法搜索得出最佳的落子，因此無論是時間上還是空間上，此方法都是可行的。

2.2? MiniMax類設(shè)計

該文設(shè)計的MiniMax類如表1所示。

MiniMax類中的部分屬性如表2所示。

MiniMax類中的部分方法如表3所示。

2.3? MiniMax搜索流程圖

整顆博弈樹通過MiniMax配合估值函數(shù)進(jìn)行搜索，MiniMax算法是一種找到對己方最有利的走步，同時也是對對方最不利的走步。MiniMax搜索算法主要是用遞歸實現(xiàn)的，遞歸是程序里面一個重要的思考策略^[9，10]，通過深度優(yōu)先模擬出更深層次的節(jié)點。MiniMax算法是在雙方博弈過程中，盡量讓己方的優(yōu)勢最大，讓對方優(yōu)勢最小，其輸贏的總和為0。

該文提出的MiniMax搜索步驟主要分為：初始搜索樹、是否為葉子節(jié)點，是否時間結(jié)束，遞歸搜索等。MiniMax搜索流程圖如圖2所示。

MiniMax搜索主要通過以下三個步驟：

（1）初始搜索樹，首先在一顆空樹上創(chuàng)建根節(jié)點，然后在其子節(jié)點上創(chuàng)建可以走步的節(jié)點，接下來可以設(shè)置每一步搜索模擬時間，目的是為了防止比賽時間超時，然后用一個變量保持棋盤的信息，后面的模擬過程全部都在這個變量上進(jìn)行演練。

（2）是否為葉子節(jié)點，初始化樹后會直接進(jìn)入遞歸搜索的階段，進(jìn)入遞歸搜索模擬之前會判斷該節(jié)點是否是葉子節(jié)點，如果是葉子節(jié)點會直接返回葉子節(jié)點，如果不是葉子節(jié)點會進(jìn)入下一步判斷。

（3）時間是否結(jié)束，進(jìn)入循環(huán)模擬時，會一直遞歸向下搜索節(jié)點，直到搜索到一個最佳節(jié)點為止，但由于時間限制，大部分情況是搜索不到葉子節(jié)點的，會在時間結(jié)束時返回一個當(dāng)前的節(jié)點。

3? 開局庫策略

一個好的開局往往是贏得比賽的基礎(chǔ)，在開局階段通過設(shè)計開局庫來節(jié)約前期搜索節(jié)點的時間，同時也可以讓局面在前期保持一定的優(yōu)勢，因此需要一個良好的開局庫來讓程序在整個對局中處于強(qiáng)勢地位。要設(shè)計一個良好的開局庫需要通過大量的測試并且通過觀察高手之間的對局情況，然后經(jīng)過不斷地模擬，抽象出一套自己系統(tǒng)可以使用的開局庫。

基本上所有優(yōu)秀的棋類博弈系統(tǒng)都有自己特殊的開局庫，如果不采用開局庫，而在開局階段就直接通過MiniMax搜索出的走步，這樣有可能會出現(xiàn)一些很不好的落子，所有我們需要在開局的時候加入一些經(jīng)驗算法規(guī)劃，這是十分關(guān)鍵的。如果使用了開局庫，在前期可以通過對手的情況來改變自己的本局的開局策略，可以避免對手進(jìn)行針對性落子，總體來說開局庫模塊對于整個系統(tǒng)來說，都是必不可少的一環(huán)。

3.1? 常規(guī)開局庫策略

開局庫就是把一些基于經(jīng)驗的固定走步存在數(shù)據(jù)庫里，然后在開局階段從數(shù)據(jù)庫中調(diào)用這些數(shù)據(jù)從而在開局階段擁有好的收益。常規(guī)開局庫圖如圖3所示，在該文常規(guī)開局庫的設(shè)定是先占領(lǐng)圖內(nèi)置的邊，再通過占領(lǐng)外置邊達(dá)到開局庫的作用，由于博弈雙方下的邊是共有的，所以在落子后并未在交互界面用不同顏色加以區(qū)分。

3.2? 鏡像開局庫策略

鏡像開局策略可以模擬對方的落子情況，通過鏡像的方式，重現(xiàn)對方的開局，當(dāng)面對實力比較強(qiáng)的對手時，通過該策略避免在前中期開局不利的情況，也可以學(xué)習(xí)對方的開局從而增加自己的開局庫信息。鏡像開局效果圖如圖4所示，在前22步都啟動鏡像開局策略來模擬對方開局。

4? 搜索引擎架構(gòu)

整個搜索模塊是點格棋博弈系統(tǒng)最核心的部分，是決定整個系統(tǒng)棋力強(qiáng)弱與否最關(guān)鍵的環(huán)節(jié)。其中一些主要功能為：

（1）判斷落子功能：在這個模塊里，程序可以自動識別玩家或者電腦落子是否規(guī)范，并且可以判斷整個游戲是否結(jié)束。

（2）搜索節(jié)點功能：整個搜索模塊主要是尋找最佳走步，在建立的博弈樹上進(jìn)行搜索，只有具備完善的搜索節(jié)點功能，整個系統(tǒng)的棋力才能得到質(zhì)的提升。而在開局階段主要采用開局庫策略和經(jīng)驗算法策略進(jìn)行搜索得出最優(yōu)點，后期采用極大極小值算法策略得到最佳落子節(jié)點。

（3）信息保存功能：在程序下棋的過程中會把每一步的信息按打譜軟件格式全部記錄下來，方便以后的測試和修改。

（4）搜索時間功能：由于比賽時限的原因，可以限制每次落子的搜索時間來保證整局游戲不超過比賽的總時長。

在點格棋博弈系統(tǒng)整體架構(gòu)中，把整個棋局分為前中后三個階段。首先在開局時，使用上一小節(jié)提到的開局庫搜索，在此階段，主要是以開局庫經(jīng)驗策略為主，在中盤階段，優(yōu)先調(diào)用依賴經(jīng)驗設(shè)計的函數(shù)構(gòu)建布局，然后通過MiniMax算法搜索落子，最后是終局階段，進(jìn)入這個階段說明游戲即將結(jié)束，如果在終局階段進(jìn)入終局庫里面，系統(tǒng)會自動調(diào)用終局必贏算法，此時勝率將達(dá)到100%。

在開始階段通過電腦落子可以判斷開局庫的使用是否成功，大概在22步之前都使用開局庫策略，然后通過MiniMax算法搜索，得出最佳節(jié)點。搜索引擎流程圖如圖5所示。

5? 實驗結(jié)果和分析

為了驗證該文提出的結(jié)合開局庫策略的MiniMax算法有效性，將該策略與蒙特卡洛算法進(jìn)行博弈對局測試，棋盤大小11×11，單方用時不超過15分鐘。該實驗環(huán)境包括：GPU型號為NVIDIA GeForce RTX 2060（6 GB），CPU型號為Intel Core i7-10700F。如表4、表5、表6所示。

由表4、表5、表6可以得出，該文提出的模型在先手時的勝率明顯更高，雖然在后手時勝率難以得到保證，但仍然在50%以上，隨著單步限時的增長，該文提出的模型勝率也更高。

6? 結(jié)? 論

在如今快速發(fā)展的人工智能領(lǐng)域中，計算機(jī)博弈研究是十分值得的。計算機(jī)博弈過程中節(jié)點的搜索都是在博弈樹上進(jìn)行的，幾乎都是通過深度優(yōu)先算法同時加上估值函數(shù)來對整個局面進(jìn)行判斷，然后進(jìn)行評估落子，其中常用的就是MiniMax算法、UCT算法等。未來改進(jìn)該系統(tǒng)時可以加入置換表，把訓(xùn)練搜索到的節(jié)點情況存入哈希表中，這樣在博弈比賽時遇到類似的搜索情況，便可直接調(diào)用哈希表中的值來節(jié)約搜索時間。

參考文獻(xiàn)：

[1] 呂征宇.基于深度強(qiáng)化學(xué)習(xí)的棋類博弈研究 [D].北京：中央民族大學(xué)，2020.

[2] 姬波，尤惠彬，盧紅星，等.一種自對弈棋局學(xué)習(xí)樣例質(zhì)量評價方法 [J].小型微型計算機(jī)系統(tǒng)，2021，42（3）：467-471.

[3] 劉成，李飛，孫玉霞，等.貫穿式案例教學(xué)法在機(jī)器博弈課程中的實踐 [J].計算機(jī)教育，2019（8）：174-178.

[4] 閆俊名.雙人零和博弈問題中策略搜索算法的研究 [D].大連：大連理工大學(xué)，2020.

[5] 王允臣.基于點格棋的博弈算法研究與改進(jìn) [D].徐州：中國礦業(yè)大學(xué)，2017.

[6] 張利群，曹楊，李廈.點格棋計算機(jī)博弈平臺通信接口 [J].計算機(jī)與現(xiàn)代化，2016（3）：96-99+126.

[7] 丁濛，張亦鵬，李淑琴.棋盤局面數(shù)據(jù)標(biāo)定方法研究 [J].計算機(jī)應(yīng)用研究，2020，37（2）：470-472.

[8] 申培萍，陳曉.一類Minimax分式規(guī)劃問題的迭代算法 [J].河南師范大學(xué)學(xué)報（自然科學(xué)版），2018，46（1）：16-22+2.

[9] 倪錦園，張建勛.遞歸算法的應(yīng)用與分析 [J].現(xiàn)代信息科技，2020，4（20）：146-148+152.

[10] 楊嬌.遞歸思想及其算法設(shè)計的探討 [J].數(shù)字通信世界，2018（11）：109+204.

作者簡介：倪錦園（1996—），男，漢族，重慶九龍坡人，碩士在讀，研究方向：數(shù)字圖像處理與分析;張建勛（1971—）男，漢族，四川樂山人，教授，碩士生導(dǎo)師，CCF會員，博士，研究方向：數(shù)字圖像處理與分析、實時計算機(jī)圖形學(xué)。

收稿日期：2021-04-06

基金項目：重慶市教委科技研究重點項目（KJZD-K201801901）