對藏棋“久”的分階段算法研究

沈強(qiáng)望　丁濛　杜文濤　趙文龍

摘要：藏族久棋是2019年中國計(jì)算機(jī)博弈錦標(biāo)賽新設(shè)棋種，在此之前，國內(nèi)外對該棋種的博弈策略研究相對較少。本文基于久棋兩個(gè)博弈階段規(guī)則和目的差異性大的特點(diǎn)，提出一種分階段的博弈策略：下子階段，考慮到無明顯勝負(fù)判別的因素，提出一種基于相對勝負(fù)的改進(jìn)蒙特卡洛樹搜索算法以獲取最佳下子點(diǎn);行棋階段，考慮到過程中的行棋方式會對后續(xù)模擬局面造成一定的影響，提出一種加入過程分值的改進(jìn)Alpha-Beta剪枝搜索算法以獲取最優(yōu)行棋方案。在上述算法模擬博弈樹的過程中，通過下子階段優(yōu)先集中在中心區(qū)域，行棋階段優(yōu)先形成褡褳的估值策略，給出了一份完整的估值評估表。實(shí)驗(yàn)結(jié)果表明，使用上述博弈策略及估值表實(shí)現(xiàn)的博弈程序棋力較高。

關(guān)鍵詞：Alpha-Beta剪枝;蒙特卡洛樹搜索;計(jì)算機(jī)博弈;藏棋

【Abstract】TibetanJiuqiisanewchesstypeinthe2019ChinaComputerGameChampionship.Priortothis，therewererelativelyfewresearchesonthegamestrategyofthischesstypeathomeandabroad.BasedonthelargedifferencesinrulesandobjectivesbetweenthetwogamestagesofJiuqi，thispaperproposesastagedgamestrategy：currentstage，takingintoaccountthefactorsthathavenoobviouswinorlosejudgment，animprovedMonteCarlotreesearchalgorithmisproposedbasedonrelativewinsandlossestoobtainthebestmovepoint;inthechess-movingstage，consideringthatthechess-movingmethodintheprocesswillhaveacertainimpactonthesubsequentsimulationposition，animprovedAlpha-Betapruningsearchalgorithmwithprocessscoresisproposedtogetthebestchessplan.Intheprocessofsimulatingthegametreewiththeabovealgorithm，currentstageisprioritizedtofocusonthecentralarea，andthechess-playingstageprioritizestheformationofacomprehensivevaluationstrategy，andacompletevaluationevaluationtableisgiven.Theexperimentalresultsshowthatthegameprogramachievedbyusingtheabove-mentionedgamestrategyandvaluationtablehashigherchesspower.

【Keywords】Alpha-Betapruning;MonteCarlotreesearch;computergame;Tibetanchess

作者簡介：沈強(qiáng)望（2000-），男，本科生，主要研究方向：計(jì)算機(jī)博弈;丁濛（1982-），男，博士，副教授，主要研究方向：可視媒體處理、計(jì)算機(jī)博弈;杜文濤（2000-），男，本科生，主要研究方向：計(jì)算機(jī)博弈;趙文龍（2000-），男，本科生，主要研究方向：計(jì)算機(jī)博弈。

0引言

隨著人工智能的不斷發(fā)展，人們對計(jì)算機(jī)博弈的研究也日趨深入[1]。除極大極小算法，Alpha-Beta搜索等傳統(tǒng)搜索算法外，深度學(xué)習(xí)[2]和強(qiáng)化學(xué)習(xí)等機(jī)器學(xué)習(xí)相關(guān)算法[3]也已廣泛地應(yīng)用到計(jì)算機(jī)博弈當(dāng)中。而藏棋“久”[4]是中國少數(shù)民族的棋種，于2019年加入到中國計(jì)算機(jī)博弈錦標(biāo)賽當(dāng)中。由于其所涵蓋受眾遠(yuǎn)小于圍棋、國際象棋等常見棋種，因此國內(nèi)外對久棋博弈策略的研究相對較少。針對這一現(xiàn)狀，本文基于久棋兩個(gè)博弈階段規(guī)則和目的差異性大的特點(diǎn)，制定了一種分階段的博弈策略：下子階段，提出一種基于相對勝負(fù)的改進(jìn)蒙特卡洛搜索算法[5];行期階段，提出了一種加入過程分值的改進(jìn)Alpha-Beta剪枝算法[6]。此外，根據(jù)下子階段優(yōu)先集中在中心區(qū)域及行棋階段優(yōu)先形成褡褳的估值策略，給出了一份完整的估值評估表。對此擬展開研究論述如下。

