一种非遗藏族久棋项目计算机博弈智能体的评估方法

张小川，刘 溜，陈 龙，涂 飞

(重庆理工大学 两江人工智能学院，重庆 401135)

文化是一个国家、一个民族的血脉和精神家园。中华优秀传统文化是中华民族生存发展的精神支撑，也是现阶段中国特色社会主义建设所植根的文化沃土。习近平总书记在河北省承德市考察时曾经强调：“保护好、传承好、利用好中华优秀传统文化，挖掘其丰富内涵，以利于更好坚定文化自信、凝聚民族精神”。中国棋文化正是中国几千年积淀并传承下来的优秀传统文化内容之一，其中包含了各民族多种棋类项目，它们共同构成中国棋文化。

藏棋，顾名思义就是主要流行于藏区的棋类项目，是藏族文化的重要组成部分，它极大地丰富了广大人民群众的精神文化生活，其历史源远流长，折射出藏民族独特气质、智慧和精神价值追求[1]。藏棋种类繁多，按照布局、着法等行棋规则和棋具及其形状的不同，大致可以分为“久棋”“密芒”两大类型。本文讲述的是广泛流传于我国西北的安多地区——青海省海南州、黄南州、果洛州、海东市和四川省阿坝州的“久棋”。

藏族久棋一度濒临失传，经过多方努力，正在稳步恢复发展中。2018年，在中国人工智能学会机器博弈专委会副主任委员、中央民族大学吴立成教授和副秘书长李霞丽教授的大力支持下，将久棋引荐进中国计算机博弈竞赛项目库，让人工智能与久棋博弈项目相结合，为其传承和发展带来深远影响。其实，全国高校，特别是民族类大学的师生们，此前已经开展了早期研究工作。比如，2011年青海民族大学开发了全国首款藏族棋类软件，首次详细介绍了棋盘、棋子和棋局的状态空间的表示方法，以及系统的解决方案[2-3]；2016年，中央民族大学引入极大-极小值方法，开发了藏式围棋博弈软件[4]；2018年，中央民族大学设计了具有优先级别的防守、攻击、连子等策略[5]；2019年首次进入中国大学生计算机博弈大赛暨第十三届中国计算机博弈锦标赛的正式比赛项目系列。从此，久棋的发展迈进了新篇章。

基于上述背景，首先分析了计算机博弈构成要素，提出博弈智能体结构，理清计算机博弈规则的离散化思路，以规则库、置换表等为案例，梳理了知识库构建思路，以此奠定博弈智能体的知识基础；然后，根据久棋特有的布局、行棋、飞子3个阶段，按照分段评估思路，根据久棋行棋过程以特殊棋型为标杆的逼近策略，对这些特殊棋型进行量化估值，从而形成久棋博弈的不同阶段盘面评估方法，构成了完整的久棋博弈局面评估体系；最后，再以此为基础，开发了久棋博弈软件，其棋力得到显著提升，取得全国大学生计算机博弈大赛优异成绩。希望此文能起到抛砖引玉之效，共同推动计算机博弈研究发展。

1 久棋计算机博弈分析

1.1 博弈要素与久棋规则

博弈本意源于游戏，而棋牌类项目是属于博弈活动的重要内容。棋牌类游戏是两人或多人针对特定规则的对抗性游戏活动，其中不乏各方斗智斗勇，既有智力对抗、也有益智娱乐，能实现切磋、消磨时光和增进了解之效，是大众喜闻乐见的游戏项目，这也是棋牌类活动经久不衰的根本所在。在棋牌游戏中，各方依据自己判断、理解、推理，会产生下棋、出牌行为，显然，此行为仅仅是博弈活动的外在表现，更为重要的思考、推理、算路等才是博弈活动的内在本质，此称之为着法。但是，所有这些过程、行为、着法都需要一种物理承载，以承载博弈活动的展开，这就是棋盘等物质载体。因此，一个完整的棋牌类博弈游戏，包含了5个关键性要素：至少有2个博弈方、博弈规则、博弈行为、博弈着法、博弈收益，如图1所示。

图1 博弈游戏的五大要素

