五子棋开发设计.zip

# 基于αβ剪枝算法的五子棋 ## 五子棋介绍 **简介**： 五子棋是世界智力运动会竞技项目之一，是一种两人对弈的纯策略型棋类游戏，是世界智力运动会竞技项目之一，通常双方分别使用黑白两色的棋子，下在棋盘直线与横线的交叉点上，先形成5子连线者获胜。 **五子棋规则**： 五子棋有多种规则，分为：原始规则、无禁类规则、有禁类规则；其中无禁类规则又有Standard Gomoku规则、Gomoku-Pro 规则、Swap规则、Swap2规则等。 本次五子棋采用原始规则： 行棋：黑子先行，一人轮流一著下于棋盘空点处。 胜负：先把五枚或以上己棋相连成任何横纵斜方向为胜。（长连仍算胜利）  ​ 棋盘示例图 ## 引入 人工智能是一门综合性很强的边缘科学，它研究如何使计算机去做那些过去只能靠人的智力才能完成的工作。而agent博弈是人工智能的重要分支，在博弈问题中提高机器的智能水平，敌对搜索对这一问题的经典解决方法，而极大极小算法是敌对搜索中最为基础的算法，为了提高极大极小搜索的效率，在极大极小搜索算法的基础上使用Alpha-Beta剪枝所产生的Alpha-Beta搜索算法则是其中最重要的算法之一。 本次试验利用Alpha-Beta搜索算法实现人机博弈中的五子棋游戏，并在此基础上，利用局部搜索、优先值启发、限制深度等方法来提高Alpha-Beta搜索算法的效率。 # 二、实验目的和环境 ## 实验目的 熟悉人工智能系统中的问题求解过程； 学会利用对抗搜索解决博弈问题； 熟悉对抗搜索中的极大极小值算法，以及在此基础上的Alpha-Beta搜索算法的应用； 熟悉对五子棋问题的建模、求解及编程语言的应用。 ## 实验环境 硬件环境： - 计算机型号：惠普Pavilion M4 - 内存：4.00GB - CPU：Intel Core i5 2.6GHz 软件环境： - 操作系统：Windows10版本 - IDE：Visual Studio 2015 社区版 - 图形库：EasyX - 实现语言：C++（C++11标准） # 三、算法和实现 ## 棋形介绍 ### 术语 - 〖阳线〗 直线，棋盘上可见的横纵直线。 - 〖交叉点〗 阳线垂直相交的点，简称“点”。 - 〖阴线〗 斜线，由交叉点构成的与阳线成45°夹角的隐形斜线。 - 〖落子〗 棋子直接落于棋盘的空白交叉点上。 - 〖轮走方〗 “行棋方”，有权利落子的黑方或白方。 - 〖着〗 在对局过程中，行棋方把棋子落在棋盘无子的点上，不论落子的手是否脱离棋子，均被视为一着。 - 〖回合〗 双方各走一着，称为一个回合。 - 〖开局〗 在对局开始阶段形成的布局。 - 〖连〗 同色棋子在一条阳线或阴线上相邻成一排。 ### 棋形 - 〖长连〗 五枚以上同色棋子在一条阳线或阴线上相邻成一排。 - 〖五连〗 只有五枚同色棋子在一条阳线或阴线上相邻成一排。 - 〖成五〗 含有五枚同色棋子所形成的连，包括五连和长连。 - 〖四〗 在一条阳线或阴线上连续相邻的5个点上只有四枚同色棋子的棋型。 - 〖活四〗 有两个点可以成五的四。 - 〖冲四〗 只有一个点可以成五的四。 - 〖死四〗 不能成五的四。 - 〖三〗 在一条阳线或阴线上连续相邻的5个点上只有三枚同色棋子的棋型。 - 〖活三〗 再走一着可以形成活四的三。 - 〖连活三〗 连的活三（同色棋子在一条阳线或阴线上相邻成一排的活三）。简称“连三”。 - 〖跳活三〗 中间隔有一个空点的活三。简称“跳三”。 - 〖眠三〗 再走一着可以形成冲四的三。 - 〖死三〗 不能成五的三。 - 〖二〗 在一条阳线或阴线上连续相邻的5个点上只有两枚同色棋子的棋型。 - 〖活二〗 再走一着可以形成活三的二。 - 〖连活二〗 连的活二（同色棋子在一条阳线或阴线上相邻成一排的活二）。简称“连二”。 - 〖跳活二〗 中间隔有一个空点的活二。简称“跳二”。 - 〖大跳活二〗中间隔有两个空点的活二。简称“大跳二”。 - 〖眠二〗 再走一着可以形成眠三的二。 - 〖死二〗 不能成五的二。 - 〖先手〗 对方必须应答的着法，相对于先手而言，冲四称为“绝对先手”。 - 〖三三〗 一子落下同时形成两个活三。也称“双三”。 - 〖四四〗 一子落下同时形成两个冲四。也称“双四”。 - 〖四三〗 一子落下同时形成一个冲四和一个活三。 ## 7.1 估值函数 五子棋是一种零和游戏，但是五子棋的搜索树有较多分支因子以及深度较大，限于有限的计算资源，实际中不可能从搜索树的根节点搜索到最终棋局的叶子节点状态，我们只能限定其搜索深度，然后对棋局状态进行评估。 进行棋局估分的具体方式是对棋盘上已经落子的每个棋子根据其在棋盘上的位置以及与周围棋子形成的棋形进行打分，整个棋局状态的估分由己方所有棋子估分和减去敌方棋子估分和，即F(state)=— 棋形估值函数具体规则： 根据五子棋的特点和根据实际情况多次调整，本次采用的棋形估值如下： ```python # define VALUE_MAX 10000000 //长连/成五 获胜 # define VALUE_L4 150000 //活四 # define VALUE_W4 7500 //冲四 # define VALUE_D4 20 //死四 # define VALUE_L3 7500 //活三 # define VALUE_W3 2000 //冲三 # define VALUE_D3 10 //死三 # define VALUE_L2 1000 //活二 # define VALUE_W2 200 //冲二 # define VALUE_D2 5 //死二 # define VALUE_L1 100 //活一 # define VALUE_W1 50 //冲一 # define VALUE_D1 0 //死一 ``` ## 算法 ### 博弈树 下棋双方在棋盘上下棋，把棋局状态作为节点，当一方任意下棋时，局面就会从一个状态转移到另一个状态。对于一个确定的局面状态，有很多种可行的走法，每一种走法都会使局面状态转移到一个不同的子状态，把子状态和生成它的父亲状态用一条边连接，然后向下递归，直到下棋结束，整个过程生成了一棵树，即为博弈树。 ### 极大极小值算法 在通常的局面中，我们往往想通过少量的搜索，为当前局面选择一步较好的走法，然而在五子棋的棋局中，一个局面的评估往往不像输、平、赢3种状态这么简单，在分不出输赢的局面中棋局也有优劣之分。也就是说，要用更细致的方法来刻画局面的优劣，而不是仅仅使用1，-1,0三个数字刻画3种终了局面。 用估值函数可以为每一个局面的优劣评分。例如甲胜为正无穷，乙胜为负无穷，和局为0,；其他的情形依据双方剩余棋子的数量及位置评定从负无穷到正无穷之间的具体分数。这样我们可以建立一棵固定深度的搜索树，其叶子节点不必是终了状态，只是固定深度的最深一层的节点，其值由上述函数评出；对于中间节点，如同前面提到的那样，甲方取子节点的最大值，乙方取子节点的最小值。 静态估值函数，用以取代固定深度的搜索。显然，我们无法拥有绝对精确的静态估值函数，否则，只要这个静态估值函数就可以解决所有的棋局了。估值函数给出的只是一个较粗略的评分，在此基础上进行的少量搜索的可靠性，理论上是不如前述的三种状态的博弈树的，但这种方法