人工智能课程五子棋博弈问题.zip

# 人工智能课程五子棋博弈问题 ## 实验概述 ### 实验目的 熟悉和掌握博弈树的启发式搜索过程、α-β 剪枝算法和评价函数，并利用 α-β 剪枝算法开发一个五子棋人机博弈游戏。 ### 实验内容 以五子棋人机博弈问题为例，实现 α-β 剪枝算法的求解程序（编程语言不限），要求设计适合五子棋博弈的评估函数。 要求初始界面显示 15*15 的空白棋盘，电脑执白棋，人执黑棋，界面置有重新开始、悔棋等操作。 设计五子棋程序的数据结构，具有评估棋势、选择落子、判断胜负等功能。 ## 实验方案设计 ### 总体设计思路与总体架构 用一个二维数组存储棋盘状态，空白、黑子、白子分别用 0、1、2 表示， 通过 Alpha– Beta 搜索算法 alphaBeta 得出下一步落子位置，运用评估函数 evaluate 对玩家当前局面进行打分，分数越高对玩家越有利，对电脑每步的操作时间进行计时，并且每次落子进行胜负判断。  说明：若棋局 k 是棋局 x 的某个子节点，则 g(k)表示对当前旗面 k 应用估值函数得到的估值，f(x)表示对 x 的所有子节点应用最大最小原理后得到的值。 ### 核心算法及基本原理 Alpha-Beta 搜索算法：在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树。一般地只生成一定深度的博弈树，然后进行极小极大搜索。 极大极小搜索是指：在一棵博弈树中，当轮到甲走时，甲定会选择子节点值最大的走法；而轮到乙走时，乙则会选择子节点值最小的走法。 使用估值函数对博弈树的每一个局面进行估值后，就可以通过极大极小搜索在博弈树中寻找最佳的合法走法。 在极大极小搜索的过程中，存在着一定程度的数据冗余。如下图左半部所示的一棵极大极小树的片断。其中节点下方数字为该节点的值，方形框节点代表计算机走，圆形框节点代表人走。A 节点表示计算机走，由于 A 是极大值点，根据极小极大搜索原理它要从 B 和 C 当中选最大的值。假设目前已经通过估值得出 B 为 18，当搜索 C 节点时，因为 C 该人走，所以根据极小极大搜索原理要从 D、E、F 中 选取最小的值。此时如果估出 D 为 16，那么 C 的值必小于或等于 16。又因为已经得出 B 的值为 18，说明节点 A 的值为 Max（B，C）=18，也就是说无须求出节点 C 的其他子节点如 E、F 的值就可以得出父节点 A 的值。这种将节点 D 的后继兄弟节点剪去的方法称为 Alpha 剪枝。同理，在下图右半部一棵极大极小树的片段中，将节点 D 的后继兄弟节点剪去称为 Beta 剪枝。将 Alpha 剪枝和 Beta 剪枝加入极大极小搜索，就得到 Alpha-Beta 搜索算法。  ## 模块设计 ① 数据结构设计 以数组形式保存当前棋盘的盘面情况： ```c++ int chessBoard[GRID_NUM][GRID_NUM]//当前棋盘，数组的每一个元素对应棋盘上的一个交叉点，用“0”，“1”，“2”分别表示空白，黑子，白子。 ``` 使用元素类型为 pair 的栈存储每一步的落子位置，pair 的两个元素分别表示横纵坐标： ```c++ stack<pair<int, int>> steps;当需要悔棋时，栈顶的元素即为上次落子的位置。 ``` ② 功能说明 | 函数名 | 作用域 | 功能 | | ---------------------------------------------------------------------------- | -------- | ------------------------------------------------ | | bool makeMove(int x, int y, int player) | 全局函数 | 执行落子操作 | | bool unMakeMove(int x, int y) | 全局函数 | 撤销落子操作 | | bool regretMove() | 全局函数 | 撤销落子 | | void move() | 全局函数 | 读取指令，移动光标位置，进行悔棋或者重新开始操作 | | void print() | 全局函数 | 棋盘打印 | | pair<int,int>searchMove(int player) | 全局函数 | 搜索函数主体 | | int alphaBeta(int player, int alpha, int beta, int depth, int turn, int val) | 全局函数 | Alpha-Beta 搜索算法 | | bool gameover(int x, int y, int player) | 全局函数 | 判断游戏是否结束 | | bool checkHorizontal(int, int, int); | 全局函数 | 检查水平方向是否有 5 子相连 | | bool checkVertical(int, int, int); | 全局函数 | 检查垂直方向是否有 5 子相连 | | bool checkDiagonal(int, int, int); | 全局函数 | 检查斜线方向是否有 5 子相连 | | int evaluate_one(int x, int y, int me, int plyer) | 全局函数 | 估值算法 | | bool inBound(int x, int y) | 全局函数 | 判断与棋盘上现有点是否有联系 | | Int createMoves(int* moves_x, int* moves_y, int* values, int player) | 全局函数 | 生成全部合法走法集 | ### 创新内容 创新内容或优化点： 将各个功能模块（剪枝搜索模块，落子模块，评估函数模块等）利用不同的头文件和 cpp 文件区分开，便于区分管理，理清思路，有利于项目进展在 define.cpp 中限定待评估的空格的范围在当前棋盘所有棋子向外延伸距离为 2 的范围内，因为此范围之外的落子对局面分数不影响，从而缩小搜索范围。 先将所有评估了的空格的评估结果进行排序取前面一部分分值较大的进行剪枝搜索，提升了搜索效率 evaluate.cpp 评估函数模块中，一个重要的问题是方向问题，由于着眼对棋型的判断，所以首先要解决方向问题，考虑到常见棋型都是线性排列的，所以利用相对位置将二维坐标转换为一维坐标，类似极坐标的概念，一位坐标里只需要存储方向和相对位置即可，减小了难度。 引用的参考网址： ```c++ www.cnblogs.com/maxuewei2/x,y/4825520.html ``` 孙文丽利用 easyx 将李辉的控制窗口的棋盘效果进行了完善，用蓝色显示 AI 的最后一步棋。在正常的下棋过程中，这个功能不难实现。但是悔棋功能要显示上一回合 AI 的最后一步棋稍微复杂一些，需要利用堆栈实现。 ## 实验过程 ### 环境说明 操作系统：Windows；语言：C++; 开发环境：Dev-C++ 核心使用库：ctime，stdio.h,string.h,math.h,conio.h,iostream,algorithm,stack，graphics.h 源代码文件清单 头文件 createmoves.h, define.h, evaluate.h, makemove.h, searchmove.h, 源文件 createmoves.cpp, define.cpp, evaluate.cpp, gameover.cpp, main.cpp, makemove.cpp, printchessboard.cpp, searchmove.cpp 可执行文件