基于 Python alpha-beta 剪枝技术的五子棋【100011489】

# 基于 alpha-beta 剪枝技术的五子棋 # 一、题目 基于 alpha-beta 剪枝技术的五子棋 # 二、问题描述 我们的五子棋博弈实现的是双人的、完备信息的五子棋问题，即游戏规则为双方严格的轮流走步，且任何一方能完全知道对方已走过的步和以后可以走的所有步，当某方有在一条直线上连续的五子时，游戏结束。游戏模式可以分为人机对弈和双人对弈两种模式。双人对弈模式比较容易实现，程序只需要判断是否产生胜利者即可。人机对弈模式则需要我们的程序代码实现机器落子的位置的选择确定，本程序采用基于启发式 MAX/MIN 算法的 alpha-beta 剪枝技术来选择出最佳的机器落子位置。除此之外，我们还设置了残局闯关模式，在增加了游戏趣味性的同时给用户们带来了更好的游戏体验。 # 三、问题分析 要想实现一个基本的五子棋博弈游戏，我们要面对的问题可大概总结为如何判断胜负，如何严格限制双方轮流下棋，游戏界面的呈现形式以及最主要的如何确定机器落子的最佳位置。经过我们团队的初步讨论后，最终决定游戏以界面的方式呈现出来，用户下棋时直接将鼠标点击在想落子的位置即可。至于判断胜负则只需要编写一个简单的函数，从横、竖、斜上、斜下四个方向逐步判断是否有五个连续的同色棋子就可实现判断。严格控制双方轮流落子通过改变 flag 的值间接确定当前位置是哪一方下棋，再通过相互调用对方落子的函数具体实现轮流下棋。 最后就是解决最关键的问题：在人机对弈模式中如何选择出机器落子的最佳位置，这是我们整个程序代码中最核心的部分，也是算法实现中最困难的部分。就像本次课程设计的题目叙述的那样，我们经讨论决定采用启发式 MAX/MIN 算法的 alpha-beta 剪枝技术来准确且较为快速地确定机器的落子位置，其中涉及到的 alpha-beta 技术的具体实现以及确定最佳位置时采用的“算分机制”会在之后的模块中详细阐述。 至此，我们就基本上完成了五子棋游戏的整体问题分析，剩下的就是一些界面优化，残局棋谱设计等非关键问题，我们的团队在不断的实践和优化中最终实现了一个功能完善，界面优美且操作流畅的五子棋博弈小游戏。 # # 四、算法概述 　　我们的系统分为人机对弈与人人对弈。黑子白子双方轮流落子，当某一方完成落子后调用判断胜负的函数盘算是否结束游戏。若游戏结束，跳出某方胜利的弹窗，点击确定清空棋盘。 对于人机对弈我们设计了 AI 算法—基于 MAXMIN 的 α-β 剪枝算法，它对 AI 的走步给出最好的决策。算法思想是：首先，判断当前的深度是否是为 0，如果为 0 则结束回溯到上一层；若不为 0，则利用估值函数计算当前棋盘的得分，若当前棋盘的得分大于等于 9999 且递归深度小于最大深度 maxdepth（设定的值为 3）时，表示该走步最佳，AI 可胜利并返回这个最佳分数；若不满足则产生新的走法，将所有所有的没有棋子的位置都初步列为 AI 可落子的位置，枚举所有的走法：假设 AI 落子在该位置时，进入 MIN 层，分析人类会走的步，深度减一，递归调用分析得出人类最不利于 AI 的走步时以及棋盘的得分，若当前的得分大于 alpha，则令 alpha 的值为当前得分数值并保存当前 AI 的走步（该走步可能为 AI 的最佳走步），当 alpha 大于等于 teba 时，进行剪枝。最后返回当前最好的分数 alpha 并返回当前最好分数的走法。 对于双人对弈，这个就必见随机，看人的心情下，比较随意，这部分我们只是简单实现刷新画布、判定胜负、放置棋子就行。我们是通过定位鼠标光标的位置以及绑定鼠标事件来确定当前落子的位置，我们设定右击鼠标可以在有效地范围内放置棋子。每放置一刻棋子时，调用 tkinter 的画布内置的 updata 函数进行画布更新。 # 五、极大极小树 目前绝大部分的博弈类游戏中的人工算法都采用这种方法。假设 AI 方为 MAX 点，我方则为 MIN 点。如果当层的节点为奇数时那么就为 MAX 层，同样为偶数时就为 MIN 层。当在 MAX 层时，该层的值就应该为下一个 MIN 层中的最大一个的值。当在 MIN 层是，该层的值就应该为它子层 MAX 的最小的一个。通俗的说就是当轮到我方时，我们就应该选择一个最有利于我们的点，预测对方可能下的最有利他方的点(相对我方来说就是最坏的点)。这样反复计算下去就能够得到根节点的最大值，这个点也就是我们最佳下棋点。在计算这个点时可以很明显的看出这是一个不断递归的过程，到达叶子节点时根据相关的计算规则算出该值然后向上一层不断的返回。下图中矩形代表极大层，椭圆代表极小层。  # 六、α-β 剪枝算法 算法描述：我们的程序主要是用 α-β 剪枝法实现的。其基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下: 对于一个与节点 MIN，若能估计出其倒推值的上确界 β，并且这个 β 值不大于 MIN 的父节点(一定是或节点)的估计倒推值的下确界 a，即 a≥β，则就不必再扩展该 MIN 节点的其余子节点了(因为这些节点的估值对 MIN 父节点的倒推值已无任何影响了)。 这一过程称为 a 剪枝。 对于一个或节点 MAX,若能估计出其倒推值的下确界 a，并且这个 a 值不小于 MAX 的父节点(- -定是与节点)的估计倒推值的上确界 β，即 a≥β，则就不必再扩展该 MAX 节点的其余子节点了(因为这些节点的估值对 MAX 父节点的倒推值已无任何影响了)。 这一过程称为 β 剪枝。  # 七、总体设计 ## 7.1 系统流程图  ## 7.2 基本设计 界面设计：基于 tkinter 设计的界面，包括游戏模式菜单、残局菜单，关于菜单三个部分组成，游戏模式菜单部分包括了人机对弈（AI 先手）、人机对弈（玩家先手）、双人对弈（白子先手）、双人对弈黑子先手）等多种模式，各种模式的随意切换，突出程序灵活的特性。残局菜单栏我们设计了五种残局，难易程度程度依次递增，增强了游戏的趣味性，这个五个残局我们在网上小程序找的棋局，难度还可以。‘关于’菜单栏部分我们设计的事宜子界面，里面就显示我们小组开发过程负责的各模块的信息。 棋盘设计： 我们的程序棋盘的显示部分是利用 tkinter 库的画布实现的，画布的背景设置为粉色，界面的美观性大大增强。在画布上画上 14*14 的小格子表示棋盘，交点处放棋子，所以棋盘的大小为 15*15。程序中的棋盘对应 15*15 的二维数组 chess_b，初始化为 0，黑子用 1 填充数组，白子用 2 填充数组。至于画棋子，我们是根据棋盘数组将对应的位置用贴图的方法将黑棋白棋贴上去。 胜负判断： 只需考虑横、竖、左斜和右斜