图1中，如果某方变成计算机，就成为人-机博弈，如果双方都是计算机，就变成机-机对弈，它们都属于计算机博弈的具体研究对象，其研究本质就是对人类博弈活动中的方法、战术、谋略、推理、情感等行为，以计算机系统形式予以模拟、模仿、仿真实现。因此，计算机博弈活动不仅有IBM“深深的蓝”打败国际象棋冠军、谷歌“阿尔法狗”打败围棋冠军这样高光实例，而且还是承载研究人们高智力、强对抗行为的最佳科学载体，这也是有学者将计算机博弈称为是人工智能研究的标准平台或果蝇的重要原因。

藏族久棋是一种两人对弈棋类项目，也具有图1的5个要素。藏民的先辈们还因地制宜、因陋就简地下棋。比如在野外，以大地为盘，就地划一个棋盘网格，此时棋盘的大小、美观和对抗思考时间长短已不是最重要的，正因为如此，现在流行的久棋规则也是参差不齐，给久棋推广、传承带来困难。为便于研究工作的开展，人们选择了大小为14×14的网格、类似于围棋的棋盘，如图2所示。也严格规定了博弈各方对抗用时和一些特定约定、条款，从而形成久棋博弈规则，详细内容可见中国人工智能学会机器博弈专委会官方网站下载专区(http://computergames.caai.cn/)。下面以吃子规则为例予以说明。

1)跳吃：要求本方棋子与相邻对方棋子在同一条棋路上，且有一个空棋位，本方棋子跳过对方棋子落在空位上，就可以将对方棋子吃掉；跳吃含单跳和连跳，只要满足条件，就可以吃掉对方若干枚棋子，如图2所示。

2)成方吃：要求四子成方形布局，即将四枚棋子走至一个棋格的4个角，就可吃掉对方任意一枚棋子，此称为单棋门。若在走子时形成2个方形，就可以吃掉对方任意2枚棋子，称为双棋门。如图2所示。

3)阵型吃：阵型包括基本阵型和特殊阵型。图2所示为褡裢、拉萨2种常见久棋阵型。其实，在藏区民间，久棋存在许多特殊阵型，需要整理、挖掘和完善。在久棋博弈中，某方棋子形成特定阵型后，就能吃掉对方若干枚棋子。

图2 跳吃、成方吃和褡裢、拉萨阵型示例图

1.2 智能体与知识库

计算机博弈的外在表现通常是一个计算机软件，但是，作为一个模拟人类棋手的智能软件，更提倡以智能体形式进行开发设计。智能体是英文Intelligent Agent(简称IA)的意译，目前学术界对其还没统一定义，不同学者也有不同解释。比如，Russell等[6]在1995年从3个角度进行了描述：

1)行为角度：任何一种智能体可通过感知器感知环境，并通过效用器对环境做出有影响的反应。

2)知识角度：对每个感知到的序列，智能体能根据自己所内嵌的知识和所感知到的序列，按照使其能最大化的原则选择自己的行动。

3)经验角度：智能体能依靠自己的经验，不是依据设计者提供的环境知识来决定自己的行为，并能适时做出选择。

综上可见，智能体是一个与某个博弈项目紧密融合的计算机系统，但它与一般的计算机系统还是存在明显差异的：一般的计算机系统是一成不变地、按编写代码简单地运行；智能体要具有较强的自主性，即智能体行为不受外界的直接干预，能最大限度控制自己行为和自身状态。而且，智能体具有一定的灵活性，即有一定的反应力和自发性行为，能感知环境并及时做出有针对的智能型响应。本文所说的博弈智能体是针对计算机博弈活动的，选择以知识库支撑为基础、智能算法为核心、能自适应软件架构为载体的方式，予以构建。采用分层递进的控制思想，将博弈智能体分成交互、感知、知识和算法共4个层，并设计了相应的流程，如图3所示。

图3 久棋博弈智能体层次结构与流程图

