中国象棋游戏的设计与实现

赵娟

[摘要]通过对人下棋过程的分析，得出计算机行棋的整个流程以及计算机在实现人机互战中所采用的技术和知识，例如，估值函数、走法产生器、遍历算法、剪枝算法等。根据这些分析，具体地实现这些算法。但系统还有很多不完善的地方有待进一步提高。

[关键词]数据结构；函数；MFC；C++

[DOI]1013939/jcnkizgsc201537131

1引言

中国象棋游戏电脑与人对战的研究最先是从国际象棋起步的，1950年美国大数学家香农经过几十年的不懈研究，终于找到了编写国际象棋程序的方法。但是近些年来经过很多中国象棋游戏编程爱好者及多个象棋开发团队的不懈努力，使得中国象棋游戏水平有了长足的进步，慢棋已经达到了业余大师的水平，快棋也可以和象棋大师进行对抗了[1]。

2游戏开发的需求分析和总体设计

要开发这样一个象棋游戏系统，首先必须对下棋的过程进行分析。图1就是对人下棋过程的一个抽象描述。用下面的图模拟人的行棋规则。

根据人的行棋规则，编程如何模拟实现下棋过程。图2给出了电脑的行棋规则。综上所述，做好一个人和电脑对战的象棋游戏需要以下几个方面：棋盘数据结构设计；棋子的行棋规则；走法产生器；棋子的价值设计及界面的优势评断；遍历算法；界面设计[2]。

3游戏的详细设计

31棋盘和棋子的实现

311棋盘的实现

一般采用9×10的二维数组作为棋盘数据结构，然而这样的话，后面判断棋子在棋盘内和对棋子走棋规则的判断需要大量的运算和规则。为了节省时间，采用空间换取时间的做法，采用16×16的棋盘数组数据结构，虽然浪费了空间，但是大大增加了效率。判断棋子是否在棋盘内可以用一个辅助的数组来实现。

312棋子表示的改变

红方棋子：一个帅，两个车，马，炮，相，士和五个兵

黑方棋子：一个将，两个车，馬，炮，象，仕和五个卒

用不同的数字来抽象表示每一种棋子，如表1所示。

33走法产生器

331车（車）的走法器设计

车（車）的走法是纵横可达，所能到达的位置广，防守攻击的点多。车的走法一般是左右上下都可以到达，可以说是勇往直前。它在一个方向所能到达的最大长度是9，因为棋盘最多是10×9的位置，所以第二层循环的判断是以9作为判断的。在遇到以下情况时不再往前走。遇到要吃对方棋子，或者说前方有对方棋子的情况，前方有自己本方的棋子，超出了棋盘边界[3]。

332炮的走法设计

炮在不吃子的情况下，和车的走法是一样的。在吃子的情况下有着“隔山打牛”的功用。因为它的走法和车的走法差不多，就是增加了一个翻山的标志。

333马的走法设计

马一共有八个方向的位置可以走，但是走的方向上不能被绊腿，否则无法走动，所以对马还设置了绊腿标志辅助数组。

334卒的走法設计

卒的走法是三个方向，过河之前只有一个方向，根据辅助数组来判断是否过河。

335相、仕、将（帅）的走法设计

相的走法要注意相田被塞，有一个辅助的，相田被塞数组。仕和将的走法简单，不再赘述。

34遍历算法的设计与实现

341遍历算法

在棋面中，当轮到一方行棋的时候，本方可能有好几十种行棋方法，然而只有其中一个被选择执行，本方无论走了哪一步棋，棋面变成另一个棋面情况了，而且轮到另一方行棋，那么另一方也有好几十种的行棋方法，然而它也只能选择其中一个行棋方法，本方在选择棋子走法的时候既要考虑本方行棋方法的好坏，而且要想到它行棋之后另一个会怎么行棋。这样产生了一个东西，那就是遍历搜索树。倘若各个局面有30个可行的走法，那么就得到一个搜索遍历的树[4]。如图3所示。

红方的棋手走棋设定为用圆形表示，黑方的棋手走棋设定为正方形表示。最底端的叶子节点是要到达的最大深度。从叶子节点得到最佳行棋走法，保存从根节点到叶子节点最佳走法的路径。然而，实际中每一方棋手每次只走一次棋，而且不一定按照我们所预先设定的走棋，所以一般只保留根节点的一步最优解。

342极大值节点和极小值节点遍历算法

从图4中可以看出，开始是红方执棋，红方会选择当前走法中使得棋面优势最大的一个，那就是8。接下来黑方走棋，黑方希望找到最小点，因为红方先执棋，所以红方已经选择了B3走法，黑方只能选择10的值了，即C7。对于红方而言，10是极大值，然而对黑方来说10是极小值，极大值和极小值是相对来说的。从上面可以看出，如果搜索深度增加的话，那么步骤应该是这样的：寻找相对最大值—寻找相对最小值—寻找相对最大值，这样依次循环直到达到所要搜索遍历的深度。

343剪枝函数的设计与实现

运用电脑强大的运算能力对整个对战树进行遍历搜索。但是遍历搜索的层数深了也是需要时间的，对10×9的棋盘进行几层遍历搜索是需要相当的时间的，极其影响效率，而且好多节点是不需要搜索的，通过裁剪遍历算法对没有用的节点分支进行裁剪，这样大大地提高效率[4]。

以下面的遍历搜索对战树为例简单介绍一下裁剪算法。在遍历到B2节点时，红方已在B1节点遍历到了当前棋面最优值8，红棋方想经过B2节点找到更加优秀的值。在遍历到C4节点时得到估值7，7也是当前B2节点的最优值。因为B2是极小值点，所以在遍历B2剩下的节点时，所有比7大的节点B2节点都不会考虑，当小于7，则取代7作为当前最优值。不管后面的节点的估值是什么，结果是B2节点的最优值不大于7。A节点找的是极大值点，A节点已经有了一个当前棋面最优值8，则A节点的最优值一定大于等于8，B2节点的值超不过7，站在A节点的立场，B2是没有用的，对B2后续节点继续进行遍历是没有意义的。所以C5、C6几点不需要进行遍历，回溯到A节点返回值，对A节点的后续其他子节点进行遍历。裁剪算法树如图5所示。

5结论

本文通过对中国象棋游戏设计与实现的思想进行分析，介绍了棋盘、棋子、走棋、走棋栈等重要数据结构。设定棋子走棋规则，满足每个棋子特定的走棋规则。探讨了走法生成器的设计与实现，对搜索遍历算法的运用。对每个棋子的价值进行拟定，对其所能到达位置的价值进行计算。系统还有很多地方有待进一步优化，例如，遍历搜索算法、剪枝算法等。这些会在以后的文章中再进行探讨。

参考文献：

[1]韩伟，任建敏，吴瑞芳基于数据库技术的中国象棋软件开局库的设计与实现[J].科学技术与工程，1998（3）：556

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

[3]危春波中国象棋系统的研究与实现[D].昆明：昆明理工大学，2000

[4]袁天鑫，傅尧青中国象棋博弈程序中的树搜索算法[J].上海交通大学学报，1990（4）：12-15