爱恩斯坦棋静态攻防策略的研究

周文敏 李淑琴

摘要：近些年来，爱恩斯坦棋作为一个在中国刚刚兴起不久的棋类游戏，其计算机博弈算法的研究还相对较少。该文尝试使用静态算法来让程序做出一个相对有利于我方的走棋路线，也着力实现一个基于枚举和静态分析策略的静态算法，并且提供一个参考的局面评估算法。经过大量模拟实验证明，该算法具有一定的有效性和实用性。

关键词：静态算法；爱恩斯坦棋；枚举；人工智能

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2014）05-1027-05

The Research of Static Algorithms in WTN Chess

ZHOU Wen-min， LI Shu-qin

（ Computer School of Beijing Information Science and Technology University， Beijing 100101， China）

Abstract： In recent years，WTN chess is just emerging as a computer game of National Computer Games Competition in China which lacks of algorithm research. This paper tries to research how to use static algorithm to make a relatively right choice to move pieces.This paper also achieves a static algorithm based on enumeration and static analysis strategies， and provides an algorithm of situation assessment.It is demonstrated that the algorithm is effective and useful.

Key words： static algorithm；WTN chess；enumeration；artificial intelligence

計算机博弈是人工智能领域一个极其重要且最具挑战性的研究方向之一[1]， 计算机博弈算法具有形式多样、算法种类纷繁、算法应用面广泛、算法涉及领域全面等诸多特点。计算机博弈算法的研究为人工智能领域扩充了很多新的实用的算法，丰富了计算机科学领域的理论成果。在过去的几十年里，世界各地的学者致力于研究各种棋牌类游戏的博弈算法，并取得了不少举世瞩目的研究成果，譬如说1997年IBM公司的“深蓝”战胜国际著名象棋大师卡斯帕罗夫的消息轰动世界，其他很多棋类的算法都已达到了世界冠军级的水准。现如今，很多大型的软件开发公司都将中国象棋等棋类的算法研究作为面试成绩的参考之一，比如微软中国公司曾经在面试中出过中国象棋的将帅问题，要求只用一个变量输出将帅的所有合法位置[2]。其它许多大型公司也出过类似这样的计算机博弈中的具有挑战性的问题。可见人工智能领域的研究越来越广泛，越来越多的编程爱好者开始着力于计算机棋类博弈算法的研究。该文就新产生的棋种之一爱恩斯坦棋的静态的攻击和防守算法做一个相对系统的研究，提供一个相对可行的策略。

1 爱恩斯坦棋简介

爱恩斯坦棋由Ingo Alth?fer[3]发明并且于2004年问世，是一个新产生的棋类游戏。爱恩斯坦棋目前是国际计算机奥林匹克大赛竞赛项目，并于2012 年首次作为中国计算机博弈大赛[4]的比赛项目。爱恩斯坦棋规则为：

1）棋盘为5×5的方格形棋盘，方格为棋位，左上角为红方出发区；右下角为蓝方出发区，如（图1）所示；

2）红蓝方各有6枚方块形棋子，分别标有数字1—6。开局时双方棋子在出发区的棋位可以随意摆放；

3）双方轮流掷骰子，然后走动与骰子显示数字相对应的棋子。如果相对应的棋子已从棋盘上移出，便可走动大于或小于此数字的并与此数字最接近的棋子；

4）红方棋子走动方向为向右、向下、向右下，每次走动一格；蓝方棋子走动方向为向左、向上、向左上，每次走动一格；

5）如果在棋子走动的目标棋位上有棋子，则要将该棋子从棋盘上移出（吃掉）。有时吃掉本方棋子也是一种策略，因为可以增加其它棋子走动的机会与灵活性；

6）率先到达对方出发区角点或将对方棋子全部吃掉的一方获胜；

7）对弈结果只有胜负，没有和棋。

8）每盘每方用时3分钟，超时判负；每轮双方对阵最多7盘，轮流先手（甲方一四五盘先手，乙方二三六七盘先手），两盘中间不休息，先胜4盘为胜方。

图1 爱恩斯坦棋棋盘

