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

沈強望　丁濛　杜文濤　趙文龍

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

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

【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

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

0引言

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

1藏族久棋規(guī)則

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

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

1.1.1下子和行棋方式

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

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

1.1.2特殊棋形

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

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

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

1.2吃子規(guī)則

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

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

1.3勝負判別

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

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

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

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

2.1下子算法

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

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

2.2行棋算法

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

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

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

2.3評估策略

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

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

final_score=result_score×0.7+location_score×0.3.

（1）

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

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

2.4評估策略分值表

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

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

3實驗結(jié)果與分析

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

3.1.1棋盤表示

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

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

3.1.2跳吃實現(xiàn)

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

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

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

（2）判斷橫縱四個方向的狀況，判斷某點是否存在可單跳的情況。

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

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

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

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

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

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

3.1.3褡褳的判斷

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

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

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

3.2算法實現(xiàn)

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

4結(jié)束語

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

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

參考文獻

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

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

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

[4]中國大學(xué)生計算機博弈大賽組委會.久棋規(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]王松.久棋強化學(xué)習博弈研究及多媒體課件開發(fā)[D].北京：中央民族大學(xué)，2019.

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