基于棋型的藏族“久”棋計算機博弈研究

李霞麗，吳立成，李永集

（中央民族大學 信息工程學院，北京 100081）

藏棋是藏族人民的傳統(tǒng)游戲，主要流傳于我國西藏以及十大藏區(qū)，是藏族文化寶庫中一顆璀璨的明珠[1]，是人類社會文化的補充與完善，具有藏族獨特的內(nèi)涵和民族文化特征，深受藏族人民的喜愛[2-3]。藏棋棋種有幾十種[4]，“久”棋是其中的大棋種，保護及傳承得也較好。“久”是藏語譯音，是“方”的意思，還有一種說法是拼圖的意思?！熬谩逼宓膶倪^程分為布局和戰(zhàn)斗兩個階段，具有極強的趣味性、競技性和生命力。布局階段將棋子布滿棋盤，不吃子、不移動棋子。戰(zhàn)斗階段通過移動棋子實現(xiàn)吃子。

“久”棋作為藏族棋類的大棋種，是具有相似棋規(guī)棋理的棋類游戲的出色代表，是中華民族的優(yōu)秀棋類文化的代表?！熬谩逼宸植紭O廣，廣泛流行于四川藏區(qū)、甘肅藏區(qū)等。經(jīng)考證，青海盛行的夾棋、西藏盛行的國王與大臣棋、內(nèi)蒙盛行的蒙古戰(zhàn)旗、貴州都勻水族傳統(tǒng)棋藝等棋種，甚至漢族地區(qū)民間的狼吃小羊棋，在棋規(guī)棋理上均與“久”棋類似。

機器博弈是人工智能領域最具挑戰(zhàn)性的研究方向之一，是人工智能的果蠅[5]。1997年，IBM深藍戰(zhàn)勝了卡斯帕羅夫，國際象棋的計算機博弈取得了機器戰(zhàn)勝棋類高手的優(yōu)異成績。2016年，谷歌Alpha Go將深度學習應用于圍棋博弈，使用政策網(wǎng)絡及價值網(wǎng)絡對搜索樹進行剪枝，取得了機器戰(zhàn)勝人類高手的優(yōu)異成績[6-7]。Facebook的Dark-Forest將卷積神經(jīng)網(wǎng)絡和蒙特卡羅樹搜索有機結(jié)合[8]，也具備很高的棋力。2017年，谷歌推出了Alpha-Go Zero，采用一種新的自對弈強化學習方法進行訓練，訓練開始時完全隨機下棋，不需要人類棋手知識的指導。AlphaGo Zero僅僅將棋盤上的黑子和白子作為輸入，使用一個神經(jīng)網(wǎng)絡進行訓練。蒙特卡洛搜索樹也更加簡潔，僅僅使用一個神經(jīng)網(wǎng)絡進行著法預測和評估[9]。與圍棋博弈研究不同，藏棋博弈研究尚處于起步階段，其博弈算法研究具有很大的發(fā)展空間[10]。

現(xiàn)有的藏棋研究文獻[11-13]主要關注藏式圍棋及其他藏棋的歷史、棋規(guī)等。也有部分文獻[14-17]探討了夾棋、王宮雙門棋、褡褳、杰布杰曾的計算機應用研究。文獻[14]首次進行了藏棋研究，開發(fā)了全國第一款藏族棋類軟件，經(jīng)考證，該棋種是流行于青海地區(qū)的夾棋；文獻[15]討論了王宮雙門棋不規(guī)則棋盤狀態(tài)空間表示、著法產(chǎn)生、終局判斷等關鍵問題，給出了基本解決策略；文獻[16]開發(fā)了“褡褳”，該款藏棋較為簡單，適用于小朋友開發(fā)智力；文獻[17]研究了對弈熵率在藏棋“杰布杰曾”上的應用，通過對弈雙方熵率比較，得出國王取勝可能性較高的結(jié)論；文獻[18]對藏式圍棋的博弈搜索算法、局面評估算法等進行了初步研究，開發(fā)了一個藏式圍棋博弈系統(tǒng)，并將其應用于教學研究中。

上述文獻雖然對藏棋的計算機應用進行研究，但多是開發(fā)軟件，將藏棋信息化，并沒有真正從機器博弈的角度研究藏棋，“久”棋的研究文獻更是接近于無。