1藏族久棋規(guī)則

久棋的博弈全局分為下子和行棋兩個(gè)階段，下子階段將棋子布滿棋盤;行棋階段通過移子來達(dá)到吃子的目的，最終獲取勝利。對此可做闡釋概述如下。

1.1下子和行棋規(guī)則

1.1.1下子和行棋方式

下子階段為棋盤中央的格子用對角線相連接的點(diǎn)上作為對局雙方下子的起始點(diǎn)，下子由白方先下，接著開始輪流下子布局，直至布滿全局之后開始行棋。

行棋階段開局如圖1所示，行棋階段中，先將棋盤中央方格的對角線兩端的棋子去掉后開始行棋。因下子階段由白方先下，為了對局雙方公平，行棋則由黑方先行。在雙方棋子個(gè)數(shù)均大于14顆時(shí)，行棋方式分為普通走子和跳子;在一方棋子個(gè)數(shù)小于14顆時(shí)，該方的行棋方式會新增飛子。飛子，即可以隨意飛至棋盤上任意空位，不受正常行棋規(guī)則的約束。普通走子，即為棋子可以移至相鄰空位。跳子分為單跳和連跳。單跳，就是相鄰位為對方棋子時(shí)，該橫（縱）方向第三點(diǎn)為空位，就可跳至該位，并跳吃中間對方棋子。連跳即為多步連續(xù)單跳。

1.1.2特殊棋形

（1）棋門：棋盤總共有196個(gè)格子，行棋時(shí)，棋盤正方形方格上的4個(gè)頂點(diǎn)都下某一方的棋子時(shí)，會形成一個(gè)最小正方形，這個(gè)正方形圖案就稱之為一個(gè)棋門。行棋是每形成一個(gè)棋門就可以吃掉對方任意一個(gè)棋子。棋門分為單棋門和雙棋門。雙棋門是2個(gè)單棋門連在一起形成。在行棋階段，每形成一個(gè)雙棋門，可以吃掉對方任意2個(gè)棋子。

（2）單褡褳：如果2個(gè)棋門之間有一個(gè)空格且有一顆棋子可以來回移動，并可以關(guān)閉兩邊的棋門。

（3）雙褡褳：如果在2個(gè)棋門之間有一個(gè)空位，并來回移動一個(gè)棋子可以關(guān)閉2個(gè)棋門，可以吃對方任意2個(gè)棋子。單褡褳或雙褡褳是保證行棋階段提前獲勝所需棋形的基本條件。

1.2吃子規(guī)則

（1）成方吃子：一方形成單棋門可以提掉對方任意位置一顆棋子，形成雙棋門可以提掉2顆。

（2）跳子吃子：己方所落棋子的縱（橫）線相鄰的點(diǎn)上為對方的棋子，而第三點(diǎn)為空白點(diǎn)時(shí)，己方可以跳吃對方的棋子，依據(jù)情況選擇單跳吃或連跳吃。

1.3勝負(fù)判別

在行棋階段的勝負(fù)判別有2種。第一種為雙方棋子個(gè)數(shù)均為14顆以上時(shí)，一方形成雙褡褳且另一方不具有形成棋門的能力，此時(shí)形成雙褡褳一方獲勝;另一種為一方棋子減少至四顆以下，此時(shí)棋子少于4顆的一方判負(fù)。

2藏棋“久”的分階段算法研究

