国际象棋博弈系统的研究与实现

马钲鸿，宁慧，张汝波

1.哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001 2.大连民族大学 机电工程学院，辽宁 大连 116600

随着计算机、互联网相关技术的不断发展，素未谋面的人们同样可以通过网络进行社交或共同游戏。游戏这一人类不可或缺的概念，随着科学技术的发展不断的改变，不仅仅各种五花八门的电子游戏应运而生，那些早已存在了几百年，甚至上千年的古老游戏，也完成了从实体化向数字化的转变。

国际象棋又称西洋棋，是世界上最为流行的双人博弈的战术棋盘游戏之一。在计算机技术高速发展的今天，有许多人使用电脑进行国际象棋游戏。同时，随着人工智能以及编程技术的不断发展，计算机博弈算法也获得了极大的发展，现如今顶尖的棋手也很难胜过电脑[1]。但就棋类运动的意义上来讲，单纯的输赢并非其意义所在，心理、智力的对抗以及其带给人们的成长更加重要[2]。因而如何使用计算机技术促使人们对国际象棋保持乐趣的同时又能在一定程度上提高棋艺，应当成为计算机博弈的发展方向之一。

1 相关技术

为了研究和实现一个可以保持乐趣、同时提升玩家棋艺的国际象棋博弈系统，本文主要使用的基础性技术有FEN 格式串、博弈算法以及原生的JavaScript、html 和CSS。

1.1 FEN 格式串

FEN 格式串来源于FEN 记号法，即“福斯夫-爱德华兹记号法”，是一种将ASCII 码用于描述国际象棋局面的方法。一份标准的局面记号对于国际象棋程序这种需要对大量的局面数据进行交换与共享的工作，具有十分重要的作用。

本系统将棋盘表示为一个二维数组，再转变成一维数组，最终变换为FEN 格式串，其中分别使用“K、Q、B、R、N、P”来表示“国王、王后、主教、战车、骑士、士兵”，并按照大小写进行颜色的区分；对于换行处，使用“/”进行标记；对于空位则使用数字进行标记。使用FEN 格式串，使得在数据传输时只需要传递一个字符串而非整个二维数组，极大地节省了空间，也为在数据传输以及与其他国际象棋软件共享棋局时提供了便利。图1 是将国际象棋的初始局面表示为FEN 格式串之后的结果。

图1 FEN 格式串举例

1.2 博弈算法

博弈算法，即通过计算机模拟人类下棋时决策所使用的算法，它通过对棋局进行评估、比较，选择出对己方有利的行棋方式。博弈算法有许多种类，本系统中采用了博弈树作为算法的基础，以对计算机的走法决策进行支持。

博弈树是在组合博弈理论中用来表达一个博弈行为中各种后续可能性的树。在一棵完整的博弈树中，其起始点表示博弈过程中的某一个情形，下一层的子节点表示其父节点博弈下一步的可能性，依此类推，直至博弈结束。博弈树在各种棋类的游戏程序中被广泛地应用，本系统对博弈树的应用方式如下：选择一种走法，计算依此法行棋可获得的局面分数，然后撤销此步，选择下一种走法，直到取遍所有的走法；默认双方都会选取对自己获得胜利最有利的点；以白方的局势评估结果(即局势所获得的评分)为标准进行行棋的比较，白方希望局势中的分数尽可能的高，而黑方希望对方的分数尽可能的低。这便是极大值极小值搜索算法的思路，也是本系统中计算机行棋时博弈树构建所使用方法的基础。

1.3 原生JavaScript、HTML 和CSS

本系统的后台逻辑以及人机交互等功能通过原生的JavaScript 实现，以HTML 作为页面，并使用CSS 对页面进行修饰。JavaScript 是一种具有函数优先的轻量级、解释型或即时编译型的编程语言，也正因为这些优点，使得本系统无需复杂的环境配置，也没有过大的空间占用，下载后使用浏览器打开即可，十分方便快捷。

本项目的后台逻辑部分主要由3 个部分组成：名为Board 的类负责棋盘的显示以及与用户之间的交互；名为Position 的类负责棋子走法的校验和棋子走法的生成；名为search 的类负责电脑行棋所使用的博弈算法。整个系统是一个可以在本地完成所有功能的Web 网页。

2 系统设计与实现

本系统作为一个游戏程序，希望玩家只需一台安装了支持JavaScript 浏览器的设备就可以随时随地进行游戏，因而以一个Web 网页的形式提供给用户。

2.1 棋盘显示及页面交互

