基于alpha-beta剪枝技术的五子棋
目录
第1章 问题描述 3
第2章 问题分析 3
第3章 算法设计 4
3.1 算法概述 4
3.2 极大极小树 4
3.3 α-β剪枝算法 5
3.3总体设计 6
3.3.1 系统流程图 7
3.3.2 基本设计 7
3.4 预处理 8
第4章 算法实现 11
4.1 估价函数 11
4.2 alpha-beta剪枝算法 15
4.2.1 算法流程图 15
4.2.2 代码实现 16
第5章 成果展示与性能分析 18
5.1 成果展示 18
5.2 性能分析 23
第6章 结论与心得体会 23
6.1 结论 23
6.2 实验心得 24
参考文献 28
第1章 问题描述
我们的五子棋博弈实现的是双人的、完备信息的五子棋问题，即游戏规则为双方严格的轮流走步，且任何一方能完全知道对方已走过的步和以后可以走的所有步，当某方有在一条直线上连续的五子时，游戏结束。游戏模式可以分为人机对弈和双人对弈两种模式。双人对弈模式比较容易实现，程序只需要判断是否产生胜利者即可。人机对弈模式则需要我们的程序代码实现机器落子的位置的选择确定，本程序采用基于启发式MAX/MIN算法的alpha-beta剪枝技术来选择出最佳的机器落子位置。除此之外，我们还设置了残局闯关模式，在增加了游戏趣味性的同时给用户们带来了更好的游戏体验。
第2章 问题分析
要想实现一个基本的五子棋博弈游戏，我们要面对的问题可大概总结为如何判断胜负，如何严格限制双方轮流下棋，游戏界面的呈现形式以及最主要的如何确定机器落子的最佳位置。经过我们团队的初步讨论后，最终决定游戏以界面的方式呈现出来，用户下棋时直接将鼠标点击在想落子的位置即可。至于判断胜负则只需要编写一个简单的函数，从横、竖、斜上、斜下四个方向逐步判断是否有五个连续的同色棋子就可实现判断。严格控制双方轮流落子通过改变flag的值间接确定当前位置是哪一方下棋，再通过相互调用对方落子的函数具体实现轮流下棋。
最后就是解决最关键的问题：在人机对弈模式中如何选择出机器落子的最佳位置，这是我们整个程序代码中最核心的部分，也是算法实现中最困难的部分。就像本次课程设计的题目叙述的那样，我们经讨论决定采用启发式MAX/MIN算法的alpha-beta剪枝技术来准确且较为快速地确定机器的落子位置，其中涉及到的alpha-beta技术的具体实现以及确定最佳位置时采用的“算分机制”会在之后的模块中详细阐述。
至此，我们就基本上完成了五子棋游戏的整体问题分析，剩下的就是一些界面优化，残局棋谱设计等非关键问题，我们的团队在不断的实践和优化中最终实现了一个功能完善，界面优美且操作流畅的五子棋博弈小游戏。
