姚想

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

關(guān)鍵詞：人工智能? 計算機博弈? 點格棋? 優(yōu)化

中圖分類號：TP181? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼：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世紀(jì)50年代產(chǎn)生的新興領(lǐng)域。其根源最早可追溯到公元前古希臘的著名思想家亞里士多德，他奠定了形式邏輯的基礎(chǔ)。計算機自發(fā)明以來發(fā)展迅猛， 機器博弈，作為典型的反映計算機智能水平的領(lǐng)域，逐漸成為熱門研究方向。歐美國家起步較早，已經(jīng)發(fā)展并研究出如“深藍(lán)”、“AlphaGo”這樣廣為人知的頂級程序，在其他復(fù)雜、不適合人類對弈（因此鮮為人知）的棋類競賽中，也占據(jù)著領(lǐng)先地位。國內(nèi)對棋類的研究尚處在起步階段，本文設(shè)計的點格棋的智能系統(tǒng)不同于國內(nèi)常規(guī)，具有一定創(chuàng)新性和價值。

1? 點格棋基本規(guī)則及術(shù)語

1.1 基本規(guī)則

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

1.2 術(shù)語

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

2? 點格棋基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)及算法實現(xiàn)

2.1 棋局表示

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

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結(jié)構(gòu)即為格子。棋盤的全部格子存在boxes[boxes_size]數(shù)組中，結(jié)構(gòu)內(nèi)的near[4]數(shù)組用于存放一個格子周圍的四條邊，建立起格子對應(yīng)的邊的聯(lián)系，其他有必備信息如記錄格子占有方、下的邊數(shù)，并將全部格子順序編號。EDGES結(jié)構(gòu)即代表邊。棋盤上的邊存在一維數(shù)組，通過box_near[2]數(shù)組存放該條邊所屬的兩個（或一個）格子，建立起邊對應(yīng)的格子的聯(lián)系。除此之外，還需要邊在棋盤中的位置、編號、以及留待后續(xù)使用的信息。

2.2 招法產(chǎn)生

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

2.3 搜索

2.3.1 MC （Monte Carlo method）

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

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

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

2.3.3 與傳統(tǒng)算法對比

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

4? 算法優(yōu)化

4.1 招法合并

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

4.2 搜索改進(jìn)實現(xiàn)：AMAF

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

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

5? 結(jié)語

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

參考文獻(xiàn)

[1] 唐霜霜.點格棋機器博弈系統(tǒng)的研究與實現(xiàn)[D].合肥：安徽大學(xué)，2015.

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

[3] 邵向陽，許敏.計算機人工智能技術(shù)的應(yīng)用及未來發(fā)展初探[J].科技創(chuàng)新導(dǎo)報，2019（29）：114-116.

[4] 王玲玲.人工智能在計算機網(wǎng)絡(luò)技術(shù)中的應(yīng)用[J].科技創(chuàng)新導(dǎo)報，2019，16（34）：152-153.

[5] 周珂，王祺.一種基于無監(jiān)督學(xué)習(xí)的博弈算法設(shè)計[J].新技術(shù)新工藝，2020（4）：30-33.

[6] 鄭歡.基于SOPC的人機博弈系統(tǒng)設(shè)計與實現(xiàn)[J].四川水泥，2019（4）：109.