藏族久棋分為下子階段和行棋階段，不同階段的博弈目的和規(guī)則也具有較大的差別。其中，下子階段是為行棋階段謀篇布局，較好的布局能使行棋階段開局己方占據(jù)主動性，能更有效地形成對己方有利的局面。行棋階段則是通過行棋來吃掉對方棋子，破壞對方的特殊棋形，形成對己方有利的棋形，以獲取最終的勝利。

考慮到該棋種兩個(gè)階段有較大差別，因此本文對一些博弈算法做出一定的改進(jìn)，以便更適合該棋種。下子階段，提出一種基于相對勝負(fù)的改進(jìn)蒙特卡洛樹搜索算法以獲取最佳下子點(diǎn);行棋階段，提出一種加入過程分值的改進(jìn)Alpha-Beta剪枝搜索算法，以便于各階段盡可能獲取最好的結(jié)果。

2.1下子算法

下子階段第一二步只能下在固定中心位置，其后便可下在任意點(diǎn)，但由于該棋盤為14×14規(guī)格，搜索空間過大[7]，若用Alpha-Beta剪枝搜索算法，搜索深度會過低，無法窮舉計(jì)算出所有情況，進(jìn)而導(dǎo)致給出的下子點(diǎn)效果不好。

下子階段的久棋是可分出相對勝負(fù)，且具有確定性、順序性和離散性的完全信息博弈。常規(guī)蒙特卡洛樹搜索算法將當(dāng)前局面作為根結(jié)點(diǎn)進(jìn)行判斷，然后進(jìn)行選擇，擴(kuò)展，接著模擬到終端局面判斷勝負(fù)情況，但考慮到久棋分為下子和行棋兩個(gè)階段，勝負(fù)判別在后一個(gè)階段，因此本文提出在對局面雙方進(jìn)行整體評估統(tǒng)計(jì)分值后，通過得分情況判斷相對勝負(fù)，賦予棋局不同狀態(tài)對應(yīng)分值，并對結(jié)點(diǎn)分值進(jìn)行反向傳播更新，以達(dá)到最終在限定時(shí)間內(nèi)獲取相對最優(yōu)下子點(diǎn)的目的。

2.2行棋算法

行棋階段開局時(shí)，可移動棋子主要集中在中心區(qū)域，初始可行棋點(diǎn)較少，搜索空間是在計(jì)算范圍內(nèi)的，可以有效模擬出所有可行點(diǎn)的行棋路徑。

傳統(tǒng)的Alpha-Beta剪枝搜索算法是在搜索到指定深度后，根據(jù)當(dāng)前局面評估分值。傳統(tǒng)Alpha-Beta算法如圖2所示，圖2中的虛線表示每一次選擇的行棋路徑，自下而上，依次比較選擇，直至獲取整個(gè)模擬過程中分值最高的行棋路徑。

考慮到久棋在行棋階段選擇不同的行棋路徑造成的吃子會對后續(xù)局面模擬造成一定影響，本文提出一種加入過程分值考量的Alpha-Beta剪枝搜索算法，如圖3所示。圖3中的虛線表示每一次比較選擇的行棋路徑，每一步行棋都會被賦予一個(gè)過程分值，到達(dá)指定搜索深度時(shí)，再由下至上反向進(jìn)行局面得分統(tǒng)計(jì)并做出相應(yīng)選擇。與圖2對比可以看出，在指定搜索深度局面相同分值的情況下，做出改進(jìn)后的Alpha-Beta剪枝搜索算法與傳統(tǒng)的每一步或最終選擇的最優(yōu)行棋路徑都可能不同。因此加入了過程分值考量的Alpha-Beta剪枝搜索算法更加契合該棋種規(guī)則。

2.3評估策略

下子階段，設(shè)置二連子、三連子、三角、成方，對角5種基礎(chǔ)攻擊棋形[8]，防止對方三角成方，防止對方三連子成雙三角，防止對角成三角棋形3種基礎(chǔ)防守棋形。在久棋博弈過程中，行棋是提取中心固定位置的雙方棋子開局，中心區(qū)域的棋子初始的能動性較高，可進(jìn)攻可防守。因此，若能在下子階段盡可能地圍繞中心區(qū)域展開布局，在行棋階段開始則能有一定的主動性，可以把整局博弈的節(jié)奏掌握在己方手中，引導(dǎo)對局趨勢朝利于己方的方向進(jìn)行。

