ckj blog

基于 EasyX 的五子棋程序。

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

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

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

运行效果如下：

完整源代码如下：

////////////////////////////////////////////////////////
// 程序名称：博弈五子棋
// 编译环境：Visual C++ 2019		EasyX_2020-3-15(beta)
// 作　　者：陈可佳 &l

基于 EasyX 的五子棋软件。

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

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

运行效果如下：

完整源代码如下：

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