第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格式 Listmatches=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 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·
·582· 智能系统学报 第13卷 Publicbooleanattack(board b){ 6测试及分析 twochess(ij);/检测二子棋型 本文邀请四川省阿坝藏羌自治州阿坝县藏棋 连子策略： 协会的原会长尼玛扎华先生、副会长甲花先生、 public voidChain(board b){ 拉萨藏棋协会的秘书长阿旺边巴老师、拉萨棋手 Getchain();/随机选出最新下子方向 白姆顿珠、中央民族大学藏族学生闹塔与软件对 } 弈了100局，其中软件获胜25局。 5.2战斗引擎内核 邀请的测试选手均为“久”棋高手，尤其是阿 战斗阶段引擎由提取活动子、活动棋子所有 坝藏棋协会的尼玛扎华先生及甲花先生的弈棋水 方案计分、排序选出最高分的方案、实施方案4 平极高，本文的博弈软件提取的棋型还非常有 部分组成。战斗阶段伪代码如下： 限，采集的棋谱也较少，没有运用机器学习方法， Voidplaygame(){ 因此棋力还不是很高。 activechess();/获取所有活动棋子 此外，2016年，使用该软件在四川省阿坝藏 scoring();/计算活动棋子所有方案 族羌族自治州第七届“体彩杯”藏棋比赛中开展了 getmaxscore(O;/排序取出最高分 人机对弈项目，进行了20局的人机对弈，软件运 carryout((O;/实施最高分策略 行稳定，表现良好。 } 7结束语 private void activechess(board b){ for(inti=0:i<196:1++) “久”棋是藏族棋类中保存及传承较好的棋类 ∥是否能移动 游戏之一，2015年，“久”棋被列为四川省非物质 if(moveable(b,pi,pj,pcolor)) 文化遗产名录。象棋、围棋的计算机博弈取得了 record(pi,pj);能移动就记录 机器战胜人类的优异成绩，但是“久”棋的机器博 ∥是否能跳吃 弈研究尚处于起步阶段。本文提取了“久”棋的常 else if(eatable(b,pi,pj.pcolor)) 用棋型，提出了基于棋型的攻防策略，将基于 record(pi,pj),∥能吃子就记录 BM的模式匹配算法应用于布局的前40步。开 } 发了博弈软件，由于提取的棋型有限，采集的对 } 弈数据较少，该软件的棋力无法与“久”棋高手对 private void scoring(board b){ 弈，但是运行稳定，功能齐全。AlphaGo Zero不需 if(eatable(O)/判断4个方向是否能跳吃 要人类知识，只训练一个神经网络，采用增强学 if(eatable()){ 习与蒙特卡洛树搜索相结合，完胜AlphaGo。借 scoring();∥跳吃后坐标进行递归 鉴AlphaGo Zero的思路，集合硬件设施条件，开 Eva=move+kill+triple+square; 展“久”棋的博弈研究工作，将有可能为未来“久” } 棋博弈研究提供重要思路。 if(moveable())∥判断4个方向上是否能走子 参考文献： Eva=move+kill+-triple+square;/徒子计分 [1]刘强.藏族传统棋艺现状及推广价值).当代体育科技， private void getmaxscore() 2012,2(27):83-84 for(inti=0;i<counts,i++){ LIU Qiang.The status and promotion value of traditional comparet();/W比较各个方案的积分，取出最大 Tibetan chess[J].Contemporary sports technology,2012, 2(27):83-84 的积分 [2]张月娟，苟小江.西藏高校引入藏族传统体育项目注意 } 的问题切.当代体育科技，2014,423)：130-132. ZHANG Yuejuan,GOU Xiaojiang.The attention of tibetan private void carryout(board b){ traditional sports introduced in Tibet college[J].Contem- while(解决方案未遍历完) porary sports technology,2014,4(23):130-132. b.set(pi,pj),把方案实施到棋盘上 [3]德康·索朗曲杰译，约翰·帕日柏林著.围棋在世界屋脊 ).西藏研究，1994,3：153-157
Publicbooleanattack(board b){ twochess(i,j); //检测二子棋型 } //连子策略： public voidChain(board b) { Getchain(); //随机选出最新下子方向 } 5.2 战斗引擎内核 战斗阶段引擎由提取活动子、活动棋子所有 方案计分、排序选出最高分的方案、实施方案 4 部分组成。战斗阶段伪代码如下： Voidplaygame(){ activechess();//获取所有活动棋子 scoring();//计算活动棋子所有方案 getmaxscore();//排序取出最高分 carryout();//实施最高分策略 } private void activechess(board b) { for(inti=0;i<196;i++){ //是否能移动 if(moveable(b,pi,pj,pcolor)) record(pi, pj); //能移动就记录 //是否能跳吃 else if(eatable(b,pi,pj,pcolor)) record(pi, pj); //能吃子就记录 } } private void scoring(board b) { if(eatable()) //判断 4 个方向是否能跳吃 if(eatable()){ scoring(); //跳吃后坐标进行递归 Eva=move+kill+triple+square; } if(moveable()) //判断 4 个方向上是否能走子 Eva=move+kill+triple+square;//走子计分 } private void getmaxscore() { for(inti=0;i<counts;i++){ compare(); //比较各个方案的积分，取出最大 的积分 } } private void carryout(board b) { while(解决方案未遍历完) b.set(pi, pj); //把方案实施到棋盘上 } 6 测试及分析 本文邀请四川省阿坝藏羌自治州阿坝县藏棋 协会的原会长尼玛扎华先生、副会长甲花先生、 拉萨藏棋协会的秘书长阿旺边巴老师、拉萨棋手 白姆顿珠、中央民族大学藏族学生闹塔与软件对 弈了 100 局，其中软件获胜 25 局。 邀请的测试选手均为“久”棋高手，尤其是阿 坝藏棋协会的尼玛扎华先生及甲花先生的弈棋水 平极高，本文的博弈软件提取的棋型还非常有 限，采集的棋谱也较少，没有运用机器学习方法， 因此棋力还不是很高。 此外，2016 年，使用该软件在四川省阿坝藏 族羌族自治州第七届“体彩杯”藏棋比赛中开展了 人机对弈项目，进行了 20 局的人机对弈，软件运 行稳定，表现良好。 7 结束语 “久”棋是藏族棋类中保存及传承较好的棋类 游戏之一，2015 年，“久”棋被列为四川省非物质 文化遗产名录。象棋、围棋的计算机博弈取得了 机器战胜人类的优异成绩，但是“久”棋的机器博 弈研究尚处于起步阶段。本文提取了“久”棋的常 用棋型，提出了基于棋型的攻防策略，将基于 BM 的模式匹配算法应用于布局的前 40 步。开 发了博弈软件，由于提取的棋型有限，采集的对 弈数据较少，该软件的棋力无法与“久”棋高手对 弈，但是运行稳定，功能齐全。AlphaGo Zero 不需 要人类知识，只训练一个神经网络，采用增强学 习与蒙特卡洛树搜索相结合，完胜 AlphaGo。借 鉴 AlphaGo Zero 的思路，集合硬件设施条件，开 展“久”棋的博弈研究工作，将有可能为未来“久” 棋博弈研究提供重要思路。 参考文献： 刘强. 藏族传统棋艺现状及推广价值[J]. 当代体育科技, 2012, 2(27): 83–84. LIU Qiang. The status and promotion value of traditional Tibetan chess[J]. Contemporary sports technology, 2012, 2(27): 83–84. [1] 张月娟, 苟小江. 西藏高校引入藏族传统体育项目注意 的问题[J]. 当代体育科技, 2014, 4(23): 130–132. ZHANG Yuejuan, GOU Xiaojiang. The attention of tibetan traditional sports introduced in Tibet college[J]. Contemporary sports technology, 2014, 4(23): 130–132. [2] 德康·索朗曲杰译, 约翰·帕日柏林著. 围棋在世界屋脊 [J]. 西藏研究, 1994, 3: 153–157. [3] ·582· 智 能 系 统 学 报 第 13 卷
第4期 李霞丽，等：基于棋型的藏族“久”棋计算机博弈研究 ·583 [4]更堆.浅淡西藏“密芒”围棋的发现和相关传统藏棋种类 计算机信息，2012,10：461-462. [).西藏大学学报：汉文版，2003,18344-48. PEI Shenglei.Study of key issues in the palace two-door GENG Dui.On the discovery of Tibetan Chess(Mimang) chess game system[J].Microcomputer information,2012, and related traditional Tibetan chesses[J].Journal of Tibet 10:461-462. university:chinese edition,2003,18(3):44-48. [16]仁增多杰，安见才让.“褡裢”藏棋的设计与实现.信 [5]徐心和，邓志立，王骄，等.机器博弈研究面临的各种挑 息与电脑（理论版），2014,08：106-107 战.智能系统学报，2008,3(4)288-293. [17]范忠雄.对弈嫡率在藏棋“杰布杰曾”上的应用.西藏 XU Xinhe.DENG Zhili.WANG Jiao,et al.Various chal- 大学学报：自然科学版，2014,01：67-70. lenging issues faced to computer game research[J].CAAI FAN Zhongxiong.Entropy rate of chess game-Tibetan transactions on intelligent systems,2008,3(4):288-293. Jiebujiezeng[J].Journal of Tibet university:natural sci- [6]MNIH V.KAVUKCUOGLU K.SILVER D,et al.Human- ence,2014,01:67-70. level control through deep reinforcement learning[J]. [18]王昕杨.藏式围棋博弈软件及其教育应用技术研究D]. Nature,.2016,518:529-533 北京：中央民族大学硕士生毕业论文，2016 [7]MNIH V,KAVUKCUOGLU K,SILVER D,et al.Master- [19]洪晓蕾.模糊有限自动机及其最小化问题D1.成都：四 ing the game of Go with deep neural networks and tree 川师范大学，2007：1-15. search[J].Nature,2016,529:484-489. HONG Xiaolei.Fuzzy finite automata and their minimiz- [8]TIAN Yuandong,ZHU Yan.Better computer goplayer ations[D].Chengdu:Sichuan Normal University,2007: with neural network and long-term prediction[EB/OL].ht- 1-15. tps://arxiv.org/abs/1511.0641. [20]张红梅，范明钰.棋型匹配BM算法改进.计算机应 [9]SILVER D.SCHRITTWIESER Julian.SIMONYAN K,et 用研究，2009,09：3249-3252 al.Mastering the game of Go without human knowledge [J.Nature,2017,550:354-358 ZHANG Hongmei,FAN Mingyu.Improved algorithm for [10]LI Xiali,DENG Songting.Review of research on com- BM string matching[J].Application research of com- puter games for Tibetan chess[C]//IEEE 14th Intl Conf on puters..2009,09:3249-3252 Dependable,Autonomic and Secure Computing.Auck- 作者简介： land.New Zealand.2016:97-99. 李霞丽，女，1979年生，副教授。 [11]李达伟，关欣.藏族传统体育项目探究).沈阳体育学 主要研究方向为计算机博弈。 院学报，2011,06：130-132,142. LI Dawei,GUAN Xin.Exploration on Tibetan traditional sports[J].Journal of Shenyang sport university,2011,06: 130-132.142. [12]角巴东主.对藏族民间棋艺抢教保护的思考U.西藏艺 术研究，2007,02：78-82 吴立成，男.1972年生，教授，主 JOPA Dondrub.Considerations on the rescuing and pro- 要研究方向为智能系统及机器人、计 tecting Tibetan folk chess art[J].Tibetan art studies,2007. 算机博弈。 02:78-82. [13]陈斌.文化哲学视域中的围棋与藏围棋几.云南师范大 学学报：哲学社会科学版，2006,38(2)：1-5 CHEN Bin.A comparison of the i-go cultures between the han and the Tibetan from the perspective of cultural 李永集，男，1993年生，硕士土研究 生，主要研究方向为计算机博弈。 philosophy[J].Journal of Yunnan normal university: philosophy and social sciences edition,2006,38(2):1-5. [14]尖扎夏贝.藏族围棋软件的设计与实现D].西宁：青海 民族大学毕业论文，2011。 [15]裴生雷.王宫双门棋博弈系统中的关键问题研究】.微
更堆. 浅淡西藏“密芒”围棋的发现和相关传统藏棋种类 [J]. 西藏大学学报: 汉文版, 2003, 18(3): 44–48. GENG Dui. On the discovery of Tibetan Chess (Mimang) and related traditional Tibetan chesses[J]. Journal of Tibet university: chinese edition, 2003, 18(3): 44–48. [4] 徐心和, 邓志立, 王骄, 等. 机器博弈研究面临的各种挑 战[J]. 智能系统学报, 2008, 3(4): 288–293. XU Xinhe, DENG Zhili, WANG Jiao, et al. Various challenging issues faced to computer game research[J]. CAAI transactions on intelligent systems, 2008, 3(4): 288–293. [5] MNIH V, KAVUKCUOGLU K, SILVER D, et al. Humanlevel control through deep reinforcement learning[J]. Nature, 2016, 518: 529–533. [6] MNIH V, KAVUKCUOGLU K, SILVER D, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529: 484–489. [7] TIAN Yuandong, ZHU Yan. Better computer goplayer with neural network and long-term prediction[EB/OL]. https://arxiv. org/abs/1511.0641. [8] SILVER D, SCHRITTWIESER Julian, SIMONYAN K, et al. Mastering the game of Go without human knowledge [J]. Nature, 2017, 550: 354–358. [9] LI Xiali, DENG Songting. Review of research on computer games for Tibetan chess[C]//IEEE 14th Intl Conf on Dependable, Autonomic and Secure Computing. Auckland, New Zealand, 2016: 97–99. [10] 李达伟, 关欣. 藏族传统体育项目探究[J]. 沈阳体育学 院学报, 2011, 06: 130–132, 142. LI Dawei, GUAN Xin. Exploration on Tibetan traditional sports[J]. Journal of Shenyang sport university, 2011, 06: 130–132, 142. [11] 角巴东主. 对藏族民间棋艺抢救保护的思考[J]. 西藏艺 术研究, 2007, 02: 78–82. JOPA Dondrub. Considerations on the rescuing and protecting Tibetan folk chess art[J]. Tibetan art studies, 2007, 02: 78–82. [12] 陈斌. 文化哲学视域中的围棋与藏围棋[J]. 云南师范大 学学报: 哲学社会科学版, 2006, 38(2): 1–5. CHEN Bin. A comparison of the i-go cultures between the han and the Tibetan from the perspective of cultural philosophy[J]. Journal of Yunnan normal university: philosophy and social sciences edition, 2006, 38(2): 1–5. [13] 尖扎夏贝. 藏族围棋软件的设计与实现[D]. 西宁: 青海 民族大学毕业论文, 2011. [14] [15] 裴生雷. 王宫双门棋博弈系统中的关键问题研究[J]. 微 计算机信息, 2012, 10: 461–462. PEI Shenglei. Study of key issues in the palace two-door chess game system[J]. Microcomputer information, 2012, 10: 461–462. 仁增多杰, 安见才让. “褡裢”藏棋的设计与实现[J]. 信 息与电脑 (理论版), 2014, 08: 106–107. [16] 范忠雄. 对弈熵率在藏棋“杰布杰曾”上的应用[J]. 西藏 大学学报: 自然科学版, 2014, 01: 67–70. FAN Zhongxiong. Entropy rate of chess game-Tibetan Jiebujiezeng[J]. Journal of Tibet university: natural science, 2014, 01: 67–70. [17] 王昕杨. 藏式围棋博弈软件及其教育应用技术研究[D]. 北京: 中央民族大学硕士生毕业论文, 2016. [18] 洪晓蕾. 模糊有限自动机及其最小化问题[D]. 成都: 四 川师范大学, 2007: 1–15. HONG Xiaolei. Fuzzy finite automata and their minimizations[D]. Chengdu: Sichuan Normal University, 2007: 1–15. [19] 张红梅, 范明钰. 棋型匹配 BM 算法改进[J]. 计算机应 用研究, 2009, 09: 3249–3252. ZHANG Hongmei, FAN Mingyu. Improved algorithm for BM string matching[J]. Application research of computers, 2009, 09: 3249–3252. [20] 作者简介： 李霞丽，女，1979 年生，副教授， 主要研究方向为计算机博弈。 吴立成，男，1972 年生，教授，主 要研究方向为智能系统及机器人、计 算机博弈。 李永集，男，1993 年生，硕士研究 生，主要研究方向为计算机博弈。 第 4 期 李霞丽，等：基于棋型的藏族“久”棋计算机博弈研究 ·583·