一、实验室名称：
电子科技大学清水河校区基础实验大楼502
二、实验项目名称：
人机博弈五子棋AI
三、实验目的：
掌握极大极小搜索与剪枝算法，使用C和C++语言完成五子棋AI的开发，使AI可以通过博弈树的遍历，找到全局位置中的最优解。
四、实验主要内容： 完成极大极小搜索算法，剪枝算法，局面评估函数，EasyX中的游戏页面与鼠标操作，算杀，启发式搜索。
五、实验器材（设备、元器件）： 电脑：联想拯救者R700P 内存：最大支持容量32GB 内存频率3200 内存类型DDR4 处理器：处理器基准频率2.90 GHz 核心八核 处理器型号4800H 线程数16线程 处理器加速频率4.20 GHz 显卡：显存容量6GB 显存类型GDDR6 显存位宽192bit 软件平台：Visual Studio 六、实验步骤：
- 问题描述 在完成五子棋AI之前，我们希望可以通过C语言编程，做出可以对全局做出评估，即AI可以对全局未落子的点形成博弈树的进行遍历，模拟对战双发的落子，在第四层对整个局面进行评估，通过极大极小搜索算法将分数返回第一层，比较每一步的分数，选择对自己最优的位置落子. 2.算法分析与概要设计 （1）首先，先完成评估函数，即对整个棋局上的每一步棋进行分数评估并将每一个棋的分数相加（玩家所得分数为负，AI所得分数为正）最终得到这个棋局的分数。因此，我的评估函数对整个棋局15*15的位置遍历，当位置上有棋子的时候用评估函数打分。评估函数以这个棋子为核心对四个方向辐射，每个方向又有两个上下或左右两个小方向，先对其中的一个方向遍历，规定flag=1这个参数记录同种颜色棋子的个数和record=0这个参数记录异种颜色的棋子个数，对一个小方向延伸，遇到同种颜色的棋子flag+1；遇到不同颜色的棋子，record+1，跳出对这个小方向的延伸；遇到空位置，直接跳出对这个小方向的延伸。然后再对另一个小方向延伸，同上改变flag与record的值。然后凭借这个方向的flag与record的值打分。在对四个方向的棋子打分后得到这个棋子的总分，对整个棋局遍历之后得到整个局面的分数。经过模拟对局，我发现如果玩家和AI与使用同一个评估函数，AI会更偏向于进攻，于是我将分别给玩家和AI使用不同的评估函数，将AI的分数相较于玩家低一些，这样AI五子棋的防守会做的比较好。 （2）然后完成博弈树的建立，同时完成极大极小搜索算法。（我以map[15][15]作为棋局，若该位置为空，则map[i][j]=0；若该位置为AI落子，则map[i][j]=1；若该位置为玩家落子，则map[i][j]=2。）
我希望可以遍历四层，那么从第0层开始逐层向下遍历，到第四层对棋局中每一中可能的落子打分。为了保证棋局的每一个位置都没有被重复或者遗漏，我定义了一个三维的数组flag[depth][i][j]来记录每层棋盘的位置是否被考虑过了，若该位置已被考虑或者已有棋子flag[depth][i][j]=1否则flag[depth][i][j]=0。那么在遍历每一层的时候，先将棋局中已有的棋子的位置的flag变为1，再遍历棋局中未落子的每一个位置，考虑过后，将这个位置的flag改为1，再将棋子删除。将第四层的打分中返回第三层，再从第三层向下遍历到第四层，重复上述操作。由于第四层是玩家落子，那么假设玩家一定会选择分数最低的位置落子，第三层所模拟的位置的分数为返回分数的最小值，当flag[4][i][j]全部为1时，第三层不再向下遍历，此时将分数返回给第二层并删除模拟的棋子，并将flag[4][i][j]全部改为0。再从第二层向下遍历到第三层，重复上述步骤，由于第三层是AI落子，返回的值为最大值。依次类推，直到返回第一层，当第一层返回第零层的时候，第零层记录返回值中最大值的位置，当flag[1][i][j]全部为1时，记录的位置即为最优位置。最后，将flag[depth][i][j]全部变为0。AI选择在这个地方落子。即将该处的值变为1。 由于遍历四层运算量大，运算速度慢。难以在剪枝前验证算法是否正确，又由遍历的过程可得遍历两层与遍历四层的思路基本一样。我先只遍历一层，检测了评估函数的可实施性，五子棋AI已可进行人机对战；再改为遍历两层，AI仍然可以完成人机对战；再增加到三层，每一步需要2分钟左右，增加到四层，每一步需要30分钟以上，需要剪枝法来加快博弈树的遍历。 （3）剪枝算法 针对博弈树的遍历，可以使用AIpha-Beta剪枝对博弈树剪枝以及对AI落子位置的剪枝。 由于AIpha-Beta剪枝中的后一层的AIpha-Beta是由前一层的AIpha-Beta传递过去的，而后一层的返回值是根据返回层为max层还是min层来决定到底是改变AIpha还是Beta，若返回的一层为AI落子，那么改变Beta；若返回的一层为玩家落子，那么改变AIpha。由此，我将AIpha定义为sum2[depth]，将Beta定义为sum1[depth]，由以上规则传递，当sum2[depth]>=sum1[depth]时，则可以剪掉该层的其他子枝，不用再向下遍历，即将flag[depth+1][i][j]全部改为1。
当我完成AIpha-Beta剪枝后，发现它对博弈树的遍历速度提高并不多，在与AI下棋的多局中，我发现根据我的评估函数，没有在棋子的两步以外落子，那么我可以通过对遍历位置的剪枝来加快博弈树的遍历速度。 在每一次模拟落子之前，都对整个棋盘遍历，找到棋盘中最靠左上的棋子的位置，再找到最靠右下的棋子的位置，以这条对角线形成的长方形为需要考虑的位置，将其余位置的flag[depth][i][j]变为1。在博弈树的逐层遍历中，每遍历到新的下一层，就重复上述的过程，这样对博弈树剪枝，从而大大加快了遍历速度。这样，就算是遍历四层在棋局并不复杂的时候也可以在几秒中找到最优位置。但是当棋局变得复杂，形成的长方形越来越大，遍历速度变慢的十分明显。 于是我再次对其优化，本来打算使用启发式搜索，但是需要把每一个位置的分数从大到小排序并以这个顺序进行遍历，这样可以提高剪枝的效率，但是我没有想到一个高效的方法记录分数从大到小的位置，于是我借用这个搜索的思路对提高剪枝效率。如果我在四层遍历之后找到最优解，那么极大概率这一步在第一层获得的分数就比较高。那么，在遍历四层之前，我先只针对第一层打分，获得第一层全部分数的最大值和最小值，取其平均数，只针对平均值以上的打分的位置向下遍历，这样又可以加快速度，但是会有可能在最初的剪枝中将最优解的位置减去；另外，取最大值与最小值的平均数作为衡量标准，可能会出现最大值过大拉高平均数导致剪枝过多，减去最优解位置。 （4）EasyX的界面设计以及鼠标操作 通过与其他AI五子棋对战以及尝试，我发现如果AI后手，第二步会在斜方向落子；如果先手，显然会在中心位置落子。于是我在先手的第一步和后手的第二步不必使AI遍历博弈树，而是固定位置。 （5）算杀 由于自己的评估函数不能对冲棋做出评估，于是当玩家做出陷阱时，如一个连二加一个空位置加一个单子时，AI并不能将其作为一个冲棋，因此不会落子在那个空位置。于是我希望加入一层的算杀来封堵。当局面遇到上述的这种情况就直接对其算杀。有时候，对于一个连三，AI也未必会做出封堵的行为，于是遇到这种情况也对其算杀。 七、实验数据及结果分析： 1、根据最初的设定，AI会在斜上方落子（图中数据黑子为玩家，白子为AI）
2、以冲四的局对五子棋做一个陷阱，加入了一步算杀，AI会对其封堵，若不加入，AI不会封堵。
3、但是由于对冲棋的判断仅存在于杀棋中，而且只有一步，于是会出现下图的情况。这种四个单子形成的冲棋局，由于评估函数会将其当成四个连一，分数极低，AI不会将其作为威胁，于是会经营右边的局，但是当中心位置落子后便会形成两个冲四，即为杀局无解。AI不能应对这种情况。
八、总结及心得体会： 该AI五子棋基本满足了进行人机对战的要求，通过极大极小搜索算法和剪枝算法完成了遍历四层的任务，并用EasyX完成了五子棋盘的页面，加入了鼠标操作优化了玩家的使用体验。但是还是有许多不足，在建立博弈树，使用极大极小搜索算法时，使用了许多全局变量。在评估函数中，没有考虑冲棋。由于没有对每一层使用启发式搜索，而只对第一层使用了类似于启发式搜索的剪枝，这种方法不像启发式搜索可以有固定的剪枝数量，不确定性很高，有剪掉最优解的可能；而且只对第一层使用对速度的提升并不大。由于对位置剪枝，当搜索四层的时候AI的落子速度会随着棋局的变大而越来越慢。最后我有加入了算杀，起初我希望在搜索的时候进行算杀，但是当它遍历四层后结果并不理想，于是我另写了算杀的函数，只对一层算杀，增加了代码的数量，虽然可以对稍微弥补了评估函数对没有考虑冲棋的漏洞。但是当玩家设置双重冲四的时候，由于只对一层算杀，所以没办法阻止。 这次AI五子棋的制作过程中，我体会到了与以前完成作业完全不一样的感觉。对于A班末尾，在完成大实验前的作业时，我就需要查找资料，甚至研究源代码以及视屏教程才可以完成。但是AI五子棋网上只提供了算法思路，代码大多数都是C++等编程语言，但我只会用C语言，于是我花了两个星期研究算法以及如何实现。当一步步地完成五子棋后，我感觉如果想要真正理解算法与代码，还是需要自己独立完成。 九、对本实验过程及方法、手段的改进建议及展望： 希望可以减少全局变量的使用，在评估函数中加入对冲棋的考虑，使用启发式搜索，找到对全局各个位置打分排序的方法，对每一层都实现启发式搜索，尝试将算杀加入博弈树遍历的过程中，这样可以减少代码的数量。对更多层使用算杀。