基于极大极小搜索算法的余一棋问题研究

《基于极大极小搜索算法的余一棋问题研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于极大极小搜索算法的余一棋问题研究摘要：计算机博弈是人工智能的一个传统研究领域。计算机博弈为人工智能提供一个实验平台，将人工智能的一些理论与方法应用于计算机博弈，可通过博弈水平的高低来建检验这些理论与方法的有效性，研究计算机博弈所得到的成果也可推广至人工智能的其他领域。二者相辅相成，相互促进。本文对余一棋博弈树搜索算法以及博弈系统进行研究，介绍了余一棋计算机博弈的关键技术，分析了估价函数在系统中所起的作用。深入研究博弈树的特性以及基于α-β剪枝的博弈树搜索算法。关键字：计算机博弈；搜索算法；估价函数MinimaxSearchAlgorithm-based

2、ResearchonGrundyGameAbstract：Computergameisatraditionalresearchingfieldofartificialintelligence(AI).ItprovideatestplatformforAI.ApplysometheoriesandmethodsofAIincomputergame,wecanprovethevalidityofthosebymeansoftestingthelevelofgamesystem.Inturn,thefruitsobtainedthroughresearching

3、thecomputergameareusedintheotherrealmsofAI.So,theysupplementandpromoteeachother.Inthisthesis,grundygametreesearchalgorithmandgamesystemsisresearched,introducesthekeytechnologyaboutgrundygame,analysistheeffectiveofevaluationfunctionanddatastructuredesign.In-depthstudythecharacteris

4、ticsofthegametree,andα-βpruningbasedonthegametreesearchalgorithm.KeyWords:computergame;searchalgorithm;evaluatefunction1绪论1.1研究背景人工智能是近年来很活跃的研究领域之一，是一门正在迅速发展的新兴的综合性很强的科学。它与生物工程、空间技术一起被并列为二十一世纪三大尖端技术。它的中心任务是研究如何让计算机去做那些过去只能靠人的智力才能做的工作。机器博弈是人工智能研究的一个重要分支[1]。让计算机学会下棋打牌，尤其和人类的精英对决，这是机

5、器博弈领域长期的奋斗目标，也是人工智能学科极富挑战性的研究课题[2]。早在上世纪五十年代，就有人设想到用机器智能来实现机器与人的对弈。国内外许多知名学者和知名科研机构都曾经涉足这方面的研究，经历半个多世纪，到目前为止已经取得了许多惊人的成就。1997年IBM的“深蓝”战胜了国际象棋世界冠军卡斯帕罗夫，更是惊动了世界[3]。机器博弈的研究发展为人工智能带来了很多重要的方法和理论，同时也产生了广泛的社会影响和学术影响以及大量的研究成果。本文运用机器博弈系统的关键技术研究做成了余一棋机器博弈的系统。通过对余一棋机器博弈及其系统的研究与实现，建立一个余一棋的人机对

6、弈的平台。具体关于余一棋的介绍见第三章。1.2国内外研究现状人机器博弈通俗来说就是让机器下棋，之所以称之为“博弈”，是因为其中渗透着博弈论的思想。机器博弈是一种动态的博弈，是现代智能化研究水平的集中体现[4]。近代机器博弈的研究是从四十年代后期开始的，国际象棋是影响最大、研究时间最长、投入研究精力最多的博弈项目，成为机器博弈发展的主线。主要经历如下[5-11]：1950年，信息论的创始人C.Shannon教授提出了为计算机象棋博弈编写程序的方案，成为了机器博弈的创始人，并且发表了两篇相关于计算机博弈的奠基性文章。1951年，A.Turing设计了一个叫做T

7、urochamp的国际象棋程序，但这个程序还不能在已有的计算机上运行。1956年，LosAlamo实验室的研究小组编写出了一个真正能够在“MANIAC一号”巨型计算机上运行的程序（这个程序对棋盘、棋子、规则都进行了简化），它是计算机博弈发展的重要里程碑。1957年，Bernstein利用深度优先搜索算法，每层选七种走法展开对局树，搜索层数为四层，他的程序在IBM704机器上操作，能够在标准棋盘上下出合理的着法，是第一个完整的计算机国际象棋程序。1967年，MIT的Greenblatt等人在PDP-6机器上，利用软件工具开发的MacHacVI程序，参加麻省国

8、际象棋锦标赛，写下了计算机正式击败人脑的记录。从1970年起，AC