“久”棋在四川阿壩藏族羌族自治州的保護及傳承很好，2015年被列為四川省非物質(zhì)文化遺產(chǎn)名錄。本文作者在阿壩地區(qū)進行了深入調(diào)研及實地考察，采集了約300局有效的對弈數(shù)據(jù)。通過分析棋譜，提取了“久”棋中的幾種常用棋型，分別為棋型命名為三角、三子、二子、對角、四子等。將作者錄制的300局對弈數(shù)據(jù)采用SGF格式進行處理后，建立棋譜庫。使用確定有限自動機識別當前盤面及棋譜，使用BM字符串匹配算法將當前盤面與棋譜進行匹配。本文提出了基于棋型的攻防策略進行“久”棋布局及戰(zhàn)斗。本文開發(fā)了首款“久”棋博弈軟件，該軟件具有人人對弈、人機對弈、自動錄制棋譜功能，邀請了“久”棋高手測試軟件，測試結(jié)果表明該軟件能夠正常運行，但是棋力尚待提高。該軟件在2016年四川省阿壩縣第七屆“體彩杯”藏棋比賽的人機對弈項目中運行穩(wěn)定。

1 “久”棋的棋規(guī)

“久”棋的棋盤有11路、14路等。常見的是14路棋盤，如圖1所示?？v橫14條等距平行線，正中的小方格里，有一對角線。布局從對角線開始，向外擴散，當棋盤上所有交叉點都被布滿之后，取掉對角上的兩顆棋子，進入戰(zhàn)斗階段。棋子只能放置在線與線的交叉點上，方格中不能放入棋子。

圖 1 “久”棋的棋盤Fig. 1 The board of JIU

1)猜先選定黑子或者白子，布局階段白子先行，戰(zhàn)斗階段黑子先走。

2)布局：白子從棋盤中央對角線的兩端任意選一個點布子，接著，黑子在對角線的另外一端布子。雙方輪流放子，直至布滿整個棋盤的交叉點。

3)戰(zhàn)斗：布局完成后，取掉對角上的兩顆棋子，進入戰(zhàn)斗階段。戰(zhàn)斗階段，黑子先行走棋。走棋的方式包括：①移動，棋子向緊鄰的空交叉點移動一格，上、下、左、右4個方向可以任意移動；②單跳，在己方棋子行走的路線上有一個對方的棋子，而且與對方棋子相鄰的點上沒有棋子時就可以跳過對方的這個棋子把它吃掉；③連跳，連續(xù)多個單跳，吃掉己方行走路線上所有對方的子，棋子落到空交叉點上。在移動、單跳、或者連跳結(jié)束后，如果已方形成一個方(4個同色的棋子形成一個正方形)，則在對方的任意位置吃掉對方一個子。因此，在布局及戰(zhàn)斗中，已方要盡力成方，同時阻止對方成方。

4)陣型：“久”棋共有160種陣型及其變形。常見的有褡褳陣、拉薩陣、槍陣、經(jīng)輪陣、鞋陣、燒陣、恰陣等。褡褳陣是“久”棋中非常重要的陣型，該陣型對棋的輸贏影響重大。褡褳分為單褡褳和雙褡褳，如圖2所示。單褡褳陣由7個棋子或者8個棋子組成。7個棋子形成的褡褳陣如圖2中左上、左下所示，該陣型中移動中間一顆黑棋就可成方。8個棋子形成的褡褳陣如圖2中右上所示，將該陣型中最下方的兩個棋子中的任意一個移動至空交叉點，即可成方。十個棋子形成的褡褳陣如圖2右下方所示，該褡褳陣屬于雙褡褳，戰(zhàn)斗力及防御能力比單褡褳更強。

圖 2 褡褳Fig. 2 Dalian

2 “久”棋的棋型及其對策

本文作者在阿壩地區(qū)進行了深入調(diào)研及實地考察，采集了約300局“久”棋高手的對弈記錄。通過分析該記錄，發(fā)現(xiàn)棋型對“久”棋勝負的影響很大，因此，研究棋型具有重要的意義。本文提取了常用棋型，設計了針對某棋型的應對策略。

1)三角棋型

三角棋型是在對方成方之前，出現(xiàn)一個缺口的棋型，如圖3中白色三子。應對策略是阻止白色棋子成方，把缺口填上，將黑子布置在圖3所示位置。

圖 3 三角棋型及其對策Fig. 3 Triangle form and its tactics

