六子棋计算机博弈及其系统的研究与优化

发布时间：2016-10-09 09:08

  本文关键词：六子棋计算机博弈及其系统的研究与实现，由笔耕文化传播整理发布。

《重庆大学》 2008年

六子棋计算机博弈及其系统的研究与优化

张颖  

【摘要】： 计算机博弈是人工智能领域一个极其重要且最具挑战性的研究方向之一,它的研究为人工智能带来了很多重要的方法和理论,产生了广泛的社会影响和学术影响以及大量的研究成果。计算机博弈是人工智能的一个果蝇,然而棋类游戏又是计算机博弈的一个标准性问题,各种搜索算法、模式识别及智能方法在计算机博弈中都可以得到广泛的应用。因此在过去的半个世纪里,世界各地的学者花费了大量的心血对于计算机博弈包括奥赛罗、checker、国际象棋、中国象棋、五子棋、围棋进行研究。涌现出大量令人震惊的成果,1997年“深蓝”战胜卡斯帕罗夫的比赛就在全世界范围内引发了震动。其他很多棋类的计算机水平都已达到了世界冠军的水平。 目前,对于像五子棋、中国象棋等棋类游戏的计算机博弈算法研究已相对成熟,六子棋作为一个刚刚兴起不久的棋类游戏,其计算机博弈算法的研究还相对较少。即使目前已经出现六子棋的论坛以及比赛的平台,真正对于六子棋计算机博弈算法以及系统的研究还不多。六子棋的发明者台湾吴毅成教授给出了六子棋的公平性问题以及基于迫著(Threats-based)的胜利策略,但是对于其计算机博弈问题没有给出更加深刻的阐述,同时也没有全面解决六子棋计算机博弈问题。本文正是对六子棋计算机博弈技术的进一步探索。 本文主要对本课题组前期实现的系统四个主要部分(搜索引擎、走法生成、评估函数和开局库)进行了完善和进一步的优化,同时对功能进行了扩展。走法生成模块中利用棋类的战场策略进行了搜索限制和棋型特征码的提取;搜索引擎模块加入策略启发式信息进行优化,使其更“智能”;评估函数模块中,由于特征码的引入使得采用遗传算法进行优化具有实际可行性;开局库存储了大量的专家棋谱,可以避免在开局时由于搜索深度的不足而带来战略上的失误,同时大大提高了对战的效率。 最后本文对六子棋计算机博弈系统进行了测试与评价,包括评估函数的准确度、搜索算法的效率以及系统的整体性能确实得到了显著的提升。

【关键词】：
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2008
【分类号】：TP18
【目录】：

摘要4-5

ABSTRACT5-9

1 绪论9-17

1.1 引言9

1.2 六子棋计算机博弈的研究意义9-11

1.3 六子棋计算机博弈在国内外的研究现状11-14

1.3.1 计算机博弈研究简史11-12

1.3.2 六子棋计算机博弈的研究现状12-14

1.4 六子棋计算机博弈的核心问题14-15

1.4.1 搜索算法14

1.4.2 评估函数14-15

1.5 六子棋计算机博弈系统的评价方法15

1.6 课题的提出和研究意义15-16

1.6.1 课题的提出15-16

1.6.2 研究的意义16

1.7 本文的主要研究内容16-17

2 六子棋平台介绍17-22

2.1 背景17

2.2 规则17

2.3 公平性问题17-19

2.3.1 五子棋的公平性问题18

2.3.2 公平的定义18-19

2.3.3 脱离战场19

2.3.4 六子棋的公平性问题19

2.4 复杂度19-20

2.5 六子棋定石和诘棋20

2.6 六子棋发展动向20-21

2.6.1 台湾六子棋协会20-21

2.6.2 六子棋学术活动21

2.7 本章小结21-22

3 棋类设计的通用方法和思想—计算机博弈22-37

3.1 计算机博弈的要点22

3.2 计算机博弈程序的组成22-36

3.2.1 人机界面22

3.2.2 棋盘和棋局表示－数据结构22-24

3.2.3 着法生成24-25

3.2.4 机器博弈、搜索技术25-32

3.2.5 评估函数32-36

3.3 本章小结36-37

4 六子棋计算机博弈系统的优化37-53

4.1 引言37

4.2 六子棋系统的实现结构模型37

4.3 棋局信息的数据表示37-44

4.3.1 棋盘状态表示37-39

4.3.2 棋子状态数组描述39-40

4.3.3 六子棋棋型及其数字化描述40-41

