象棋人工智能算法的C＋实现（一）

第一时间关注程序猿（媛）身边的故事

作者

De掉所有bug

已获原作者授权，如需转载，请联系原作者。

前言：自AlphaGo战胜世界著名九段围棋手李世石之后，我就对棋类人工智能产生了极大的兴趣，并想要自己实现象棋的人工智能。然而那个时候我还在读高二，没有这么深厚的代码基础，所以那个时候也就只能想想了。但是现在不一样了，通过学习编程，已经可以让我在棋类人工智能这个领域向前探索了。

首先说明一下本系列博客描述的人工智能算法不是基于机器学习、深度学习这么高深的知识，而是一种穷举找最优走法的算法。之所以AlphaGo不能使用这种算法战胜李世石，是因为围棋棋局局势的判断是极为复杂的，想要穷举所有的情况，全世界所有的计算机一起运行一百万年也无法找到最优走法。所以DeepMind团队的大佬就想出了另一种解决方案就是让AlphaGo自己学习高水平棋手间的对局，从而提升AlphaGo的棋力。然而象棋的棋局判断还是比较容易的，杀掉对面的老将就可以获胜，杀掉对面的车马炮等棋子就可以提高自己的胜率/降低对方的胜率。具体的算法在之后的篇章详细讲解。

实现本系列博客中算法的编程工具是Qt5.5.1。

既然实现象棋人工智能的算法的本质是穷举，那么就要找到所有的通路，所谓的通路就是能够走棋的那些“路”们，走不通的那些“路”就要直接被pass掉。

1.先把棋盘抽象出来，象棋棋盘有10行9列，行标设为0~9，列标设为0~8。以左上角的坐标为(0,0)，假设初始时上方为红棋，下方为黑棋。则初始时所有棋子的坐标为：

车1（红方）：(0,0)；车2（红方）：(0,8)；

马1（红方）：(0,1)；马2（红方）：(0,7)；

相1（红方）：(0,2)；相2（红方）：(0,6)；

士1（红方）：(0,3)；士2（红方）：(0,5)；

将（红方）：(0,4)；

炮1（红方）：(2,1)；炮2（红方）：(2,7)；

兵1（红方）：(3,0)；兵2（红方）：(3,2)；兵3（红方）：(0,4)；兵4（红方）：(0,6)；兵5（红方）：(0,8)；

注：红方的棋子行列坐标对应黑方棋子的行列坐标的关系为：红方行号+黑方行号=9；红方列号+黑方列号=8。

车1（黑方）：(9,8)；车2（黑方）：(9,0)；

马1（黑方）：(9,7)；马2（黑方）：(9,1)；

相1（黑方）：(9,6)；相2（黑方）：(9,2)；

士1（黑方）：(9,5)；士2（黑方）：(9,3)；

将（黑方）：(9,4)；

炮1（黑方）：(7,7)；炮2（黑方）：(7,1)；

兵1（黑方）：(6,8)；兵2（黑方）：(6,6)；兵3（黑方）：(6,4)；兵4（黑方）：(6,2)；兵5（黑方）：(6,0)；

下面给大家看一下棋盘类的源代码，里面是关于棋盘类的一些属性（数据成员）和需要在棋盘上进行的一些操作（函数成员），在这里我只给大家提供一个框架，各种成员函数的具体实现就要靠大家开动脑筋了。

2.再把棋子抽象出来。每个棋子都有一个id，初始时共有32枚棋子，id从0到31；棋子所具有的属性除了id还有所处的行列位置，棋子的类型（车马炮将士相兵），棋子的颜色（红/黑），棋子是否还存活着。id置为int型；棋子类型置为枚举类型enum TYPE；棋子的颜色置为bool型_red，红棋为true，黑棋为false；棋子是否还存活置为bool型，活着为true，被吃掉为false。

3.按照象棋的规则实现每个棋子的走法的前期函数铺垫。这一部分是后期人工智能算法的基础，因为后期要将所有能走的通的“路”保存在一个C++容器（类似于C语言中的数组）里。

（1）确定某个行列位置上是否存在棋子。

这个函数在后面具体棋子的走法算法中应用的非常广泛。例如走马的时候需要判断是否别了马腿，也就是需要判定想要移动的马在要去的方向的正前方的位置是否有别的棋子挡住，即判断该位置上是否存在棋子；再例如如果出现了“对将”的情况，需要判断红将和黑将之间与其在同一直线上的所有位置上是否存在棋子，若所有位置都不存在棋子则两个将可以对吃。

其实现的原理很简单，即输入一个行列坐标后遍历所有存活的棋子的行列坐标看一下有没有棋子与之完全吻合，若存在这样的棋子，则表示该行列坐标上存在棋子。

（2）计算某一棋子与某一行列坐标之间有几颗棋子。

这个函数主要应用在“对将”以及车和炮的走棋算法上。例如炮如果想要隔着炮架吃掉对方的棋子就需要保证该炮与想要吃掉的对方的棋子之间有且仅有一个棋子；再例如车想要走棋到某一行列坐标必须保证该车与想要走到的位置之间没有棋子。

有了（1）的铺垫，本函数的实现就变得容易了。首先需要判定一下即将行走的棋子的位置与目标位置在不在同一行（列）上。如果不在同一行（列）上则直接返回-1；如果在则可以遍历一整行（列）并调用（1）所介绍的函数beStone来统计即将行走的棋子与目标位置之间棋子的个数。

- The End -