由于爱恩斯坦棋走每一步棋之前都需要掷骰子以确定走动的棋子的编号，随机性对棋局的影响很大。该文力图构造一个算法以减少由于掷骰子的数不同从而给棋局带来的不利影响，增加其有利的影响，使棋局向着尽可能使我方获胜的方向发展。

2 爱恩斯坦棋之静态攻击策略

本文的算法主要采用静态算法。此算法基于枚举和贪心策略。棋局中将假设我方是蓝方，敌方为红方。进攻的总体策略是根据走棋的棋子的周围棋子的布局情况确定是否向前攻击以及攻击的方向。

定义1：周围棋子数

指我方（蓝方）某个棋子左边、左上方和正上方的棋子数目之和，取值范围为0-3。例如：某爱恩斯坦棋棋盘布局如（图2）所示，假设选定的棋子为蓝5，那么它周围的棋子数目为2。即左方的蓝6和正上方的蓝4。

图2 爱恩斯坦棋某个棋盘布局

定义2：主对角线：主对角线是指爱恩斯坦棋棋盘（5*5）的矩阵中从左上角到右下角的连线。

定义3：副对角线：副对角线是指爱恩斯坦棋棋盘（5*5）的矩阵中从左下角到右上角的连线。

定义4：敌人总数目：敌人总数目是指敌方（红方）的所有棋子的数量之和，取值范围在0-6之间。

定义5：出发点：对于我方来说，右下角的格子为我方的出发点；对于敌方来说，左上角的格子为敌方的出发点。

定义6：终点：对于我方来说，左上角的格子为我方的终点；对于敌方来说，右下角的格子为敌方的终点。换句话说，我方出发点为敌方终点，敌方出发点为我方终点。

定义7：周围敌人数：周围的所有棋子中敌方棋子的数量。

定义8：周围我方棋子数：周围的所有棋子中我方棋子的数量。

定义9：失去全歼能力：即敌方至少有一个棋子不能被我方任意一棋子吃掉，此时我方不能以全歼的方式赢取敵方。

1）离终点只有一步的情况

此种情况最简单，当我方被选中的棋子到达第一行第二列、第二行第一列或者第二行第二列的时候，只需要再走一步就能到达终点赢取胜利。此时，不管周围有几个敌方棋子或者是我方其它棋子，都不去吃它们，而朝着终点走一步赢取胜利。

如（图3）所示，假设当前我方被选中的棋子是蓝4，此时蓝4可以不去管周围的敌人，直接朝着终点走一步获得胜利。具体的三种情况见（图4）。

图3 走一步就能获胜的情况

图4 走一步就能获胜的三种情况（空白处可以有任意棋子或者无棋子）

2）我方棋子失去全歼能力的情况

当敌方某一个或几个棋子不能够被我方任意棋子吃掉的情况下，我方就不能用全歼的方式赢取对方。换句话说，我方此时不应该吃对方任意一个棋子，因为吃对方棋子既不可能以全部歼灭的方式赢取对方，又给对方的棋子增加了灵活性，增加了他们赢得比赛的机会。

当这种情况出现的时候，我方被选中棋子要朝着终点的最短距离前进，即能斜着走就斜着走，如果到达某一边界了就只能横着向左走或者竖着向上走。如（图5）所示的一种失去全歼能力的情况。

图5 失去全歼能力的情况

在（图5）中所示的一种失去全歼能力的情况，红5已经不能被我方的任意一个棋子吃掉，此时假设我方选中的棋子是蓝5，蓝5到达终点的最少步数是3，那么此时蓝5走竖直上方和斜上方都可以。但是如果走斜上方把红4吃掉了，红方的灵活性就提高了，所以此时蓝5最好的方案就是竖直向上走，避开红4，在不影响到达终点的步数的同时还可以防止对方的灵活性增加。

3）避开我方棋子的情况

当我方棋子总数目小于等于3的时候，我方如果继续把自己的棋子吃掉的话，虽然可以提高灵活性，但是会造成我方被敌方全歼的危险。如（图6）所示的15种情况，我方被选中的棋子需要避开我方的其它棋子，前提是我方的总棋子数目小于等于3。

图6 避开我方棋子的情况

情况1：我方被选中棋子的斜上方有我方其它棋子，这个时候需要避开我方棋子。（大前提是我方的总棋子数目小于等于3，下同。）这种情况下，应该横着走左方或者竖着走上方，具体这两种走法走哪种要根据下文中的局面评估算法来评定。