2)三子棋型

三子棋型是在同一直線上擺放三個同色棋子，如圖4中白子。若白棋走在圖中黑子位置，白棋就能做出兩個棋門，威力很大。因此，應對該棋型的策略是如圖4所示，阻止白棋形成兩個三角棋型。

圖 4 三子棋型及其對策Fig. 4 Trinity form and its tactics

3)二子棋型

二子棋型是指兩個棋子周圍均沒有己方的棋子，如圖5白色二子所示。

圖 5 二子棋型Fig. 5 Twain form

當某方出現(xiàn)該棋型時，若再下一子，就會變成三子棋型或者三角棋型。

因此，應對該棋型的策略是阻止該棋型成為三子棋型或者三角棋型。

4)對角棋型

對角棋型是指棋盤上同色兩子成90°夾著異色棋子的陣型。如圖6中黑色二子夾著白色一子。此時，為了阻止黑色棋子布置在白色的對角成方，應將白色棋子下在圖6中所示位置進行應對。

圖 6 對角棋型及其對策Fig. 6 Contrast form and its tactics

圖 8 使用確定有限自動機識別棋譜過程Fig. 8 Deterministic finite automaton to recognize chess record

5)四子棋型

四子棋型是指同色四子形成一個方，如圖7中白色的四顆棋子所示。四子棋型是整個戰(zhàn)斗階段中最強的陣型，褡褳、拉薩等陣型都是由此形成。一旦己方形成四子棋型，就可以吃掉棋盤上對方的任意一子。因此，在布局和戰(zhàn)斗階段，己方要盡力使自己形成四子棋型，阻止對方形成四子棋型。

圖 7 四子棋型Fig. 7 Square form

3 “久”棋中使用的模式匹配算法

“久”棋中，布局的質(zhì)量對勝負影響很大，而以棋盤中央對角線為中心的約40步棋的布局幾乎決定了整個布局的質(zhì)量，因此，在布局的前40步，使用模式匹配方法進行布局。具體來說，將錄制的300局對弈數(shù)據(jù)采用SGF格式進行處理后，構(gòu)建棋譜。使用確定有限自動機表示識別棋譜，使用BM字符串匹配算法進行模式匹配。

由于“久”棋的棋盤與圍棋類似，因此借鑒圍棋打譜的方式，仿照SGF的格式，建立“久”棋的棋譜文件。

3.1 確定有限自動機識別棋譜及當前盤面

棋譜及當前盤面的識別是模式匹配中的重要環(huán)節(jié)。確定有限狀態(tài)機(deterministic finite automaton，DFA)能夠識別字符串，做出接受或者拒絕的判斷[17]。下棋的若干步之間存在依賴關系，因此可以把每一個棋譜看作一個DFA。

把棋譜表示成一個確定有限自動機，如圖8。

3.2 BM模式匹配算法

BM(Boyer Moore)算法是最為快速的模式匹配算法之一[18]，因此，本文采用BM算法對棋譜及當前局面進行模式匹配。待匹配字符串為長度為的棋譜，定義為，模式串為長度為的當前局面，定義為，其中，“久”棋中，模式匹配算法的偽代碼如下：

changtodfa;//把棋局的下子順序變成DFA格式

List＜Integer＞ matches =BoyerMoore.match(strb,str[i]); //使用BM算法對所有存在的棋譜與當前棋局相匹配

}//去除所有相匹配的棋局的下子策略

4 基于棋型的攻防策略

“久”棋布局階段的質(zhì)量對弈棋勝負影響很大，棋盤中央對角線附近約40步棋的棋子布局又直接決定一盤棋布局的好壞。戰(zhàn)斗階段，哪一方最先形成褡褳，哪一方就具有明顯的贏棋優(yōu)勢。在布局及戰(zhàn)斗階段，好的棋型非常重要。本文設計了基于棋型的攻防策略，分別應用于“久”棋布局及戰(zhàn)斗階段。

4.1 基于矩陣的棋型識別方法

對于上述提出的棋型，本文提出了基于矩陣的棋型識別方法，具體如下。以三角棋型為例，定義矩陣TS如式(1)所示：

式中：0是該位置為空，1是該位置為白棋，2是該位置為黑棋。當前棋局的矩陣TB如式(2)所示。

把矩陣TS擴充成與TB規(guī)模相同的矩陣TSE，如式(3)所示：

