《中国象棋计算机博弈中搜索算法的研究与改进》由会员分享，可在线阅读，更多相关《中国象棋计算机博弈中搜索算法的研究与改进（46页珍藏版）》请在金锄头文库上搜索。
1、河北大学 硕士学位论文 中国象棋计算机博弈中搜索算法的研究与改进 姓名：郭秀丽 申请学位级别：硕士 专业：应用数学 指导教师：王熙照 20100501 摘 要 I 摘 要 在人工智能领域，机器博弈始终是一个重要的组成部分。自从计算机问世以来，人 们为了让计算机具有与人类棋手一样的博弈能力，进行了大量的研究和实验。机器棋手 和人类棋手之间也展开了长达几十年的竞赛。其中最广为人知的要数“深蓝”在国际象 棋上所取得的成就。 “深蓝”的成功标志着计算机棋手战胜人类顶级大师已经从梦想变 成了现实。 而中国象棋的计算机博弈研究比国际象棋要落后三、四十年。虽然起步晚，但也取 得了一定的成绩，出现了一大批具有
2、高水平的象棋程序。本文针对中国象棋博弈系统进 行研究，介绍了中国象棋计算机博弈的关键技术，总结并比较了不同的搜索算法、搜索 策略在实战中的不同效果，分析了评估函数和辅助搜索机制在系统中所起的作用，并在 研究的基础上实现了基于最佳优先搜索策略的算法， 设计并改进了符合此算法的评估函 数，使系统能够达到一定的实战水平。实验结果表明这种改进的评估函数对于最佳优先 搜索的算法而言是有效的。 关键词 计算机博弈 博弈树搜索 搜索算法 最佳优先搜索 评估函数 Abstract II Abstract Computer chess game is one of the important parts in
3、Artificial Intelligence (AI). After the invention of Computer, many people put their focus on research about computer chess game in order to make the computer player to be the same level as human player. There has been a decades term time competition between computer layers and human players. The ac
4、complishment “Deep Blue” has acquired makes it famous in the world. That means the dream that the computer player conquer the human player come true. The research of computer Chinese chess game dropped behind about 30 years of the Chess game. But it also acquired some achievements. Many excellent ga
5、me playing systems have emerged. In this thesis, we introduced the key technique of computer Chinese chess game, made the comparison among different search algorithms. We analyzed the action of the evaluation function and the assistant mechanism. We applied the best-first search algorithm in our sys
6、tem, and designed an evaluation function which is accord with this type of search strategy. With using this evaluation function, the system has reached a certain level. The experiment results indicate that this evaluation function is feasible and effective in computer Chinese chess game. Keywords Co
7、mputer Chess Game Search Tree Solution Search Algorithm Best-First Search Evaluation Function 第 1 章 绪论 1 第 1 章 绪论 1.1 研究背景 电子计算机可以说是二十世纪人类最伟大的发明，它使人们的工作、生活变得更加 方便快捷。 但是在它刚刚问世的时候， 并没有今天这样强大的运算速度和数据处理能力， 而且还是个庞然大物，无论是制造，还是使用、维护的成本都很高。不过一些有远见的 科学家看到了它巨大的发展潜力，并且不断研究与计算机科学相关的理论，试图让计算 机具有和人类一样的“思考”能力，也就是具
8、有人工智能（Artificial Intelligence） 。 怎样才能判断计算机具有人工智能呢？科学家们首先想到了棋类博弈游戏。 在棋类 博弈游戏中，对战双方各尽所能，通过自己对游戏规则和经验知识的掌握和运用，尽力 使自己一方获得最大收益。 这一过程， 就是人类思考的过程， 如果计算机能够和人一样， 在棋类博弈游戏中能够达到一定的竞技水平， 就可以说， 计算机具备了一定的人工智能。 于是，棋类游戏的机器博弈，成为了人工智能领域的一只小白鼠。对机器博弈的研究取 得的成果不仅仅只用在棋类游戏上， 而且也已广泛应用于军事、 政治、 经济等多个领域， 给人类带来了极大的社会效益。 在计算机学科发展
9、的初期（1950） ，信息论的创始人香农就提出，可以用计算机来 进行国际象棋的博弈，并且给出了构建博弈程序的理论依据，也就是博弈树搜索。这一 理论成为随后机器博弈研究的基础理论，而香农也成为了机器博弈的创始人。随后的 1953 年， 图灵将理论变成了现实， 他编写出了世界上第一个国际象棋的计算机程序 Turochess。在计算机领域，图灵是一个伟大的科学家，同时他还是一个蹩脚的棋手。 他出于兴趣和对人工智能的探索，写出了这个程序，但是由于当时的计算机运算速度不 高，这个程序最终没能在计算机上运行，图灵只能自己执行这个程序。Turochess 的效 率并不高，每走一步就要花费很长时间，同时它的棋
10、力也很低，甚至下不过它的主人。 1956 年，Las Alamos 实验室设计出了一个真正能在 MANIAC-1 的计算机上运行的程 序，成为第一个真正的计算机博弈程序。但是它并不是一个完整的国际象棋博弈系统， 只是一个缩减了棋盘大小，省去了部分棋子和一些特殊走法的缩略版程序。 1957 年,第一个完整的象棋程序由Bernstein设计完成，这个程序运行在IBM 704机 器上，每秒钟可以算出200步，并能够走出合理着法，从此第一个完整的机器博弈程序 河北大学理学硕士学位论文 2 诞生了。 1966年， 美国斯坦福大学和前苏联实验与理论物理学院拿出各自的象棋程序进行对 战，前苏联以两胜两和的成
11、绩显示了他们在机器博弈方面的实力。 由于硬件水平的制约， 当时的象棋程序能力很有限。 然而， 无论实际情况如何艰难， 都挡不住人们对机器博弈研究的热情。随着计算机软硬件水平的飞速发展，机器博弈领 域的成果逐渐涌现出来。 1967 年， 麻省理工学院研制出的 MacHackVI 程序在一次锦标赛中击败了一名人类业 余棋手，从而写下了电脑击败人脑的记录。 1973-1979年间,美国西北大学开发出来的CHESS系列，棋力稳步提升。1978年,苏格 兰国际象棋大师Levy以三胜一和一负的战绩击败了当时棋力最强的CHESS 4.7。这一次 虽然电脑没有获得最终胜利， 但也写下正式比赛中电脑程序赢了人类
12、象棋大师一盘棋的 记录。当时的CHESS 4.7相当于国际象棋一级的水平。 1978年， Ken Thompson 开发出一台名叫BELLE的象棋机,每秒钟可以搜索十万个局 面，达到了国际象棋的精通级水平。 80 年代中期,卡内基梅隆大学开始研究计算机象棋程序“深思”。随后的1993 年,“深思”二代击败了丹麦国家队, 并且击败了世界优秀女棋手小波尔加。 1997 年,卡内基梅隆大学的“深蓝”小组研究开发出“更深的蓝”，挑战人类大师。 深蓝最为人称道的是它强大的硬件配置。它存储了历史上世界顶尖棋手的近 10 亿个棋 谱，而且拥有强大的并行处理能力,可以在每秒钟计算 2 亿步。 最后在全世界目光
13、的关 注下，“超级深蓝”以 3.5 比 2.5 击败了棋王卡斯帕罗夫。成为人工智能历史上里程 碑式的事件，也标志着机器博弈的重大成功 1。 进入二十一世纪，随着人们对机器博弈领域的不断探索和计算机硬件的飞速发展， 计算机棋手的能力日益强大，屡屡在世界级的比赛中击败人类顶尖棋手，标志着机器博 弈在国际象棋上的研究已经日趋成熟。 1.2 中国象棋机器博弈研究的发展状况 中国象棋机器博弈的研究滞后于国际象棋。大约在上世纪七十年代末，我国台湾省 的一些学者开始了中国象棋计算机程序的研究工作。 当时的研究充分借鉴了国际象棋的成功经验。 1981 年台湾大学的一名硕士研究生张 第 1 章 绪论 耀腾在他的
14、毕业论文人造智慧在电脑象棋中的应用中用残局做实验，并介绍分析了 中国象棋评估函数的组成。这是第一篇研究中国象棋机器博弈的文章。在随后的 1982 年，台湾交通大学的一名硕士研究生廖嘉成实现了一个完整的中国象棋机器博弈程序。 在他的毕业论文利用计算机下象棋之实验中，他详细介绍了自己程序的设计思路， 即将程序分为开局抢位，中局搏杀，残局收尾三个阶段，并针对不同阶段的特点分别进 行处理，开局按照棋谱进行匹配，中局展开完整的搜索，残局记录必杀着法，已经具备 了相当的智能。而这种分阶段的程序设计思路也被后来的研究者们广泛应用。 台湾大学的许舜钦教授于八十年代中期开始了对中国象棋机器博弈程序的全面研 究工
15、作。在他 1991 年的两篇论文中，总结并介绍了到当时为止几乎所有的搜索算法， 并且指出了这些电脑象棋搜索算法的不足和人们对这些算法存在的误区。 这些研究成果 为以后计算机象棋的发展做好了铺垫， 至今仍在指导着人们进行计算机象棋的研究和实 验工作 23。许舜钦教授也因自己所作的巨大贡献而被称为中国计算机象棋之父。 最近十几年，在中国大陆的一些高校、单位、个人对中国象棋机器博弈研究投入了 大量的工作，涌现了一大批优秀的象棋软件，如中山大学研究生涂志坚的“纵马奔流” 4，北京陈朝阳的“象棋旋风” ，赵明阳的“象棋奇兵” ，黄晨的“象眼”等等。其中值 得一提的是东北大学的“棋天大圣” ，这款软件是由
16、深蓝的设计者之一，号称深蓝之父 的华人许峰雄博士参与的团队研究开发出来的，曾在 2006 年的计算机博弈奥林匹克竞 赛中获得过冠军。上海机器博弈研究所的黄晨凭个人兴趣开发出来的“象眼”引擎挂在 “象棋巫师”的界面上，具有很高的对战能力，可以说是棋力最强的非商业化软件 5。 与国际象棋（64 个落子点）相比，中国象棋（90 个落子点）的空间复杂度更高， 规则也更为复杂，下表列出了几种常见棋类的空间复杂度对比。 表 1-1 棋类空间复杂度对比 显然，中国象棋较高的空间复杂度，也给国内学者们提出了严峻的挑战。 3 河北大学理学硕士学位论文 4 1.3 中国象棋机器博弈简介 中国象棋的计算机程序与国际象棋类似，包含界面部分和引擎部分。界面部分就是 一个可视化的游戏界面，具有显示局面和控制落子的基本功能，有的界面还提供诸如记 录棋谱、悔棋等附加功能。引擎部分必须包括数据结构定义、着法生成、局面评估和搜 索机制，有些引擎还提供了开局库和残局库，供整个引擎参考走棋。引擎部分和界面部 分是相互独立的，通过UCCI通用引擎标准协议连接。这给不同的程序之间进行比
