點格棋計算機博弈系統的設計與實現

倪錦園 張建勛

DOI：10.19850/j.cnki.2096-4706.2021.09.021

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

關鍵詞：計算機博弈;蒙特卡洛;開局庫;MiniMax

中圖分類號：TP311.5 文獻標識碼：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? 引? 言

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

針對以上問題，該文設計了一種結合開局庫策略的MiniMax算法作為搜索引擎，通過不同的開局庫策略讓己方棋子在博弈開局階段處于優勢地位，在中期階段通過MiniMax算法和經驗搜索布局來進行落子，在博弈雙方進入終局階段后，如果雙方的棋局進入我方終局必贏策略，此時程序將直接調用終局庫，勝率會達到100%。

1? 點格棋計算機博弈規則

點格棋計算機博弈系統的規則是根據全國大學生計算機博弈大賽的規則制定的，詳細的規則為：

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

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

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

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

（5）格子全部圍成后，博弈結束，占領格子較多的一方為獲勝方。

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

2? 算法介紹

2.1? MiniMax算法設計

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

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

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

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數量級的空間大小，一般計算機難以達到這個量級的搜索量，所以通過限制搜索層數或者限制搜索時間，利用MiniMax算法搜索得出最佳的落子，因此無論是時間上還是空間上，此方法都是可行的。

2.2? MiniMax類設計

該文設計的MiniMax類如表1所示。

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

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

2.3? MiniMax搜索流程圖

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

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

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

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

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

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

3? 開局庫策略

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

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

3.1? 常規開局庫策略

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

3.2? 鏡像開局庫策略

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

4? 搜索引擎架構

整個搜索模塊是點格棋博弈系統最核心的部分，是決定整個系統棋力強弱與否最關鍵的環節。其中一些主要功能為：

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

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

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

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

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

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

5? 實驗結果和分析

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

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

6? 結? 論

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

參考文獻：

[1] 呂征宇.基于深度強化學習的棋類博弈研究 [D].北京：中央民族大學，2020.

[2] 姬波，尤惠彬，盧紅星，等.一種自對弈棋局學習樣例質量評價方法 [J].小型微型計算機系統，2021，42（3）：467-471.

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

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

[5] 王允臣.基于點格棋的博弈算法研究與改進 [D].徐州：中國礦業大學，2017.

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

[7] 丁濛，張亦鵬，李淑琴.棋盤局面數據標定方法研究 [J].計算機應用研究，2020，37（2）：470-472.

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

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

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

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

收稿日期：2021-04-06

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