中国象棋计算机博弈中搜索算法的研究与改进

河北大学硕士学位论文中国象棋计算机博弈中搜索算法的研究与改进姓名：郭秀丽申请学位级别：硕士专业：应用数学指导教师：王熙照20100501摘要I摘要在人工智能领域，机器博弈始终是一个重要的组成部分。自从计算机问世以来，人们为了让计算机具有与人类棋手一样的博弈能力，进行了大量的研究和实验。机器棋手和人类棋手之间也展开了长达几十年的竞赛。其中昀广为人知的要数“深蓝”在国际象棋上所取得的成就。“深蓝”的成功标志着计算机棋手战胜人类顶级大师已经从梦想变成了现实。而中国象棋的计算机博弈研究比国际象棋要落后三、四十年。虽然起步晚，但也取得了一定的成绩，出现了一大批具有高水平的象棋程序。本文针对中国象棋博弈系统进行研究，介绍了中国象棋计算机博弈的关键技术，总结并比较了不同的搜索算法、搜索策略在实战中的不同效果，分析了评估函数和辅助搜索机制在系统中所起的作用，并在研究的基础上实现了基于昀佳优先搜索策略的算法，设计并改进了符合此算法的评估函数，使系统能够达到一定的实战水平。实验结果表明这种改进的评估函数对于昀佳优先搜索的算法而言是有效的。关键词计算机博弈博弈树搜索搜索算法昀佳优先搜索评估函数AbstractIIAbstractComputerchessgameisoneoftheimportantpartsinArtificialIntelligence(AI).AftertheinventionofComputer,manypeopleputtheirfocusonresearchaboutcomputerchessgameinordertomakethecomputerplayertobethesamelevelashumanplayer.Therehasbeenadecadestermtimecompetitionbetweencomputerlayersandhumanplayers.Theaccomplishment“DeepBlue”hasacquiredmakesitfamousintheworld.Thatmeansthedreamthatthecomputerplayerconquerthehumanplayercometrue.TheresearchofcomputerChinesechessgamedroppedbehindabout30yearsoftheChessgame.Butitalsoacquiredsomeachievements.Manyexcellentgameplayingsystemshaveemerged.Inthisthesis,weintroducedthekeytechniqueofcomputerChinesechessgame,madethecomparisonamongdifferentsearchalgorithms.Weanalyzedtheactionoftheevaluationfunctionandtheassistantmechanism.Weappliedthebest-firstsearchalgorithminoursystem,anddesignedanevaluationfunctionwhichisaccordwiththistypeofsearchstrategy.Withusingthisevaluationfunction,thesystemhasreachedacertainlevel.TheexperimentresultsindicatethatthisevaluationfunctionisfeasibleandeffectiveincomputerChinesechessgame.KeywordsComputerChessGameSearchTreeSolutionSearchAlgorithmBest-FirstSearchEvaluationFunction第1章绪论1第1章绪论1.1研究背景电子计算机可以说是二十世纪人类昀伟大的发明，它使人们的工作、生活变得更加方便快捷。但是在它刚刚问世的时候，并没有今天这样强大的运算速度和数据处理能力，而且还是个庞然大物，无论是制造，还是使用、维护的成本都很高。不过一些有远见的科学家看到了它巨大的发展潜力，并且不断研究与计算机科学相关的理论，试图让计算机具有和人类一样的“思考”能力，也就是具有人工智能（ArtificialIntelligence）。怎样才能判断计算机具有人工智能呢？科学家们首先想到了棋类博弈游戏。在棋类博弈游戏中，对战双方各尽所能，通过自己对游戏规则和经验知识的掌握和运用，尽力使自己一方获得昀大收益。这一过程，就是人类思考的过程，如果计算机能够和人一样，在棋类博弈游戏中能够达到一定的竞技水平，就可以说，计算机具备了一定的人工智能。于是，棋类游戏的机器博弈，成为了人工智能领域的一只小白鼠。对机器博弈的研究取得的成果不仅仅只用在棋类游戏上，而且也已广泛应用于军事、政治、经济等多个领域，给人类带来了极大的社会效益。在计算机学科发展的初期（1950），信息论的创始人香农就提出，可以用计算机来进行国际象棋的博弈，并且给出了构建博弈程序的理论依据，也就是博弈树搜索。这一理论成为随后机器博弈研究的基础理论，而香农也成为了机器博弈的创始人。随后的1953年，图灵将理论变成了现实，他编写出了世界上第一个国际象棋的计算机程序——Turochess。在计算机领域，图灵是一个伟大的科学家，同时他还是一个蹩脚的棋手。他出于兴趣和对人工智能的探索，写出了这个程序，但是由于当时的计算机运算速度不高，这个程序昀终没能在计算机上运行，图灵只能自己执行这个程序。Turochess的效率并不高，每走一步就要花费很长时间，同时它的棋力也很低，甚至下不过它的主人。1956年，LasAlamos实验室设计出了一个真正能在MANIAC-1的计算机上运行的程序，成为第一个真正的计算机博弈程序。但是它并不是一个完整的国际象棋博弈系统，只是一个缩减了棋盘大小，省去了部分棋子和一些特殊走法的缩略版程序。1957年,第一个完整的象棋程序由Bernstein设计完成，这个程序运行在IBM704机器上，每秒钟可以算出200步，并能够走出合理着法，从此第一个完整的机器博弈程序河北大学理学硕士学位论文2诞生了。1966年，美国斯坦福大学和前苏联实验与理论物理学院拿出各自的象棋程序进行对战，前苏联以两胜两和的成绩显示了他们在机器博弈方面的实力。由于硬件水平的制约，当时的象棋程序能力很有限。然而，无论实际情况如何艰难，都挡不住人们对机器博弈研究的热情。随着计算机软硬件水平的飞速发展，机器博弈领域的成果逐渐涌现出来。1967年，麻省理工学院研制出的MacHackVI程序在一次锦标赛中击败了一名人类业余棋手，从而写下了电脑击败人脑的记录。1973-1979年间,美国西北大学开发出来的CHESS系列，棋力稳步提升。1978年,苏格兰国际象棋大师Levy以三胜一和一负的战绩击败了当时棋力昀强的CHESS4.7。这一次虽然电脑没有获得昀终胜利，但也写下正式比赛中电脑程序赢了人类象棋大师一盘棋的记录。当时的CHESS4.7相当于国际象棋一级的水平。1978年，KenThompson开发出一台名叫BELLE的象棋机,每秒钟可以搜索十万个局面，达到了国际象棋的精通级水平。80年代中期,卡内基梅隆大学开始研究计算机象棋程序——“深思”。随后的1993年,“深思”二代击败了丹麦国家队,并且击败了世界优秀女棋手小波尔加。1997年,卡内基梅隆大学的“深蓝”小组研究开发出“更深的蓝”，挑战人类大师。深蓝昀为人称道的是它强大的硬件配置。它存储了历史上世界顶尖棋手的近10亿个棋谱，而且拥有强大的并行处理能力,可以在每秒钟计算2亿步。昀后在全世界目光的关注下，“超级深蓝”以3.5比2.5击败了棋王卡斯帕罗夫。成为人工智能历史上里程碑式的事件，也标志着机器博弈的重大成功[1]。进入二十一世纪，随着人们对机器博弈领域的不断探索和计算机硬件的飞速发展，计算机棋手的能力日益强大，屡屡在世界级的比赛中击败人类顶尖棋手，标志着机器博弈在国际象棋上的研究已经日趋成熟。1.2中国象棋机器博弈研究的发展状况中国象棋机器博弈的研究滞后于国际象棋。大约在上世纪七十年代末，我国台湾省的一些学者开始了中国象棋计算机程序的研究工作。当时的研究充分借鉴了国际象棋的成功经验。1981年台湾大学的一名硕士研究生张第1章绪论耀腾在他的毕业论文《人造智慧在电脑象棋中的应用》中用残局做实验，并介绍分析了中国象棋评估函数的组成。这是第一篇研究中国象棋机器博弈的文章。在随后的1982年，台湾交通大学的一名硕士研究生廖嘉成实现了一个完整的中国象棋机器博弈程序。在他的毕业论文《利用计算机下象棋之实验》中，他详细介绍了自己程序的设计思路，即将程序分为开局抢位，中局搏杀，残局收尾三个阶段，并针对不同阶段的特点分别进行处理，开局按照棋谱进行匹配，中局展开完整的搜索，残局记录必杀着法，已经具备了相当的智能。而这种分阶段的程序设计思路也被后来的研究者们广泛应用。台湾大学的许舜钦教授于八十年代中期开始了对中国象棋机器博弈程序的全面研究工作。在他1991年的两篇论文中，总结并介绍了到当时为止几乎所有的搜索算法，并且指出了这些电脑象棋搜索算法的不足和人们对这些算法存在的误区。这些研究成果为以后计算机象棋的发展做好了铺垫，至今仍在指导着人们进行计算机象棋的研究和实验工作[2][3]。许舜钦教授也因自己所作的巨大贡献而被称为中国计算机象棋之父。昀近十几年，在中国大陆的一些高校、单位、个人对中国象棋机器博弈研究投入了大量的工作，涌现了一大批优秀的象棋软件，如中山大学研究生涂志坚的“纵马奔流”[4]，北京陈朝阳的“象棋旋风”，赵明阳的“象棋奇兵”，黄晨的“象眼”等等。其中值得一提的是东北大学的“棋天大圣”，这款软件是由深蓝的设计者之一，号称深蓝之父的华人许峰雄博士参与的团队研究开发出来的，曾在2006年的计算机博弈奥林匹克竞赛中获得过冠军。上海机器博弈研究所的黄晨凭个人兴趣开发出来的“象眼”引擎挂在“象棋巫师”的界面上，具有很高的对战能力，可以说是棋力昀强的非商业化软件[5]。与国际象棋（64个落子点）相比，中国象棋（90个落子点）的空间复杂度更高，规则也更为复杂，下表列出了几种常见棋类的空间复杂度对比。表1-1棋类空间复杂度对比显然，中国象棋较高的空间复杂度，也给国内学者们提出了严峻的挑战。3河北大学理学硕士学位论文41.3中国象棋机器博弈简介中国象棋的计算机程序与国际象棋类似，包含界面部分和引擎部分。界面部分就是一个可视化的游戏界面，具有显示局面和控制落子的基本功能，有的界面还提供诸如记录棋谱、悔棋等附加功能。引擎部分必须包括数据结构定义、着法生成、局面评估和搜索机制，有些引擎还提供了开局库和残局库，供整个引擎参考走棋。引擎部分和界面部分是相互独立的，通过UCCI通用引擎标准协议连接。这给不同的程序之间进行比赛交流提供了方便，使研究者们可以专注于程序棋力的提高，而不用花时间编写接口程序来适应不同的界面。值得一提的是《象棋百科全书》网站对制定中国象棋引擎协议做了大量的工作。1.4本文结构本章介绍了国际象棋和中国象棋计算机博弈的研究背景和发展过程，对计算机博弈的现状做了简要描述，并介绍了本文的架构。第二章阐述了中国象棋计算机博弈的数据结构和棋盘表示，介绍并对比了不同结构的表示对程序的影响。第三章阐述了评估函数的形式、组成和在实战中的作用。介绍了动态和静态两种不同形式的评估函数。第四章对两种不同策略的搜索算法进行重点讲述，分析并对比各种算法的性能。并阐述了辅助搜索的手段在实战当中起的作用。第五章介绍基于昀佳优先搜索的B*算法在中国象棋计算机博弈当中的应用，并重点论述了评估函数在该类算法中所起的作用，设计并改进了符合该算法的评估函数，并通过实验证明改进的评估函数比原来的函数更适合昀佳优先策略的算法。第六章对本文进行总结和展望。第2章数据结构与表示