（计算机软件与理论专业论文）中国象棋计算机博弈中的增强学习研究.pdf

东北大学硕士学位论文 摘要 中国象棋计算机博弈中的增强学习研究 摘要 计算机博弈曾一直被称为是人工智能研究的“果蝇”，但对于有几千年历史的中国 象棋的计算机博弈的研究却远远落后于其它棋类，为了改变这种局面，东北大学成立了 “棋天大圣”中国象棋计算机博弈代表队。论文选题正是来源于在队内所做的研究工作。 为了解决传统的线性评估函数对中国象棋局面的评估不够精确的问题，本文提出了 两个解决方案：一个是使用t d ( ) 增强学习算法优化传统的线性评估函数的可调参数； 另一个是使用人工神经元bp 网络替代传统的线性评估函数，然后使用t d ( ) 算法训练 该网络。一个中国象棋增强学习系统被设计用来实现这两个方案的学习过程。在该系统 中可以使用t d ( ) 算法进行四种形式的学习：专家棋谱数据库学习，自学习，固定对手 学习和网络对战学习。为了验证学习的效果，设计了一个连线器用于将本系统连接到 i n t e r a c t 上的一个网络对战平台一弈天棋缘，通过在网上擂台的等级来评价学习后的棋 力提高程度。 实验表明，使用t d ( ) 算法训练b p 网络的方案潜力巨大，值得进行更深入的研究； 使用t d ( ) 算法优化线性评估函数的方案实施效果很好，可以大大提高系统的棋力。 关键词：中国象棋计算机博弈；评估函数；人工神经元网络：t d ( ) 算法；时间差分学 习 i i 东北大学硕士学位论文 a b s t r a c t r e s e a r c ho fr e i n f o r c e m e n tl e a r n i n gf o r c o m p u t e r c h i n e s ec h e s s a b s t r a c t c o m p u t e rb o a r dg a m eh a sb e e nc a l l e dt h e d r o s o p h i l a ”i na ia r e a ，b u tt h er e s e a r c ha b o u t c h i n e s e - c h e s si n v e n t e de v e ns e v e r a lt h o u s a n d sa g oh a sb e e nf a rb e h i n do t h e rb o a r dg a m e s t oc h a n g et h i ss i t u a t i o n ，ac o m p u t e rc h i n e s e c h e s st e a mn a m e d “q it i a nd as h e n g w a s e s t a b l i s h e di nn o r t h e a s t e r nu n i v e r s i t y t h es u b j e c to ft h i sd i s s e r t a t i o ni sf r o mt h er e s e a r c h w o r ki nt h et e a m t os o l v et h ep r o b l e mt h a to r i g i n a ll i n e a re v a l u a t i o nf i m c f i o nc a n te v a l u a t ec h i n e s ec h e s s p o s i t i o nw e l le n o u g h ，t h i sd i s s e r t a t i o np r o p o s e st w om e t h o d s o n ei s t o o p t i m i z e t h e m o d i f i a b l ep a r a m e t e r so ft h el i n e a re v a l u a t i o nf u n c t i o nt h r o u g ht d ( ) r e i n f o r c e m e n t l e a r n i n ga l g o r i t h m ，a n dt h eo t h e ri st ot r a i na na r t i f i c i a ln e u r a lb pn e t w o r kw h i c hp r e s e n t sa s t h en o n l i n e a re v a l u a t i o nf u n c t i o n as y s t e mn a m e dc o m p u t e rc h i n e s ec h e s sr e i n f o r c e m e n t l e a r n i n gs y s t e mi sd e s i g n e d t o i m p l e m e n tt h e s et w ok i n d so fa p p l i c a t i o n t h r o u g ht h i s s y s t e m ，c o m p u t e rc a ni m p r o v ei t sa b i l i t yb yl e a m i n gf r o me x p e r t sb o o k sd a t a b a s e ，p l a y i n g c h i n e s ec h e s sw i t hi t s e l f , a n o t h e rc o m p u t e ro p p o n e n to rh u m a no p p o n e n t sf r o mi n t e m e t a l i n k e ri sd e s i g n e dt ol i n kt h es y s t e mt ot h es e r v eo fy i t i a n q i y u a n ，af a m o u sc h i n e s ec h e s ss i t e p r o v i d i n go n - l i n ec o m p e t i t i o ns e r v i c e ，a n dt h er a n ko nt h es i t ei su s e dt oe v a l u a t et h ee f f e c to f l e a r n i n g e x p e r i m e n t sp r o v et h a tt h em e t h o do ft r a i n i n gb pn e t w o r ki sw o r t h yo fd e e p e rr e s e a r c h ， a n dt h a tt h em e t h o do fa p p l y i n gt d ( ) a l g o r i t h mt oa t r t i n gt h em o d i f i a b l ep a r a m e t e r so f e v a l u a t i o nf i m c t i o ni ss u c c e s s i v ea n dr e c o m m e n d e d k e yw o r d s ：c o m p u t e rc h i n e s ec h e s s ；e v a l u a t i o nf u n c t i o n ；a r t i f i c i a ln e u r a ln e t w o r k ；t d ( ) a l g o r i t h m ；t i m ed i f f e r e n c el e a r n i n g i i i 东北大学硕士学拉论文 声明 声明 本人声明，所里交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任蜘贡献均己在论文中作了明确的说明并表示谢 恚。 本入签名王涛 日 期：棚6 。l 。； 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位 论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印 徉和磁盘，允许沦文被查阅和借阅。本人同意东北大学可以将学像论文 的全部或部分内容编入有关数据库避行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名：否捉l j 视力同意。) 学位论文作者签名_ 王缚 签字日期：6 、j 、5 导师签名：凇前纠 签字日期：阳6 。f # 东北大学硕士论文 第一章绪论 1 1背景 第一章绪论 1 1 1 人机博弈的历史 博弈( g a m ep l a y i n g ) 是一种竞争，而竞争现象广泛存在于社会活动的许多 方面，因此博弈论可以很自然地引申并应用到含有竞争现象的政治、经济、军事、 外交等各个领域。从狭义的“博弈”来讲，计算机博弈是各个领域博弈理论的起 源与基础，在人工智能方面更是一个重要的研究方向，曾一直被称为是人工智能 研究的“果蝇”。由博弈技术衍生出来的各种应用，如航空调度、天气预报、资 源勘探、军事博弈、金融经济调度等领域，取得了大量引人注入的成果。 回顾国际象棋人机博弈的历史会发现人类研究计算机博弈走过了一条艰辛 而辉煌的路程： 1 9 5 8 年，i b m 7 0 4 成为第一台能同人下棋的计算机，名为“思考”，思考 速度每秒2 0 0 步。 6 0 年代中期，科学家德里夫斯断言，计算机将无法击败一位年仅1 0 岁 的棋手。 1 9 7 3 年，国际象棋软件4 0 被开发出来，这是未来程序的基础。 1 9 7 9 年，国际象棋软件4 9 达到专家级水平。 1 9 8 1 年，c r a y b l i t z 新的超级计算机拥有特殊的集成电路，预言将可 在1 9 9 5 年击败世界棋王。 1 9 8 3 年，b e l l e a t t 开发了国际象棋硬件，达到了大师水平。 8 0 年代中期，皮兹堡的c a 鼢咂g i e m e l l o n 大学开始研究世界级的国 际象棋计算机程序。 1 9 8 7 年，“深思”首次以每秒钟7 5 万步的思考速度露面，它的水平相当 于拥有国际等级分为2 4 5 0 的棋手。 19 8 8 年，“深思”击败丹麦特级太师拉尔森。 1 9 8 9 年，“深思”已经有6 台信息处理器，每秒思考速度达2 0 0 万步，但 在与世界棋王卡斯帕罗夫进行的“人机大战”中对阵以0 比2 败北。 东北大学硕士论文 第一章绪论 1 9 9 0 年，“深思”第二代产生，使用i b m 的硬件，吸引了前世界棋王卡 尔波夫与之对抗。 1 9 9 1 年，“弗里茨”问世。 1 9 9 3 年，“深思”二代击败了丹麦国家队，在与世界优秀女棋手小波尔加 的对抗中获胜。 1 9 9 5 年，“深蓝”更新程序，新的集成电路将其思考速度达到每秒3 0 0 万 步。 1 9 9 6 年，“深蓝”在与卡斯帕罗夫的挑战赛中，以2 比4 不敌卡斯帕罗夫。 1 9 9 7 年，“超级深蓝”开发出了更加高级的“大脑”，4 名国际大师参与i b m 的挑战小组为电脑与卡斯帕罗夫重战出谋划策，最后“超级深蓝”以3 比 2 击败了卡斯帕罗夫，卡斯帕罗夫要求重赛，但没有得到回应。 1 9 9 9 年，“弗里茨”升级为“更弗星茨”。 2 0 0 1 年，“更弗里茨”更新了程序，击败了卡斯帕罗夫和阿南德，以及除 了克拉姆尼克之外的所有排名世界前十位的棋手。 2 0 0 2 年1 0 月，“更弗罩茨”与克拉姆尼克在巴林进行“人机大战”，思考 速度为每秒6 0 0 万步。 2 0 0 3 年1 2 月“更年少者”与卡斯帕罗夫举行人机对抗，双方3 比3 战 平。 不光在国际象棋，计算机博弈也在其他棋类发展迅速，如西洋双陆棋、西洋 跳棋、奥赛罗等等。而在中国象棋方面的研究到目前为止相对要滞后一些 1 1 2 计算机博弈涉及的技术 走。 人机对弈的程序，至少应具备如下几个部分： ( 1 ) 某种在机器中表示棋局的方法，能够让程序知道博弈的状态。 ( 2 ) 产生核发走法的规则，以使博弈公f 地进行，并可判断人类对手是否乱 ( 3 ) 从所有合法的走法中选择最佳的走法的技术。 ( 4 ) 一种评估局面优劣的方法，用以同上面的技术配合做出智能的选择。 ( 5 ) 一个界面，有了它，这个程序才能用。 计算机博弈涉及的主要技术有： ( 1 ) 棋盘表示( b o a r dr e p r e s e n t a t i o n so 棋盘表示就是使用一种数据结构来 2 东北大学硕士论文 第一章绪论 描述棋盘及棋盘上的棋子，通常是使用一个二维数组。一个典型的中国象棋棋盘 是使用9 1 0 的二维数组表示。每一个元素代表棋盘上的一个交点。一个没有 棋子的交点所对应的元素是0 ，一个黑帅对应的元素是1 ，黑士则用2 表示等等， 依此类推。棋盘的数据表示直接影响到程序的时间及空间复杂度。为了追求更高 效率，研究人员针对不同棋类提出了多种不同的表示方法，比如位棋盘表示法等。 ( 2 ) 走法生成( m o v eg e n e r a t i o n ) 。博弈的规则决定了哪些走法是合法的。对 有的游戏来说，这很简单，比如五子棋，任何空白的位置都是合法的落子点。但 对于象棋来说，就有马走日，蒙走田等一系列复杂的规则。走法产生是博弈程序 中一个相当复杂而且耗费运算时间的方面。不过，通过良好的数据结构，可以显 著地提高生成的速度。 ( 3 ) 搜索技术( s e a r c ht e c h n i q u e s ) 。对于计算机来说，直接通过棋盘信息判 别走法的好坏并不精确。除了输赢这样的局面可以可靠地判别外，其他的判断都 只能做到大致估计。判别两种走法孰优孰劣的一个好方法就是察看棋局走下去的 结果。也就是向下搜索若干步，然后比较发展下去的结果。为了避免差错，我们 假定对手的思考也和我们一样，也就是，我们想到的内容，对手也想到了。这就 是极大极小搜索算法的基本原则。极大极小搜索算法是本书中所有搜索算法的基 础。极大极小搜索算法的时间复杂度是o ( b n ) 。这里b 是分枝因子( b r a n c h i n g f a c t o r ) ，指棋局在各种情况下的合法走步的平均值；n 是搜索的最大深度，也就 是向下搜索的博弈双方的走步之和。例如向下搜索甲乙双方备走一步的情形，n 就是2 。显然对于象棋这种分枝因子在4 0 左右的棋类游戏，时间开销随着n 的 增大会急剧的增长，不出几层就会超出计算机的处理能力，这将导致在有限时间 内得不到令人满意的结果。人们在开发高效的搜索算法上投入了大量的研究。在 过去的几十年中，一些相当成功的改进大大提高了极大极小搜索的效率。 a i p h a b e t a 剪枝、迭代深化、置换表、历史启发、杀手启发等手段的综合应用将 搜索效率提高了几个数量级。 ( 4 ) 估值( e v a l u a t i o n ) 。然而，现有的计算机的运算能力仍然十分有限。不 可能一直搜索到分出输赢的那一步，在有限搜索深度的末端，我们用一些静态的 方法，来估计局面的优劣。这些方法在很大程度上依赖于具体的游戏规则和我们 对于该游戏的经验知识，其中相当一部分不完全可靠。例如，中国象棋的程序通 常将一个炮赋予远高于一个兵的价值，但一个兵在高手的运用之下往往可以产生 不次于炮的作用。写出一个好的估值函数并不是一件轻松的事，它需要你对所评 3 一 东北太学硕士论文 第一章绪论 估的棋类相当了解，最好是一个经验丰富的高手。然后还要进行无数次的试验， 经历几番失败后才可能得到一个基本令人满意的估值函数。本文将要探讨的是通 过另外一种途径，即通过时间差分( t e m p o r a l d i f f e r e n c e ，简称t d ) 的增强学习 方法不断提高计算机的估值能力，从而让计算机学习到很高的象棋知识。 ( 5 ) 其他技术。计算机博弈在实际实现中还有许多的技术需要考虑，如_ 丌局 库、残局库、循环探测、哈希表、专家系统等等。 1 1 3 中国象棋计算机博弈的历史与现状 关于中国象棋电脑的研究，是八十年代起步的，这恐怕有两个原因：一是外 在原因，既国际象棋电脑在八十年代取得重大突破，美国贝尔公司的电脑参加 8 3 年美国人类比赛，成绩优异，等级分达2 3 0 0 分，被授予大师称号。于是有人 想到如将国际象棋电脑技术移植到中国象棋上来，会带动中国象棋电脑较快的发 展。二是内在原因，既中国象棋到八十年代进入繁荣时期，并从技术研究进入理 论研究，有关开、中局、残局理论以及象棋对策相继建立起来，为电脑中国象棋 提供了理论基础。 电脑中国象棋研究的进展，是从残局到全盘，从实践到商品，从软盘到下棋 机。较早论文是1 9 8 1 年张耀腾发表的( 人造智慧在电脑象棋上的应用 ) ，他提 出审局函数为静态子力值，棋子位置值，棋子灵活度值，威胁与保护等四项之和。 但该文主要以残局做实验，缺乏完整对局的考虑。 1 9 8 2 年廖嘉成发表( ( 利用计算机象棋的实验) ) 就进了一步，研究了开局， 中局，残局三个阶段，构成完整的一盘棋。开局阶段采用棋谱信息库但输八的着 法较少。中局阶段采用棋路搜索法，并设计了审局函数，包括子力，棋子的灵活 度，威胁与保护，兑子( 优势方尽量兑子以减少对方反击机会，并使棋路树压缩， 提高搜索速度) ，攻子与对方主将的距离等因素。 1 9 8 3 年黄少龙、周玉龙合作制成象棋排局系列软盘，先后在西安、上海、 南京、香港摆擂向人类挑战核软件为专家系统，把象棋大师的有关着法输入电脑， 以高超的棋力与人对弈。象棋排局是以指定的局面开始对弈的，虽然不是全盘， 但其变化仍然非常复杂，可能结局数目超过一百万。制作都要首先需要搞清楚全 部棋路变化，进行归纳简化处理，将其逻辑关系输入电脑中。对弈时，从知识库 找到对立的着法，无论对手如何变化，均能应付。 1 9 8 6 年美基公司研究成n o 、，a g 弈棋机能进行全盘对弈，或根据人的 1 9 8 6 年美基公司研究成n o 、r a g 弈棋机能进行全盘对弈，或根据人的 - - 4 一 东北大学硕士论文第一章绪论 意图布子，下让子棋或残棋。这是一种棋盘式电脑，在棋盘上摆棋子对弈，比屏 幕显示的电脑下棋更有真实感。 1 9 8 7 年，台湾举办电脑象棋赛。从1 9 8 9 年起，在英国举办世界电脑奥林匹 克大赛，其中设中国象棋电脑的比赛项目。这些比赛推动了电脑象棋研究的的发 展，引起了象棋界和电脑界的兴趣和关注。 目前我们所能接触到的电脑中国象棋软件有许多，如象棋奇兵、象棋水 浒传、特级大师、象棋武林贴、楚汉棋缘、将族i i d 、梦入神机等 等，不下二十余种，但其中a i 特别高者不多。在电脑技术不断更新的今天，中 国象棋博弈软件的研究反而放慢了脚步，更多是个人为主的非商业研究。中国象 棋计算机博弈的研究者在国际上所达到的水平还不如国际象棋和西洋跳棋等棋 类那样成功。 1 1 4 研究中国象棋计算机博弈的意义 研究中国象棋计算机博弈，具有多方面的重大意义。首先，具有一定的学术 意义，计算机博弈仍然是a i 领域具有挑战性的课题，虽然国际象棋等其它棋类 取得了一定成功，中国象棋仍需努力。另外，通过研究中国象棋计算机博弈，也 能提高中国象棋的棋艺水平，具有很高的体育方面的意义。 1 1 5 东北大学“棋天大圣”中国象棋计算机博弈代表队 为了发挥团队攻坚的集体优势，迅速提高中国象棋计算机博弈的水平，东北 大学人工智能与机器人研究所成立了东北大学“棋天大圣”中国象棋计算机博弈 代表队。在东北大学做了宣传动员活动，选拔了一批充满活力与热情的专业组和 业余组的队员，并聘请了“深蓝之父”许峰雄博士做咨询顾问，树立了挑战中国 象棋全国冠军的宏伟目标，并制定了稳步发展的攻关计划。相信在不久的将来， 中国象棋计算机博弈水平能达到甚至超过国际象棋计算机博弈的水平。本文来自 在于在队内所做的研究工作。 5 一 东北大学硕士论文 第一章绪论 1 2 论文结构 本文各章的内容安排为：第一章是引言部分，重点是关于计算机博弈的背景 知识介绍，以及中国象棋计算机博弈的现状。第二章引出本文所要解决的问题， 即评估函数的准确与学习能力的问题。第三章介绍传统的线性评估函数，并指出 其不足之处。针对传统线性评估函数的不足，本文在第四章提出两种解决方案， 并详细论述新的解决方案所涉及的各项技术。其中包括传统线性评估函数可调参 数的优化，人工神经元b p 网络表示的非线性评估函数以及t d ( ) 算法。为了测 试解决新的解决方案的实际效果，本文设计了一个中国象棋计算机博弈增强学习 系统，在第五章中将重点介绍该系统的系统结构及其u m l 设计。在第六章中，本 文将介绍使用中国象棋增强学习系统进行t d ( ) 算法的各种学习的实验情况和 些实验结果。最后，第七章从实验结果得出一些结论，并对未来的研究进行展 望。 一6 东北大学硕士论文 第二章问题提出 第二章问题提出 在上一章中列举了中国象棋计算机博弈所能用到的很多技术。其中核心的两 项技术就是搜索和评估。二者的关系可以用一颗博弈树( 又叫做搜索树) 来描述。 博弈树是把计算机和用户所有可能走法和局面罗列出来的一颗树。 p t h = l 图2 1 深度为2 的博弈树 f i g 2 1 a 2 - p l ys e a r c ht r e e 如图2 1 所示，红黑双方交替地按合理走法把树展开，树的每一个节点都 表示某一个特定局面。根节点a 表示的是当前需要计算的局面，中间节点b 、c 、 d 表示的是对弈过程中可能出现的某个局面，叶子节点e 、f 是树的最底端。 叶子节点和根节点之间的最大距离，称为搜索深度。整个博弈树描述的是从当前 局面出发，包含所有可能的对弈过程的搜索树。 如果计算机能从初始局面开始，建立一棵博弈树，树的所有叶子节点都是分 出胜负的局面，那么这棵树可以称为完全博弈树。如果可以建立完全博弈树，中 国象棋的问题就可以得到解决。也就是说电脑总能找到一个取胜的路径，也就是 象棋的不败算法。但是完全博弈树大概有1 0 “4 个节点，建立这个博弈树已经远远 超出了当代计算机的处理能力。 唯一的解决方法就是让博弈树扩展到计算机运算可以接受的深度，然后对没 有分出胜负的叶子节点进行评估，得到一个尽可能准确的评估值，表示此局面下 计算机取得胜利的可能性。 有了所有叶子节点的评估值，中国象棋计算机博弈问题也就转化为寻求最佳 路径的问题。对弈双方交替走棋，每一方都会尽量争取取得最大的利益。所以， 要找到电脑的最佳走法，也就要假定用户的走法也是对电脑最有威胁的。如图1 7 东北大学硕士论文 第二章问题提出 所示，如果将棋局用符号表示，那正方形表示在可能棋局中取极大值，而圆圈表 示应该取极小值。电脑选取的是取值最大的分枝，用户选取的是取值最小的分枝。 这就是极大极小搜索( m i n i m a xa l g o r i t h m ) 的思想。 搜索引擎是人机博弈问题的一个重点，其中涉及许多算法，这里不再赘述。 本文要探讨的是人机博弈的另一个重点：评估函数。 评估函数是要完成一个从某个棋局到打分之间的函数映射。这个打分就是对 当前棋局下我方胜率的预测。这个打分的准确与否，也在很大程度上影响着博弈 程序的棋力。那么，问题是如何才能尽量给出合理准确的打分呢? 有哪些方法可 以使得预测更准确，从而提高中国象棋计算机博弈的水平? 更重要的是如何使得 这种提高是一个持续的过程，即计算机具有在不断的学习中提高的能力? 一8 一 东北大学硕士论文 第三章研究现状 第三章研究现状 上一章提出了如何对中国象棋局面进行精确评估的问题。当前，大部分评估 函数是从当前棋盘局面中抽取代表象棋知识的特征，通过特征函数计算这些特征 值，所有这些特征值与其特征系数乘积的累加是对当前局面的打分。计算公式为： s c o r e = z k f i ( xj( 3 1 ) 其中，k i 为特征系数，f i 为特征函数，x 为当前棋局。 在评估某个棋局时，一般考虑以下几个特征值：固定子力值、棋子位置值、 棋子灵活度值、棋盘控制值、动态调整值等等。 3 1固定子力值 所谓固定子力值表示棋盘上棋子的本身的价值。在象棋程序的评价值中，首 先计算的就是双方的子力价值，子力价值在象棋中相当重要，如果一方多子( 即 子力价值比对方多) ，这是体现优势的一个主要方面。比如，根据当前象棋理论 的研究，一般比较认同的棋子的子力值是： 表3 1 棋子的固定子力值 t a b l e31m a t e r i a lv a l u e so fp i e c e s 棋子车马炮士 象 丘 、 分值 944 5 22l 这里要注意两个问题：第一，因为中国象棋的胜负是依据帅和将是否存在而 确定，所以帅和将的值要设成非常大的一个值。第二，兵比较特殊，兵在不同位 置上值相差的很悬殊，兵的位置值比固定值更为重要。 则计算固定子力值特征值的公式为： f 子力2z _ 鼢( n u m i xp e c e v a l u e t ) f 、1 、 一勖亨r m ，p i e c e v a l u e ，j 其中，n u m i 为某种棋子的数量，p i e c e v a l u e i 为某种棋子的固定子力值。 9 东北大学硕士论文 第三章研究现状 3 2 棋子位置值 棋子位置值表示某个棋子在棋盘上某个位置的价值。判断中国象棋局面的好 坏很重要的一个方面就是是否占据有利位置。棋子在不同的位置上，应该有不同 的奖励或者惩罚值。比如，车在棋盘上位置值如图2 2 所示。 则计算棋子位置值特征的公式为： f 艚。x 耪( n u 聊护0 3 f f f 鲫砌l u e o f 3 3 、 一勖方fn u m i p o s i t i o n v a l u e , ) 其中，n u m i 为某个落子点上棋子的数量，p o s i t i o n v a l u e i 为某个棋子在某个落子 点的位置值。 3 3 棋子灵活度值 图3 2 一个车的位置值 f i g 3 2p o s i t i o n v a l u e so f ar o o k 棋子灵活度值描述的是棋子的活动范围，即棋子向各处调动的可能性大小。 棋子的威力能否充分发挥，与它的活动性直接相关。本方棋子可以走的点越多， 说明本方棋子的灵活度越大，一般也把这个值作为灵活度值。通常情况下，车马 炮以外的棋子的灵活度对局面的发展影响并不大，所以一般只考虑车马炮的灵活 度值。计算棋子灵活度值特征的公式为： f 是皓受= x 耢( m o v e n u m i xa g i l i t y v a l u e i ) 。、 一x 州2 r ( m o v e n u m 。a g i l i t y v a l u e lj 、 其中，m o v e n u m i 为某个棋子当前可走的步法数量，a g i l i t y v a l u e i 为某种棋子的 一l o h 酶h h琵砼6 4 0 甚 麟扮心您确m璩0 4 坶 ：i酶：撕=j m 3 6 g 6 8 4 8 2 8 o 4 4 6 4 l，王二l_上l，1，j 1 j 6 6 8 2 s 0 4 2 2 l 2 l 2 l 2 l l 8 l 8 毒s 2 8 o 4 4 6 4 l量l量，l，1 1 卫l l 您砖n堪硷琏8 6 8 拄 4 o 2 8 4 6 o o ，i 2，i，i，i，1 a 5 4 _ 1 h：；呈n弛n：矗0 0 o 东北大学硕士论文 第三章研究现状 灵活度值。 3 4 棋盘控制值 一方对棋盘控制的棋盘区域越多，那么他就越具有主动性。由于棋盘在不同 区域的控制具有不同的重要性，所以先要制定一个棋盘控制分数表，也就是越接 近对方九宫的控制分数越大，然后累加计算各个主要子力对棋盘的控制分数。计 算公式为： 麓翥篡糍等 b s ， 一三对方f c o n 扣0 1 l u e i ) 、。 其中，c o n t r o l v a l u e i 为某个棋子在某个位置的控制值。 3 5 动态调整值 动态调整值包括很多，包括当头炮，子力协调，担子炮，连环马，牵手兵等 等。动态调整是把上述4 项发现不了的一些特殊情况提取出来，赋予一定的奖励 或惩罚值，这也是评估函数的一个重要方面。 麓z 2 , 跏e y ( d y 跏n a m 绷i c v 耙a 烹l u e , ( 3 6 ) 一 j r 其中，d y n a m i c v a l u e i 为某个特定棋型的动态调整值。 3 6 传统评估函数的缺点 如果将公式( 2 1 ) 展开，得到公式( 2 7 ) ： s c o r e = 肌f r j = w i x t ( 3 7 ) 其中，w i 为可以调整的参数，x i 为从当前棋局得到的变量。 可见，当前采取的评估函数实质上是一个线性的评估函数。即评估值与表示 棋局的变量和其权重参数都是线性的关系。虽然这种线性的评估函数有简单，计 算快的优点，但其缺点也很明显，主要有两点： ( 1 ) 过于简单的评估函数导不能完整表示复杂的中国象棋局面，从而导致评 估不够准确。中国象棋是非常复杂的棋类游戏，其复杂度甚至比国际象棋稍微高 些。传统的线性评估函数只是通过几个根据人类棋类经验总结出来的几个特征是 一l l 东北大学硕士论文 第三章研究现状 很难表达复杂的象棋知识的。 ( 2 ) 另外，目前对于权重参数w i 都是根据人类经验进行手工调整，由于受 到人类象棋知识的限制，也导致评估的不准确性。另外，手工调整是一项非常烦 琐而又效率不高的方法。 一1 2 一 东北大学硕士论文 第四章解决方案 第四章解决方案 上一章介绍了传统上广泛采用的线性评估函数，并分析了其优越点。本章将 提出新的解决方案并详细论述其中所涉及的技术。 本文针对传统线性评估函数的缺点，提出两套新的解决方案：第一套方案是 继续采用传统的线性评估函数，但使用t d ( ) 增强学习算法优化其可调参数， 而不是传统的手工调整。第二套解决方案是使用人工神经元b p 网络结构构建非 线性的评估函数以替代传统的线性评估函数，再使用t d ( 九) 算法训练该b p 网络。 这两套方案不仅致力于更精确的评估结果，更重要的是为中国象棋计算机博弈系 统增加了学习的能力。下面对新方案所涉及的技术进行详述。 4 1线性评估函数的参数优化 上一章介绍的传统的线性评估函数包含大量的可调参数：p i e c e v a l u e i 、 p o s i t i o n v a l u e i 、a g i l i t y v a l u e i 、c o n t r o l v a l u e i 和d y n a m i c y a l u e i 。在传统上这些参 数都是根据人类经验设定，进行手工调整的。由于受到人类象棋知识的限制，尤 其是博弈系统的设计者未必是中国象棋的专家，所以，手工调整的参数未必准确， 从而影响了评估函数的准确度。针对这个问题，本文引入s u t t o n 4 用于解决多步 预测问题的t d ( 凡) 算法来自动优化这些参数。在4 3 中将对t d ( ) 算法进行详 细论述。 4 2 人工神经元网络评估函数 4 2 1 人工神经元网络简介 人脑是产生自然智能的源泉，是真正出色的并行计算机。人工神经网络 ( a r t i f i c i a ln e u r a ln e t w o r k s ，简称a n n ) 是在人类对其大脑神经网络认识理解 的基础上人工构造的能够实现某种功能的神经网络，它是理论化的人脑神经网络 的数学模型，是基于模仿大脑神经网络结构和功能而建立的一种非算法的信息处 理系统。人工神经网络吸取了生物神经网络的许多优点，因而有其固有的特点： ( 1 ) 高度并行性：人工神经网络是由许多相同的简单处理单元并联组合而成， 一1 3 东北大学硕士论文第四章解决方案 使其对信息的处理能力与效果惊人。 ( 2 ) 高度非线性全局作用：人工神经网络每个神经元接受大量其它神经元的 输入，并通过并行网络产生输出影响其它神经元。网络之间的这种相互制约和相 互影响，实现了从输入状态到输出状态空间的非线性映射从全局的观点来看， 网络整体性能不是网络局部性能的简单迭加，而表现出某种集体性的行为。 ( 3 ) 良好的容错性与联想记忆功能：人工神经网络通过自身的网络结构能够 实现对信息的记忆，而所记忆的信息是存储在神经元之间的权值中。从单个权值 中看不出所存储的信息内容，因而是分布式的存储方式，这使得网络具有良好的 容错性，既能进行模式信息处理工作，有能进行模式联想等的模式信息处理工 作，又能进行模式识别工作。 ( 4 ) 十分强的自适应、自学习功能：人工神经网络可以通过训练和学习来获 得网络的权值与结构，呈现出很强的自学习能力和对环境的适应能力。 人工神经网络的实质反映了输入转化为输出的一种数学表达式，这种数学关 系是由网络的结构确定的，网络的结构必须根据具体问题进行设计和训练。学习 人工神经网络的关键在于掌握生物神经网络与人工神经网络建模的联系，人工神 经网络的数学基础，以及人工神经网络的应用。以下根据一些文献的介绍，列出 神经网络在一些主要领域的应用情况： ( 1 ) 模式信息处理和模式识别：所谓模式，从广义上说，就是事物的某种特 性类属，如：图像、文字、声纳信号、动植物种类形态等信息。模式信息处理就 是对模式信息进行特征提取、聚类分析、边缘检测、信号增强噪声抑制、数据压 缩等各种变换。模式识别就是将所研究客体的特性类属映射成“类别号”，以实 现对客体特定类别的识别。人工神经网络特别适宜解算这类问题，形成了新的模 式信息处理技术。它在各领域的广泛应用是神经网络技术发展的重要侧面。这方 面的主要应用有：图形符号、符号、手写体及语音识别，雷达及声纳等目标的识 别，药物构效关系等化学模式信息辨识，机器人视觉、听觉，各种最近相邻模式 聚类及识别分类等等。 ( 2 ) 最优化问题计算：人工神经网络的大部分模型是非线性动态系统，若将 计算问题的目标函数与网络某种能量函数对应起来，网络动态向能量极小值方向 移动的过程则可视作优化问题的解算过程，稳态点则是优化问题的局部的或全局 最优动态过程解。这方面的应用包括组合优化、约束条件优化等一类求解问题， 如：任务分配、货物调度、路径选择、组合编码、排序、系统规划、交通管理以 一1 4 东北大学硕士论文 第四章解决方案 及图论中各类问题的解算等。 ( 3 ) 复杂控制：神经网络在诸如机器人运动控制等复杂控制问题方面有独到 之处。较之传统数字计算机的离散控制方式，更适宜于组成快速适时自适应控制 系统。这方面主要应用是：多变量自适应控制、变结构优化控制、并行分布控制、 智能及鲁棒控制等。 ( 4 ) 通信：神经网络的自学习和自适应能力使其成为对各类信号进行多用途 加工处理的一种天然工具，尤其在处理连续时序模拟信号方面有很自然的适应 性。这方面的主要应用有：自适应滤波、时序预测、谱估计和快速傅里叶变换、 通信编码和解码、信号增强和降噪、噪声相消、信号特增检测等。神经网络在作 弱信号检测、通信、自适应滤波等方面的应用尤其引人注目，已在许多行业得到 运用。 神经系统的基本构造单元是神经细胞，也称神经元。它和人体中其它细胞的 关键区别在于具有产生、处理和传递信号的功能。每个神经元都包括三个主要部 分：细胞体、树突和轴突。树突的作用是向四方收集由其他神经细胞传来的信息， 轴突的功能是传出从细胞体送来的信息。每个神经细胞所产生和传递的基本信息 是兴奋或抑制。在两个神经细胞之间的相互连接触点称为突触。人们正是通过对 人脑神经系统的初步认识，尝试构造出人工神经元以组成人工神经网络系统来对 人的智能，甚至是思维行为进行研究；尝试从理性角度阐明大脑的高级机能。人 工神经元的主要结构单元是信号的输入、综合处理和输出。人工神经元之问通过 互相连接形成网络， 称为人工神经网络。目前多数人工神经网络的构造大体上 都采用如下一些的原则： ( 1 ) 有一定数量的基本单元分层联接构成。 ( 2 ) 每个单元的输入、输出信号以及综合处理内容都比较简单。 ( 3 ) 网络的学习和知识存储体现在各单元之间的联接强度上。 x i x 2 ： x m 图4 1 人工神经元模型 f i g 4 1m o d e lo f a na r t i f i c i a ln e r v ec e l l 1 5 一 东北大学硕士论文第四章解决方案 图4 1 表示出了作为n n 的基本单元的神经元模型，它有三个基本要素： ( 1 ) 一组连接( 对应于生物神经元的突触) ，连接强度有个连接上的权值表示， 权值为j 下表示激活，为负表示抑制。 ( 2 ) 一个求和单元，用于求取各输入信号的加权和( 线性组合) 。 ( 3 ) 一个激活函数，起映射作用并将神经元输出幅度限制在一定范围内。 从层次结构看，人工神经网络可分为单层神经网络和多层神经网络；从连接 方式看，人工神经网络主要有两种：前馈型网络和反馈型网络。 ( 1 ) 单层神经元网络：将两个或更多的简单的神经元并联起来，是每个神经 元具有相同的输入矢量x ，即可组成一个神经元层，其中每个神经元产生一个输 出。 ( 2 ) 多层神经网络：将两个以上的单层神经网络级联起来则组成多层神经网 络。每层网络都有一个权矩阵w ，一个偏差矢量b 和一个输出矢量a 。多层网 络的每一层起着不同的作用，最后一层为网络的输出层，所有其它层称为隐含层。 在设计多层网络时，隐含层的激活网络应采用非线性的，否则多层网络的计算能 力并不比单层网络更强。 ( 3 ) 前馈网络：前馈网络的特点是：信号的流向是从输入通向输出。 ( 4 ) 反馈网络：反馈网络的主要不同点表现在它的输出信号通过与输入连接 而返回到输入端。在反馈网络中，由于将输出循环返回到输入，所以每一时刻的 网络输出不仅取决于当前的输入，而且还取决于上一时刻的输出，其输出状态由 输入矢量设定后，随着网络的不断运行，从输出反馈到输入的信号不断改变，使 得输出不断变化，从而使网络表现出暂态特性，使得反馈网络表现出前向网络所 不具有的振荡或收敛特性。 通过向环境学习获取知识并改进自身性能是a n n 的一个重要特点。按环境所 提供信息的多少，网络的学习方式可分为三种： ( 1 ) 监督学习：这种学习方式需要外界存在一个“教师”，它可对一组给定输 入提供应有的输出结果( 正确答案) 。学习系统( n n ) 可以根据已知输出与实际 输出之间的差值( 误差信号) 来调节系统参数。 ( 2 ) 非监督学习：不存在外部“教师”，学习系统完全按照环境所提供数据的 某些统计规律来调节自身参数或结构( 这是一种自组织过程) 。 ( 3 ) 再励学习：这种学习介于上述两种情况之间，外部化境对系统输出结果 只给出评价( 奖或惩) ，而不是给出正确答案，学习系统通过强化那些受奖励的 一1 6 一 东北大学硕士论文 第四章解决方案 动作来改善自身的性能。 人工神经元网络采用的学习算法有： ( 1 ) 误差纠正学习：误差纠正学习的最终目的是使某一基于误差信号的目标 函数达到最小，一是网络中每一输出单元的实际输出在某种统计意义上最逼近应 有输出。一旦选定了目标函数形式，误差纠正学习已经成为一个典型的最优化问 题。 ( 2 ) h e b b 学习：神经心理学家h e b b 提出的学习规则可归结为“当某一突触 两端的神经元的激活同步时，该连接的强度应增强，反之则应减弱”。 ( 3 ) 竞争学习：顾名思义，在竞争学习时网络个输出单元相互竞争，最后达 到只有一个最强激活者。 4 2 2 用印网络结构表示评估函数 图4 2 误差逆传播( b p ) 网络结构 f i g 4 2s t r u c t u r eo fb pn e t w o r k 如图4 2 所示，误差逆传播( b p ) 网络是一种多层前馈网络。图4 _ 2 所示是 具有三层的网络结构，分别是输入层、隐藏层输出层。每层都有一定数量的神经 元。 b p 网络结构可用于表示中国象棋计算机博弈中的评估函数，比如：建立一 个9 0 n 1 的b p 网络( n 为隐藏层的个数) ，输入层代表的是局面信息，表示中 国象棋棋盘上每个交叉点上棋子的固定子力值。隐藏层个数是决定学习效果的一 个因素，虽然有一些指导性的原则用于确定隐藏层个数，但一般需要根据具体的 学习应用进行实验和调整。输出层是对当前局面的评估值，范围为 一1 ，1 。输 出值越趋向于1 ，表示我方胜率越大，越趋向于一1 ，表示对方胜率越大，越趋向 一1 7 一 东北犬学硕士论文 第甜章解决方案 予0 ，则表示双方和棋的概率较犬。隐藏层与输出层的害串经元的激活函数均使用 双极型的双曲正切函数。 b p 嘲络的误差逆传攒训练算法是一种迭代梯瘦算法，用于求躺前馈网络的 实黼输出与期望辕出闻的最小均方差值。其缺点是训练时闻较长，且容易陷入局 部极小点。 标准的b p 网络学习算法是一种存益督的学瓣，郎对于每个输入慎耍有个期 望输出值，输入值与新望输出值构成了一对训练样例，所以我们需要的训练样例 楚棋局及其客观合理的打分。馋很明显这样的训练样例是不存在的。另外，一盘 棋结采后毙得到的诚练信惠仪是对弈最最的胜负。如果以每个棋局及其最终维渠 构成训练样例同样是不可取的，因为，一盘棋的最终输赢未必能说明这盘棋当中 的每一个棋盘状态的好螺。所以中间局面训练值兵有内在的模糊性，传统的b p 网络的反晦传播训练算法不能适应这种学习了。 综上，如果幢蔫b p 网络缝构表零评信函数和存储象棋知识，在网络具体调 箍权值参数时和转统的b p 训练算法耍有所不同，本文介缨的是使用t d ( x ) 算法 的增强式学习方法。 4 。3 t 1 2 九) 算法 无论燕侵用线性评估函数，还是人工神经元网络评 古函数，实埂上都可以表 永为这样一个函数：f ( w l 、靴、w 3 w 。，x ) 。其中，x 表示当前棋局对应