陈可佳

我还是小学生,不足之处请大家指点

博弈五子棋(人机对战)算法改进

基于 EasyX 的五子棋程序。

界面依旧,唯一不同的是算法。改进前的 AI 眼光短浅,只顾当前局面。改进后的 AI 使用 DFS(深度优先搜索)进行对博弈树的遍历,再挑选分值最大的根节点进行落子。具体的,就是先算出每个点的当前分值,再递归去寻找落子后对方分值,把这两个值相减,就可以得到这个位置真正的分值。

可是如果直接递归,时间复杂度很大,大约是 O((192)n)( n 为递归次数),于是就加入了两个剪枝(只查找周边有棋子的空位)(如果位置初始分值大于最大分值才递归)和层数限制(只考虑以后4步)。

改进后基本1秒就可以算出来。

运行效果如下:

完整源代码如下:

////////////////////////////////////////////////////////
// 程序名称:博弈五子棋
// 编译环境:Visual C++ 2019	...

博弈五子棋(人机对战)

基于 EasyX 的五子棋软件。

算法部分想了很久,也参考了网上的其他游戏的。原理主要就是:遍历每个空闲的点,根据下在那个点后连成的棋形来判断其分值,再选出分值最高的位置并返回给游戏函数。

还在上小学,更深层次的判定算法还没学,就先将就一下吧。

运行效果如下:

完整源代码如下:

////////////////////////////////////////////////////////
// 程序名称:博弈五子棋
// 编译环境:Visual C++ 2019		EasyX_20190529(beta)
// 作  者:陈可佳 <emil09_chen@126.com>
// 最后修改:2019-9-30
//
#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <gra...