經(jīng)過多次博弈實(shí)戰(zhàn)，最終在蒙特卡洛樹搜索算法模擬的結(jié)果得分和該棋子的位置得分之間獲取了一個(gè)較好的比例平衡，對應(yīng)數(shù)學(xué)公式可寫為：

final_score=result_score×0.7+location_score×0.3.

（1）

其中，final_score表示最終評估得分;result_score表示模擬的結(jié)果得分;location_score表示棋子的位置得分。

行棋階段中，有一個(gè)極為重要的攻防棋形—褡褳，形成單雙褡褳會使一方在博弈對局中取得明顯優(yōu)勢，既可以破壞對方成方及形成褡褳，也可以為己方成方及再次形成褡褳清除掉對方中有威脅的棋子。所以在其他基本棋形的基礎(chǔ)上，新增褡褳的形成及破壞得分，同時(shí)新增吃子的得分，利用Alpha-Beta有效的搜索，選取己方分?jǐn)?shù)最大的行棋路徑。

2.4評估策略分值表

為了評判修改后的參數(shù)是否更優(yōu)，本文采取機(jī)機(jī)博弈，即2個(gè)AI程序交替下棋直至分出勝負(fù)，通過控制變量法，將2個(gè)AI程序除了相應(yīng)策略有關(guān)參數(shù)以外的所有函數(shù)均保持一致，通過蒙特卡洛樹搜索算法計(jì)算出終端局面雙方棋子的總分值，評判相對更優(yōu)參數(shù)。下子階段最終評估局面如圖4所示，白子總分值高于黑子，此時(shí)白子的參數(shù)相對更好。接著修改評分較低一方的參數(shù)，模擬對局，直至出現(xiàn)比第一次較優(yōu)參數(shù)更高的分值，以此來調(diào)試參數(shù)。

博弈策略分為2種，即：主進(jìn)攻和主防守。其中，主進(jìn)攻為優(yōu)先形成自己的棋形，占據(jù)一定主動性，即己方形成一些基礎(chǔ)棋形的分值會高于阻止對方形成相應(yīng)棋形的分值。主防守則為優(yōu)先阻止對方形成一些特定棋形，具有一定的被動性。在下子階段形成褡褳會留空給對方棋子，以便提掉對方棋子后，中間可移動棋子可以來回成方，反復(fù)提取對方棋子，但若行棋階段不能盡早成方提子，則該留空褡褳會被對方破壞，無法達(dá)到預(yù)期的效果，因此留空褡褳不宜貪多。此外，成方棋形靈活性較低，需多步才能制造優(yōu)勢，一般是為了形成褡褳的基礎(chǔ)，因此盡可能優(yōu)先形成基礎(chǔ)棋形中可塑性最強(qiáng)的三角棋形。依據(jù)此策略，研究中還繪制了一份評估策略分值表，限于篇幅，此處不做贅述。

3實(shí)驗(yàn)結(jié)果與分析

3.1規(guī)則實(shí)現(xiàn)

3.1.1棋盤表示

久棋的棋盤有9路、11路、14路等，本文的算法研究均是在14路棋盤上展開。棋盤有縱橫各十四條等距離，垂直交叉的平行線構(gòu)成，形成196個(gè)交叉點(diǎn)，在藏棋中每個(gè)交叉點(diǎn)就是落子的地方，稱為下子點(diǎn)。棋盤整體形狀以及每個(gè)格子縱橫向比相等。

本文采用14×14的二維矩陣抽象地表示各個(gè)下子點(diǎn)的下子狀況，用1表示白子，用2表示黑子，用0表示下子點(diǎn)為空。

3.1.2跳吃實(shí)現(xiàn)

