爱恩斯坦棋计算机博弈系统的研究与实现

发布时间：2017-06-16 10:11

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

【摘要】：计算机博弈,也称机器博弈,是一个极具挑战与发展前景的计算机研究领域,其作为人工智能领域一个极其重要的课题,素有人工智能领域“果蝇”之称。而对于棋类游戏的研究又是计算机博弈研究过程中的一个标准且极为重要的问题。现有的很多重要理论和技术方法诸如各类搜索算法及智能方法,最初的提出都是为了解决存在于棋类博弈中的某些问题。对于计算机博弈的研究最早可以追溯到半个世纪之前,在过去的五六十年里,人工智能的学者们呕心沥血的研究了计算机博弈中的包括奥赛罗、国际象棋、跳棋、五子棋、围棋等等,取得了大量傲人的成果。97年IBM的“深蓝”战胜棋王卡斯帕罗夫更是引起了世人的瞩目与震动,让世人第一次意识到冰冷的机器在棋类博弈上的智能超越了人类；而在不久之前,人机围棋大战巅峰对决——谷歌围棋人工智能AlphaGo VS人类顶尖棋手李世石刚刚落幕,AlphaGo以4：1击败李世石,从某种层面上来说机器的智能已经远远超过了人类。相比于国外,国内对于此方面的研究起步较晚,但是随着这几年的国内各种博弈比赛的开展,吸引了越来越多的学生与学者参与博弈的研究,国内的计算机博弈研究迎来了黄金期,极大的促进了国内计算机博弈研究的发展。传统的机器博弈模型多是完全信息博弈,即在对弈过程中完全了解其他对手的状态特征、策略和得益方式,现有的机器博弈研究大多以此类为研究载体,如五子棋、象棋等等。此种棋类的数据结构和局面状态描述设计依赖于准确的状态策略信息,搜索引擎也有现成的模板可供参考。本文的研究对象爱恩斯坦棋博弈属于不完全信息博弈,对博弈过程中的信息了解不完全,在进行数据结构和局面状态描述设计之前,需要先对其他对手的状态特征等信息进行一个估计,让博弈信息“伪完全化”,然后再进行相关设计,同样,需要对传统的博弈搜索算法进行修改,使其适应于不完全信息博弈。本文以爱恩斯坦棋博弈平台为研究载体,研究了计算机博弈关键技术,包括基本概念、研究对象分析和搜索引擎,设计了爱恩斯坦棋机器博弈系统。在棋盘数据结构设计过程中,对对手的状态信息等进行了预判和估计量化,使其信息完全化,从攻击和防守两个方向同时评估,得到了攻防兼备的估值函数；同时,还研究了估值函数的参数优化方法,保证估值函数设计的准确性和合理性；在搜索算法方面,基于传统的完全信息博弈算法——极大极小算法,参考期望搜索算法,在极大层与极小层之间人为加入一层骰子层,并将上述估值函数应用到算法中同时加入置换表优化技术,设计了适应于爱恩斯坦棋的攻防兼备的期望算法,解决了使用传统博弈算法无法构建博弈树的问题,提高博弈水平。从搜索效率和博弈水平两个角度攻防兼备的期望算法,虽然在搜索效率有所下降,但是在博弈水平方面却有较好的突破,博弈水平明显提高证明了应用了攻防兼备的估值函数的期望算法在一定深度范围内博弈水平和博弈效率取得了较好的平衡,既具有较高的博弈水平,又充分利用了博弈时间。同时,加入置换表优化方法之后,搜索效率与博弈水平都有一定的提升,本文的创新点如下：(1)研究并设计了适用爱恩斯坦棋的不完全信息博弈的数据结构,深入研究估值函数的构成,针对传统的估值函数存在的估值片面不准确的问题,从攻击防守两个方向同时考虑并结合爱恩斯坦棋的两种赢棋方式,设计了准确且效率较好的攻防兼备的估值函数；同时分析研究了一些应用于估值参数优化的方法和策略。在设计估值函数时,使用了攻击因子和威胁度因子来调整着法路径,有效的提高了博弈水平。(2)具体上采用爬山法结合手工调整对攻防兼备的估值进行参数优化,将优化之后的估值应用到算法中去,极大的提高了博弈水平。(3)基于传统的极大极小博弈算法,参考期望搜索算法,改进并设计了适用于爱恩斯坦棋的攻防兼备的期望算法,在原有的极大极小层中加入一层骰子层,来模拟投骰子的过程,解决了博弈过程中信息不完全的问题,并将(1)中的估值函数应用到算法中,加入置换表来优化算法,降低搜索过程中的节点数量,提高了搜索算法的效率。上述方法均在爱恩斯坦棋博弈系统“行云流水”与“流刃若火”程序中成功应用,其中“行云流水”在2014年“成理杯”全国大学生计算机博弈大赛爱恩斯坦棋项目荣获季军(一等奖),实践上证明本文提出的估值方法及搜索算法具有可操作性与实际应用价值。
【关键词】：计算机博弈 爱恩斯坦棋 估值函数 攻防兼备 期望算法
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要3-5
• Abstract5-11
• 第一章 绪论11-18
• 1.1 研究背景11-13
• 1.1.1 人工智能11-12
• 1.1.2 计算机博弈12-13
• 1.2 研究现状13-15
• 1.3 研究意义15-16
• 1.4 本文研究工作16-18
• 1.4.1 具体研究内容16
• 1.4.2 本文组织结构16-18
• 第二章 计算机博弈相关技术18-28
• 2.1 基本概念及技术19-24
• 2.1.1 博弈树19-20
• 2.1.2 搜索树20-22
• 2.1.3 复杂度22-23
• 2.1.4 递归23-24
• 2.1.5 回溯24
• 2.2 研究对象及分析24-26
• 2.2.1 研究对象分类24-26
• 2.2.2 本文研究对象分析26
• 2.3 本章小结26-28
• 第三章 爱恩斯坦棋计算机博弈建模28-39
• 3.1 爱恩斯坦棋概述28-32
• 3.1.1 规则28-30
• 3.1.2 基本概念30-32
• 3.2 特征要素32-36
• 3.3 数学建模36-38
• 3.4 本章小结38-39
• 第四章 攻防兼备的估值函数39-55
• 4.1 数据结构40-41
• 4.2 攻防兼备的估值函数41-47
• 4.2.1 进攻值42-43
• 4.2.2 阻击值43-44
• 4.2.3 威胁值44-45
• 4.2.4 总体估值函数45-46
• 4.2.5 估值方法计算举例46-47
• 4.3 参数优化47-53
• 4.3.1 相关优化方法47-49
• 4.3.2 参数优化策略49-51
• 4.3.3 估值实验51-53
• 4.4 本章小结53-55
• 第五章 攻防兼备的期望搜索算法55-65
• 5.1 经典搜索算法简介56-59
• 5.1.1 极大极小算法56-58
• 5.1.2. 期望搜索算法58-59
• 5.2 攻防兼备的期望搜索算法59-61
• 5.3 实验分析61-64
• 5.3.1 实验环境设置61-62
• 5.3.2 搜索效率实验62-63
• 5.3.3 博弈水平实验63-64
• 5.4 本章小结64-65
• 第六章 爱恩斯坦棋计算机博弈系统65-70
• 6.1 系统设计65-67
• 6.1.1 系统总体结构设计65-66
• 6.1.2 系统流程图66-67
• 6.2 系统实现67-69
• 6.2.1 实现技术67-68
• 6.2.2 系统界面68-69
• 6.3 本章小结69-70
• 第七章 总结与展望70-73
• 7.1 本文的主要贡献与结论70-71
• 7.2 未来工作与展望71-73
• 参考文献73-77
• 致谢77-78
• 攻读硕士期间的学术与科研成果78

