象棋人工智能算法的C++实现（一）
前言：自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)；
下面给大家看一下棋盘类的源代码，里面是关于棋盘类的一些属性（数据成员）和需要在棋盘上进行的一些操作（函数成员），在这里我只给大家提供一个框架，各种成员函数的具体实现就要靠大家开动脑筋了。如果大家在这期间遇到什么问题，尽量要自己解决，如果实在解决不了，给大家提供一下我的邮箱：freedom11235@126.com。
#ifndefBOARD_H#defineBOARD_H#include#include"Stone.h"#include"Step.h"#include#includeclassBoard:publicQWidget{Q_OBJECTpublic:explicitBoard(QWidget*parent=0);//32颗棋子Stone_s[32];//棋子的像素半径int_r;//选中棋子的idint_selectid;//该不该红棋走bool_bRedTurn;//保存棋子的行走步骤QVector_steps;//输入行列获取棋子的idintgetStoneId(introw,intcol);//计算即将行走的棋子与某一坐标之间有几颗棋子intnum_of_Stone(intmoveid,introw,intcol);//输入行列坐标判断该坐标上有没有棋子boolbeStone(introw,intcol);boolcanSelect(intid);//最基本的能不能走的判断判断boolcanMove(intmoveid,introw,intcol,intkillid);//判断将能不能走boolcanMoveJIANG(intmoveid,introw,intcol,intkillid);//判断士能不能走boolcanMoveSHI(intmoveid,introw,intcol,intkillid);//判断象能不能走boolcanMoveXIANG(intmoveid,introw,intcol,intkillid);//判断车能不能走boolcanMoveCHE(intmoveid,introw,intcol,intkillid);//判断马能不能走boolcanMoveMA(intmoveid,introw,intcol,intkillid);//判断炮能不能走boolcanMovePAO(intmoveid,introw,intcol,intkillid);//判断兵能不能走boolcanMoveBING(intmoveid,introw,intcol,intkillid);//尝试函数voidtrySelectStone(intid);voidtryMoveStone(intkillid,introw,intcol);//判断两个棋子是否是同一方的boolsameColor(intid1,intid2);//走棋函数极其重载voidmoveStone(intmoveid,intkillid,introw,intcol);voidmoveStone(intmoveid,introw,intcol);//杀死棋子的函数voidkillStone(intid);//复活棋子的函数voidreliveStone(intid);voidsaveStep(intmoveid,intkillid,introw,intcol,QVector&steps);//与鼠标点击有关的函数voidmouseReleaseEvent(QMouseEvent*);voidclick(QPointpt);virtualvoidclick(intid,introw,intcol);//获取鼠标点击位置的行列坐标boolgetRowCol(QPointpt,int&row,int&col);//与显示到窗口中有关的函数voiddrawStone(QPainter&painter,intid);voidpaintEvent(QPaintEvent*);//输入行列坐标返回像素坐标QPointcenter(introw,intcol);//输入棋子的id返回像素坐标QPointcenter(intid);signals:publicslots:};#endif//BOARD_H2.再把棋子抽象出来。每个棋子都有一个id，初始时共有32枚棋子，id从0到31；棋子所具有的属性除了id还有所处的行列位置，棋子的类型（车马炮将士相兵），棋子的颜色（红/黑），棋子是否还存活着。id置为int型；棋子类型置为枚举类型enumTYPE{JIANG,CHE,PAO,MA,BING,SHI,XIANG}；棋子的颜色置为bool型_red，红棋为true，黑棋为false；棋子是否还存活置为bool型，活着为true，被吃掉为false。
#ifndefSTONE_H#defineSTONE_H#includeclassStone{public:Stone();//枚举棋子的所有类型enumTYPE{JIANG,CHE,PAO,MA,BING,SHI,XIANG};//棋子所处的行int_row;//棋子所处的列int_col;//棋子的idint_id;//棋子是否已死bool_dead;//棋子是否为红子bool_red;//棋子类型TYPE_type;//初始化棋子voidinit(intid);//获取棋子的类型名QStringgetText();};#endif//STONE_H3.按照象棋的规则实现每个棋子的走法的前期函数铺垫。这一部分是后期人工智能算法的基础，因为后期要将所有能走的通的“路”保存在一个C++容器（类似于C语言中的数组）里。
（1）确定某个行列位置上是否存在棋子。
这个函数在后面具体棋子的走法算法中应用的非常广泛。例如走马的时候需要判断是否别了马腿，也就是需要判定想要移动的马在要去的方向的正前方的位置是否有别的棋子挡住，即判断该位置上是否存在棋子；再例如如果出现了“对将”的情况，需要判断红将和黑将之间与其在同一直线上的所有位置上是否存在棋子，若所有位置都不存在棋子则两个将可以对吃。
其实现的原理很简单，即输入一个行列坐标后遍历所有存活的棋子的行列坐标看一下有没有棋子与之完全吻合，若存在这样的棋子，则表示该行列坐标上存在棋子。
/*确定某个行列位置上是否有棋子*/boolBoard::beStone(introw,intcol){for(inti=0;i0)for(i=_s[moveid]._col+1;icol;i--){if(beStone(_s[moveid]._row,i)==true)sum++;}returnsum;}elseif(_s[moveid]._col==col){if(row-_s[moveid]._row>0)for(i=_s[moveid]._row+1;irow;i--){if(beStone(i,_s[moveid]._col)==true)sum++;}returnsum;}//两个棋子不在一条直线上return-1;}这个项目我会连载，后期各种算法的实现敬请期待！
欢迎大家关注/订阅我的微信公众号CodeArtOnline，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓
人工智能如何玩转国际象棋
前国际象棋世界冠军弗拉基米尔•克拉姆尼克(左)与杰米斯•哈萨比斯(右)创立的Alphabet旗下的DeepMind合作，探索使用人工智能的新型国际象棋。
国际象棋在大约500年前迅速传播，当时欧洲棋手将一种移动缓慢的棋子提升为现代强大的王后，这给了这个游戏更多的活力。1996年，也就是IBM的“深蓝”击败卡斯帕罗夫的前一年，国际象棋神童、现逃犯鲍比•菲舍尔(BobbyFischer)在布宜诺斯艾利斯召开了一场新闻发布会，抱怨国际象棋需要重新设计，以降低电脑强化记忆能力，鼓励创新。他推出了费舍尔随机国际象棋(FischerRandomChess)，这种象棋保留了通常的游戏规则，但随机化了每局棋盘背面强大棋子的起始位置。菲舍尔随机牌，也被称为960象棋，慢慢地在国际象棋世界中赢得了一席之地，现在有了自己的比赛。
DeepMind和Kramnik发掘了AlphaZero从零开始学习游戏的能力，以比人类几十年或几个世纪的游戏更快地探索新的变种，人类的游戏会揭示出它们的美丽和缺陷。“你不想投资数月或数年的你的生活想玩的东西,只有意识到,“哦,这并不是一个美丽的游戏,“”Tomašev说。
AlphaZero是AlphaGo更灵活、更强大的继任者。2016年，AlphaGo打败了围棋冠军，在人工智能历史上留下了一个里程碑。它开始学习一个只有规则、记分的方法和一种预先设定好的尝试和胜利的冲动的游戏。参与该项目的另一位DeepMind研究员乌尔里希•帕奎特(UlrichPaquet)表示:“当它开始玩的时候，它的表现非常糟糕，我都想躲到桌子底下。”“但看到它从虚无的虚空中进化出来，令人兴奋，几乎是纯粹的。”
在国际象棋中，AlphaZero最初并不知道它可以拿走对手的棋子。在几个小时的高速游戏中，不断地对抗更强大的化身，它变得更熟练，对一些人来说，比之前的象棋引擎更自然。在这个过程中，它重新发现了人类几个世纪以来的象棋理念，并增加了自己的天赋。英国特级大师马修·萨德勒(MatthewSadler)将钻研AlphaZero的游戏描述为“发现过去一些伟大棋手的秘密笔记本”。
AlphaZero测试的九种备选国际象棋方案中，包括克拉姆尼克和其他人已经在考虑的无castling国际象棋，并在1月份举行了第一场专门的比赛。它消除了一种叫castling的移动方法，该方法允许玩家将自己的国王隐藏在其他棋子的保护屏后——这种强大的防御方式也会令人窒息。五种变体改变了棋子的移动，包括鱼雷象棋，在整个游戏中，棋子可以一次移动两个方格，而不是只在第一次移动的时候。
读取AlphaZero结果的一种方法是使用冷数字。与传统规则相比，无等级象棋下的平局更少见。学习了不同的规则后，AlphaZero放在不同棋子上的值就会发生变化：在传统规则下，皇后的值是9.5个卒子；在鱼雷规则下，女王只值7.1卒。
最终，DeepMind的研究人员对该项目中另一个伟大的象棋大脑克拉姆尼克(Kramnik)的分析更感兴趣。“这不是关于数字,而是优质愉悦的感受人类坐下来玩游戏,”Tomašev说。周三发布的一份技术文件中，有70多页克拉姆尼克对AlphaZero探索的评论。
克拉姆尼克在AlphaZero如何适应新规则的过程中看到了一些亮点。他说，无等级象棋激发了保护国王安全的丰富新模式。另一个更极端的变化，自我捕获国际象棋，玩家可以自己拿棋子，被证明更有吸引力。克拉姆尼克说，这一规则实际上给了玩家更多的机会，让他们可以牺牲一部分来获得成功。几个世纪以来，这种战术一直被视为优雅玩法的标志。“总而言之，这只会让比赛变得更美好，”他说。
克拉姆尼克希望AlphaZero在国际象棋中的冒险经历能够说服所有级别的玩家都尝试一下。“这是我们给国际象棋世界的礼物，”他说。现在可能是一个合适的时机。
两届美国女子国际象棋冠军詹妮弗·沙哈德说，国际象棋已经流行了多年，但随着许多人寻求新的智力刺激，国际象棋经历了大规模流行。人们对960国际象棋的兴趣也在增加，这表明人们对包括一些超级明星在内的新型玩法有了兴趣。本周晚些时候，沙哈德将为包括世界排名第一的卡尔森(MagnusCarlsen)和前冠军卡斯帕罗夫(Kasparov)在内的960国际象棋(Chess960)锦标赛提供评论。
和克拉姆尼克一样，沙哈德在AlphaZero测试的几个变体中也看到了一些类似的东西，尽管像允许卒子横向移动这样的变化让人感觉“难以置信”。“如果有市场获得吸引力，一些玩家仍将希望依靠电脑和深入研究来领先，但重新设定周期可能会引人入胜。”Shahade同时也是美国国际象棋联合会的女子项目主任，她说:“这些发现会让人感觉新鲜——这将是非常令人兴奋的，而且会让不同类型的玩家受益。”既然机器是不可战胜的，DeepMind和克拉姆尼克的项目可能也会鼓励计算机国际象棋变得更有创造性。
以色列巴伊兰大学(Bar-IlanUniversity)研究员伊莱•大卫(EliDavid)表示：“我们可以专注于把国际象棋作为一种游戏形式的艺术，而不是让计算机国际象棋变得更强大，从而摧毁人类。”大卫自己制造了一台以机器学习为动力的国际象棋引擎。在他的实验室里，一名研究生正在研究一种能模仿特定棋手风格的国际象棋软件，这种软件可以询问机器过去或现在最喜欢的大师在特定情况下会做什么。
Kramnik的经验表明，让人类与机器一起工作，而不是对抗机器，可以扩展游戏的情感体验和技术体验。AlphaZero甚至把他带到了他广阔的理解力之外的地方。他说：“三招之后你就不知道该怎么做了。”“感觉很好，就像你是个孩子。”
来源：机器人在线返回搜狐，查看更多