毕业设计-找毕设网--最真实的毕业设计交流论坛

 找回密码
 立即注册
查看: 1598|回复: 7

六子棋博弈研究与引擎实现(C++开发六子棋程序)内附毕业论文+毕业设计

[复制链接]

670

主题

1024

帖子

3318

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
3318

活跃会员

发表于 2015-11-10 23:21:32 | 显示全部楼层 |阅读模式
【摘要】

计算机博弈的研究已经为人工智能领域带来了很多重要的方法和理论,并且产生了广泛的社会影响,同时也应用于许多棋类游戏的研究和实现中。六子棋是最近几年才兴起并发展起来的棋类运动,它已经被越来越多的人所接受,但其计算机博弈的研究还相对较少。本文所设计的系统主要分为走法输入与输出、走法生成、搜索函数、评估函数等模块。本文以现有的计算机博弈理论为基础,并将α-β搜索算法应用于六子棋系统中采用C++开发六子棋程序。系统开发平台为visual studio2008,应用传统的MFC技术设计系统总体框架和相关功能。
【关键词】
计算机博弈;六子棋;搜索技术;棋局评估



2.2.3走法生成
走法生成方法一般有棋盘扫描、模板匹配法和预置表法,时常还结合使用。
①棋盘扫描法
在走法生成的过程中需要在棋盘上反复扫描有效区域、制约条件和落子状况,确定有哪些地方可以落子。
根据六子棋的规则,棋盘有效区域内的所有空白的交点都是可行落子点,一般不是距离前两子其中任一子为6格距离的范围。六子棋、五子棋、围棋一类的棋类设计中最常用,在走法的表达上,棋盘扫描法最为直观,但时间开销巨大。本系统即是使用这种方法。
②模板匹配法
以象棋为例,当动子即当前落子确定之后,其落址与提址的相对关系便被固定下来。于是可以为某些动子设计“模板”,只要匹配到提址,便可以迅速找到落址。比如走马这一步,当马对准提址,根据蹩马点的具体分布,很容易判断可能的落址。
然而在六子棋中,不存在提址问题,只有落子位置,而且所有当前无子的位置都是有效的走法,所以在六子棋中用模板匹配法并不实用。
③预置表法
预置表法是使用最为经常的着法生成方法。它的基本思想就是用空间换时间。为了节省博弈过程中的生成着法的扫描时间,将动子在棋盘任何位置(提址)、针对棋子的全部可能分布,事先给出可能的吃子走法和非吃子走法。当然,六子棋无吃子情况。当然这种方法对于特殊情况的走子,可以快速的生成应对措施,在六子棋中,开局的走法比较固定且应对措施也比较固定所以采用预置表法效率比较高,而且开局时的形势是最不明朗的时候,采用棋盘扫描法生成的可行走法就比较多,从中选出最优走法的花费比较大。采用预置表法就形成了开局库。
综上所述,本系统采用了棋盘扫描法和预置表法相结合的方法。
2.2.4机器博弈、搜索技术
①博弈树
任何棋类游戏都要定义一棵有根的树(即“博弈树”),一个节点就代表棋类的一个局面,子节点就是这个局面走一步可以到达的一个局面。
②搜索算法
搜索算法是博弈树求解的灵魂,只有有了有效的搜索算法才能在有限的时间内找到正确的解。搜索算法是求解此类图模型的基本方法。我们无法在有限的时间内搜索到最终的胜负状态,于是搜索的目标便成为如何在有限深度的博弈树中找到评估值最高而且变动最不大的最佳状态,于是从当前状态出发到达最佳状态的路径便称为最佳路径(Principal continuation),它代表着理智双方精彩对弈的系列着法。而最佳路径上的第一步棋便成为当前局面的最佳着法(The best move)。
需要注意的是博弈树不同于一般的搜索树,它是由对弈双方共同产生的一种“变性”搜索树。所以搜索到的最佳路径有两种,一种是有利于黑方的,一种是有利于白方的,对弈的过程就可表示成在不同深度的那层节点间寻找不利于对方且有利于己方的节点。
1)极大极小搜索
假设六子棋的两个玩家对弈,黑白方分别对应极大极小算法中的MAX方和MIN方。MAX先走,之后两人交替走步直到游戏结束。由于不可能对完整解图进行搜索,利用本文所定义的评估函数对当前局面进行估值,规定有利于MAX的估值很大,有利于MIN的估值则很小。下图为极大极小算法过程。




[ 此帖被nau308在2013-03-09 15:08重新编辑 ]



图片:


这是第一条纪录哦~
回复

使用道具 举报

670

主题

1024

帖子

3318

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
3318

活跃会员

 楼主| 发表于 2015-11-10 23:22:08 | 显示全部楼层
C++开发六子棋程序 很好哦~
这是第一条纪录哦~
回复 支持 反对

使用道具 举报

670

主题

1024

帖子

3318

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
3318

活跃会员

 楼主| 发表于 2015-11-10 23:22:14 | 显示全部楼层
C++开发六子棋程序可以下载~
这是第一条纪录哦~
回复 支持 反对

使用道具 举报

670

主题

1024

帖子

3318

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
3318

活跃会员

 楼主| 发表于 2015-11-10 23:22:21 | 显示全部楼层
非常好的源码~
这是第一条纪录哦~
回复 支持 反对

使用道具 举报

670

主题

1024

帖子

3318

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
3318

活跃会员

 楼主| 发表于 2015-11-10 23:22:27 | 显示全部楼层
赞~
这是第一条纪录哦~
回复

使用道具 举报

670

主题

1024

帖子

3318

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
3318

活跃会员

 楼主| 发表于 2015-11-10 23:22:38 | 显示全部楼层
很不错的代码
这是第一条纪录哦~
回复 支持 反对

使用道具 举报

670

主题

1024

帖子

3318

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
3318

活跃会员

 楼主| 发表于 2015-11-10 23:22:44 | 显示全部楼层
还可以啊
这是第一条纪录哦~
回复

使用道具 举报

0

主题

1

帖子

9

积分

新手上路

Rank: 1

积分
9
发表于 2016-6-1 11:13:34 | 显示全部楼层
admin 发表于 2015-11-10 23:22
C++开发六子棋程序 很好哦~

怎么下载代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|服务支持:DZ动力| 找毕设网

GMT+8, 2019-12-11 21:36 , Processed in 0.023530 second(s), 26 queries , Gzip On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表