象棋人工智能算法的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)；
下面给大家看一下棋盘类的源代码，里面是关于棋盘类的一些属性（数据成员）和需要在棋盘上进行的一些操作（函数成员），在这里我只给大家提供一个框架，各种成员函数的具体实现就要靠大家开动脑筋了。
class Board : public QWidget
{
Q_OBJECT
public:
explicit Board(QWidget *parent = 0);
//32颗棋子
Stone _s[32];
//棋子的像素半径
int _r;
//选中棋子的id
int _selectid;
//该不该红棋走
bool _bRedTurn;
//保存棋子的行走步骤
QVector<Step*> _steps;
//输入行列获取棋子的id
int getStoneId(int row,int col);
//计算即将行走的棋子与某一坐标之间有几颗棋子
int num_of_Stone(int moveid,int row,int col);
//输入行列坐标判断该坐标上有没有棋子
bool beStone(int row,int col);
bool canSelect(int id);
//最基本的能不能走的判断判断
bool canMove(int moveid,int row,int col,int killid);
//判断将能不能走
bool canMoveJIANG(int moveid,int row,int col,int killid);
//判断士能不能走
bool canMoveSHI(int moveid,int row,int col,int killid);
//判断象能不能走
bool canMoveXIANG(int moveid,int row,int col,int killid);
//判断车能不能走
bool canMoveCHE(int moveid,int row,int col,int killid);
//判断马能不能走
bool canMoveMA(int moveid,int row,int col,int killid);
//判断炮能不能走
bool canMovePAO(int moveid,int row,int col,int killid);
//判断兵能不能走
bool canMoveBING(int moveid,int row,int col,int killid);
//尝试函数
void trySelectStone(int id);
void tryMoveStone(int killid, int row, int col);
//判断两个棋子是否是同一方的
bool sameColor(int id1, int id2);
//走棋函数极其重载
void moveStone(int moveid, int killid, int row, int col);
void moveStone(int moveid, int row, int col);
//杀死棋子的函数
void killStone(int id);
//复活棋子的函数
void reliveStone(int id);
void saveStep(int moveid, int killid, int row, int col, QVector<Step*>& steps);
//与鼠标点击有关的函数
void mouseReleaseEvent(QMouseEvent *);
void click(QPoint pt);
virtual void click(int id,int row,int col);
//获取鼠标点击位置的行列坐标
bool getRowCol(QPoint pt,int &row,int &col);
//与显示到窗口中有关的函数
void drawStone(QPainter& painter,int id);
void paintEvent(QPaintEvent *);
//输入行列坐标 返回像素坐标
QPoint center(int row,int col);
//输入棋子的id 返回像素坐标
QPoint center(int id);
signals:
public slots:
};
2.再把棋子抽象出来。每个棋子都有一个id，初始时共有32枚棋子，id从0到31；棋子所具有的属性除了id还有所处的行列位置，棋子的类型（车马炮将士相兵），棋子的颜色（红/黑），棋子是否还存活着。id置为int型；棋子类型置为枚举类型enum TYPE{JIANG,CHE,PAO,MA,BING,SHI,XIANG}；棋子的颜色置为bool型_red，红棋为true，黑棋为false；棋子是否还存活置为bool型，活着为true，被吃掉为false。
class Stone
{
public:
Stone();
//枚举棋子的所有类型
enum TYPE{JIANG,CHE,PAO,MA,BING,SHI,XIANG};
//棋子所处的行
int _row;
//棋子所处的列
int _col;
//棋子的id
int _id;
//棋子是否已死
bool _dead;
//棋子是否为红子
bool _red;
//棋子类型
TYPE _type;
//初始化棋子
void init(int id);
//获取棋子的类型名
QString getText();
};
3.按照象棋的规则实现每个棋子的走法的前期函数铺垫。这一部分是后期人工智能算法的基础，因为后期要将所有能走的通的“路”保存在一个C++容器（类似于C语言中的数组）里。
（1）确定某个行列位置上是否存在棋子。
这个函数在后面具体棋子的走法算法中应用的非常广泛。例如走马的时候需要判断是否别了马腿，也就是需要判定想要移动的马在要去的方向的正前方的位置是否有别的棋子挡住，即判断该位置上是否存在棋子；再例如如果出现了“对将”的情况，需要判断红将和黑将之间与其在同一直线上的所有位置上是否存在棋子，若所有位置都不存在棋子则两个将可以对吃。
其实现的原理很简单，即输入一个行列坐标后遍历所有存活的棋子的行列坐标看一下有没有棋子与之完全吻合，若存在这样的棋子，则表示该行列坐标上存在棋子。
/*确定某个行列位置上是否有棋子*/
bool Board::beStone(int row,int col)
{
for(int i=0;i<32;i++)
if(_s[i]._row==row&&_s[i]._col==col&&!_s[i]._dead)
return true;
return false;
}（2）计算某一棋子与某一行列坐标之间有几颗棋子。
这个函数主要应用在“对将”以及车和炮的走棋算法上。例如炮如果想要隔着炮架吃掉对方的棋子就需要保证该炮与想要吃掉的对方的棋子之间有且仅有一个棋子；再例如车想要走棋到某一行列坐标必须保证该车与想要走到的位置之间没有棋子。
有了（1）的铺垫，本函数的实现就变得容易了。首先需要判定一下即将行走的棋子的位置与目标位置在不在同一行（列）上。如果不在同一行（列）上则直接返回-1；如果在则可以遍历一整行（列）并调用（1）所介绍的函数beStone来统计即将行走的棋子与目标位置之间棋子的个数。
//计算即将行走的棋子与某一坐标之间有几颗棋子 默认返回值为-1
int Board::num_of_Stone(int moveid,int row,int col)
{
int i;
int sum=0;
if(_s[moveid]._row==row)
{
if(col-_s[moveid]._col>0)
for(i=_s[moveid]._col+1;i<col;i++)
{
if(beStone(_s[moveid]._row,i)==true)
sum++;
}
else
for(i=_s[moveid]._col-1;i>col;i--)
{
if(beStone(_s[moveid]._row,i)==true)
sum++;
}
return sum;
}
else if(_s[moveid]._col==col)
{
if(row-_s[moveid]._row>0)
for(i=_s[moveid]._row+1;i<row;i++)
{
if(beStone(i,_s[moveid]._col)==true)
sum++;
}
else
for(i=_s[moveid]._row-1;i>row;i--)
{
if(beStone(i,_s[moveid]._col)==true)
sum++;
}
return sum;
}
//两个棋子不在一条直线上
return -1;
}
- The End -
点击文末阅读全文，看『程序人生』其他精彩文章推荐
「若你有原创文章想与大家分享，欢迎投稿。」
加编辑微信ID，备注#投稿#：
程序 丨 druidlost
小七 丨 duoshangshuang
推荐阅读：
print_r('点个赞吧')；
var_dump('点个赞吧')；
NSLog(@"点个赞吧！")
System.out.println("点个赞吧!");
console.log("点个赞吧!");
print("点个赞吧!");
printf("点个赞吧!\n");
cout << "点个赞吧!" << endl;
Console.WriteLine("点个赞吧!");
fmt.Println("点个赞吧!")
Response.Write("点个赞吧")；
alert（’点个赞吧’）