久棋行棋階段的跳吃路徑存儲，縱向采取的數(shù)組形式，存儲多個(gè)可行點(diǎn);橫向采取的單鏈表形式，存儲多條可行路徑。走子的存儲是找到己方所有可行點(diǎn)，并在該點(diǎn)的上、下、左、右四個(gè)方位的相鄰位置判斷是否有空位，若有空位，即可直接記錄起始點(diǎn)和終點(diǎn)坐標(biāo)。

跳子分為單跳和連跳。單跳是通過判斷己方所有棋子的相鄰位置是否為對方棋子及第三點(diǎn)是否為空位，若是則可以單跳。連跳其實(shí)是一個(gè)不斷將上一次單跳終點(diǎn)變?yōu)橄乱淮螁翁鹗键c(diǎn)的單跳過程，最終將整條行棋路徑串連，即為完整連跳路徑。獲取所有點(diǎn)可行跳吃路徑步驟可分述如下：

（1）調(diào)用JumpMoveList函數(shù)對不同位置的己方點(diǎn)進(jìn)行遍歷，且相鄰點(diǎn)為對方棋子，單跳到達(dá)點(diǎn)為無子情況。

（2）判斷橫縱四個(gè)方向的狀況，判斷某點(diǎn)是否存在可單跳的情況。

（3）若存在單跳，調(diào)用hop函數(shù)判斷單跳的終點(diǎn)是否可以連跳;若不存在，則退出跳子行棋方式判斷。

（4）遞歸調(diào)用jump函數(shù)不斷地將不同方向的連跳情況存入在內(nèi)。

（5）當(dāng)某條跳子路徑到達(dá)盡頭時(shí)，調(diào)用jumpback函數(shù)回溯，恢復(fù)初始狀態(tài)。

（6）重復(fù)（2）～（5），判斷上一階段某點(diǎn)的其余方向存在跳子可能的情況，直至找到所有可行點(diǎn)的可行路徑。

其中，hop函數(shù)是判斷某點(diǎn)能否連跳;jumpback函數(shù)是回溯到棋局初始狀態(tài);jumpMoveList函數(shù)是獲取單跳路徑;jump函數(shù)是遞歸查找所有連跳方法。

綜上可得，連跳前的棋局如圖5所示，連跳后的棋局如圖6所示，單跳成方吃子前棋局如圖7所示，單跳成方吃子后棋局如圖8所示。

3.1.3褡褳的判斷

褡褳是久棋中十分重要的棋形，分為單褡褳和雙褡褳。在博弈過程中，許多進(jìn)攻和防守的操作都是通過褡褳完成的。分析可知，褡褳的特點(diǎn)就在于，每移動一次褡褳中間的棋子，至少可以提掉對方一顆棋子，極具主動性。

單褡褳以不同的形式遍布在一個(gè)3×4（或豎置）的格局內(nèi)，由于單褡褳樣式一定，因此本文采用枚舉的方法，搭建一個(gè)單褡褳庫，再與所有符合情況的單褡褳進(jìn)行匹配，給予不同的標(biāo)號標(biāo)識，并記錄單褡褳中可移動棋子的位置，便于后續(xù)評估函數(shù)制定分值比重。而雙褡褳是基于單褡褳的復(fù)雜棋形，可通過單褡褳的特殊疊加方式判別。

在整個(gè)棋盤中，遍歷每一個(gè)3×4的矩形區(qū)域，首先判斷其是否為一個(gè)褡褳，如果不是則排除;如果是，就記錄該矩形左上角點(diǎn)的坐標(biāo)，用于記錄這個(gè)褡褳在整個(gè)棋盤中的位置。通過遍歷整個(gè)棋盤一次，可以查詢出所有橫置褡褳的位置，接著將棋盤數(shù)組轉(zhuǎn)置，再進(jìn)行一次前述的遍歷操作，就可查詢出所有豎置的褡褳。在此基礎(chǔ)上，將所有的褡褳位置用鏈表存儲，用于后續(xù)的評估操作。

3.2算法實(shí)現(xiàn)

