李霞麗，吳立成，李永集

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖 2 褡褳Fig. 2 Dalian

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

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

1)三角棋型

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

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

2)三子棋型

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

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

3)二子棋型

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

圖 5 二子棋型Fig. 5 Twain form

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

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

4)對角棋型

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

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

圖 8 使用確定有限自動(dòng)機(jī)識(shí)別棋譜過程Fig. 8 Deterministic finite automaton to recognize chess record

5)四子棋型

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

圖 7 四子棋型Fig. 7 Square form

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

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

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

3.1 確定有限自動(dòng)機(jī)識(shí)別棋譜及當(dāng)前盤面

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

把棋譜表示成一個(gè)確定有限自動(dòng)機(jī)，如圖8。

3.2 BM模式匹配算法

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

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

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

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

4 基于棋型的攻防策略

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

4.1 基于矩陣的棋型識(shí)別方法

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

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

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

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

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

4.2 布局階段的攻防策略

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

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

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

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

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

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

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

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

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

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

布局階段的偽代碼如下：

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

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

6 測試及分析

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

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

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

7 結(jié)束語

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