从图3可见，规则是博弈智能体知识库的重要内容之一。一般来讲，棋牌规则需要进行预处理，先提取其中关键性指标、博弈逻辑与步骤等特征信息，再进行知识化实现，通常采用If…then…、语义网络等形式存储。本质上是对棋牌规则离散化、可计算性处理，当然也是一个降维处理过程，该过程当前仍然以人工操作为主。至于AlphaGo Zero声称通过短时间学习，能自己掌握围棋、日本将棋等规则并打败了之前AlphaGo Lee(即打败李世乭的版本)、AlphaGo Master(即创造线上与人类棋手对战的60∶0战绩版本)和日本将棋冠军等程序，当下并不具有普适性，因为Zero版本需要强大算力和电力支持，还需要标注后的、符合博弈项目规则的大量对局数据，这在普通博弈智能体的构造过程中，是不具备这些条件的或者难以做到[7]。因此，本文中选择了性价比更高、更具有应用普及意义的人工建立知识库方法。

久棋博弈规则是藏族精神、久棋要义的具体体现，也是藏文化精髓所在，它们在久棋博弈智能体中，就具体表现为程序代码的特殊限制和博弈流程的特定规约，而这些都可用知识形式存储于数据库中。为在全国大学生课外科技活动中推广，机器博弈专委会为此成立专家委员会并完成了久棋计算机博弈规则整理与定义。为节约篇幅，在此以跳吃规则为例予以简要说明。

第一，博弈载体的离散化。在久棋计算机博弈中，棋盘是博弈活动的舞台、棋子是博弈活动的舞者，首先需要离散化，这是久棋可计算的前提，而相应的数据结构和框架就是离散化的具体呈现。对久棋棋盘通常采用二维矩阵方式、用数组形式予以实现，在此注意的是要充分考虑智能体代码的自适应性。比如，棋盘长、宽坐标等参数值，就要考虑到不同地域、不同比赛的不同变化，拟采取参数可配置法予以实现，其伪代码如下。

public class Board

{

public int x_wide;//棋盘宽度

public int y_long;//棋盘长度

x_wide=inita.wide;//取初始化参数值

y_long=inita.long;

public Position[，] positions =new Position[x_wide，y_long];……

}

14×14棋盘共有196个网格节点，每个节点有3种状态，可使用点数组方法量化处置：如黑方棋子标记为1、白方棋子标记为-1、空白点标记为0。如果采用点数组的话，就可以建立网格节点与点数组中元素的1、-1对应关系，并以此表示棋子的数据结构，从而所有元素构成的点数组在某时间点t就成为久棋t时刻的久棋局面，记为状态St，随着时间t的改变，获得博弈状态随时间变化的状态序列{St|t=1，2，3,…}，可以描述成根节点在上的一棵博弈树，如图4所示。

图4 博弈状态的博弈树结构图

此外，还可以通过增加点数组的维数或赋予网格节点多于3种状态的表示方法，从而让点数组承载更多的棋局信息，比如黑方棋子是成方的棋子，标记为4…，从而满足博弈智能体更宽泛的需求。

第二，规则条款的离散化。久棋规则同其他博弈项目规则一样，也是对行棋过程中设置系列边界条件，外观呈现就是条条款款，体现的是久棋内在的逻辑。因此，可采用函数体或类结构等方式来构造。此时，需特别注意条款的量化表示方式，即数据结构，也要严格包含执行时序，即空间顺序和时间约束与限制。在此以久棋跳吃规则的2种情况为例予以说明：首先是同方向棋路中，异子相邻时，可以隔空跳吃；然后连续跳吃时，可多次吃子。据此规则，在设计规则库时，就要体现2个关键性触发因素：一是搜索当前棋子是否具备处于跳吃的位置；二是判断在某个方向上是否可以具备跳吃的条件。如图5所示就为此知识点的工作流程，最后，据此可设计为一个跳吃函数。

图5 久棋跳吃规则实现流程图

由于状态St与St-1状态密切相关，不具有完全的随机性，也不是完全意义的马尔科夫随机过程，但博弈论中相关的一些搜索算法，特别是著名的极大值-极小值算法，以及剪枝、启发等方法，就能快速发现图4博弈树合适的着法，这就是图2优化计算步骤的主要工作内容。

1.3 置换表数据结构

在实际对弈中，仅依靠单次搜索就想达到目标是不现实的。但是，如果每次都重复上次搜索，其效率又将极其低下，因此，如果能充分利用上次搜索，利用增量搜索思想，即仅仅搜索上次搜索中变化的博弈树树枝，无疑将极大提高搜索效率。这就是引入置换表的目的之一。