情况2：直接走斜线，因为这样到达终点的速度最快，又不会使我方的棋子数目减少，防止被对方全歼的危险。

情况3： 与情况2类似。

情况4： 当斜方向有我方棋子而竖直方向或者横方向（对应情况5）有敌方棋子的时候，我方不去斜着走吃掉自己的棋子，理由同上。此时如果我方没有失去全歼能力的情况下可以把对方的棋子吃掉（对应情况4则向上竖着走），如果我方已经失去了全歼能力，则需要横着向左走向空白位置。

情况5： 与情况4类似。

情况6： 如果敌人只有这么一个，可以将敌人吃掉以全歼的方式获得胜利，否则的话走斜对角线方向走向空白位置。

情况7： 与情况6类似。

情况8： 如果斜对角走把敌方棋子吃掉不会大大增加敌方棋子灵活性则斜着走，反之则走向空白区域。是否增加敌方灵活性需要根据局面评估算法判断。

情况9： 与情况8类似。

情况10： 吃掉任意一个敌人均可，此时是横着向左吃敌人还是竖着向上吃敌人要根据下文提到的局面评估算法来判断。

情况11： 斜着走把敌人吃掉。

情况12： 与情况11类似。

情况13： 斜着走把敌人吃掉。

情况14： 横着向左走把敌人吃掉。

情况15： 竖着向上走把敌人吃掉。

4） 主动吃掉对方棋子的情况

当敌方的棋子数目只有一个的时候，将其吃掉就可以以全歼的方式获得本局胜利。

在敌方当前总棋子数目多于一个的前提下，如果此时我方被选中的棋子周围的一个敌人离我方起点步数在两步以内，则应该把它吃掉。如果有不止一个敌人到我方的起点不超过两步，则视它们对我方的威胁程度选择吃哪个棋子。优先吃掉离我方终点最近的并且可以吃到的棋子，当有两个或三个棋子都可以被我方被选中的棋子吃掉的时候，则根据具体情况选择吃掉的棋子。具体情况如（图7）所示。

图7 主动吃对方棋子的情况

情况1：当上面和左边的两个敌人都可以被吃掉的时候，选择吃掉对敌方灵活性影响不大的棋子。

情况2：当斜方向和正上方都有敌方棋子的时候，优先选择吃斜方向上的棋子，这样可以使我方的棋子更接近敌方的起点。

情况3：处理方法与情况2类似。

情况4：首先考虑吃掉斜方向的棋子是否可以大大增强敌方的灵活性，如果吃掉斜方向的棋子后大大增强了敌方的灵活性，那么吃掉斜方向的棋子对我方而言就得不偿失了。所以，吃掉斜方向的棋子可以大大增强敌方灵活性的时候，优先选择吃横方向或者竖直方向的棋子。反之，吃掉斜方向的棋子。

3 爱恩斯坦棋之静态防守策略

当我方被选中的棋子走某一步之后会碰到被敌方三个棋子包围的情况，那么这一步就千万不要走，否则的话等于是羊入虎口。

当我方被选中的棋子走某一步之后会碰到被敌方两个棋子包围的情况，是否可以走这步，需要具体情况具体分析，情况如（图8）所示。

图8 走一步以后碰到两个敌人包围的情况（红点表示走了某一步后到达的位置）

当红A和红B两个棋子（A和B代表该棋子上的数字）数字的绝对值之差不超过3，那么此时如果将我方棋子移动到红点位置，很有可能被红A或者红B吃掉。所以这种情况下出于防守思维的考虑，不应将我方被选中的棋子移动到红点位置。

4 爱恩斯坦棋之初始布局设计

由于爱恩斯坦棋本身是一种依靠骰子来决定棋子移动的棋种，因此能够让棋子本身更为灵活移动就极为重要了。本次采取的策略是以牺牲一小部分棋子为代价来换取一定的灵活性，但不会为了绝对的灵活性而导致自身处于危险的境地。

