【Qt象棋游戏】08_人机博弈高阶算法
2021/6/13 20:21:25
本文主要是介绍【Qt象棋游戏】08_人机博弈高阶算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 01 - 极大极小值算法
- 02 - 电脑和人类所有走棋路径
- 03 - 走一步看两步
- 04 - 走一步看多步
- 04 - 总结
01 - 极大极小值算法
上一期博客介绍了最为简单的人机博弈算法,包括获取所有合法路径,简单的估值以及电脑走棋,本期博客在介绍估值算法上增加极大极小值算法(Minmax算法),让电脑走棋更加智能化。
极大极小值算法是一种找出失败的最大可能性中的最小值的算法,即最小化对手的最大收益。举个栗子,电脑为A,人类为B,A在走棋之前需要考虑A走了某一步之后,看看B有哪些走法,B又不傻,所以B肯定是要选择让A得分最小的走法走棋,而A就是在A的所有走法中选择B给出让A得分最小的走法中得分最多的走法。听起来比较抽象,试着多读几遍就理解了。
电脑导入极大极小值算法分以下3步:
(1)在当前局面下获取电脑所有走棋路径,并试着走一下;
(2)在电脑试着走完一步基础上获取人类所有走棋路径,并以人类的视角试着走一下,然后评估局面分(局面分是以电脑角度计算的,即电脑总分 - 人类总分),遍历完人类所有走棋路径后返回这些局面中的最小值(对电脑最不利而对人类最优利的情况);
(3)在上一步返回的局面分的最小值中,找到最大值,并且锁定与该最大值对应的走棋路径作为“步”返回值返回。
02 - 电脑和人类所有走棋路径
实现算法第一步是要获取电脑和人类的所有走棋路径,所以对getAllPossibleMove函数稍微做出以下修改:
/** * * @brief : 获取所有棋子可行走的步骤 * * @param : steps : 保存移动棋子信息的属性(原坐标、目标坐标、ID、目标ID) * * @return: 无 * **/ void ChessArea::getAllPossibleMove(QVector<Step *> &steps) { int min = 16, max = 32; if(this->bRedTurn) { min = 0; max = 16; } //遍历所有黑方棋子 for(int i = min; i < max; i++) { //如果棋子已死则直接跳过 if(myChess[i].isDead) continue; // 遍历所有行坐标 for(int x=0; x<9; x++) { // 遍历所有列坐标 for(int y=0; y<10; y++) { //获取想要杀死的棋子的id int killid = this->getChessID(x, y); //若想要杀死的棋子与行走的棋子颜色相同则跳过 if(sameColor(i, killid)) continue; //判断某一棋子能不能行走 if(canMove(i, killid, x, y)) { //将可以行走的“步”存放到steps中 saveStep(i, killid, x, y, steps); } } } } }
03 - 走一步看两步
跟上一期博客相比,我们不再调用calcScore估值函数直接计算出对电脑最有利的分值而实施走棋,而是先代用getMinScore函数计算出对电脑最不利而对人类最优利的分值,并在局面分的最小值中,找到最大值,实现“走一步看两步”。
/** * * @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; }
/** * * @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_人机博弈高阶算法
这篇关于【Qt象棋游戏】08_人机博弈高阶算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)