搜索
1本科毕业论文(科研训练、毕业设计)题目：中国象棋博弈算法研究姓名：李文耀学院：软件学院系：软件工程专业：软件工程年级：2004级学号：04369083指导教师：史亮职称：副教授2008年6月5日2摘要计算机博弈是人工智能研究的一个重要分支，被专家门称为人工智能界的果蝇，意思是说人类对计算机博弈的研究衍生了大量的研究成果，这些成果在人工智能领域产生了重要影响。国际象棋计算机博弈研究已经有了五十多年的历史，IBM公司在1997年开发出了超级计算机“深蓝”战胜了当时世界国际象棋大师卡斯帕罗夫，标志其水平已达到国际象棋世界冠军水平。而中国象棋的历史更为悠久，虽然中国象棋计算机博弈研究起步晚于国际象棋，但起点高，国际象棋计算机博弈研究的成果为我们提供了很多的借鉴技术。近年来随着研究的不断深入，中国象棋计算机博弈越来越成为继国际象棋后计算机博弈研究的热点之一。本文在对目前主流的计算机博弈技术进行全面的综述后，对构成计算机博弈系统的四个组成部分进行了优化和改进，特别是针对静态估值算法不能应对局势变化的固有缺点，提出了动态局势再评估算法。在此之上实现了一个中国象棋计算机博弈系统，论文主要研究了以下3方面的问题：第一、对计算机博弈系统的四个组成部分及基础技术进行了研究，包括数据结构，着法生成，搜索算法，估值算法。第二、研究了建立在Alpha-Beta搜索算法基础之上的各种优化技术。主要讨论了窗口探测，静寂搜索，历史启发，深层迭代，NullMove5个方面的优化方法，并根据实验结果结合置换表技术提出了具体的组合方案。第三、论文针对目前广泛使用的静态估值算法不能应对局势变化的固有缺点，提出了动态局势再评估算法。通过引入“局势因子”，使得估值算法根据当前局面形势做出攻防策略。关键词：人工智能；中国象棋；博弈算法；动态局势再评估；局势因子3AbstractComputergameisanimportantbranchofartificialintelligenceresearch.Itisdescribedasafruitflyoftheartificialintelligencebyexperts.That’stosayhuman’sresearchtothecomputergamehasachievedmassiveresearchresults.Theseachievementshaveplayedanimportantinfluenceonamorewidespreaddomain.Througoverseasresearchers’explorationofchessgamblingsystemformorethan50years,IBMCorporationdevelopedsupercomputer”DarkBlue”in1997，andhasdefeatedworldchessmasterKsparov;whiletheChinesechesshistoryismoreglorious.TheresearchofChinesechesscomputergameislaterthantheresearchofchesscomputergame,butitbasedonthecomputergame’sresearchresults.Withthedeeperstudyofresearch,Chinesechesscomputergamebecomesoneofthemostactivepartsofcomputergameresearcharearecently.AftersummarizingrelatedresearchesonChinesechesscomputergame.Somekeyproblemsarestudiedanddiscussedinthisdissertation.Basedonabovework，anintegratedChinesechesscomputergamesystemaredesignedanddeveloped.Thewholeworkmainlyfocusesonthefollowingthreeaspects:1.IntroducethekeycomponentpartsofaChinesechesscomputergamesystemwhichinvolvedatestructure,generatelegalmoves,searchalgorithmsandevaluatealgorithms.2.MakeastudyontheoptimizationofsearchalgorithmbasedontheAlpha-BetaalgorithmwhichincludedPrincipalVariationSearch,quiescencesearch,historyheuristic,interativedeepening,null-movepruningandsoon.3.Thispaperprovidesanalgorithmcalled“dynamicsituationevaluatealgorithm”whichavoidsthedrawbackofstaticevaluate.Astheintroductionof“decisionfactor”,computercanmakedecisionsbysituation.Keywords:artificialintelligence;Chinesechess;gamealgorithm;dynamicsituationevaluatealgorithm;decisionfactor4目录第一章绪论......................................................................................................................................81.1选题背景和研究意义.............................................................................................................81.2中国象棋计算机博弈的发展历程.........................................................................................81.3国内外研究现状...................................................................................................................101.4本文的主要工作和论文结构................................................................................................11第二章背景知识............................................................................................................................132.1数据结构...............................................................................................................................132.1.1棋盘表示.....................................................................................................................132.1.2置换表.........................................................................................................................142.2着法生成...............................................................................................................................152.3搜索算法...............................................................................................................................162.3.1博弈树的基本概念.....................................................................................................162.3.2极大极小算法..............................................................................................................172.3.3负极大值法.................................................................................................................192.3.4Alpha-Beta搜索算法..................................................................................................202.4估值算法...............................................................................................................................222.5本章小结...............................................................................................................................23第三章搜索算法的优化................................................................................................................243.1窗口探测...............................................................................................................................243.1.1渴望搜索......................................................................................................................243.1.2极小窗口算法...................................................