进化世界

XiaoP

发到这里来看能不能给大家一个新的思路^-^

            
                                                      开始的小测试环境

        上图是前天构造的一个测试小环境，模拟个体能够获得（得到输入）自己的当前速度、角度、HP以及最近目标的相对位置，离目标越近HP减少得越慢，存活时间越长者适应度越高。刚开始的情况是完全随机，模拟个体完全在一个随机的最小结构神经网络的支持下处理自己的输入。这样的设置相当简单，程序员几乎不做什么工作！接下来就是运行，运行，再运行。个体会不断地发生变化最终达到这个小环境设计者心里的样子吗？到底明天它会不会自动设计出策划要求去达到这个简单任务的NPC呢？


        几个月前，我为自己的一个实验性项目构建的分布式模拟环境基本就绪。该环境采用了HLA网络结构组建，基本上完成了对HLA核心网进行的二次封装，另外构造了一个广域网的扩展接入系统方便更广泛的人机交互！目前这个体系的基本稳定为我的试验项目奠定下了第一个基础。

        这三年来我一直致力于图形引擎的开发和应用工作，之前在MSRA的纯图形学以及图形硬件的研究工作也奠定了足够的图形基础，因此对这个试验项目而言，一个较为完善的软件研究平台和图形支持系统也很快基本成型，并且能够很方便地投入到研究和设计工作中去。这可以说是试验项目的第二个基础。

        前段时间，我在这个平台上对随机宇宙（过程宇宙——Real-Time Procedural Universe，这方面主要研究自动、随机地生成各类拟真的图形、图像、逻辑内容）的一些基础算法、架构的研究模拟和实现（link），使得我更加确信CH系统在内容上人机交互的支持能力也一定会相当强大，特别是对人机图形界面，任何内容的变化都能实时表现在远程的图形客户端上。



        两个月前，我觉得系统底层的一些必要支持已经基本到位，于是我开始构造这个项目的第三大基础架构（即CH必须是一个智能的、自组织的、演化的系统），另外我也希望能提出一种自下而上的开发方式。我知道，CH这样一个大系统，必然是一个“复杂系统”。对复杂系统的研究目前学术界也仅有几个前沿的方向，比如人工智能、人工生命、神经网络、分形、细胞自动机等理论、模型及算法。既然认为CH系统必须要是一个智能的自组织世界，就必然涉及到这些学科方向。这几年来我一直借助在游戏/网络游戏领域的工作机会，探索它们应用的可行性，但长期来对人工智能的有限应用总是让人找不到方向。要么必须在一些明确的问题域上面求得具体的实现（比如A Star），要么必须要找到游戏内容相关的复杂具体模型（比如路点模型、有限状态机模型等等），这对程序开发人员和策划人员来说实际上都是很痛苦的。严格的说，目前我在游戏上的这些工作还谈不上与复杂系统有什么关系，仅仅是一些自上而下的常规开发策略。

        幸喜的是，早就有不少游戏/软件开发公司开始尝试类似自下而上的开发方式。比如，据说Maxis公司的《模拟城市》近几个系列中就采用了人工神经网络技术；不少单机策略或者射击游戏中，开发公司在设计时也离线进化了不少游戏角色和策略；EA在最新的模拟类游戏Spore（孢子）中也很可能采用了一些进化方面的算法或者技术。

        其实在复杂系统中，细胞自动机、神经网络、进化算法、粒子群算法（比如蚁群算法）等领域都是具有良好的应用前景（当然是什么时候大规模应用我们就不去追究了），开始我打算直接在CH系统中使用人工神经网络（ANN），但是在试验中发现，ANN除了本身需要一个较为难描述的环境模型外（特别是实际游戏应用，网游就更不用说了），如果要达到一个通用的、优秀的、无监督的求解性能的话，ANN的算法也是要相当考究的，目前这方面也正是ANN领域研究的重中之重。应此在游戏应用或者模拟研究中，我觉得不大可能寻求到一个现实的实时自适应ANN系统来满足要求，而且毕竟我们不是搞研究而是搞应用的。

               
            一个反相传播的神经网络。设计这样一个网络对于复杂输入和输出的环境来说“几乎”是不可能的。


         为此前段时间我投入到细胞自动机、蚁群算法等领域中去找寻一些应用上的可能点。都怪“元胞自动机（CA）”前不久闹得很火，霍夫曼（自称CA之父）也曾大言不惭CA能颠覆人类得一切科学，谓之“新科学”。拜读其大作以及进行一些试验后，发觉一些思想确实非常新颖独到，很多试验也相当有趣。但是总觉得对CA的研究大多以证明某某理论为结果，没有一点预测能力（即科学的理论总是可以预测的），总有点事后诸葛的感觉。我也很难从CA引出一些能辅助设计的路子来（nb的霍夫曼认为“宇宙就是一巨大的CA，除了实实在在地注视、观看这些规则会如何呈现其结果之外，没有任何办法去预先知道这些结果”，那研究这个理论有个P用啊）。况且它和蚁群算法一样，问题域或者空间维数的增大不可避免地需要庞大的甚至不且实际的计算量（这点蚁群算法还算好些）。


                     
        一个有趣的报告是Wolfram公司的Paul Jean做的，他研究基本细胞自动机（Elementary Cellular Automata,ECA）家族中的第146号，发现了一个奇特的现象。以某个特定的初始条件开始，146号ECA在经过300多步演化之后会突然出现一个相变行为：本来随机排列的一些黑白方格在一个时间步内突然集体变成了白色，并且这个白色区域经过几步演化之后逐渐衰退，因而会在时间图上留下一个大的三角形区域。
        这种现象对于146号ECA来说属于一种极其罕见的行为：只有在特定的初始条件才能发现，Paul称这一现象为Monolith，即“独石碑”。Wolfram常常把自己发明的细胞自动机比喻成当年伽利略发明的望远镜，透过先进的工具，我们可以得到一些全新的科学观察。




        Spore这样的游戏让我看到了另外一个可能方向——进化。从Spore的介绍以及细节上看来，似乎不是严格意义上的实时进化，而且也不大可能会有形态上面的进化（形态进化需要更为有效的图形学理论以及强大的计算能力）。游戏过程仍然是处于人为选择或者策划设定的进化模拟，大多数内容仍然是事先设定好的，不过模型的有机化和进化的思想和表现倒是其卖点。Spore的发行一拖再拖，似乎Will Wright（就是开发《模拟城市》和《模拟人生》那个家伙哈）不把它做得完美就不罢休似的，所以最终版本出来是什么样子还不得而知，期待中…… ^-^

        在Spore这个游戏感受的诱惑下，我考查了许多进化相关的游戏或者软件系统的资料和Paper，国际上也有很多的小项目组专门做这方面的探索，从各种复杂系统小程序到Tierra/Avida的代码进化，从Framsticks的形态行为进化到AI.Planet那漂亮的生物乐园。真还没有想到，居然处处都有进化人工生命的影子！


           
                                  Panspermia中进化出来的生物和世界


           
           
           
  Framsticks:
               1. A creature made of sticks, each is specialized in some function. You can see three receptors ? touch, smell, equilibrium, and a red muscle.
               2. Underwater creature seeking energy.
               3. Hunt: a creature trying to catch and kill the other one.


              
                                                    AI.Planet中丰富的进化世界


        对GA（遗传算法）的详细考查过后，我决心将遗传算法简洁高效的进化思想应用到CH系统中来，正巧我已经准备好了一个很好的HLA模拟体系，加上对ANN比较熟悉，我选取了来自NNRG（nerual netwaoks research group）的一些研究成果来进行攻关和改进。NNRG虽然看起来仅是国际上的一个神经网络研究小组（The group is part of the Artificial Intelligence Lab in the Computer Science Department at the University of Texas at Austin），但是从它的研究领域和项目中可以看到，它对基于NN应用的一个很大领域都有涉猎，而且它融入了很多其他领域的成果。NNRG有个NEAT项目，是一个关于自适应地从简单到复杂构造一个满足问题域的神经网络，适应算法上又采用了GA的思想，应此性能和效果都比较好，对我而言它更重要的是还不用关心NN的具体模型和优化细节！有趣的是，NNRG甚至也出了一个游戏，叫NERO，可以离线进化一些很好的策略来进行战斗对抗。
        我现在拥有的HLA核心网络上可以进行较好的分布式模拟，因此我对NEAT进行了改进，将基因的进化和ANN的适应度评估和应用较独立的分开来。应用NEAT的实时进化特性（rtNEAT），加上我对核心网扩展的广域网接入系统，人类（玩家）也可以很好的加入互动，这样设计有利于未来在网络游戏具体项目上的应用。



        由于基因的进化在服务器上进行，并且可以随时保存和重加载，以网络游戏的角度来看，实时进化在不间断的人机互动中可以表现得很好。再从游戏的设计上来看，策划无需设定甚至分析具体的任务实现过程（特别是NPC），程序员不用为实现这个过程煞费苦心做复杂的设计（况且每个程序员设计出来的算法不一定就是最优的，策划也不一定具有相当丰富的专业知识和经验。而遗传算法在理论上来说就可以达到全局最优），所有的设计工作都是在长期的在线运行和与环境（甚至真人）的互动中进化达成；策划也可以设定广泛的游戏环境和属性（这目前是策划大量的工作）而不用再担心诸如增加一个属性就会造成各个系统的相应修正和程序配合修改这种事情（比如NPC从不能攻击到支持攻击，环境中新增加一种叫做“food”的道具）。
       经过这段时间的试验，我想再从策划的角度来看，策划设计一个东西就可以考虑是走自上而下的分析路子，还是较为傻瓜的自下而上的新路子了！目前我只是提出这样一个设计方向，还有待进一步试验来观察它的实际应用效果。


       BTW，由于这个小环境试验前几天才设定好，这几天还没有来得及去运行它，反正进化的基因可以保存和再加载，可以说设计过程是连续的，每天都可以出新花样。所以我在接下来的日子可以经常报告这个CH小世界的情况，多多截屏。比如下周发现新进化出（设计出）了一个光吃不打的farmer类角色或者一个光打不吃的warrior类角色；又或者在下周某天我加入了一种新的食物类obj或者阻挡类obj，他们又会涌现（复杂系统？？）出某些行为模式出来。暂且将之后这类日志归入博客上的“CH世界大事记”一栏吧，嘿嘿。