【参考文献】

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

1 李占宇;李淑琴;顾磊;史玉峰;周文敏;;爱恩斯坦棋算法设计与分析[J];信息技术与信息化;2014年01期

2 周文敏;李淑琴;;爱恩斯坦棋静态攻防策略的研究[J];电脑知识与技术;2014年05期

3 聂华;;基于四皇后问题的回溯法求解及算法实现[J];电子测试;2013年18期

4 眭俊华;刘慧娜;王建鑫;秦庆旺;;多核多线程技术综述[J];计算机应用;2013年S1期

5 宋金平;;递归程序编写方法探讨[J];科技通报;2013年04期

6 张明亮;吴俊;李凡长;;五子棋机器博弈系统评估函数的设计[J];计算机应用;2012年07期

7 吕艳辉;宫瑞敏;;计算机博弈中估值算法与博弈训练的研究[J];计算机工程;2012年11期

8 王骄;徐心和;;计算机博弈:人工智能的前沿领域——全国大学生计算机博弈大赛[J];计算机教育;2012年07期

9 徐长明;马宗民;徐心和;李新星;;面向机器博弈的即时差分学习研究[J];计算机科学;2010年08期

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

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

1 徐心和;王浩;孔凡禹;;事件对策理论及在棋类游戏中的应用[A];2007年中国智能自动化会议论文集[C];2007年

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

1 徐长明;基于连珠模式的六子棋机器博弈关键技术研究[D];东北大学;2010年

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

1 唐霜霜;点格棋机器博弈系统的研究与实现[D];安徽大学;2015年

2 李景棚;非完备信息博弈估值算法的研究[D];哈尔滨工业大学;2014年

3 王小龙;连珠模式棋类博弈的搜索优化[D];安徽大学;2014年

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

5 张柳;基于极大极小搜索算法的亚马逊棋博弈系统的研究[D];东北大学;2010年

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

7 郭秀丽;中国象棋计算机博弈中搜索算法的研究与改进[D];河北大学;2010年

8 贾春艳;中国象棋计算机博弈评估函数与开局库研究[D];西安理工大学;2009年

9 张颖;六子棋计算机博弈及其系统的研究与优化[D];重庆大学;2008年

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

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

本文编号：455127