置换表是基于空间换时间的思想[8]，用表格将之前搜索过的信息保存下来，表中每个数据项对应于一个博弈树的节点及其估值等，在搜索时，把已被搜索节点的相关信息记录下来，如果与该表中待搜索节点特征相匹配的话，就直接提取置换表对应结果而勿需继续搜索，以此节约搜索时间。

置换表可以保留搜索记录，帮助改变节点搜索顺序，从而达到对博弈树的剪枝效果。比如，在搜索过程中，节点评估值如果是介于某一个区间，此区间可以假设为此节点的最小评估值与最大评估值所构成的区间，则立即启动搜索操作并将当前节点评估值存入置换表之中，以备后续查询。而对于评估值不在上述区间的，可以忽略，从而加快了搜索速度，能帮助尽快发现最优节点。

置换表是基于哈希表的一种数据结构，它存在一个重要问题：即在数据量特别大时，哈希表存在地址冲突问题。对这个问题，常用方法是基于Zobrist键值的哈希方法，针对久棋棋盘的196网格节点，使用Zobrist方法可构造32位哈希值，用Zobrist[X，N，N]数组保存32位随机数，X=0表示黑子棋盘，X=1表示白子棋盘。例如，当棋盘上(2，2)点有黑子、(3，3)点有白子时，棋盘的哈希值可由式(1)计算获得：

Hashcode=Zobrist[0][2][2]^Zobrist[0][3][3]

(1)

如果在(3，3)点黑子被吃掉，通过异或计算即可得新的哈希值，如式(2)：

Hashcode=Hashcode^Zobrist[1][2][2]

(2)

另外，增加一个32位的blackZobrist常量来区分先手、后手。若是黑子落子，计算完哈希值后异或上blackZobrist，如式(3)：

Hashcode=Hashcode^Zobrist

(3)

通过上述方式，就使得创建关键字的地址冲突概率极低。其他的如开局库、终局库、定式库，以及棋手的妙招与经典着法等人类经验，也是博弈智能体知识库的重要内容。通过知识库，博弈智能体就可以掌握人类棋手许多常识、下棋着法，实现对博弈智能体的首次赋能。限于篇幅，在此仅以开局中布局定式为例，予以说明设计思路。

布局是久棋对弈中第一个阶段，高质量的布局不仅有利于快速吃子、确立开局优势，还能帮助构建理想阵型、奠定胜利基础[9]。经过大量棋谱分析和实战测试，发现久棋最终胜利与一些特定棋型密切相关，如图6所示。

图6 久棋布局中的5种典型棋型

第1种棋型为山字棋型，此种棋型包含2个棋门，有2次成方机会；第2种棋型为回字棋型，此种棋型在中心填子便能成方，且在四周填子还可以形成4个山字棋型；第3种为十字棋型，此种棋型包含4个棋门，具有4次成方的机会；第4种棋型为方阵棋型，此种棋型已经成方，可以吃掉对方任意棋子，以此为基础还可以演化为褡裢、拉萨等更复杂棋形；第5种为三角阵型，此种棋型有1个棋门，在角落填子就可成方，适当填子后还可演变成山字阵型。将上述基本棋型存入开局库中，以此指导博弈智能体的布局，能最大限度避免走出愚型、昏招，提高智能体布局棋力。

2 基于棋型匹配的分段评估方法

藏族久棋博弈过程与一般棋类博弈过程的不同之处就体现在规则迥异的3个阶段：即布局阶段、行棋阶段、飞子阶段。3个阶段彼此独立、又相互联系、相互影响[10]。因此照搬其他棋类的盘面评估方法，在久棋博弈中就行不通。本文基于分段评估思想，结合棋型匹配方法，针对每个阶段规则和特性，为每个阶段构造不同评估策略，以提高整体评估的准确性[11]。

2.1 布局阶段的局面评估方法

久棋实战中，棋手往往会根据对手实力和风格，确定不同策略。面对整体实力较弱的对手，通常采用进攻策略，尽快建立优势，以快速取得胜利；面对实力较强的对手，通常采用防守策略，极力避免在布局阶段产生较大劣势，以待行棋阶段再与对方进行斡旋、寻找机会。进一步研究发现，久棋的防守和攻击策略与布局阶段的棋型存在较强的关联性：适合于进攻的有图6中十字、回字等阵型；偏重于防守的有图6中山字型、方型；而比较中性的为三角型。以此，就可以按照表1分值，赋予不同阵型的估值。

