第13卷第4期 智能系统学报 Vol.13 No.4 2018年8月 CAAI Transactions on Intelligent Systems Aug.2018 D0:10.11992/tis.201609023 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180515.1116.002.html 基于棋型的藏族“久”棋计算机博弈研究 李霞丽，吴立成，李永集 (中央民族大学信息工程学院，北京100081) 摘要：“久”棋是藏族人民的传统棋类游戏，游戏过程分为布局阶段和战斗阶段，布局的质量对弈棋结果影响 很大。与围棋博弈智能软件战胜人类高手的情况比较，“久”棋博弈研究几乎空白。为了拓宽机器博弈研究的 游戏范围，开发具有较高棋力的“久”棋软件，作者开展了基于棋型的“久”棋计算机博弈研究。通过实地考察， 在四川阿坝地区采集了约300局有效的“久”棋对弈数据，提取了常见棋型，分别为棋型命名为三角、三子、二 子、对角、四子等。在布局阶段，采用模式匹配算法提高棋型的匹配速度。在布局和战斗阶段，基于棋型，设计 了具有优先级别的防守、攻击、连子策略。采用C语言开发了“久”棋博弈软件，该软件具有人人对弈、人机对 弈、自动录制棋谱等功能。该软件在2016年四川省阿坝县第七届“体彩杯”藏棋比赛中成功开展了人机对弈， 但是棋力有待提高。结果表明，基于棋型的攻防策略能够有效地应用于“久”棋计算机博弈。 关键词：计算机博弈：藏族“久”棋：棋型：攻防策略：模式匹配 中图分类号：TP39文献标志码：A文章编号：1673-4785(2018)04-0577-07 中文引用格式：李霞丽，吴立成，李永集.基于棋型的藏族“久”棋计算机博弈研究J智能系统学报，2018,13(4)：577-583， 英文引用格式：LI Xiali,WU Licheng,LI Yongji.Tibetan JIU computer game research based on chess formJ.CAAI transactions on intelligent systems,2018,13(4):577-583. Tibetan JIU computer game research based on chess form LI Xiali,WU Licheng,LI Yongji (School of Information Engineering,Minzu University of China,Beijing 100081,China) Abstract:JIU is a traditional Tibetan board game that is divided into two sequential stages-embattle(or prepare for battle)and battle.The embattle stage has a critical effect on the subsequent battle.Compared with AlphaGo and Al- phaGo Zero computer programs,which have defeated top human players,research on the game of JIU is almost nonex- istent.To broaden the scope of computer game research and work toward the development of a sophisticated JIU chess game,we conducted a computer game study of the formations used in chess.Specifically,we collected about 300 JIU play records in an on-the-spot investigation in the Aba Autonomous Prefecture of Sichuan Province.In our analysis of these play records,we identified several common chess formations,which we refer to as the triangle,trinity,twain,con- trast,and square formations.To increase the speed of the character string matching process,we used a pattern matching algorithm in the embattle stage.We also designed defensive,attack,and collaboration strategies for the embattle and battle stages based on these chess formations.The defensive,attack,and collaboration strategies have decreasing prior- ity.Then,we developed JIU chess software using C language,with functions including the man-man VS mode, human-computer VS AI mode,and automatic recording of the play process.This software performed consistently in the man-machine game play exhibition at the 2016 Seventh "Sports Lottery Cup"Tibetan Chess Contest held in the Aba Autonomous Prefecture of Sichuan Province.However,the chess level realized by the software must be improved.The results show that attack and defense strategies based on chess formations can be effectively applied to JIU chess com- puter games. Keywords:computer games,Tibetan JIU chess;chess form;attack and defense strategies,pattern matching 收稿日期：2016-09-23.网络出版日期：2018-05-17 藏棋是藏族人民的传统游戏，主要流传于我 基金项目：国家自然科学基金项目(61602539,61773416) 通信作者：吴立成.E-mail:Wulicheng@tsinghua.edu.cn 国西藏以及十大藏区，是藏族文化宝库中一颗璀
DOI: 10.11992/tis.201609023 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180515.1116.002.html 基于棋型的藏族“久”棋计算机博弈研究 李霞丽，吴立成，李永集 （中央民族大学 信息工程学院，北京 100081） 摘 要：“久”棋是藏族人民的传统棋类游戏，游戏过程分为布局阶段和战斗阶段，布局的质量对弈棋结果影响 很大。与围棋博弈智能软件战胜人类高手的情况比较，“久”棋博弈研究几乎空白。为了拓宽机器博弈研究的 游戏范围，开发具有较高棋力的“久”棋软件，作者开展了基于棋型的“久”棋计算机博弈研究。通过实地考察， 在四川阿坝地区采集了约 300 局有效的“久”棋对弈数据，提取了常见棋型，分别为棋型命名为三角、三子、二 子、对角、四子等。在布局阶段，采用模式匹配算法提高棋型的匹配速度。在布局和战斗阶段，基于棋型，设计 了具有优先级别的防守、攻击、连子策略。采用 C 语言开发了“久”棋博弈软件，该软件具有人人对弈、人机对 弈、自动录制棋谱等功能。该软件在 2016 年四川省阿坝县第七届“体彩杯”藏棋比赛中成功开展了人机对弈， 但是棋力有待提高。结果表明，基于棋型的攻防策略能够有效地应用于“久”棋计算机博弈。 关键词：计算机博弈；藏族“久”棋；棋型；攻防策略；模式匹配 中图分类号：TP39 文献标志码：A 文章编号：1673−4785(2018)04−0577−07 中文引用格式：李霞丽, 吴立成, 李永集. 基于棋型的藏族“久”棋计算机博弈研究[J]. 智能系统学报, 2018, 13(4): 577–583. 英文引用格式：LI Xiali, WU Licheng, LI Yongji. Tibetan JIU computer game research based on chess form[J]. CAAI transactions on intelligent systems, 2018, 13(4): 577–583. Tibetan JIU computer game research based on chess form LI Xiali，WU Licheng，LI Yongji (School of Information Engineering, Minzu University of China, Beijing 100081, China) Abstract: JIU is a traditional Tibetan board game that is divided into two sequential stages—embattle (or prepare for battle) and battle. The embattle stage has a critical effect on the subsequent battle. Compared with AlphaGo and AlphaGo Zero computer programs, which have defeated top human players, research on the game of JIU is almost nonexistent. To broaden the scope of computer game research and work toward the development of a sophisticated JIU chess game, we conducted a computer game study of the formations used in chess. Specifically, we collected about 300 JIU play records in an on-the-spot investigation in the Aba Autonomous Prefecture of Sichuan Province. In our analysis of these play records, we identified several common chess formations, which we refer to as the triangle, trinity, twain, contrast, and square formations. To increase the speed of the character string matching process, we used a pattern matching algorithm in the embattle stage. We also designed defensive, attack, and collaboration strategies for the embattle and battle stages based on these chess formations. The defensive, attack, and collaboration strategies have decreasing priority. Then, we developed JIU chess software using C language, with functions including the man–man VS mode, human–computer VS AI mode, and automatic recording of the play process. This software performed consistently in the man–machine game play exhibition at the 2016 Seventh “Sports Lottery Cup” Tibetan Chess Contest held in the Aba Autonomous Prefecture of Sichuan Province. However, the chess level realized by the software must be improved. The results show that attack and defense strategies based on chess formations can be effectively applied to JIU chess computer games. Keywords: computer games; Tibetan JIU chess; chess form; attack and defense strategies; pattern matching 藏棋是藏族人民的传统游戏，主要流传于我 国西藏以及十大藏区，是藏族文化宝库中一颗璀 收稿日期：2016−09−23. 网络出版日期：2018−05−17. 基金项目：国家自然科学基金项目 (61602539, 61773416). 通信作者：吴立成. E-mail：Wulicheng@tsinghua.edu.cn. 第 13 卷第 4 期 智 能 系 统 学 报 Vol.13 No.4 2018 年 8 月 CAAI Transactions on Intelligent Systems Aug. 2018
·578· 智能系统学报 第13卷 璨的明珠，是人类社会文化的补充与完善，具有 式围棋的博弈搜索算法、局面评估算法等进行了 藏族独特的内涵和民族文化特征，深受藏族人民 初步研究，开发了一个藏式围棋博弈系统，并将 的喜爱。藏棋棋种有几十种，“久”棋是其中 其应用于教学研究中。 的大棋种，保护及传承得也较好。“久”是藏语译 上述文献虽然对藏棋的计算机应用进行研 音，是“方”的意思，还有一种说法是拼图的意 究，但多是开发软件，将藏棋信息化，并没有真正 思。“久”棋的对弈过程分为布局和战斗两个阶 从机器博弈的角度研究藏棋，“久”棋的研究文献 段，具有极强的趣味性、竞技性和生命力。布局 更是接近于无。 阶段将棋子布满棋盘，不吃子、不移动棋子。战 “久”棋在四川阿坝藏族羌族自治州的保护及 斗阶段通过移动棋子实现吃子。 传承很好，2015年被列为四川省非物质文化遗产 “久”棋作为藏族棋类的大棋种，是具有相似 名录。本文作者在阿坝地区进行了深入调研及实 棋规棋理的棋类游戏的出色代表，是中华民族的 地考察，采集了约300局有效的对弈数据。通过 优秀棋类文化的代表。“久”棋分布极广，广泛流 分析棋谱，提取了“久”棋中的几种常用棋型，分 行于四川藏区、甘肃藏区等。经考证，青海盛行 别为棋型命名为三角、三子、二子、对角、四子等。 的夹棋、西藏盛行的国王与大臣棋、内蒙盛行的 将作者录制的300局对弈数据采用SGF格式进行 蒙古战旗、贵州都匀水族传统棋艺等棋种，甚至 处理后，建立棋谱库。使用确定有限自动机识别 汉族地区民间的狼吃小羊棋，在棋规棋理上均与 当前盘面及棋谱，使用BM字符串匹配算法将当 “久”棋类似。 前盘面与棋谱进行匹配。本文提出了基于棋型的 机器博弈是人工智能领域最具挑战性的研究 攻防策略进行“久”棋布局及战斗。本文开发了首 方向之一，是人工智能的果蝇。1997年，BM深 款“久”棋博弈软件，该软件具有人人对弈、人机 蓝战胜了卡斯帕罗夫，国际象棋的计算机博弈取 对弈、自动录制棋谱功能，邀请了“久”棋高手测 得了机器战胜棋类高手的优异成绩。2016年，谷 试软件，测试结果表明该软件能够正常运行，但 歌Alpha Go将深度学习应用于围棋博弈，使用政 是棋力尚待提高。该软件在2016年四川省阿坝 策网络及价值网络对搜索树进行剪枝，取得了机 县第七届“体彩杯”藏棋比赛的人机对弈项目中运 器战胜人类高手的优异成绩s-。Facebook的Dark- 行稳定。 Forest将卷积神经网络和蒙特卡罗树搜索有机结 1“久”棋的棋规 合网，也具备很高的棋力。2017年，谷歌推出了Apha Go Zero,.采用一种新的自对弈强化学习方法进行 “久”棋的棋盘有11路、14路等。常见的是 训练，训练开始时完全随机下棋，不需要人类棋 14路棋盘，如图1所示。纵横14条等距平行线， 手知识的指导。AlphaGo Zero仅仅将棋盘上的黑 正中的小方格里，有一对角线。布局从对角线开 子和白子作为输入，使用一个神经网络进行训练。 始，向外扩散，当棋盘上所有交叉点都被布满之 蒙特卡洛搜索树也更加简洁，仅仅使用一个神经 后，取掉对角上的两颗棋子，进入战斗阶段。棋 网络进行着法预测和评估。与围棋博弈研究不 子只能放置在线与线的交叉点上，方格中不能放 入棋子。 同，藏棋博弈研究尚处于起步阶段，其博弈算法 研究具有很大的发展空间。 现有的藏棋研究文献[11-13]主要关注藏式围 棋及其他藏棋的历史、棋规等。也有部分文献141可 探讨了夹棋、王宫双门棋、褡裢、杰布杰曾的计算 机应用研究。文献[14]首次进行了藏棋研究，开 发了全国第一款藏族棋类软件，经考证，该棋种 是流行于青海地区的夹棋；文献[15]讨论了王宫 双门棋不规则棋盘状态空间表示、着法产生、终 局判断等关键问题，给出了基本解决策略；文献 [16]开发了“褡裢”，该款藏棋较为简单，适用于小 图1“久”棋的棋盘 朋友开发智力：文献[1]研究了对弈熵率在藏棋 Fig.1 The board of JIU “杰布杰曾”上的应用，通过对弈双方熵率比较， 1)猜先选定黑子或者白子，布局阶段白子先 得出国王取胜可能性较高的结论；文献[18]对藏 行，战斗阶段黑子先走
璨的明珠[1] ，是人类社会文化的补充与完善，具有 藏族独特的内涵和民族文化特征，深受藏族人民 的喜爱[2-3]。藏棋棋种有几十种[4] ，“久”棋是其中 的大棋种，保护及传承得也较好。“久”是藏语译 音，是“方”的意思，还有一种说法是拼图的意 思。“久”棋的对弈过程分为布局和战斗两个阶 段，具有极强的趣味性、竞技性和生命力。布局 阶段将棋子布满棋盘，不吃子、不移动棋子。战 斗阶段通过移动棋子实现吃子。 “久”棋作为藏族棋类的大棋种，是具有相似 棋规棋理的棋类游戏的出色代表，是中华民族的 优秀棋类文化的代表。“久”棋分布极广，广泛流 行于四川藏区、甘肃藏区等。经考证，青海盛行 的夹棋、西藏盛行的国王与大臣棋、内蒙盛行的 蒙古战旗、贵州都匀水族传统棋艺等棋种，甚至 汉族地区民间的狼吃小羊棋，在棋规棋理上均与 “久”棋类似。 机器博弈是人工智能领域最具挑战性的研究 方向之一，是人工智能的果蝇[5]。1997 年，IBM 深 蓝战胜了卡斯帕罗夫，国际象棋的计算机博弈取 得了机器战胜棋类高手的优异成绩。2016 年，谷 歌 Alpha Go 将深度学习应用于围棋博弈，使用政 策网络及价值网络对搜索树进行剪枝，取得了机 器战胜人类高手的优异成绩[6-7]。Facebook 的 DarkForest 将卷积神经网络和蒙特卡罗树搜索有机结 合 [8] ，也具备很高的棋力。2017 年，谷歌推出了 AlphaGo Zero，采用一种新的自对弈强化学习方法进行 训练，训练开始时完全随机下棋，不需要人类棋 手知识的指导。AlphaGo Zero 仅仅将棋盘上的黑 子和白子作为输入，使用一个神经网络进行训练。 蒙特卡洛搜索树也更加简洁，仅仅使用一个神经 网络进行着法预测和评估[9]。与围棋博弈研究不 同，藏棋博弈研究尚处于起步阶段，其博弈算法 研究具有很大的发展空间[10]。 现有的藏棋研究文献[11-13]主要关注藏式围 棋及其他藏棋的历史、棋规等。也有部分文献[14-17] 探讨了夹棋、王宫双门棋、褡裢、杰布杰曾的计算 机应用研究。文献[14]首次进行了藏棋研究，开 发了全国第一款藏族棋类软件，经考证，该棋种 是流行于青海地区的夹棋；文献[15]讨论了王宫 双门棋不规则棋盘状态空间表示、着法产生、终 局判断等关键问题，给出了基本解决策略；文献 [16]开发了“褡裢”，该款藏棋较为简单，适用于小 朋友开发智力；文献[17]研究了对弈熵率在藏棋 “杰布杰曾”上的应用，通过对弈双方熵率比较， 得出国王取胜可能性较高的结论；文献[18]对藏 式围棋的博弈搜索算法、局面评估算法等进行了 初步研究，开发了一个藏式围棋博弈系统，并将 其应用于教学研究中。 上述文献虽然对藏棋的计算机应用进行研 究，但多是开发软件，将藏棋信息化，并没有真正 从机器博弈的角度研究藏棋，“久”棋的研究文献 更是接近于无。 “久”棋在四川阿坝藏族羌族自治州的保护及 传承很好，2015 年被列为四川省非物质文化遗产 名录。本文作者在阿坝地区进行了深入调研及实 地考察，采集了约 300 局有效的对弈数据。通过 分析棋谱，提取了“久”棋中的几种常用棋型，分 别为棋型命名为三角、三子、二子、对角、四子等。 将作者录制的 300 局对弈数据采用 SGF 格式进行 处理后，建立棋谱库。使用确定有限自动机识别 当前盘面及棋谱，使用 BM 字符串匹配算法将当 前盘面与棋谱进行匹配。本文提出了基于棋型的 攻防策略进行“久”棋布局及战斗。本文开发了首 款“久”棋博弈软件，该软件具有人人对弈、人机 对弈、自动录制棋谱功能，邀请了“久”棋高手测 试软件，测试结果表明该软件能够正常运行，但 是棋力尚待提高。该软件在 2016 年四川省阿坝 县第七届“体彩杯”藏棋比赛的人机对弈项目中运 行稳定。 1 “久”棋的棋规 “久”棋的棋盘有 11 路、14 路等。常见的是 14 路棋盘，如图 1 所示。纵横 14 条等距平行线， 正中的小方格里，有一对角线。布局从对角线开 始，向外扩散，当棋盘上所有交叉点都被布满之 后，取掉对角上的两颗棋子，进入战斗阶段。棋 子只能放置在线与线的交叉点上，方格中不能放 入棋子。 图 1 “久”棋的棋盘 Fig. 1 The board of JIU 1) 猜先选定黑子或者白子，布局阶段白子先 行，战斗阶段黑子先走。 ·578· 智 能 系 统 学 报 第 13 卷
第4期 李霞丽，等：基于棋型的藏族“久”棋计算机博弈研究 ·579· 2)布局：白子从棋盘中央对角线的两端任意 很大，因此，研究棋型具有重要的意义。本文提 选一个点布子，接着，黑子在对角线的另外一端布 取了常用棋型，设计了针对某棋型的应对策略。 子。双方轮流放子，直至布满整个棋盘的交叉点。 1)三角棋型 3)战斗：布局完成后，取掉对角上的两颗棋 三角棋型是在对方成方之前，出现一个缺口 子，进入战斗阶段。战斗阶段，黑子先行走棋。 的棋型，如图3中白色三子。应对策略是阻止白 走棋的方式包括：①移动，棋子向紧邻的空交叉 色棋子成方，把缺口填上，将黑子布置在图3所示 点移动一格，上、下、左、右4个方向可以任意移 位置。 动：②单跳，在己方棋子行走的路线上有一个对 方的棋子，而且与对方棋子相邻的点上没有棋子 时就可以跳过对方的这个棋子把它吃掉；③连 跳，连续多个单跳，吃掉己方行走路线上所有对 方的子，棋子落到空交叉点上。在移动、单跳、或 者连跳结束后，如果已方形成一个方(4个同色的 棋子形成一个正方形)，则在对方的任意位置吃掉 图3三角棋型及其对策 对方一个子。因此，在布局及战斗中，已方要尽 Fig.3 Triangle form and its tactics 力成方，同时阻止对方成方。 2)三子棋型 4)阵型：“久”棋共有160种阵型及其变形。 三子棋型是在同一直线上摆放三个同色棋 常见的有褡裢阵、拉萨阵、枪阵、经轮阵、鞋阵、 子，如图4中白子。若白棋走在图中黑子位置，白 烧阵、恰阵等。褡裢阵是“久”棋中非常重要的阵 棋就能做出两个棋门，威力很大。因此，应对该 型，该阵型对棋的输赢影响重大。褡裢分为单褡 棋型的策略是如图4所示，阻止白棋形成两个三 裢和双褡裢，如图2所示。单褡裢阵由7个棋子 角棋型。 或者8个棋子组成。7个棋子形成的褡裢阵如图 2中左上、左下所示，该阵型中移动中间一颗黑棋 就可成方。8个棋子形成的褡裢阵如图2中右上 所示，将该阵型中最下方的两个棋子中的任意一 个移动至空交叉点，即可成方。十个棋子形成的 褡裢阵如图2右下方所示，该褡裢阵属于双褡裢， 战斗力及防御能力比单褡裢更强。 ABCDE FGHI JKLMNO 图4三子棋型及其对策 14 Fig.4 Trinity form and its tactics 13 3 3)二子棋型 ) 二子棋型是指两个棋子周围均没有己方的棋 9 9 子，如图5白色二子所示。 8 6 6 5 5 3 43 2 2 ABCDEFGHIJKLMNO 图5二子棋型 图2褡链 Fig.5 Twain form Fig.2 Dalian 当某方出现该棋型时，若再下一子，就会变成 2“久”棋的棋型及其对策 三子棋型或者三角棋型。 因此，应对该棋型的策略是阻止该棋型成为 本文作者在阿坝地区进行了深入调研及实地 三子棋型或者三角棋型。 考察，采集了约300局“久”棋高手的对弈记录。 4)对角棋型 通过分析该记录，发现棋型对“久”棋胜负的影响 对角棋型是指棋盘上同色两子成90°夹着异
2) 布局：白子从棋盘中央对角线的两端任意 选一个点布子，接着，黑子在对角线的另外一端布 子。双方轮流放子，直至布满整个棋盘的交叉点。 3) 战斗：布局完成后，取掉对角上的两颗棋 子，进入战斗阶段。战斗阶段，黑子先行走棋。 走棋的方式包括：①移动，棋子向紧邻的空交叉 点移动一格，上、下、左、右 4 个方向可以任意移 动；②单跳，在己方棋子行走的路线上有一个对 方的棋子，而且与对方棋子相邻的点上没有棋子 时就可以跳过对方的这个棋子把它吃掉；③连 跳，连续多个单跳，吃掉己方行走路线上所有对 方的子，棋子落到空交叉点上。在移动、单跳、或 者连跳结束后，如果已方形成一个方 (4 个同色的 棋子形成一个正方形)，则在对方的任意位置吃掉 对方一个子。因此，在布局及战斗中，已方要尽 力成方，同时阻止对方成方。 4) 阵型：“久”棋共有 160 种阵型及其变形。 常见的有褡裢阵、拉萨阵、枪阵、经轮阵、鞋阵、 烧阵、恰阵等。褡裢阵是“久”棋中非常重要的阵 型，该阵型对棋的输赢影响重大。褡裢分为单褡 裢和双褡裢，如图 2 所示。单褡裢阵由 7 个棋子 或者 8 个棋子组成。7 个棋子形成的褡裢阵如图 2 中左上、左下所示，该阵型中移动中间一颗黑棋 就可成方。8 个棋子形成的褡裢阵如图 2 中右上 所示，将该阵型中最下方的两个棋子中的任意一 个移动至空交叉点，即可成方。十个棋子形成的 褡裢阵如图 2 右下方所示，该褡裢阵属于双褡裢， 战斗力及防御能力比单褡裢更强。 14 13 12 11 10 9 8 7 6 5 4 3 2 1 A B C D E F G H I J K L M N O A B C D E F G H I J K L M N O 14 13 12 11 10 9 8 7 6 5 4 3 2 1 图 2 褡裢 Fig. 2 Dalian 2 “久”棋的棋型及其对策 本文作者在阿坝地区进行了深入调研及实地 考察，采集了约 300 局“久”棋高手的对弈记录。 通过分析该记录，发现棋型对“久”棋胜负的影响 很大，因此，研究棋型具有重要的意义。本文提 取了常用棋型，设计了针对某棋型的应对策略。 1) 三角棋型 三角棋型是在对方成方之前，出现一个缺口 的棋型，如图 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 当某方出现该棋型时，若再下一子，就会变成 三子棋型或者三角棋型。 因此，应对该棋型的策略是阻止该棋型成为 三子棋型或者三角棋型。 4) 对角棋型 对角棋型是指棋盘上同色两子成 90°夹着异 第 4 期 李霞丽，等：基于棋型的藏族“久”棋计算机博弈研究 ·579·
·580· 智能系统学报 第13卷 色棋子的阵型。如图6中黑色二子夹着白色一 此可以把每一个棋谱看作一个DFA。 子。此时，为了阻止黑色棋子布置在白色的对角成 把棋谱表示成一个确定有限自动机，如图8。 方，应将白色棋子下在图6中所示位置进行应对。 年始 -一→0"甲0o"o0一→© 图8使用确定有限自动机识别棋谱过程 Fig.8 Deterministic finite automaton to recognize chess record 图8中，W[gg、Bhh、W[gh、B[hg表示状 态转移条件，W表示白子，B表示黑子，中括号的 字母表示棋子的坐标。 图6对角棋型及其对策 3.2BM模式匹配算法 Fig.6 Contrast form and its tactics BM(Boyer Moore)算法是最为快速的模式匹 5)四子棋型 配算法之一图，因此，本文采用BM算法对棋谱及 四子棋型是指同色四子形成一个方，如图7 当前局面进行模式匹配。待匹配字符串为长度为 中白色的四颗棋子所示。四子棋型是整个战斗阶 n的棋谱T,定义为T[OT[1]T[2]…Tn-2]Tn-1], 段中最强的阵型，褡裢、拉萨等阵型都是由此形 模式串为长度为m的当前局面P,定义为P[O]P[1] 成。一旦己方形成四子棋型，就可以吃掉棋盘上 P[2]…P[m-2]P[m-1],其中，n≥m 对方的任意一子。因此，在布局和战斗阶段，己 “久”棋中，模式匹配算法的伪代码如下： 方要尽力使自己形成四子棋型，阻止对方形成四 private coordinate sgfmatch(inti){ 子棋型。 changtodfa;把棋局的下子顺序变成DFA格式 List<Integer>matches=BoyerMoore.match(strb, st[]),∥使用BM算法对所有存在的棋谱与当前 棋局相匹配 for(Integer integer:matches){ i=str[i].charAt(integer+strb.length()+2)-'a'; j=str[i].charAt(integer+strb.length()+3)-'a'; 图7四子棋型 } Fig.7 Square form /去除所有相匹配的棋局的下子策略 3“久”棋中使用的模式匹配算法 4基于棋型的攻防策略 “久”棋中，布局的质量对胜负影响很大，而以 “久”棋布局阶段的质量对弈棋胜负影响很 棋盘中央对角线为中心的约40步棋的布局几乎 大，棋盘中央对角线附近约40步棋的棋子布局又 决定了整个布局的质量，因此，在布局的前 直接决定一盘棋布局的好坏。战斗阶段，哪一方 40步，使用模式匹配方法进行布局。具体来说， 最先形成褡裢，哪一方就具有明显的赢棋优势。 将录制的300局对弈数据采用SGF格式进行处理 在布局及战斗阶段，好的棋型非常重要。本文设 后，构建棋谱。使用确定有限自动机表示识别棋 计了基于棋型的攻防策略，分别应用于“久”棋布 谱，使用BM字符串匹配算法进行模式匹配。 局及战斗阶段。 由于“久”棋的棋盘与围棋类似，因此借鉴围 4.1基于矩阵的棋型识别方法 棋打谱的方式，仿照SGF的格式，建立“久”棋的 对于上述提出的棋型，本文提出了基于矩阵 棋谱文件。 的棋型识别方法，具体如下。以三角棋型为例， 3.1确定有限自动机识别棋谱及当前盘面 定义矩阵TS如式(1)所示： 棋谱及当前盘面的识别是模式匹配中的重要 环节。确定有限状态机(deterministic finite auto- s=[9 (1) maton,DFA)能够识别字符串，做出接受或者拒绝 式中：0是该位置为空，1是该位置为白棋，2是该 的判断。下棋的若干步之间存在依赖关系，因 位置为黑棋。当前棋局的矩阵TB如式(2)所示
色棋子的阵型。如图 6 中黑色二子夹着白色一 子。此时，为了阻止黑色棋子布置在白色的对角成 方，应将白色棋子下在图 6 中所示位置进行应对。 图 6 对角棋型及其对策 Fig. 6 Contrast form and its tactics 5) 四子棋型 四子棋型是指同色四子形成一个方，如图 7 中白色的四颗棋子所示。四子棋型是整个战斗阶 段中最强的阵型，褡裢、拉萨等阵型都是由此形 成。一旦己方形成四子棋型，就可以吃掉棋盘上 对方的任意一子。因此，在布局和战斗阶段，己 方要尽力使自己形成四子棋型，阻止对方形成四 子棋型。 图 7 四子棋型 Fig. 7 Square form 3 “久”棋中使用的模式匹配算法 “久”棋中，布局的质量对胜负影响很大，而以 棋盘中央对角线为中心的约 40 步棋的布局几乎 决定了整个布局的质量，因此，在布局的 前 40 步，使用模式匹配方法进行布局。具体来说， 将录制的 300 局对弈数据采用 SGF 格式进行处理 后，构建棋谱。使用确定有限自动机表示识别棋 谱，使用 BM 字符串匹配算法进行模式匹配。 由于“久”棋的棋盘与围棋类似，因此借鉴围 棋打谱的方式，仿照 SGF 的格式，建立“久”棋的 棋谱文件。 3.1 确定有限自动机识别棋谱及当前盘面 棋谱及当前盘面的识别是模式匹配中的重要 环节。确定有限状态机 (deterministic finite automaton，DFA) 能够识别字符串，做出接受或者拒绝 的判断[17]。下棋的若干步之间存在依赖关系，因 此可以把每一个棋谱看作一个 DFA。 把棋谱表示成一个确定有限自动机，如图 8。 开始 0 1 2 3 4 结束 W [gg] B[hh] W [gh] B[hg] 图 8 使用确定有限自动机识别棋谱过程 Fig. 8 Deterministic finite automaton to recognize chess record W [ gg]、B[hh]、W [ gh]、B [ hg] 图 8 中 ， 表示状 态转移条件，W 表示白子，B 表示黑子，中括号的 字母表示棋子的坐标。 3.2 BM 模式匹配算法 n T T[0]T[1]T[2]···T[n−2]T[n−1] m P P[0]P[1] P[2]···P[m−2]P[m−1] n ⩾ m BM(Boyer Moore) 算法是最为快速的模式匹 配算法之一[18] ，因此，本文采用 BM 算法对棋谱及 当前局面进行模式匹配。待匹配字符串为长度为 的棋谱 ，定义为 ， 模式串为长度为 的当前局面 ，定义为 ，其中， “久”棋中，模式匹配算法的伪代码如下： private coordinate sgfmatch(inti) { changtodfa;//把棋局的下子顺序变成 DFA 格式 List<Integer> matches =BoyerMoore.match(strb, str[i]); //使用 BM 算法对所有存在的棋谱与当前 棋局相匹配 for (Integer integer : matches) { i=str[i].charAt(integer+strb.length()+2)-'a'; j=str[i].charAt(integer+strb.length()+3)-'a'; } }//去除所有相匹配的棋局的下子策略 4 基于棋型的攻防策略 “久”棋布局阶段的质量对弈棋胜负影响很 大，棋盘中央对角线附近约 40 步棋的棋子布局又 直接决定一盘棋布局的好坏。战斗阶段，哪一方 最先形成褡裢，哪一方就具有明显的赢棋优势。 在布局及战斗阶段，好的棋型非常重要。本文设 计了基于棋型的攻防策略，分别应用于“久”棋布 局及战斗阶段。 4.1 基于矩阵的棋型识别方法 对于上述提出的棋型，本文提出了基于矩阵 的棋型识别方法，具体如下。以三角棋型为例， 定义矩阵 TS 如式 (1) 所示： TS = [ 0 1 1 1 ] (1) 式中：0 是该位置为空，1 是该位置为白棋，2 是该 位置为黑棋。当前棋局的矩阵 TB 如式 (2) 所示。 ·580· 智 能 系 统 学 报 第 13 卷
第4期 李霞丽，等：基于棋型的藏族“久”棋计算机博弈研究 ·581 00000000000000 式中：move为移动的评分，kill为单跳吃（连跳 0000000000000 0 吃)的总评分，triple为是否阻止敌方成为四子棋 000000000 0000 0 0000000000000 0 型的总评分，sugare为己方在跳吃或者移动以后 0000000000000 0 成为四子棋型的总评分。 0000002010000 0 根据上述的策略评估方法，在布局阶段和战 00000011100000 TB= 0000020200000 0 斗阶段，可以选出较优的攻防策略。 000000000 0000 0 0 0000000 0000 0 5“久”棋博弈软件的设计和实现 0000 0000 0 0000 0 0 0000000 0000 0 “久”棋博弈软件由布局阶段和战斗阶段组 0 0000 0 00 0 0000 0 成。软件的整体设计如图9所示。布局界面接受 00000000000000 用户点击，把棋子下到界面上某位置，并标记下 (2) 把矩阵TS扩充成与TB规模相同的矩阵TSE, 子的顺序。战斗界面接受用户的点击，实现提子 如式(3)所示： 和下子的功能，并判断下子后是否形成方，询问 01000000000000 用户是否吃子。 11000000000000 久棋博弈软件 00000000000 00 0 000000 0 000000 0 000000 0 000000 布局阶段 战斗阶段 00000 0 0 0 0000 0 0 TSE= 000000 000000 布局界面 布局引擎内核 战斗界面 000000 0 0 战斗引擎内核 0000 0 0 0000000000000 0 图9程序结构 000000 0 00000 0 Fig.9 Program structure 000 000 0 0 000 0 0 0 0000000000000 0 5.1 布局引擎内核 000000 0 0000 00 0 布局阶段的引擎由棋型匹配、防御策略、攻 100000000000000 击策略、连子策略组成。 (3) 根据矩阵乘法的性质，把棋型矩阵扩展后的 布局阶段的伪代码如下： TSE和矩阵TB的转置矩阵相乘，如式(4)： voidplaygame(){ TR=TSE.TBT (4) FormGet();/∥从棋谱数据库中获取棋型 如果相乘的结果TR和TSE相等，则当前的 (棋谱数据库中无棋型) 局面中存在三角棋型。同理，其他棋型也能通过 defense(b),∥先采取防守策略 上述的方法进行识别。 局面安全)判断需不需要防守，局 4.2布局阶段的攻防策略 面安全则进攻 布局阶段，设计3种策略：防守、攻击、连子， attack(b): 3种策略的优先级别从高到底，即防守策略有效 elseif(没有防守的策略和进攻策略)H 时，进攻和连子策略不考虑，进攻策略有效时，连 chain(b);/连子策略 子策略不考虑。防守策略主要基于三子棋型、三 } 角棋型及对角棋型。攻击策略主要基于二子模型。 连子策略是在最新下的子的周围随机选择落点。 防守策略： 每种策略中，针对不同棋型，赋予不同的评估 Publicbooleandefense(board b) 分值。防守策略中，三子棋型为5分，三角棋型 tribe(i,j):/检测三子棋型 为4分，对角棋型为3分。攻击策略中，二子棋型 triangle(i,j/检测横三角棋型 为5分。 contrast(ij);∥检测对角棋型 4.3战斗阶段的攻防策略 sortMapBy Value(),/排序权值 在战斗阶段，使用式（⑤）的评估方法： Eva move +kill triple square (5) ∥进攻策略：
TB= 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 2 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (2) 把矩阵 TS 扩充成与 TB 规模相同的矩阵 TSE， 如式 (3) 所示： TSE= 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (3) 根据矩阵乘法的性质，把棋型矩阵扩展后的 TSE 和矩阵 TB 的转置矩阵相乘，如式 (4)： TR = TSE·TBT (4) 如果相乘的结果 TR 和 TSE 相等，则当前的 局面中存在三角棋型。同理，其他棋型也能通过 上述的方法进行识别。 4.2 布局阶段的攻防策略 布局阶段，设计 3 种策略：防守、攻击、连子， 3 种策略的优先级别从高到底，即防守策略有效 时，进攻和连子策略不考虑，进攻策略有效时，连 子策略不考虑。防守策略主要基于三子棋型、三 角棋型及对角棋型。攻击策略主要基于二子模型。 连子策略是在最新下的子的周围随机选择落点。 每种策略中，针对不同棋型，赋予不同的评估 分值。防守策略中，三子棋型为 5 分，三角棋型 为 4 分，对角棋型为 3 分。攻击策略中，二子棋型 为 5 分。 4.3 战斗阶段的攻防策略 在战斗阶段，使用式 (5) 的评估方法： Eva = move+kill+triple+square (5) 式中：move 为移动的评分，kill 为单跳吃 (连跳 吃) 的总评分，triple 为是否阻止敌方成为四子棋 型的总评分，suqare 为己方在跳吃或者移动以后 成为四子棋型的总评分。 根据上述的策略评估方法，在布局阶段和战 斗阶段，可以选出较优的攻防策略。 5 “久”棋博弈软件的设计和实现 “久”棋博弈软件由布局阶段和战斗阶段组 成。软件的整体设计如图 9 所示。布局界面接受 用户点击，把棋子下到界面上某位置，并标记下 子的顺序。战斗界面接受用户的点击，实现提子 和下子的功能，并判断下子后是否形成方，询问 用户是否吃子。 久棋博弈软件 布局阶段 战斗阶段 布局界面 布局引擎内核 战斗界面 战斗引擎内核 图 9 程序结构 Fig. 9 Program structure 5.1 布局引擎内核 布局阶段的引擎由棋型匹配、防御策略、攻 击策略、连子策略组成。 布局阶段的伪代码如下： voidplaygame(){ FormGet();//从棋谱数据库中获取棋型 if(棋谱数据库中无棋型) defense(b);//先采取防守策略 if(局面安全){//判断需不需要防守,局 面安全则进攻 attack(b); } elseif(没有防守的策略和进攻策略){ chain(b);//连子策略 } } //防守策略： Publicbooleandefense(board b){ tribe(i,j); //检测三子棋型 triangle(i,j); //检测横三角棋型 contrast(i,j); //检测对角棋型 sortMapByValue(); //排序权值 } //进攻策略： 第 4 期 李霞丽，等：基于棋型的藏族“久”棋计算机博弈研究 ·581·