4.3.4 前期棋型数组表示的错误41-42

4.3.5 改进的棋型表示方法－特征码表示42-44

4.4 六子棋计算机博弈问题描述－博弈树44-45

4.5 优化的搜索算法－基于启发式信息的搜索45-51

4.5.1 α-β剪枝搜索算法的实现45-48

4.5.2 优化的α-β剪枝搜索算法－启发式搜索48-51

4.6 本章小结51-53

5 评估函数优化及遗传算法优化评估值53-58

5.1 引言53

5.2 局面评估方法53

5.3 评估值和评估函数的改进53-54

5.4 遗传算法的实际操作54-56

5.4.1 奠定应用遗传算法的基础54-55

5.4.2 遗传算法优化棋型评估值的操作过程和方法55

5.4.3 改进的遗传算法55-56

5.5 实际操作结果对比分析56-57

5.6 本章小结57-58

6 系统功能的完善58-62

6.1 引言58

6.2 程序的完善58-61

6.2.1 悔棋的实现58-59

6.2.2 棋谱保存59-60

6.2.3 其他优化60-61

6.3 本章小结61-62

7 结论与展望62-66

7.1 结论、比赛结果及系统评价62-64

7.2 本系统目前存在的问题和不足64

7.3 后续工作64-65

7.4 结语65-66

致谢66-67

参考文献67-69

附录69-71

A 作者在攻读硕士学位期间发表论文目录69-71

下载全文 更多同类文献

CAJ全文下载

(如何获取全文？ 欢迎：购买知网充值卡、在线充值、在线咨询)

CAJViewer阅读器支持CAJ、PDF文件格式

【引证文献】

中国硕士学位论文全文数据库 前3条

1 闵文杰;六子棋计算机博弈关键技术研究[D];重庆交通大学;2010年

2 刘雅靖;基于Alpha-Beta搜索算法的计算机博弈的研究与实现[D];大连交通大学;2012年

3 曹森;对α-β剪枝算法的性能改进研究[D];内蒙古师范大学;2012年

【参考文献】

中国期刊全文数据库 前3条

1 王骄,王涛,罗艳红,徐心和;中国象棋计算机博弈系统评估函数的自适应遗传算法实现[J];东北大学学报;2005年10期

2 李果;;基于遗传算法的六子棋博弈评估函数参数优化[J];西南大学学报(自然科学版);2007年11期

3 徐心和;王骄;;中国象棋计算机博弈关键技术分析[J];小型微型计算机系统;2006年06期

【共引文献】

中国期刊全文数据库 前10条

1 官庆;工程设计保险的逆向选择问题研究[J];四川建筑科学研究;2003年02期

2 项勇,陶学明;基于寻租理论的工程监理博弈行为分析[J];四川建筑科学研究;2005年01期

3 杨岑;彭盈;陈玉水;;招投标中的博弈分析[J];四川建筑科学研究;2006年05期

4 项勇;任宏;;建设工程项目监理过程中寻租博弈行为分析[J];四川建筑科学研究;2006年06期

5 项勇;陶学明;王永强;;不对称信息下建设项目委托代理激励机制理论分析[J];四川建筑科学研究;2009年02期

6 杨太华;郑庆华;;建设工程中质检站、监理机构和承包商寻租行为的博弈分析[J];四川建筑科学研究;2009年05期

7 阳霞;周文峰;;代建项目双层委托代理模型分析[J];四川建筑科学研究;2010年03期

8 赵盈盈;申玲;;既有建筑节能改造进程中群体间的演化博弈分析[J];四川建筑科学研究;2012年03期

9 宁立志;曹亚玲;;从经济法视角看社会团体的法主体地位[J];安徽大学法律评论;2004年02期

10 万可,汤卫君;头垄断厂家产品定价中的博弈论问题———兼评我国彩电行业价格大战[J];安徽大学学报;2002年01期

中国重要会议论文全文数据库 前10条

1 黎秀蓉;;“李约瑟之谜”的博弈论解读[A];第十一届中国制度经济学年会论文汇编（上）[C];2011年

2 李五四;;不同信息环境下价格功能的历史考察——兼论营销·博弈价格功能下的经济政策效应[A];中国道路：理论与实践——第三届北京中青年社科理论人才“百人工程”学者论坛（2009）论文集[C];2009年

3 李春;;城市社区公共服务多元协作组织研究[A];科学发展：社会管理与社会和谐——2011学术前沿论丛（下）[C];2011年

