# 基于αβ剪枝算法的五子棋
## 五子棋介绍
**简介**:
五子棋是世界智力运动会竞技项目之一,是一种两人对弈的纯策略型棋类游戏,是世界智力运动会竞技项目之一,通常双方分别使用黑白两色的棋子,下在棋盘直线与横线的交叉点上,先形成5子连线者获胜。
**五子棋规则**:
五子棋有多种规则,分为:原始规则、无禁类规则、有禁类规则;其中无禁类规则又有Standard Gomoku规则、Gomoku-Pro 规则、Swap规则、Swap2规则等。
本次五子棋采用原始规则:
行棋:黑子先行,一人轮流一著下于棋盘空点处。
胜负:先把五枚或以上己棋相连成任何横纵斜方向为胜。(长连仍算胜利)
![](https://www.writebug.com/myres/static/uploads/2022/7/3/490696602a9349415fe65de375f353d8.writebug)
棋盘示例图
## 引入
人工智能是一门综合性很强的边缘科学,它研究如何使计算机去做那些过去只能靠人的智力才能完成的工作。而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)=![](https://www.writebug.com/myres/static/uploads/2022/7/3/8f910ce69eb34afa850401b9caee0144.writebug)—![](https://www.writebug.com/myres/static/uploads/2022/7/3/1839cabe0a8a48da1146887927b25fe3.writebug)
棋形估值函数具体规则:
根据五子棋的特点和根据实际情况多次调整,本次采用的棋形估值如下:
```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,;其他的情形依据双方剩余棋子的数量及位置评定从负无穷到正无穷之间的具体分数。这样我们可以建立一棵固定深度的搜索树,其叶子节点不必是终了状态,只是固定深度的最深一层的节点,其值由上述函数评出;对于中间节点,如同前面提到的那样,甲方取子节点的最大值,乙方取子节点的最小值。
静态估值函数,用以取代固定深度的搜索。显然,我们无法拥有绝对精确的静态估值函数,否则,只要这个静态估值函数就可以解决所有的棋局了。估值函数给出的只是一个较粗略的评分,在此基础上进行的少量搜索的可靠性,理论上是不如前述的三种状态的博弈树的,但这种方法�
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
资源包含文件:课程论文word+演示PPT+项目源码及可执行exe文件 五子棋是世界智力运动会竞技项目之一,是一种两人对弈的纯策略型棋类游戏,是世界智力运动会竞技项目之一,通常双方分别使用黑白两色的棋子,下在棋盘直线与横线的交叉点上,先形成5子连线者获胜。 详细介绍参考:https://biyezuopin.blog.csdn.net/article/details/125588734
资源推荐
资源详情
资源评论
收起资源包目录
五子棋开发设计.zip (103个子文件)
Evaluate.cpp 4KB
Evaluate.cpp 3KB
Evaluate - 副本 (2).cpp 3KB
AI.cpp 3KB
Evaluate.cpp 3KB
Evaluate - 副本.cpp 3KB
display.cpp 3KB
display.cpp 3KB
AI.cpp 2KB
AI.cpp 2KB
display.cpp 2KB
main.cpp 2KB
main.cpp 1KB
main.cpp 1KB
C++实现的基于αβ剪枝算法五子棋设计.docx 217KB
ai.obj.enc 247KB
Gomoku.exe 194KB
Gomoku-Final-ai-black.exe 152KB
Gomoku-Final.exe 152KB
Gomuko-v1.0.exe 152KB
test.exe 45KB
Gomoku-Final.vcxproj.filters 2KB
Gomoku.vcxproj.filters 2KB
Gomuko-v1.0.vcxproj.filters 2KB
Gomoku.vcxproj.filters 2KB
Evaluate.h 1KB
Evaluate.h 875B
display.h 797B
display.h 784B
Evaluate.h 750B
Global.h 525B
Global.h 513B
AI.h 480B
AI.h 473B
Global.h 428B
display.h 411B
AI.h 378B
vc140.idb 1.07MB
vc140.idb 971KB
vc140.idb 947KB
Gomoku.ilk 1.03MB
Gomuko-v1.0.ilk 836KB
Gomoku-Final.ilk 836KB
test.ilk 412KB
Gomoku-Final.lastbuildstate 185B
Gomuko-v1.0.lastbuildstate 179B
Gomoku.lastbuildstate 178B
LICENSE 1KB
Gomoku-Final.log 2KB
Gomuko-v1.0.log 2KB
Gomoku.log 2KB
README.md 12KB
AI.obj 388KB
AI.obj 232KB
AI.obj 223KB
main.obj 61KB
main.obj 40KB
Evaluate.obj 35KB
main.obj 30KB
display.obj 29KB
display.obj 29KB
display.obj 25KB
Evaluate.obj 25KB
Evaluate.obj 25KB
Gomoku.pdb 1.64MB
Gomuko-v1.0.pdb 1.56MB
Gomoku-Final.pdb 1.45MB
test.pdb 916KB
vc140.pdb 540KB
vc140.pdb 532KB
vc140.pdb 284KB
GomokuFowChart.pdf 35KB
演示PPT.pptx 410KB
Gomoku.sdf 35.69MB
Gomoku-Final.sdf 34.38MB
Gomoku.sln 2KB
Gomoku-Final.sln 1KB
.suo 61KB
.suo 46KB
CL.read.1.tlog 170KB
CL.read.1.tlog 88KB
CL.read.1.tlog 77KB
CL.write.1.tlog 10KB
link.read.1.tlog 8KB
CL.write.1.tlog 7KB
CL.command.1.tlog 5KB
CL.command.1.tlog 5KB
link.read.1.tlog 4KB
link.read.1.tlog 4KB
CL.write.1.tlog 4KB
link.command.1.tlog 4KB
link.command.1.tlog 3KB
CL.command.1.tlog 2KB
link.write.1.tlog 2KB
link.command.1.tlog 2KB
link.write.1.tlog 1KB
link.write.1.tlog 958B
search.txt 3KB
search.txt 0B
Gomuko-v1.0.vcxproj 6KB
共 103 条
- 1
- 2
shejizuopin
- 粉丝: 9189
- 资源: 1288
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
- 3
前往页