[转自我的博客：http://xiaopplus.blog.163.com，实验正在继续，欢迎提出建议]

        2楼是一个简单试验，用以测试神经网络进化的基本算法
        3楼是尝试环境改变的试验
        17楼是近期的一个试验，尝试将NN的输入输出进一步连接上抽象的生物体器官，并且试图用一个简化的“发育”算法来增强“进化神经网络”的应用性，欢迎给出建议到：http://xiaopplus.blog.163.com/blog/static/4601920071114817135

XiaoP

这是上周开始的测试写的日志：

           
                                                            系统开始时的状态

           
           
                                                            10分钟后系统的状态

         星期六开始运行这个简单设置的环境，模拟个体所能获得的输入包括周围个体数目、自己的当前速度、角度、HP以及最近目标的相对位置，离目标越近HP减少得越慢，存活时间越长者适应度越高。系统中人口数为100，个体和基因一一对应。
         刚开始的情况是完全随机，模拟个体的大脑完全由各种随机的、最小结构的神经网络支持。

         上面的图是运行大概十分中后的截屏。左边的图中可以看到多于一半的个体开始有向目标移动的趋势，个体速度也由最初的随机值（基本上是很小的速度）趋向于较大值。从场景的分析可以得出，这是向全局最优解靠近的正确方向。

         再运行一段时间后（>1000秒），右边的图中可以看到部分优势个体除了向目标靠近外，到达目标后产生了“刹车”的趋势，以达到徘徊于目标附近的目的。这个结果就该场景而言已经很接近最优解了。



         这次试验发觉，对基本的NN（神经网络）进化而言，程序员仍然有一个工作要做，那就是得依据环境和个体的情况分析出NN的输入和输出，包括其个数和意义！可以联想到游戏中策划的这个工作也正是巨大的，如果设计一个NPC，得事先“规定”好它们的有效行为有哪些，它们的有效输出是什么。策划必须以专业知识指出哪些输入、输出是有用的，而且限于分析和程序承受量，还得尽量以最少的输入输出进行设计，即有效的“Feature Select”。对NN而言，输入和输出的个数增加特别是多余的输入和输出（比如现在我试验中的“周围个体数目”对完成任务的NN来说就是一多余输入），对NN的进化和执行性能均带来巨大负担！因此，FeatureSelect的工作就更加重要和繁重了。
        我尝试在系统中对NN的输入和输出不加以严格定义，将目前我能提供的所有信息全部作为NN的输入（达21个之多），目标位置检测采用在个体360度范围内均匀放置物体传感器（sensor）。类似于昆虫的复眼，每个传感器对相应方向上范围中的物体进行探测。

        根据遗传神经网络算法的特征，可以将“对输入的选择”本身也进行进化，从而找到合理的最小输入集！



        接下来的几天，我将对目标的位置进行随机的变换，看这些个体能否进一步学会追踪不同位置的目标；接着可能给个体增加一个“eat”的行为对应NN的一个新的输出，然后看试验结果。

XiaoP

         
        个体增加了“eat”动作，目标“food”可以被吃掉，然后随机在另外一个地方产生

       接上回的系统设定，这次我将场景中预置了100个“food”Object，每个food可以被吃掉，吃掉后的food在1秒钟后随机地在另外一个地方重生。个体增加一个输出用以激活“eat”行为，该行为在离最近的一个food 50单位的距离内生效，无效的eat行为会受到减hp的惩罚。eat行为成功后，个体将增加hp。不再以个体靠近food与否进行加分。
       这回我们看能设计出什么样的个体来！由于目前场景和个体行为简单，我们可以人工分析出最后最优个体的行为模式来比对！但是在将来复杂的环境，甚至本身就在进化的环境中，我相信个体行为会让我们大吃一惊的！



       加载上次运行的结果（个体大脑NN的基因），刚开始运行时可以看到大部分个体围着food打转，由于新输出的“eat”行为目前几乎随机产生，因此个体受到惩罚较大，死亡还是较快的。运行一段时间后，可以看到有些个体不但能“吃掉”身边的food，还能够在吃掉后赶紧跑到另外的最近food处继续。

       这里需要说明一下，GNN（进化神经网络）的优势是可以“记忆”之前的进化结果，即之前的基因结构被有效保留，个体在新的环境中可以利用旧的知识进行活动。因此可以看到，该系统中一个环境的逐渐改变能够导致物种的逐渐进化，如果环境突变，个体将大灭绝，这和自然界非常相似！从程序设计的角度讲，不会因为环境新的改变（food要消失并且在他处出现）和个体新的行为（增加eat行为）而从零开始去运行进化程序，个体基因（实际上就是代表该物种的设计）能适当地适应新的环境、正确发出新的行为，并且仍然能有效地继续优化（进化）。

       BTW，在前天的个体输入处理上（视觉传感器），我犯了一个极大的错误，没有考虑进个体当前的方向。现在据我分析，由于food目标的不变以及hp增减的算法固定，因此仍然能够进化出来像昨天那样的结果，即某种局部最优解。今天发现这个问题后我立即修正了ant的视觉传感器，天，其实在昨天的情况下，不到3分钟便能进化出相当高效的行动模式来了，而且更加真实合理。今天的新场景也能够相当快地进化出可观的结果（都是几分钟）。

明夕何夕

国外好像有一个游戏也是跟LZ贴的类似的，还获得过当年E3的最佳创意好像，好像是叫《孢子》
找了一下资料，06的E3上展出过的，EA出品，《Sim City》的制作人做的，好像delay了，要明后年才能推出- -

sftk

人工智能，很感兴趣的领域。。

遗憾的是目前国内没几个人认为有多大用，包括一些“顶尖”的程序员，如何在适用于网游是个需要考虑的问题

心灵震撼者

专业……闪了…………

nofear

这个属于前沿科学了，非常前沿，以至于还很不成熟。钱学森80年代以后就一直在研究这个领域。

至于那个《孢子》，据我所知，和复杂系统毫无关系，只是拿一些老掉牙的游戏形式放在同一个游戏里，再加了一些变化而已。

yrn0107

呵呵，刚好写了篇人工智能在游戏方面的应用报告，遗传算法很好，但做成普通游戏AI还不成熟，相比简单AI无法玩家无法明确的区分出来。

不过，可能的应用方向应该在模拟类游戏上，国外有款根据DNA来制作怪物战斗的网游好像用了这个，怪物的战斗
是通过玩家控制来学习，不过正式战斗时是AI，玩家无法控制的，游戏做成了电视节目，好像很受欢迎

XiaoP

    看来大家对这个还是很感兴趣啊^-^

    这几天工作较忙，另外我在设计类似生物通用的感受器和效应器，以期达到个体对输入和输出的进化选择，还不知道是什么效果。因此没有进一步考查复杂的环境（本来说要加入阻挡和攻击行为的）。

    我希望不再定义个体的概念（比如ant,human,warrior等等）、不再整个地将输入输出提供给个体选择（如前所述）。我希望个体能在进化中选择最适合自己的感受器作为输入，最适合自己的效应器作为输出，实际上是选择对环境最适合的。这样就NN而言可以达到最少的输入端和输出端，也可以在某种程度上表现个体的物理差异。如果将不同感受器和不同效应器用外形来美化，则我们可以准确的看到生物外形的变化和能力一致！之后我们可能看到“六条腿的生物”、“特大的生物”、“大量触角的生物”、“坚牙厉嘴的生物”，从直观上就可以给它们命名！我相信一条生物界的原则，任何自然界中的生物，其外形和表现均是为其竞争服务的！

    例如，这几天我将上面的试验抽象出来，个体的感受器可以有两种选择“能检测出特定类型的雷达（type related radar）”，“速度感受器（velocity sensor）”，这些感受器实现类似于NNRG的NERO项目，但是比他们更灵活。效应器有两种选择“驱动器（类似于靠左右加力来获得转角和速度）”，“取食器”。试验开始后，生物最初逐渐随机选择了一些感受器和驱动器，完全一片混乱（有些生物妄图对同伴激活自己的“取食器”，汗）。昨天发现，似乎不选择速度感受器的话，生物则不能较好地控制自己的加力。试验还在继续，会在这几天有个结果

漂泊的云

感兴趣。

呵呵，很有趣的东西。但是如果一切都自主进化了，那那玩家控制什么，玩什么。

现在大部分游戏的AI，还都是状态机吧。

之前看过涂晓媛博士介绍人工鱼的数，我觉得对游戏npc的设计思路有帮助。