4 李亚敏;;信息不对称与保险公司竞合研究——一个基于合作博弈理论的新视阈[A];深化改革，，稳中求进：保险与社会保障的视角——北大赛瑟（CCISSR）论坛文集·2012[C];2012年

5 翁禾倩;黄源泉;李宇星;林心颖;;“绿色信贷”实施中制度缺陷的多维博弈分析[A];2011中国环境科学学会学术年会论文集（第三卷）[C];2011年

6 刘效民;韦秀远;;垦区城乡一体化跨越发展的理论研究[A];黑龙江垦区现代化大农业建设理论研讨会论文专辑上册[C];2009年

7 赵礼强;郭亚军;;制造商分销渠道战略选择的博弈分析[A];第二十六届中国控制会议论文集[C];2007年

8 冯闻捷;彭力;;牛角棋计算机博弈系统的实现[A];第二十七届中国控制会议论文集[C];2008年

9 赵礼强;;多渠道冲突下制造商价格协调策略研究[A];中国自动化学会控制理论专业委员会D卷[C];2011年

10 王焱;;浅析公开招投标中不完全信息博弈[A];责任与使命——七省市第十一届建筑市场与招标投标联席会优秀论文集[C];2011年

中国博士学位论文全文数据库 前10条

1 江翔宇;公司型基金法律制度研究[D];华东政法大学;2010年

2 王荣;农业高新技术产业风险投资研究[D];山东农业大学;2010年

3 李平英;产业组织结构与农产品质量管理研究[D];山东农业大学;2010年

4 马晓丽;我国农产品市场信息不对称问题研究[D];山东农业大学;2010年

5 王荣;农业高新技术产业化风险投资研究[D];山东农业大学;2010年

6 刘家国;基于突发事件风险的供应链利益分配与行为决策研究[D];哈尔滨工程大学;2010年

7 杨皎平;产业集群特性要素对技术创新的影响研究[D];辽宁工程技术大学;2010年

8 刘嘉莹;第三方逆向物流系统构建及其运行优化研究[D];辽宁工程技术大学;2010年

9 陈飞;基于Agent船载危险品应急管理资源协同分配机制研究[D];大连海事大学;2010年

10 徐连章;新制度经济学视角下的我国海洋渔业资源可持续利用研究[D];中国海洋大学;2010年

中国硕士学位论文全文数据库 前10条

1 张雄;土地使用权征用法经济学分析[D];华中农业大学;2010年

2 张舒;基于博弈论视角的开发区土地集约利用研究[D];华中农业大学;2010年

3 林敏;社会医疗保险道德风险分析及其控制对策研究[D];南京医科大学;2010年

4 叶宗玲;改革开放以来中国小型私营企业诚信问题研究[D];河南理工大学;2010年

5 温新刚;基于双边道德风险规避的企业高管契约设计研究[D];山东科技大学;2010年

6 张娜;技术创新中寡头垄断企业竞争策略选择研究[D];山东科技大学;2010年

7 黄齐;量能课税原则与我国个人所得税法的完善[D];山东科技大学;2010年

8 刘园园;环境法律政策的执行机制研究[D];山东科技大学;2010年

9 贾学兰;信息不对称下的最优保险契约分析[D];山东科技大学;2010年

10 张晓庆;Fudenbery-Maskin无名氏定理与可行集的维数限制问题[D];辽宁师范大学;2010年

【同被引文献】

中国期刊全文数据库 前10条

1 李红;吴粉侠;刘小豫;;博弈树搜索算法研究[J];长春工程学院学报(自然科学版);2007年02期

2 王晓鹏;王骄;徐心和;郑新颖;;中国象棋与国际象棋比较分析[J];重庆工学院学报(自然科学版);2007年01期

3 徐长明;马宗民;徐心和;;一种新的连珠棋局面表示法及其在六子棋中的应用[J];东北大学学报(自然科学版);2009年04期

4 张振;顾治华;;机器博弈及其搜索算法的研究[J];电脑知识与技术;2008年24期

5 黄继平;张栋;苗华;;六子棋智能博弈系统的研究与实现[J];电脑知识与技术;2009年25期

6 王镌;博弈树搜索的算法改进[J];福建电脑;2004年02期

7 门洪华;博弈论与国际机制理论:方法论上的启示[J];国际观察;2000年03期

8 张聪品;刘春红;徐久成;;博弈树启发式搜索的α-β剪枝技术研究[J];计算机工程与应用;2008年16期