表1 不同策略下的棋型得分表

注意，表1中估计值来源于经验，对博弈智能体来讲属于先验性知识。其实还可以利用优化方法，比如遗传算法等进行离线寻优，获得更优估值。

2.2 行棋阶段的局面评估方法

行棋是久棋全局中承上启下的阶段，直接关乎棋局最终的输赢。其中的局面评估尤其重要，同时局面也最为浑浊从而使得局面评估最为艰难。在行棋阶段，可以通过棋型分类，为不同策略提供相应的先验棋型：将用于逐渐吃子后，建立优势的归为基础棋型；将能直接获得胜利的棋型归为胜利棋型，久棋中也称吉祥棋型。

经过研究发现，基础棋型中最常见的有“门”棋型，如图2左图右上角的单门和双门所示，其实本质就是图6的最具效率的仅有3颗棋子的三角形棋型，至于其他所有棋型都是基于门棋型的变化而来。因此，将门棋型定义为基础棋型。至于胜利棋型包含棋型就多了。而且在藏文化中，对一些特殊形状“棋”有独钟，常见的胜利棋型有图2中的褡裢及其演化的拉萨两大类棋型，它们至少需要13颗棋子、最多的需要24颗棋子，这对行棋时间与空间都有较强的要求，在实际对局中产生这样的胜利棋型自然难度就非常大。

分析发现，久棋在行棋阶段的局面评估可以从式(4)获得相应估值：

(4)

式中：kill是吃子评分；basicScore是基础得分；victoryScore是胜利得分；β是表2中棋型对应的分值。特别是对于各种胜利棋型，β估值可以给予智能体最大值。

表2 行棋阶段中基础棋型得分表

2.3 飞子阶段局面评估方法

飞子是久棋行棋的最后阶段，通常情况下，某方处于巨大劣势时，在行棋阶段就可以确定输赢。但是，久棋规则中，在飞子阶段，对少子方的移动棋子是不会受限制的，此时该方可以移动任何棋子到任意空白位置，如果此时能构成胜利棋型，便可以反败为胜，这是久棋独有魅力的地方，当然，也给博弈智能体的决策构造带来极大不确定性。

分析发现，在飞子阶段主要有2种棋型，如图7所示，一种是十字飞子型，由6颗棋子组成具有3个棋门的十字图形。此时，黑方的任意棋子可以落在图形中A、B、C点，并吃掉对方任意棋子；第二种是九子飞子型，它以9颗棋子组成了包含7个棋门的图形，此时少子方的任意棋子可以落到A、B、C、D、E点，并能连续成方吃掉对方棋子。

图7 飞子阶段的2种棋型

对飞子阶段2种棋型，可以赋予如表3所示的分值。

表3 飞子阶段的基础棋型得分表

当然，久棋还有其他一些吉祥阵型[12-13]，比如由14颗棋子构成的金鱼阵型，15颗棋子的幢阵型，16颗棋子的右旋海螺阵型、宝瓶阵型和宝伞阵型，17颗棋子的妙莲阵型，20颗棋子的吉祥结阵型，以及24颗棋子的法轮阵型等，由于这些阵型需要棋子多，对方一般不会给予己方如此的大空间和长时间去摆放这些棋型，自然在实际博弈中，出现概率少，但是从完备性角度讲，在博弈智能体知识库中还是有存在必要的。

3 结论

提出了久棋博弈智能体层次结构，描述了知识库构建方法，梳理了博弈智能体关键流程，针对藏族久棋特殊的分段行棋规则，依据分段评估思路，构造了不同阶段的局面评估方法。以上述方法构建了久棋博弈智能体，参加了2021年中国大学生计算机博弈大赛暨中国计算机博弈锦标赛久棋项目比赛，取得全国一等奖优异成绩，证明了本文思想、方法的可行性和实效性。但是，在久棋其他特殊阵型的挖掘与知识化方面，特别是机器学习方法应用上，还需要进一步开展研究工作。