本文首先定義一個(gè)結(jié)點(diǎn)類，其屬性有chessmans，rewardMap，accessNumber，nextNode等，chessmans表示該結(jié)點(diǎn)的棋盤狀態(tài)，在進(jìn)行選擇的時(shí)候，默認(rèn)優(yōu)先選擇未被擴(kuò)展的結(jié)點(diǎn)，即棋盤上顯示為0的點(diǎn)（利用Node的nextNode屬性，該屬性為一個(gè)Node二維數(shù)組，大小為14×14，Node.nextNode[i][j]=null就表示其未被擴(kuò)展），當(dāng)該結(jié)點(diǎn)的所有子結(jié)點(diǎn)都已被選擇遍歷，利用getBestChild，通過公式（2）計(jì)算該節(jié)點(diǎn)UCB值：

4結(jié)束語

本文對藏棋“久”進(jìn)行分階段算法研究，在下子階段，提出一種基于相對勝負(fù)的改進(jìn)蒙特卡洛樹搜索算法，在限定下子時(shí)間內(nèi)獲取相對最優(yōu)下子點(diǎn);在行棋階段，提出一種加入過程分值的改進(jìn)Alpha-Beta剪枝搜索算法，并給出一份完整的估值評估表。通過與技術(shù)較高的棋手博弈，測試發(fā)現(xiàn)通過上述算法及估值表實(shí)現(xiàn)的AI博弈引擎具有較強(qiáng)的棋力。

雖然本文提到了一些較好的設(shè)計(jì)思想，但因?yàn)橐恍┎豢煽匾蛩?，具體功能在實(shí)現(xiàn)上還有待進(jìn)一步完善。如該棋種規(guī)則相對復(fù)雜，涉及吃子、特殊棋形及多種著子方式，因此普通的傳統(tǒng)算法若沒有良好的評估函數(shù)和剪枝條件，就會進(jìn)行大量無用的搜索，甚至?xí)羧ポ^好的局面，造成搜索深度過低且棋力不足等后果，接下來的研究會優(yōu)化評估函數(shù)和剪枝條件。此外，Alpha-Beta搜索的層數(shù)過低，算法以及數(shù)據(jù)結(jié)構(gòu)還需再進(jìn)行深入優(yōu)化，動態(tài)控制搜索深度。MCTS搜索的結(jié)點(diǎn)過少，數(shù)據(jù)結(jié)構(gòu)還需做進(jìn)一步優(yōu)化，考慮的因素需要做適當(dāng)?shù)脑鰟h。

參考文獻(xiàn)

[1]張芃芃，孟坤，楊震棟.基于強(qiáng)化學(xué)習(xí)的海克斯棋博弈算法研究與實(shí)現(xiàn)[J].智能計(jì)算機(jī)與應(yīng)用，2020，10（3）：142-145.

[2]LECUNY，BENGIOY，HINTONG.Deeplearning[J].Nature：InternationalWeeklyJournalofScience，2015，521（7553）：436.

[3]周志華.機(jī)器學(xué)習(xí)[J].北京：清華大學(xué)出版社，2016.

[4]中國大學(xué)生計(jì)算機(jī)博弈大賽組委會.久棋規(guī)則及棋譜簡介[EB/OL].[2019-04-29].http：//computergames.caai.cn/info/news190429.html.

[5]CHASLOTG，BAKKESS，SZITAI，etal.Monte-Carlotreesearch：AnewframeworkforgameAI[C]//ArtificialIntelligence&InteractiveDigitalEntertainmentConference.PaloAlto，California：DBLP，2008：216-217.

[6]PEARLJ.Thesolutionforthebranchingfactorofthealpha-betapruningalgorithmanditsoptimality[J].CommunicationsoftheACM，1982，25（8）：559.

[7]王松.久棋強(qiáng)化學(xué)習(xí)博弈研究及多媒體課件開發(fā)[D].北京：中央民族大學(xué)，2019.

[8]李霞麗，吳立成，李永集.基于棋型的藏族“久”棋計(jì)算機(jī)博弈研究[J].智能系統(tǒng)學(xué)報(bào)，2018，13（4）：577-583.