文章目录01 -极大极小值算法02 -电脑与人类所有棋步路径03 -进一步两步04 -进一步多步04 -总结
01 -极大极小值算法
上次的博客介绍了最简单的人机游戏算法。 这包括所有合法路径、简单估值和计算机象棋的获得。 在这次的博客中，在评价算法的介绍中增加了极小值算法(Minmax算法)，使计算机象棋变得更加智能。
极小值算法是指在失败的最大可能性中找到最小值的算法，使对方的最大利益最小化。 举个例子吧。 设计算机为a，人为b。 A在下手前需要考虑A在下了某一步之后B在下哪一步。 B不是笨蛋，所以B一定会选择让a得分最小的棋。 然后，a会在a的所有棋步中，选择b使a得分最小的棋步中得分最高的棋步。 听起来很抽象，但读几次就能理解了。
在计算机中引入极大极小值算法包括三个步骤。
(1)在当前局面下获取并尝试计算机所有棋步路径；
)2)计算机在进一步尝试的基础上，获取人的所有棋步路径，并以人的观点进行尝试。 然后，棋局点(棋局点是用计算机的视点来计算的。 也就是说，计算机的总分-人的总分) )，遍历人的所有棋步后，回到这些棋局中的最小值)对计算机最不利、对人类最有利的情况。
)3)在当前棋步返回的棋局部分的最小值中，找出最大值，锁定与该最大值对应的棋步路径，作为“棋步”的返回值返回。
02 -计算机与人的所有棋着路径实现算法的第一步是获取计算机与人的所有棋着路径，因此在getAllPossibleMove函数上稍作修改。
/** * * @brief :获取所有棋子都能走的步骤* * @param : steps :移动棋子信息的属性(原坐标、目标坐标、ID、目标id(*@return3360无(* */voidchod if(this-bredturn({min=0； max=16； (//所有黑方驹for(intI=min； i max； I ) (/棋子死后，直接输入if(mychess[I].isdead ) continue； //遍历所有行坐标for (intx=0； x9； x ()//遍历所有列的坐标for (inty=0； y10； y ()//获取想杀的棋子的idintkillid=this-getchessid(x，y )//如果想杀的棋子和走的棋子的颜色相同，则为if(samecolor(I，killid ) ) coco //判断某个棋子是否能走的if(canmove(I，killid，x，y ) ) /将能走的“步”存储在steps中的saveStep(i ) I，killid，x，y，steps )； }}}03-1与其走两步跟上一期博客，不如直接调用calcScore评估函数来计算对计算机最有利的分数并下手，而是用getMinScore函数代替计算对计算机最不利的人
/* * * * @获取brief :计算机优化路径* * @param :无* * @return:优化棋子信息的属性(原始坐标、目标坐标、ID、目标id (* */step * chessarep //初始化比重int maxScore=-100000； Step* ret； qvectors TEP * :3360迭代器it=steps.begin (for )； 信息技术！=steps.end (； it ) { Step* step=*it；//试着走//FakeMove(Step )； //获取电脑当前走法对自己最不利的分数intscore=getminscore(level-1 )//再走unfakemove(step )；
//取最高的分数 if(score > maxScore) { maxScore = score; ret = step; } } return ret;} /** * * @brief : 获取人类下一步走法对电脑最不利的分数 * * @param : 无 * * @return: 对电脑最不利的分数值 * **/int ChessArea::getMinScore(){ QVector<Step*> steps; bRedTurn = true; // 获取人类的所有走棋路径 getAllPossibleMove(steps); bRedTurn = false; int minScore = 100000; for(QVector<Step*>::iterator it=steps.begin(); it!=steps.end(); ++it) { Step* step=*it; // 以人类的视角试着走一下 fakeMove(step); //评估局面分 int score = calcScore(); qDebug() << QString(“红旗评分： %1”).arg(score); // 再走回来 unfakeMove(step); // 找到对电脑最不利的分数作为返回值返回 if(score < minScore) { minScore=score; } } return minScore;}
到目前为止，电脑下棋已经变得更加智能了，大概效果如下：
从运行效果可以看出，我吃掉电脑的炮后，它出了車，我把炮放在它眼前，它反而不吃，因为它知道我在拿炮钓它的車，这个便是实现了“走一步看两步”的博弈算法智能。
04 – 走一步看多步
既然能实现“走一步看两步”，那么是不是能实现“走一步看三步”乃至更多步的人工智能呢？答案是肯定的。我们可以用递归的思想改写前面介绍的getBestMove函数和getMinScore函数，然后在家一个递归的getMaxScore函数，用Level表示递归深度，Level越大，电脑越聪明，这样就能实现“走一步看多步”。
level = 3; // widget初始化时，设置优化等级3 /** * * @brief : 调用回调函数getMinScore获得局面最大分数 * * @param : 无 * * @return: 最大分数值 * **/int ChessArea::getMaxScore(int level){ if(level == 0) return calcScore(); QVector<Step*> steps; getAllPossibleMove(steps); int maxScore = -100000; for(QVector<Step*>::iterator it=steps.begin();it!=steps.end(); ++it) { Step* step=*it; fakeMove(step); int score = getMinScore(level-1); unfakeMove(step); if(score>maxScore) { maxScore=score; } } return maxScore;} /** * * @brief : 获取人类下一步走法对电脑最不利的分数（可回调） * * @param : 无 * * @return: 对电脑最不利的分数值 * **/int ChessArea::getMinScore(int level){ if(level == 0) return calcScore(); QVector<Step*> steps; bRedTurn = true; // 获取人类的所有走棋路径 getAllPossibleMove(steps); bRedTurn = false; int minScore = 100000; for(QVector<Step*>::iterator it=steps.begin();it!=steps.end();++it) { Step* step=*it; fakeMove(step); int score = getMaxScore(level-1); unfakeMove(step); if(score<minScore) { minScore=score; } } return minScore;} /** * * @brief :获取电脑最优移动路径 * * @param : 无 * * @return: 最优棋子信息的属性(原坐标、目标坐标、ID、目标ID) * **/Step *ChessArea::getBestMove(){ QVector<Step *> steps; // 获取电脑的所有走棋路径 getAllPossibleMove(steps); int maxScore = -100000; Step* ret; for(QVector<Step*>::iterator it=steps.begin(); it!=steps.end(); ++it) { Step* step= *it; fakeMove(step); int score = getMinScore(level-1); unfakeMove(step); if(score > maxScore) { maxScore = score; ret = step; } } return ret;}
下面看看电脑实现“走一步看三步”的下棋效果：
04 – 总结
注意Level值不要设置太大，回调深度越大消耗内存越严重，我电脑是4G内存，Level值设置为4，走棋就非常卡顿，后期基本卡死了，原因是后期棋子变少，活着的棋子行走的选择会越多，因此占用内存会越大，直到程序崩溃。
到目前为止，整个象棋的人工博弈算法算是讲完了，实际的效果不错，可以自己搭建电脑端玩一玩。
01_开发象棋游戏简介 02_绘画象棋棋盘 03_象棋棋子摆放 04_象棋走棋规则——車、炮、士 05_象棋走棋规则——象、马、将、兵 06_象棋游戏法则 07_人机博弈算法开端 08_人机博弈高阶算法