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

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

【相似文献】

中国期刊全文数据库

前20条

1

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

2

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

3

田翠华;宋兴亮;朱顺痣;孔丽新;;中国象棋计算机博弈算法研究[J];信息技术;2011年12期

5

汤云雄;董从民;;计算机博弈系统在中国象棋教学中的应用[J];科技信息;2011年19期

6

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

7

胡强;谢显中;张小川;;一个幻影围棋计算机博弈系统的设计与实现[J];数字通信;2014年01期

8

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

9

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

10

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

11

周玮;王友政;马庆增;;利用局势变化攫取优势博弈[J];系统仿真学报;2008年17期

12

周玮;王水涛;孙旸;;中国象棋计算机博弈中的一种数据结构方法[J];计算机工程与应用;2006年35期

13

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

14

黄晨;;棋类游戏中的先行权[J];智能系统学报;2007年03期

15

吴岳;;一种高性能西洋跳棋引擎设计[J];电脑编程技巧与维护;2014年02期

16

李汝光;;基于机器学习的围棋死活问题算法设计[J];常州工学院学报;2013年05期

17

周玮;张赜;周静怡;;基于对弈局势的二次估值方法[J];系统仿真学报;2006年09期

18

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

20

裴生雷;;王宫双门棋博弈系统中的关键问题研究[J];微计算机信息;2012年10期

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

前1条

1

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

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

前10条

1

侯鑫磊;并行计算在计算机博弈中的研究与应用[D];重庆理工大学;2015年

2

欧阳明;国际象棋游戏的学习软件的设计与实现[D];电子科技大学;2015年

3

罗文浩;五子棋对弈平台的设计与实现[D];西安电子科技大学;2015年

4

5

6

7

9

刘明慧;计算机博弈的估值方法研究[D];东北大学;2008年

10