基于機器博弈的點格棋智能系統的優化研究

姚想

摘? 要：人工智能的發展常以棋類為先鋒。計算機博弈因其特點已成為人工智能發展的重要分支：棋中戰術遵循規則，勝負可判，棋力可考，可復現性強，具有人機對抗與純機器博弈兩種測試方式，能直觀反映出人工智能的發展水平。本文以點格棋為研究對象，通過創建棋盤數據結構、模擬招法選擇、棋局樹搜索及優化等方式，實現完整點格棋智能系統的構建;同時與傳統的Alpha-Beta搜索進行對比，說明本文算法優化的提升效果及意義。

關鍵詞：人工智能? 計算機博弈? 點格棋? 優化

中圖分類號：TP181? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? 文章編號：1674-098X（2020）10（a）-0132-03

Abstract： Chess is often applied as a pioneer in development of AI （artificial intelligence）. And computer game has become an essential branch of AI development due to the following characteristics： Tactics in chess obey certain rules; victory and level of the program can be judged or measured; great reproducibility can be shown. There are two test methods including man-machine counterwork and machine-machine counterwork， which can both reflect the level of development of AI intuitively. Dots-and-Boxes is chosen as the research object. Establishment of the AI system can be realized by basic chessboard data structure， simulation on choices of moves， tree search and optimization. Meanwhile， compared with the conventional Alpha-Beta search， innovative value and great meaning of this algorithm optimization can be shown clearly.

Key Words： Artificial intelligence; Computer game; Dots-and-Boxes; Optimization

計算機博弈（亦稱機器博弈），是20世紀50年代產生的新興領域。其根源最早可追溯到公元前古希臘的著名思想家亞里士多德，他奠定了形式邏輯的基礎。計算機自發明以來發展迅猛， 機器博弈，作為典型的反映計算機智能水平的領域，逐漸成為熱門研究方向。歐美國家起步較早，已經發展并研究出如“深藍”、“AlphaGo”這樣廣為人知的頂級程序，在其他復雜、不適合人類對弈（因此鮮為人知）的棋類競賽中，也占據著領先地位。國內對棋類的研究尚處在起步階段，本文設計的點格棋的智能系統不同于國內常規，具有一定創新性和價值。

1? 點格棋基本規則及術語

1.1 基本規則

點格棋（即Dots-and-Boxes），是法國數學家愛德華·盧卡斯于1891年推出的兩人紙筆游戲，常用6X6規格的正方形棋盤。共兩方選手，雙方輪流走招法，所下的是棋盤上的邊（縱向、橫向），共60條邊為有效招法。終局：當所有有效邊均已被下則游戲結束。得分：當一方補全正方形最后一條邊，則該方得一分。勝負判斷：終局后得分更多的一方獲勝。另一方失敗。特殊規則：連下，當有一方得分，則不交換走棋方，必須繼續填補其他邊，直到未得分或終局。

1.2 術語

點格棋中存在一些固定的棋形術語。chain：長鏈，占有的格數固定且大于等于3，在長鏈中所有格子度均為2，且有兩端在邊界。short chain：短鏈，與長鏈類似，但占有格數小于3。circle;環，所有格子度為2，占據格子固定，但完全封閉。degree：度，起始每個格子度為4，終局應當每個格子度為0。度即為每個格子空閑邊的數量。double cross：雙交，對于長、短鏈或環來說，接下來走棋的一方走一步可以得兩分，這樣即為雙交。

2? 點格棋基礎數據結構及算法實現

2.1 棋局表示

點格棋的棋盤是走邊，與圍棋、五子棋這樣走交叉點的棋局有著顯著區別，相比于五子棋的落子可以簡單地用（x，y）二維坐標來表示，如何表示每條邊、棋盤的數據結構就尤為重要。點格棋中弱化了點的作用，關鍵在于所下的邊和占據得分的格子，分別用兩個數據結構來表示邊和格子。