对我方的棋子分别登记编号，则对应的边缘的三个棋子将作为被吃掉的棋子来换取灵活性。当初始的骰子置为内部的三个棋子时，采取吃掉周围的棋子来换取灵活性。吃掉的最大的棋子个数应该为三个，此时具有相对较大的灵活性，而且比较稳固，避免了被全盘吃掉的危险。而且三个棋子的状态在攻击和防守均具有一定的优势。

经过探究发现初始局面应该保证吃掉后的棋盘只剩下1， 3， 5时，（或者只剩下2，4，6，总之最好是间断序列。）此时可以获得更多的灵活性，同样的一个骰子的点数可以选择移动两个棋子，而且此时一个棋子移动的概率也会大大增加，此时能够获得非常理想的效果。

本策略我方采取的初始棋局布置如（图9）所示。

图9 初始棋盘布置

将2，4，6布置在外面从而方便1，3，5棋子吃掉它，获取一定的灵活性，如果运气比较差一直投掷的是比较恒定的外围的棋子，那么其移动将会以接近终点的方式进行，此时可以对此灵活策略进行调整，改为进攻模式，即其他棋子防止对先锋棋子自残，维持先锋棋子的优势。

在己方的危险区域（靠近终点一格和二格的位置），采取优先消灭对方危险棋子的策略，即此时应尽可能吃掉对方的棋子来消除危险，而在危险区域以外，将以优先走到终点为主。同时要注意的是如果对方只剩下一个棋子的时候，应该采用同样的消灭对方的策略。

5 爱恩斯坦棋之局面评估算法

爱恩斯坦棋的静态评估策略主要集中在骰子选数函数上，因为骰子数是固定的，每一轮一旦骰子掷出，如果棋盘上有骰子数对应的棋子的时候，那么就别无选择地走那个棋子。所以只有在骰子数对应的棋子被吃掉，此时才可以就近选择两边的棋子。根据规则，如果骰子数对应的棋子被吃掉了，那么可以选择其数字两端与其最接近的数的棋子，比如2和3被吃掉了，那么此时如果1和4都存在并且骰子数为2或者3的时候，走1号棋子和走4号棋子都是符合规则的。有一种情况，比如1，2，3号棋子都被吃掉了，4，5和6在棋盘上，如果骰子数是1，2或者是3，那么此时都只能走4号棋子，不能认为数轴是循环的，即不能认为6在1的左边。那么当有两个棋子都可以选的时候，选择谁更能让自己赢的概率大呢？我们可以通过做大量的模拟实验总结规律，然后得出一套评分法则，即谁更有优势就让谁的分数多一些，通过分数对比，选择更合适的棋子走棋。下面是本文的评分标准，仅供参考。

走一步就可以到达终点加10000分。横竖斜三个方向之一有敌人且敌人距离我方起点只有一步，敌人再走一步就能获胜加5000分。走两步能到达终点加1000分。敌人距离我方起点两步以内加500分。其他情况根据坐标位置计分。

选择棋子的具体实现流程为：首先，当骰子数对应的棋子已经被吃掉的时候，上下分别搜索离其最近的棋子；然后，通过算法选出两个可以走棋的棋子；再通过评估函数计算出这两个棋子相应的分值，分值高的棋子为本轮走棋棋子。

6 总结

经过大量模拟实验，该策略在和随机策略的比赛试验中，具有明显的优势，并且该策略辅助应用于“东大杯第二届全国大学生计算机博弈大赛暨第六届全国计算机博弈锦标赛”爱恩斯坦棋项目的比赛中，在这项比赛中本组成员获得了一等奖的好成绩，侧面证实了这种策略具有一定的优越性和实用性。今后我们会继续完善和加强对静态攻防策略的研究。

参考文献：

[1] 徐心和， 王骄. 中国象棋计算机博弈关键技术分析[J]. 小型微型计算机系统， 2006， 27（6）： 961-969.

[2] 《编程之美》小组. 《编程之美》： 中国象棋将帅问题[J]，北京：电子工业出版社2008.3.

[3] Alth?fer， I. On the origins of EinStein würfelt nicht！[EB/OL]. Http：//www.althofer.de/origins-of-ewn.html.

[4] 王骄， 徐心和. 计算机博弈： 人工智能的前沿领域： 全国大学生计算机博弈大赛[J]. 计算机教育， 2012（7）： 14-18.