根據(jù)矩陣乘法的性質(zhì)，把棋型矩陣擴展后的TSE和矩陣TB的轉(zhuǎn)置矩陣相乘，如式(4)：

如果相乘的結(jié)果TR和TSE相等，則當前的局面中存在三角棋型。同理，其他棋型也能通過上述的方法進行識別。

4.2 布局階段的攻防策略

布局階段，設計3種策略：防守、攻擊、連子，3種策略的優(yōu)先級別從高到底，即防守策略有效時，進攻和連子策略不考慮，進攻策略有效時，連子策略不考慮。防守策略主要基于三子棋型、三角棋型及對角棋型。攻擊策略主要基于二子模型。連子策略是在最新下的子的周圍隨機選擇落點。

每種策略中，針對不同棋型，賦予不同的評估分值。防守策略中，三子棋型為5分，三角棋型為4分，對角棋型為3分。攻擊策略中，二子棋型為5分。

4.3 戰(zhàn)斗階段的攻防策略

在戰(zhàn)斗階段，使用式(5)的評估方法：式中：move為移動的評分，kill為單跳吃(連跳吃)的總評分，triple為是否阻止敵方成為四子棋型的總評分，suqare為己方在跳吃或者移動以后成為四子棋型的總評分。

根據(jù)上述的策略評估方法，在布局階段和戰(zhàn)斗階段，可以選出較優(yōu)的攻防策略。

5 “久”棋博弈軟件的設計和實現(xiàn)

“久”棋博弈軟件由布局階段和戰(zhàn)斗階段組成。軟件的整體設計如圖9所示。布局界面接受用戶點擊，把棋子下到界面上某位置，并標記下子的順序。戰(zhàn)斗界面接受用戶的點擊，實現(xiàn)提子和下子的功能，并判斷下子后是否形成方，詢問用戶是否吃子。

圖 9 程序結(jié)構(gòu)Fig. 9 Program structure

5.1 布局引擎內(nèi)核

布局階段的引擎由棋型匹配、防御策略、攻擊策略、連子策略組成。

布局階段的偽代碼如下：

5.2 戰(zhàn)斗引擎內(nèi)核

戰(zhàn)斗階段引擎由提取活動子、活動棋子所有方案計分、排序選出最高分的方案、實施方案4部分組成。戰(zhàn)斗階段偽代碼如下：

6 測試及分析

本文邀請四川省阿壩藏羌自治州阿壩縣藏棋協(xié)會的原會長尼瑪扎華先生、副會長甲花先生、拉薩藏棋協(xié)會的秘書長阿旺邊巴老師、拉薩棋手白姆頓珠、中央民族大學藏族學生鬧塔與軟件對弈了100局，其中軟件獲勝25局。

邀請的測試選手均為“久”棋高手，尤其是阿壩藏棋協(xié)會的尼瑪扎華先生及甲花先生的弈棋水平極高，本文的博弈軟件提取的棋型還非常有限，采集的棋譜也較少，沒有運用機器學習方法，因此棋力還不是很高。

此外，2016年，使用該軟件在四川省阿壩藏族羌族自治州第七屆“體彩杯”藏棋比賽中開展了人機對弈項目，進行了20局的人機對弈，軟件運行穩(wěn)定，表現(xiàn)良好。

7 結(jié)束語

“久”棋是藏族棋類中保存及傳承較好的棋類游戲之一，2015年，“久”棋被列為四川省非物質(zhì)文化遺產(chǎn)名錄。象棋、圍棋的計算機博弈取得了機器戰(zhàn)勝人類的優(yōu)異成績，但是“久”棋的機器博弈研究尚處于起步階段。本文提取了“久”棋的常用棋型，提出了基于棋型的攻防策略，將基于BM的模式匹配算法應用于布局的前40步。開發(fā)了博弈軟件，由于提取的棋型有限，采集的對弈數(shù)據(jù)較少，該軟件的棋力無法與“久”棋高手對弈，但是運行穩(wěn)定，功能齊全。AlphaGo Zero不需要人類知識，只訓練一個神經(jīng)網(wǎng)絡，采用增強學習與蒙特卡洛樹搜索相結(jié)合，完勝AlphaGo。借鑒AlphaGo Zero的思路，集合硬件設施條件，開展“久”棋的博弈研究工作，將有可能為未來“久”棋博弈研究提供重要思路。