陈可佳

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

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

基于 EasyX 的五子棋程序。

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

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

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

运行效果如下:

完整源代码如下:

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