棋盘棋子显示，点击响应函数的绑定、编写，刷新棋盘以及开局、重开局等基础功能均在Board 类中实现，并反映在用户的操作界面中，方便用户进行游戏。

2.1.1 棋盘棋子显示

棋盘棋子的显示即用户游戏界面的显示。界面是用户操作的对象，一个简洁、美观、易用的界面十分重要。本系统中的棋盘主体为一个HTML中的div 标签，其中id 为container，该标签的背景为一张棋盘的图片；而棋盘上的每一个位置，都是一个添加进div 标签中的img 标签，每个img 都指向一张准备好的图片；选中框的显示通过为img 标签添加背景图片来实现。

其中div 容器的修改，包括大小的设定、背景图片的路径以及img 标签及其相关参数的动态添加均在初始化Board 对象时进行；而选中框的消除则是由点击响应函数运行后调用Board 类中的drawSquare()方法实现[3]。

2.1.2 点击响应事件绑定、行棋及刷新

点击响应函数clickSquare()同样属于Board类中的方法之一，在Board 类初始化时，通过JavaScript提供的onmousedown 方法添加至img 标签。

点击响应函数发生后，调用Board 中的addMove()方法进行行棋，并通过调用postAddMove()对选中框的显示问题进行处理，在行棋结束后调用Board中的flush()方法实现棋盘的刷新，从而反馈至用户界面。图2 为棋盘显示及页面交互界面。

图2 棋盘显示及页面交互

2.2 行棋校验

国际象棋中每一种棋子都有其自己的走法，当选择的走法不符合规则时，应拒绝执行这一步棋并重新选择走法，这就需要对行棋进行校验，该功能主要在Position 类中实现。当用户点击并触发Board 类中的clickSquare()函数后，将会调用addMove()函数以执行行棋功能。行棋时首先便会调用Position 类中的legal()函数对走法是否合法进行校验，合法则进行后续的工作，否则会阻止进程，重新等待用户的选择。

国际象棋共有6 种棋子，这其中使用了3 种不同的校验方式：对于国王与骑士，使用辅助数组进行校验；对于王后、战车、主教这种走直线的棋子，首先判断其行进方向，然后每次只移动一步，并依次对路径中的每一个格子进行判断；士兵的走法则比较复杂，通过枚举出不同的情况，依次进行判断[4]。

2.3 电脑行棋决策算法

电脑行棋算法是本系统的核心部分之一。在用户行棋之后，会调用Board 中的postAddMove()方法。该方法在对棋子显示相关的问题进行处理后触发，会调用Board 中的response()算法，随后进一步调用Search 类中的searchMain()方法，控制电脑进行行棋决策。电脑行棋决策方法的实现主要分为2 个部分：第一部分是定义在Position 类中的generateMoves()方法，该方法会生成目前棋局中本方所有可能的行棋方法；第二部分则是定义在Search 类中maxminSearch()方法，在生成的算法中进行选择，本项目中使用了极大值极小值搜索算法。

2.3.1 走法生成算法

走法生成算法用来生成当前局面下所有符合规则的行棋方法，即进行行棋时的走法遍历。这一功能为之后的走法评估以及最终的行棋决策提供了进行计算以及选择的对象，该算法主要实现在Position 类中的generateMoves()函数[5]。

遍历开始时，该函数会建立一个用于储存所有可能的下一步行棋方式的动态数组，其中的每一个对象，都记录了一步棋的起点与终点。遍历开始后，该函数会对棋盘上的每一个位置进行遍历，对于空位及对方棋子不做处理，而对于每一个己方的棋子，则根据该棋子的行棋规则，生成当前棋盘局势下所有的、不重复的行棋位置，并将这些合法的走法保存至建立好的动态数组中，遍历结束后将动态数组返回，用于下一步中的处理。

2.3.2 博弈算法

博弈算法分为棋局评估部分以及搜索算法部分。

评估部分的具体参数，即不同棋子在不同位置上的评分，主要由棋子在棋盘上某个位置时能够控制的位置数量决定，这一分值由不断地实验与改进得到。本项目中的取值参考了国际象棋WIKI 中提供的相关数据，而棋局局面的评分通过双方场上所有存在的棋子的价值总和之差表示[6]。由于棋盘是对称的，双方初始分数相同，所以只需在每次行棋后对变化棋子的分值进行计算[7]，评分过程在Position 类中定义的addChess()函数中实现。