struct BOXES{Edge_near near[4]; int degree;int id;int owner}; struct EDGES{int captured;Box_near box_near[2];int id;int flag;};BOXES結構即為格子。棋盤的全部格子存在boxes[boxes_size]數組中，結構內的near[4]數組用于存放一個格子周圍的四條邊，建立起格子對應的邊的聯系，其他有必備信息如記錄格子占有方、下的邊數，并將全部格子順序編號。EDGES結構即代表邊。棋盤上的邊存在一維數組，通過box_near[2]數組存放該條邊所屬的兩個（或一個）格子，建立起邊對應的格子的聯系。除此之外，還需要邊在棋盤中的位置、編號、以及留待后續使用的信息。

2.2 招法產生

棋盤中所有沒下過的邊都可以作為接下來的有效招法。每當要產生招法時遍歷棋盤上的全部owner=0的邊即可。但需要注意，在點格棋中，存在chain（長鏈）的棋形，當一方在長鏈中下任意一條邊，對方可將這條長鏈全部連下。如果未全部下完，則下回合輪到該方行棋時可補全，因此對于對方來講，全部補全是一種較好的策略，此時純隨機顯然不明智。這就為后續招法篩選和優化做了鋪墊。

2.3 搜索

2.3.1 MC （Monte Carlo method）

蒙特卡洛方法，也稱統計模擬方法，產生于20世紀40年代，主要基于概率統計和數值計算。模擬棋類博弈中對于一個已有的局面，每次行棋都隨機下一條邊（或落子），直到游戲終局。這樣的下棋持續上千萬次或更多，最后得到的一方勝率將近似成這個局面真實的勝率。將蒙特卡洛方法應用到計算機博弈上，可以有效地模擬并統計當前局面下，一盤棋局的勝率。雙方按照規則隨機下任意邊，隨著棋局的進行，每一個對方的招法對應的我方招法有多種，反之亦然。逐層擴展，少量的上層節點呈指數級展開到下層節點，就引入了招法樹（蒙特卡洛樹搜索）。

2.3.2 MCT （Monte Carlo Tree） 與UCT （Upper Confidence Bound Apply to Tree）

蒙特卡洛樹，也即蒙特卡洛樹搜索。每個節點存儲的信息是當前棋局上一步的玩家、招法以及勝負信息。除此之外，規定sim_max與sim_min作為單個節點的最大、最小模擬量。player用于記錄玩家;visit用于記錄實際模擬量;win記錄勝場;depth記錄節點所在樹的深度。對于一次模擬，首先把當前局面這個節點設為根節點，如果當前節點模擬量（visit）大于等于sim_max，就訪問它的子節點，沒有則擴展子節點。在子節點中尋找勝率最高的節點，繼續設為當前節點，實質是遞歸的過程。對于模擬量小于sim_min的節點，默認初始給出一個極大值作為其勝率（rate），否則rate=win/total。這保證了模擬量小的節點優先訪問，也就是所有節點均保證基礎模擬量。對當前節點代表的棋局進行隨機模擬，得出勝負，完成了一次模擬。這次模擬的結果會通過反向更新影響其上層節點。偽代碼如下：for （從當前節點到根路徑上的全部節點，包含現、根節點）{節點visit自增1;if （該節點player與模擬的勝利玩家相同）該節點win自增1;}重復這樣的模擬-更新過程，直到步時到達或訪問量足夠。而UCT（上限置信區間算法）則是對蒙特卡洛樹搜索選取節點策略的改進。其綜合了勝率與節點模擬量，為模擬量小，可能出現誤判的節點增加了被選擇的機會。

2.3.3 與傳統算法對比

