中图分类号：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）我方棋子失去全歼能力的情况 (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）