中国科研软件论坛 » 【神经网络】 » NGNS基于神经网络的象棋软件的初步构想

查看完整版本: NGNS基于神经网络的象棋软件的初步构想

michael 2007-7-13 10:41

NGNS基于神经网络的象棋软件的初步构想

摘要：指出当今象棋软件学习功能的不足，提出基于神经网络技术的解决办法，为新一代象棋软件指明发展方向。
研究方向：让软件“象人一样思考”。
备注：NGCS—Next Generation  Chess  Software%o'ZH[9kO$^f#T

      1997年5月，发生了一件震惊世界的大事，美国IBM“深蓝”超级计算机首次击败国际象棋男子世界冠军卡斯帕罗夫。“人机大战”最后一局较量中，“深蓝”仅用了一个小时便轻松战胜小卡，并以3.5比2.5的总比分赢得胜利。输棋之后，小卡很快起身，沮丧地离开了棋室。那么人类败了吗？实际上，在第二局输棋之后小卡就曾表示有一“上帝之手”在助“深蓝”一臂之力，认为电脑不可能有那几步超人的应对。他的怀疑是非常有道理的，也就是我们现在常说的“人机合一”，可能有一位大师级别的高手“帮助”了电脑。
      这个说法得到了间接的证实。6年后，咽不下这口气并且始终在寻找机会的小卡在纽约和另外一台超级电脑“更弗里茨”开战，结果下成2比2平。很显然，根据电脑的超级发展速度，“更弗里茨”比“深蓝”更胜一筹，小卡满意于和局并指出电脑还不能领先于人脑。
   其实，人脑的弱点正是人性的本质。棋王为了避开“深蓝”的计算优势，不惜放弃自己最擅长的攻击棋路，刻意营造“捉摸不定”的布局。但是“深蓝”下棋只有“穷举法”这一招，根本没有任何学习功能。棋王的“攻心为上”碰到“深蓝”的“无心可攻”，不仅白费力气，而且为自己带来无限的挫折和焦虑。
      尽管“深蓝”的胜利是与卡斯帕罗夫的心理压力、表现失常等原因不无关系，但对“深蓝”的成绩也是应该予以充分肯定的。 leC(qp
      严格说来，“深蓝”只有并行操作和资料搜寻的技术，谈不上“智能”二字。它不能自己选择目标，也不能修改用来权衡进展的标准，更无法进行多元的价值取舍。电脑目前在学习功能等方面甚至不如婴儿，人们在人工智能道路上的摸索还只是刚起步而已。
   学习和掌握知识对一个人来说是一件十分自然的事，但要让机器也这样做就相当困难了。最新革命性的观点是将机器和人体结合在一起，将微型超级计算机植入人脑，很简单地实现学习功能，变得空前强大，那时人到底是机器，还是人，是一个非常难以回答的问题。M&d,e_l/sQ4bPO
   在微型超级计算机植入人脑之前，我们想到了神经网络技术——by 萍果^*m6BT)[
-J9@ tW u"|:Bk
[align=center]第一章：传统棋类软件面临挑战[/align][k:_8O-p,^I0A*g
[align=left]       在编写人机博弈软件之初，科学家们举步维艰难。遇到的主要难题是计算量实在太大了！比如每个局面大约有40步符合规则的着法，如果你对每步着法都考虑应着就会遇到40 x 40 = 1600个局面。这意味着两层之后，单一步棋就会出现1600个不同的局面，而两步之后是250万个，三步之后是41亿个。按每盘棋走40步计算，所有可能局面就有10的128次方个，这个数字远远多于已知宇宙的原子总数！很显然，没有一台电脑可以搜索全部可能的着法来下棋。这种局面在1958年出现了突破，匹兹堡大学的三位科学家发现：可以从搜索树中剔除相当大的部分而不影响最后结果，他们把这叫Alpha-beta算法，也就是我在另一篇关于软件层数分析的文章中提到的
“剪枝”和“门槛”。
　  Alpha-beta算法的原理是：比如电脑已经完成评价一步棋，开始计算第二步棋。一旦单个变化显示返回的值低于第一步棋的值，就可以立即中止这个搜索。我们不需要精确知道第二步棋究竟有多差，程序会明确选择第一步棋。“煎枝”技术的成功与否，取决于软件的审局能力。客观上，Alpha-beta大大减少了计算机的搜索量，以至于最初的电脑也可以在一个能让人忍受的时间范围内搜索到七、八层。这个算法作为一个基础一直保留到今天，我们目前所看到的三大中象棋软象棋奇兵、棋海无涯、谢谢大师无一例外的保留了该算法，其中奇兵和谢谢更是沿袭了正宗的国象血统（引擎）。我们所能看到的其他的搜索方法，不过是该法的改进版本或者辅助工具，例如“MAX-MIN”搜索、迭代加深、静态搜索、空着裁减、期望窗口、PVS(NegaScout)和MTD(f)等。$vam1K,D]Sw
电脑棋力的另一个重要方面是下棋时使用浩瀚的开局库。多少代人类大师的知识积累和经验可以轻易地储存在硬盘上并且在开局阶段采用，对这些局面的每一个都有完整的统计(着法、胜率、使用率等等)。程序经常是连走10个回合之后才第一次需要计算。如果没有从这些人类的开局知识精华中受益，程序将实力大减。 -A'J9b{-cUIOUKg6i
出乎编程专家的想象而象棋高手意料之中的是，残局库所发挥的作用远远不如开局库那样有效。程序员设想的是，电脑使用这些残局数据库，可以把每个残局走得绝对完美，就象上帝一样。然而有些单方面多于二个进攻子力的残局就让程序员狼狈不堪，有时甚至出现让东邪这样水平的棋手为之捧腹的悲剧。实际上与开局库大不相同，固定的局面很难恰好出现，在某些仅余几子的局面里，要取胜不得不进行超过百步的计算，人类走残局时，经验和知识比重很大，有很多棋根本不用考虑就知道该怎么样走，但电脑却是“一丝不苟”地全部去算。从应用的实例来看，棋隐的残局库就是一个失败的例子：拥有超过主程序几十倍的残局库，却无法在和东邪这样级别的选手的较量中取胜。L`5{2S&L1CH ave
必须提到的是软件的审局，这需要建立局面评估函数，这是软件力量的核心。该函数包括子力的价值、动能、势能、胁能等很多变量，这在我之前的那篇关于软件审局和层数分析的文章中已经详述，这里只作简单介绍。子力的价值不是静态的，不是一成不变的，它随着自身的位置以及与其他协作部队的关系而发生变化，举例来说，一个未过河的卒价值为1，那么当它行进到对方王前并且有其他己方子力配合的时候，其作用几乎要等同于一个车，那么它的价值将要加上动能、势能、胁能等很多附加值，届时它的值也许要变成10。局面评估函数的准确与否，直接关系到棋软的力量，它是其他一切计算的依据。它与算法构成软件的引擎。
传统棋软的基本知识就介绍到这里，它们已经发展得非常强大，就目前的三大棋软来说，其佼佼者已可以在快棋中对抗人类大师。但是，传统的棋软亦存在相当的不足，那就是它的学习功能。也许你会问，目前棋隐、谢谢和奇兵看起来都有不错的学习功能，为什么这反而被说成不足了呢？经过研究我们发现，上述软件的学习功能是基于在实战中忠实地记录双方较好的着法，以便日后使用。但何为较好的着法，软件本身还是只能利用自己的局面评估函数来作判断，哪怕你走出一个精彩的弃子局，而局面函数显示为负数，程序也绝对不会采纳。再者，即便是正数，假如在另外的对局中走到相似或相同的局面，软件仍然会以自身的审局机制来进行判断，优先选择棋认为分值更高的着法，除非你来回拆棋直到软件认可。在大量实践中，我至今没有获得明显的证据证明软件吸纳了哪怕是相当微小数量的“手筋”应用于实战。有些哪怕是东邪这样水平的棋手看上两次也能哼哈领悟的妙手，软件偏偏重复掉进那个弹坑而永不爬起来。
究其根本，不是软件不能干，而是人类太狡猾。即便是最新的棋软，也只接受强迫它学习才有效，因此作者出了一版又一版，修改引擎，提升实力。电脑不如人脑的关键是他不会主动思考。因此现阶段凭借一两盘棋来得出电脑能够战胜人脑的结论是不科学的。事实是，电脑在某些个别方面的个别功能超过人脑是完全有可能的，但要全面超过人脑，可以说是遥遥无期。要搞明白人脑的思维和智能机制，还说不清要过多少年，要超过它，更是一个未知数。4t[`f~x
我认为，要让电脑“象人那样思考”，是人工智能研究取得突破性进展的关键。　　 ]-j7D9[c%x
在微型超级计算机植入人脑之前，我们想到了神经网络技术——by 萍果[/align]
[align=left]请看第二章。
[/align][align=left]                                        第二章：NGCS-基于神经网络技术的象棋软件的初步构想

80年代初，世界掀起了一股研究神经网络理论和神经计算机的热潮，很多国家已经制定计划，开展对脑功能和新型人工智能的研究。[/align][align=left] 人脑是自生命诞生以来，生物经过数十亿年漫长岁月进化的结果，是具有高度智能的复杂系统，它不必采用繁复的数字计算和逻辑运算，却能灵活处理各种复杂的，不精确的和模糊的信息，善于理解语言、图象并具有直觉感知等功能。人脑的信息处理机制极其复杂，从结构上看它是包含有140亿神经细胞的大规模网络。单个神经细胞的工作速度并不高（毫秒级），但它通过超并行处理使得整个系统实现处理的高速性和信息表现的多样性。B#q(]1@-o/B
因此，从信息处理的角度对人脑进行研究，并由此研制出一种象人脑一样能够“思维”的智能计算机和智能信息处理方法，一直是人工智能追求的目标。
如果基于神经网络技术来建立数学模型，将类人的思维方式灌输于电脑，传统象棋软件的弱点就能得以解决。在这里，我们并不排斥传统的象棋软件中的先进技术，一切优秀实用的技术都是向下兼容的，我们鼓励保留部分传统的优秀算法并利用神经网络技术建模来弥补学习功能存在的缺陷。
让软件“象人那样思考”是我们的目标，超越人类并不是最终目的。&V3?-x7X AF
神经网络就是通过对人脑的基本单元---神经元的建模和联结，来探索模拟人脑神经系统功能的模型，并研制一种具有学习、联想、记忆和模式识别等智能信息处理功能的人工系统。这里简单介绍一下神经网络的特点及研究动态。
早期生物学家就发现在人类的心脏中有混沌现象存在，血管在显微镜下交叉缠绕，其中也有惊人的有序性。在生物脑神经系统中从微观的神经膜电位到宏观的脑电波，都可以观察到混沌的性态，证明混沌也是神经系统的正常特性。九十年代开始，则更进一步将混沌和神经网络结合起来，提出多种混沌神经网络模型，并探索应用混沌理论的各种信息处理方法。经过试验，由这种混沌神经网络模型所绘出的输出图形和脑电图极为相似。现代脑科学把人脑的工作过程看成为复杂的多层次的混沌动力学系统。脑功能的物理基础是混沌性质的过程，脑的工作包含有混沌的性质。通过混沌动力学，研究、分析脑模型的信息处理能力，可进一步探索动态联想记忆、动态学习并应用到模式识别等工程领域。Y Rq1R:T'o,Ix&zK6^
模糊集理论和神经网络虽然都属于仿效生物体信息处理机制以获得柔性信息处理功能的理论，但两者所用的研究方法却大不相同，神经网络着眼于脑的微观网络结构，通过学习、自组织化和非线性动力学理论形成的并行分析方法，可处理无法语言化的模式信息。神经网络和模糊集理论目标相近而方法各异。因此如果两者相互结合，必能达到取长补短的作用。将模糊和神经网络相结合的研究，约在15年前便已在神经网络领域开始，为了描述神经细胞模型，开始采用模糊语言，把模糊集合及其运算用于神经元模型和描述神经网络系统。与神经网络相比，模糊集理论和模糊计算是更接近实用化的理论，因此，利用模糊理论为神经网络建模是简明而有效的方法。遗传算法是模拟生物的进化现象（自然、淘汰、交叉、突然变异）的一种概率搜索和最优化方法。是模拟自然淘汰和遗传现象的工程模型。该方法不但可以用于建立神经网络的母代子代模型，而且可以使现有的神经网络软件交叉配种，以达到杂交优势。
神经网络、模糊集理论和以遗传算法为代表的进化算法都是仿效生物信息处理模式以获得智能信息处理功能的理论。三者目标相近而方法各异；将它们相互结合，必能达到取长补短、各显势的效果。[/align][align=left]    以上是神经网络技术的主要特点和研究动态，大部分信息都摘选自相关学术文章，我们的命题则是：怎样让软件“象人一样思考”，这需要解决软件主动去学习的难题。
神经网络主要通过两种学习算法对软件进行训练，即有师学习算法和无师学习算法。此外，还存在第三种学习算法，即强化学习算法；可把它看做有师学习的一种特例。"{8G"r"Kc
1、有师学习：有师学习又称有监督学习。在这种学习模式中，神经网络对输入模式的训练在预先提供的正确样本（教师）的指导下完成。神经网络按照一定的学习算法，不断调整输出模式与正确样本（教师）之间的误差，实现输出的最佳结果。有师学习算法能够根据期望的和实际的网络输出(对应于给定输入)间的差来调整神经元间连接的强度或权。因此，有师学习需要有个老师或导师来提供期望或目标输出信号。!x+s:~1kz vj
2、无师学习：无师学习又称无监督学习，或自组织学习。在这种学习模式中，神经网络对模式的训练是在无教师的情况下完成的。神经网络仅仅依靠局部信息和内部的自适应调整，控制其输出，完成训练和输出最终解。无师学习算法不需要知道期望输出。在训练过程中，只要向神经网络提供输入模式，神经网络就能够自动地适应连接权，以便按相似特征把输入模式分组聚集。
3、强化学习如前所述，强化学习是有师学习的特例。它不需要老师给出目标输出。强化学习算法采用一个“评论员”来评价与给定输入相对应的神经网络输出的优度（质量因数）。强化学习算法的一个例子是遗传算法(GAs)。处理单元（神经元）的每一个输入都有一个相对加权。其作用是影响该输入的作用，这一点类似于生物神经元不同的突触强度，用以区别不同的输入对输出的不同影响。在神经网络中，权值是可以自适应调整的参数，它决定了输入信号的强度。[/align][align=left]学习性是神经网络的一个重要特征。
基于神经网络学习的理论我们可以得知，神经网络软件可以在三种模式下自主学习，即有师、无师、强化学习。其中有师学习类似于当今软件的学习方法，就是软件作者来修改它的引擎并提升棋力。但是无师学习和强化学习无疑具有革命性的进步，正因为神经软件可以“依靠局部信息进行自适应调整”，它无疑具备了部分人的思维特征。强化学习谈到了两个方面，一个是评论员”学习，也就是这个“师”，不必要是软件作者，只需要是对棋艺有独特见解的人，就可以来充当“馈者”，为爱好者提供了极大便利，便于我们打造自己的“日不落”棋软。
另外特别有意思的一点就是软件的遗传性，相信在不远的将来，我们的软件不仅具有人的思维特征，并且能够产子，也可以结婚，通过杂交优势，产生出更优秀的软件。东邪、太平、贞子可不要在那里遮着嘴发笑，也许软件作者们已经明白，并着手考虑。
]:s}2_$f|
世界上没有疯子，有的只是思维滞后的傻子——by 萍果
在微型超级计算机植入人脑之前，我们想到了神经网络技术——by 萍果
[/align]

页: [1]

查看完整版本: NGNS基于神经网络的象棋软件的初步构想