Alpha-Beta算法是對極大極小算法（min-max）的優化，也是一種對博弈樹的剪枝策略。其在搜索時，需要擴展完全的一層節點后返回勝率視為有效。博弈樹的擴展呈指數級，因此Alpha-Beta面對限時情況，不可避免地會在最后一層浪費巨大的模擬量，做無用功。而UCT因其搜索樹非對稱擴展的特性，可在搜索過程中隨時中止并返回選擇招法。Alpha-Beta算法的估值（Evaluation）函數也至關重要。它執掌評判局面、招法選擇的大權。然而局面估值依據人類所認為的優勢與劣勢走棋進行賦值，棋力有限，長久以來圍棋AI棋力不佳可作例證。UCT則以統計學為依據，其招法未必符合人類常識，卻是經全盤考慮、基于數千萬模擬次數得到的最佳招法。但Alpha-Beta方法也有可取之處。終局階段Alpha-Beta借助估值函數收斂快，能走出最快取勝的招法;而UCT此時因為局面甚優，節點之間勝率差異不大，樹處在平均擴展的狀態，最終結果是取勝，但其過程很大幾率會走彎路。因此殘局階段使用Alpha-Beta進行估值快速取勝，可作為今后的優化方向之一。整體看，二者各有利弊，然UCT表現出更多亮點，尤其是以模擬代替估值，去除了人類固有思維的影響，使得計算機博弈的發展有極廣的探索空間。

4? 算法優化

4.1 招法合并

對于點格棋，招法本身隨機。但由于點格棋的連下機制，招法結果只可能為全吃或雙交，所以在UCT過程中將連下的邊合并成同一招法，記錄并保存。這樣做的結果會減少大量和重復的無用搜索過程，使棋力、智能性提升。

4.2 搜索改進實現：AMAF

在AI模擬過程中，可能不同的節點在某次模擬中達到了相同的狀態，但這時卻把他們看作兩個不同的節點。而AMAF算法，它認為使棋盤達到某一相同狀態的所有的著法都是等價的，如圖1所示。

經A、B、C三步后得到當前的盤面狀態，這三步的順序可能不同，但是得到狀態是相同的，故視為等價。基本的AMAF算法在每次AI模擬下棋之后將UCT與AMAF更新相組合。該算法快速增長UCT樹中的節點處的計數，并因此增加算法對勝率的置信度。另一方面，節點處的計數增加不是因為移動是在由父節點表示的位置進行的，而是因為它是在不同的模擬環境中進行的。改進的α-AMAF算法混合了來自標準更新和AMAF更新的值估計。它在每個節點保存兩組計數，一個用標準UCT更新而其他更新用AMAF更新。α-AMAF估計節點的值為α乘以估計值AMAF更新計數加上（1-α）乘以來自標準UCT更新計數。因此，α= 0對應于標準UCT算法，α= 1對應于基本AMAF算法。其中α參數變化對比圖如圖2所示。

5? 結語

本文通過巧妙構造的數據結構及算法解決了棋局表示和招法選擇的難點，實現完整的點格棋智能系統。同時對已有的招法搜索模擬進行優化，在對弈方面取得了更好效果。采用的蒙特卡洛方法已在各領域作數值分析、計算等用途，應用廣泛，因此優化亦可供多領域參考，作為將來研究的發展方向。

參考文獻

[1] 唐霜霜.點格棋機器博弈系統的研究與實現[D].合肥：安徽大學，2015.

[2] 何軒，洪迎偉，王開譯，等.機器博弈主要技術分析——以六子棋為例[D].吉首：吉首大學，2019.

[3] 邵向陽，許敏.計算機人工智能技術的應用及未來發展初探[J].科技創新導報，2019（29）：114-116.

[4] 王玲玲.人工智能在計算機網絡技術中的應用[J].科技創新導報，2019，16（34）：152-153.

[5] 周珂，王祺.一種基于無監督學習的博弈算法設計[J].新技術新工藝，2020（4）：30-33.

[6] 鄭歡.基于SOPC的人機博弈系統設計與實現[J].四川水泥，2019（4）：109.