前言：上期博客介绍了最简单的人机游戏算法，包括获取所有合法路径、简评和计算机国际象棋。 这次博客的先进之处在于，介绍的评估算法是基于上次博客简单评估函数的极大极小值算法Minimax算法)。
关于极大极小值算法：
极大极小算法是指在失败的最大可能性中找到最小值的算法。 也就是说，将对方的最大利益最小化。 例如，电脑为A，人类为B，A在走棋之前需要思考，A走了某一步后，看看B有哪些走法，B又不傻，所以B肯定是要选择让A得分最少的走法走棋，而A就是在A的所有走法中选择B给出的让A得分最少的走法中得分最多的走法。可能听起来很抽象、绕圈子，但请多次阅读和理解。
在计算机上配置极大极小值算法，让计算机选择棋步路径，大致分三步走还是计算机为a，人为b ) :
1 .在当前局面下取得a所有棋步的传球，然后尝试。
2 .根据前面的步骤a已经尝试过)获得b的所有棋步，并在b的视点上尝试。 然后评价棋局因为A是电脑，所以局面分是以A的角度计算的，即A的总分-B的总分)，遍历b的所有棋步后，返回到这些棋局中的最小值)对a最不利，对b最有利)。
3 .在前一手返回的棋局分的最小值中，找出最大值，锁定与该最大值对应的棋步，作为返回值返回。
现在需要获取计算机的所有手指路径和人类的所有手指路径，所以稍微修改一下getAllPossibleMove函数。
//获取所有通过的通过方法存储在数组steps中的voidsinglegame 33603360 getallpossiblemove qvectors TEP * steps ) { int min=16，max=32； ifthis-_bredturn ) { min=0，max=16； ) /所有棋子forintI=min； imax； I ) /棋子死后ifs ) I )._dead ) continue； //遍历所有行的坐标for introw=0； row=9； row//遍历所有列的坐标for intcol=0； col=8； col )//取得想杀的棋子的idintkillid=this-getstoneid row，col )//如果想杀的棋子和走的棋子是同一颜色的话是ifsamecolorkillid，I ) ) //判断某个棋子是否能走的ifcanmoveI，killid，row，col ) ) /将能走的“步”存储在steps中的saveStepi ) I，killid，row，col，sstep } } } }}与上次的博客相比，getBestMove函数没有直接调用评估函数，而是调用getMinScore函数，找到了对a最不利、对b最有利的分数。
上面getBestMove函数的源代码：
//最佳走法step * single game :3360 getbestmove ) { QVectorStep * steps； //获取电脑所有棋步路径的地理位置移动steps )； int maxScore=-100000； Step* ret； qvectors TEP * :3360迭代器it=steps.begin for )； 信息技术！=steps.end ； it ) { Step* step=*it；//试着走//FakeMoveStep )； //取得电脑目前走法对自己最不利的分数int score=getMinScore ； //再走unfakemovestep )； //从对自己最不利的所有得分中发现对自己最有利的得分，锁定棋步，作为返回值输入if scoremaxscore { max score=score )； ret=步骤； } }返回； }上getMinScore函数的源代码：
intsinglegame : getminscore ) { QVectorStep* steps； //获取人类所有棋步路径的getAllPossibleMo
vesteps); int minScore=100000; forQVector<Step*>::iterator it=steps.begin);it!=steps.end);++it) { Step* step=*it; //以人类的视角试着走一下 fakeMovestep); //评估局面分 int score=calcScore); //再走回来 unfakeMovestep); //找到对电脑最不利的分数作为返回值返回 ifscore<minScore) { minScore=score; } } return minScore;}
到目前为止，象棋人工智能的效果是这样的：
能够看出来，电脑变得比之前更聪明了。我吃掉它的炮后，它出了车，我把炮放在它眼前，它反而不吃，因为它知道我是在拿我的炮钓它的车。 这便是“走一步看两步”的两步人工智能。
那么问题来了，如何实现“走一步看三步”的三步人工智能乃至更多步人工智能呢？可以用递归的思想改写上面介绍的getBestMove函数和getMinScore函数，然后再加一个递归的getMaxScore函数，还需要在SingleGame类中加一个数据成员_level来表示递归的层数（当然递归的层数越大电脑越聪明）。
写一个SingleGame类的构造函数来将_level初始化：
SingleGame::SingleGame){ _level=3;}
上getMaxScore函数的源代码：
int SingleGame::getMaxScoreint level){ iflevel==0) return calcScore); QVector<Step*> steps; getAllPossibleMovesteps); int maxScore=-100000; forQVector<Step*>::iterator it=steps.begin);it!=steps.end);++it) { Step* step=*it; fakeMovestep); int score=getMinScorelevel-1); unfakeMovestep); ifscore>maxScore) { maxScore=score; } } return maxScore;}
getMaxScore函数可以仿照getMinScore函数写，他们两个的区别就在于返回最大值还是返回最小值。
上改写后的getMinScore函数的源代码：
int SingleGame::getMinScoreint level){ iflevel==0) return calcScore); QVector<Step*> steps; getAllPossibleMovesteps); int minScore=100000; forQVector<Step*>::iterator it=steps.begin);it!=steps.end);++it) { Step* step=*it; fakeMovestep); int score=getMaxScorelevel-1); unfakeMovestep); ifscore<minScore) { minScore=score; } } return minScore;}
上改写后的getBestMove函数的源代码：
Step* SingleGame::getBestMove){ QVector<Step *> steps; //看看有哪些步骤可以走 getAllPossibleMovesteps); int maxScore=-100000; Step* ret; forQVector<Step*>::iterator it=steps.begin);it!=steps.end);++it) { Step* step=*it; //试着走一下 fakeMovestep); int score=getMinScore_level-1); unfakeMovestep); ifscore>maxScore) { maxScore=score; ret=step; } } return ret;}
大家注意！！！_level的值不要设置太大。我测试过，我的电脑4G内存，_level设置为4前期还可以勉强运行（运行速度特别慢），后期剩下的棋子越来越少，每个活着的棋子行走的选择就会越来越多，因此占的内存会越来越大，直到程序崩溃。不知道8G内存的电脑情况如何，大家可以自行测试一下。
_level设置为4，后期电脑思考时飙升的内存占用：
再后期程序会异常结束。
毕竟最佳走棋路径是穷举出来的，消耗内存是避免不了的，还请各位大佬勿喷。
到目前为止，象棋的基础人工智能算法算是讲完了。然而，后期更深度的优化还有好多。如果反响比较强烈，我会选择继续更博。
欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