搜索算法部分使用了极大值极小值搜索算法，由Search 类中的maxminSearch()实现，这是一种经典算法[8]，基于以下的思路设计：认为双方都足够强大，每一次都会选取对自己最有利的点作为下一步的走法；以白方的局势评估结果(即局势所获得的评分，使用白方总分减去黑方总分)为标准进行行棋比较，白方希望局势评估中自己的分数尽可能高，而黑方希望对方的评估分数尽可能的低[9]。

该算法的实现基于深度优先遍历。运行时将依次遍历generateMoves()函数中生成的走法数组，每选中一种走法，就执行这一步，并重复执行走法生成、棋局评估这一过程，执行设置好的次数，之后在所有的可能性中选取棋局评分对己方最有利的走法[10]。采用的极大值极小值搜索算法会生成一棵如图3 所示的搜索树。

图3 极大值极小值搜索树

2.4 决策算法的研究与修改

现如今计算机博弈算法发展已经十分完善，人机对弈中人类的胜率不断地降低。随着计算机计算性能的进一步发展，人与计算机的差距的扩大是可以预见的[11]。可以认为人机对战的胜利与否已经失去了悬念，因此，本系统对博弈算法进行了修改，编写了以保证棋局局面平衡为目标的博弈算法，以此降低人机差距，达到保持玩家游戏体验的同时，提高玩家棋艺的目的。

2.4.1 基本思路及实现

因为棋局对称，所以对初始局势的双方局势得分进行评估时，双方得分相同，因此只需计算游戏开始后每一步行棋后局势的变化即可。故使用与之前相同的棋局评估方式，且棋局评分越接近0，则代表双方局势越接近平衡。本算法实现于Search 类中的balSearch()方法，调用该方法后，首先调用用于生成所有走法的generateMoves()方法，之后遍历全部的走法。对于这些不同的走法，依次执行，之后评估局面得分，保存执行后局面评估的结果，之后撤销这一步行棋，以执行对下一种走法的操作[10]。将不同的结果做对比，选出得分绝对值最小的走法作为电脑的走法，通过这样的方式，使得局面始终比较平衡，避免某一方轻易获胜或失败。

2.4.2 存在问题及解决方式

当双方的棋局排列相似度较高(比如开局)时，为保证双方局势平衡，电脑经过决策并选择的走法有极大的可能性会与玩家一致，导致棋局效果不佳。因此，算法在进行决策时，不只选用唯一一种走法，而是保存能够保证局势较为平衡的10 种走法，并使用随机抽选的方式选择出一种走法，这样就有效地避免了双方棋局相似时，计算机总是选择与玩家对称的行棋方式。基于这种考虑，本算法首先调用generateMoves()方法获得全部可能的走法，并储存在mvs 数组中；然后，对数组中的走法进行遍历，针对每一种走法，计算执行后的局面分值，如果may 数组中的走法不足10 种，则直接保存，否则将分值与may 数组中走法对应的val 数组中的分值进行比较，保存最符合要求的走法；最后，撤销这一步使棋盘还原，继续遍历。算法程序如下所示。

遍历结束后，计算机在10 种走法中随机任选一种走法执行。

3 测试与验证

接下来对新算法进行测试，测试其在面对不同水平的玩家时，能否顺利达成保持棋局局势平衡的目的[6]。这里使用网络中现有的国际象棋AI 对本模块进行测试。为测试本模块，在项目的实现中加入了新代码，新代码会在每一次电脑行棋后，在浏览器的控制台中输出当前的局势评分。要确定本算法能否保持局势平衡，只需要观察能否维持评估的结果值接近0 即可。测试进行了多次实验，表1 为部分实验数据。

表1 平衡博弈算法测试

从测试结果来进行分析，当玩家水平低于难度II 的电脑AI 时，本模块可以较好地保持棋局局面的平衡，可以达成在保证“初学者”对国际象棋乐趣的同时，经验有所提升这一目标；当玩家水平进一步的提升后(即在测试时选择更高的游戏难度时)，本模块的效果会下降。综上所述，考虑将本功能的目标用户定位于国际象棋初学者。

4 结论

本文提出了以保持对弈双方局面平衡为目的的计算机博弈决策算法，致力于维持玩家对游戏的乐趣的同时，提高玩家的棋艺水平。同时，因为使用JavaScript 实现系统，使得系统可以跨平台使用，且无需事先编译，使用方便。总之，本系统提供了一个占用空间小、运行环境简单、功能完善的国际象棋游戏程序，为人们提供了一个既可以娱乐，又可以提升自己下棋水平的国际象棋游戏平台。