9 焦尚彬;刘丁;;博弈树置换表启发式算法研究[J];计算机工程与应用;2010年06期

10 张丽新;王家钦;赵雁南;杨泽红;;机器学习中的特征选择[J];计算机科学;2004年11期

中国博士学位论文全文数据库 前1条

1 岳鹏;计算机围棋中的算法研究[D];西南大学;2007年

中国硕士学位论文全文数据库 前10条

1 王璐;随机DBPSO-AO~*测试性分析算法研究[D];江西农业大学;2011年

2 莫建文;机器自学习博弈策略研究与实现[D];广西师范大学;2002年

3 谷蓉;计算机围棋博弈系统的若干问题研究[D];清华大学;2003年

4 王骐;博弈树搜索算法的研究及改进[D];浙江大学;2006年

5 万翼;计算机国际象棋博弈系统的研究与实现[D];西南交通大学;2006年

6 董红安;计算机五子棋博奕系统的研究与实现[D];山东师范大学;2005年

7 张赜;计算机中国象棋博弈中的二次估值方法及其优化的研究[D];东北大学;2006年

8 王一非;具有自学习功能的计算机象棋博弈系统的研究与实现[D];哈尔滨工程大学;2007年

9 娄跃荣;基于Agent的元搜索引擎研究[D];烟台大学;2007年

10 李果;六子棋计算机博弈及其系统的研究与实现[D];重庆大学;2007年

【二级引证文献】

中国期刊全文数据库 前1条

1 刘雅靖;;计算机博弈之六子棋的主要技术分析[J];电脑知识与技术;2011年10期

中国硕士学位论文全文数据库 前2条

1 刘雅靖;基于Alpha-Beta搜索算法的计算机博弈的研究与实现[D];大连交通大学;2012年

2 曹森;对α-β剪枝算法的性能改进研究[D];内蒙古师范大学;2012年

【相似文献】

中国期刊全文数据库 前10条

1 李之棠,陈华民;博弈树并行搜索算法[J];小型微型计算机系统;1998年10期

2 舒康元;胡福乔;;中国象棋计算机博弈引擎改进[J];微计算机信息;2009年29期

3 徐心和;;从计算机博弈到机器人足球——人工智能长期而持续的挑战[J];机器人技术与应用;2010年01期

4 张利群;;五道棋计算机博弈程序的设计与实现[J];计算机工程;2010年10期

5 魏钦刚;王骄;徐心和;南晓斐;;中国象棋计算机博弈开局库研究与设计[J];智能系统学报;2007年01期

6 张小川;陈恋昶;李祖枢;;引入意图的中国象棋计算机博弈系统[J];重庆理工大学学报(自然科学版);2010年10期

7 刘雅靖;;计算机博弈之六子棋的主要技术分析[J];电脑知识与技术;2011年10期

8 陆慧;夏正友;;四国军棋游戏中搜索算法的实验与分析[J];江南大学学报(自然科学版);2007年06期

9 张颖;;6子棋启发式搜索算法的优化与设计[J];西北师范大学学报(自然科学版);2008年04期

10 张颖;李祖枢;;棋类计算机博弈系统的主要研究方法及在6子棋上的应用[J];重庆工学院学报(自然科学版);2008年09期

中国硕士学位论文全文数据库 前10条

1 万翼;计算机国际象棋博弈系统的研究与实现[D];西南交通大学;2006年

2 谢艳茹;中国象棋计算机博弈数据结构与评估函数的研究和实现[D];西安理工大学;2008年

3 危春波;中国象棋博弈系统的研究与实现[D];昆明理工大学;2008年

4 谢国;中国象棋机器博弈数据结构设计与搜索算法研究[D];西安理工大学;2008年

5 王一非;具有自学习功能的计算机象棋博弈系统的研究与实现[D];哈尔滨工程大学;2007年

6 鹿荣;混合博弈树算法在中国象棋人机博弈中的应用研究[D];大连交通大学;2008年

7 李乃金;兵棋推演人机博弈决策模型的设计与实现[D];东北大学;2009年

8 高强;一种混合博弈树算法在中国象棋人机博弈中的应用研究[D];大连交通大学;2007年

9 田嘉俊;基于机器学习的人机博弈的研究与实现[D];东华大学;2007年

10 毕津滔;中国象棋对弈机器人控制系统研究[D];哈尔滨理工大学;2009年

  本文关键词：六子棋计算机博弈及其系统的研究与实现，由笔耕文化传播整理发布。

本文编号：134561