资源描述：
《遗传算法在机器博弈中的创新应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、本栏目责任编辑：谢媛媛软件设计开发遗传算法在机器博弈中的创新应用徐阳东,刘弘(山东师范大学信息科学与工程学院,山东济南250014)摘要:解决机器博弈问题的传统方法是在博弈树上采用各种搜索算法,结合局面评估,来生成相应的走法。本文将遗传算法引入到人机博弈中来,通过对搜索树进行选择,交叉,变异等操作,得到可能包含更优解的博弈树,运用评估函数估值,从而产生当前局面下的最佳着法。关键词:遗传算法;机器博弈;搜索技术中图分类号:TP183文献标识码:A文章编号:1009-3044(2008)07-11275-04TheCreativeAppli
2、cationofGeneticAlgorithmsinMachineAdversarialXUYang-dong,LiuHong(SchoolofInformationScienceandEngineering,ShandongNormalUniversity,Jinan250014,China)Abstract:Usingadversarialsearchtechnologieswiththeevaluationfunctionandthencreatingmovegenerationsinthegametreeisthetradit
3、ionalmethods,whichisforsolvingtheproblemsofmachineadversarial.Thisthesisusesthegeneticalgorithmsinmachineadversarial.WiththeOperationsofselection,crossoverandmutation,wewillgetthebestoptimalsolutionsofthegametreeandhavethebestmoveofcurrentsituation.Keywords:geneticalgori
4、thms;machineadversarial;adversarialsearch1引言人工智能是一门正在迅速发展的综合性很强的科学。其中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作,有诸多的研究领域,机器博弈即为其中之一。机器博弈是一种完全知识博弈,即参与双方在任何时候都完全清楚博弈双方的局面与状态。五子棋、象棋等都属于完全知识博弈。完全知识博弈中典型方法是搜索博弈树以决定走哪一步。标准机器博弈包含四部分:(1)状态表示;(2)候选走法产生;(3)搜索方法;(4)一个确定相对优势状态的局面评估函数[1]。机器博弈的人
5、工智能体现在电脑通过基于局面评估函数的搜索算法从所有合法的候选走法中找到一个最佳走法,并由搜索算法做出选择[2]。2博弈树常用搜索算法解决机器博弈问题的传统方法是搜索树(博弈树)法。以机器下棋为例,首先要定义一棵有根的树(博弈树如图1,以五子棋为例),一个结点就代表棋类的一个局面,子结点就是这个局面走一步可以到达的一个局面。下棋过程中每走一步称为一个应对(着法),从当前棋局状态(根节点)出发,找出所有可能的应对(子节点),再从每个应对出发找出对方对应于每个应对的所有应对,⋯⋯,直到终局,由此构成一棵树,称为搜索树。在搜索树中通过估值找出
6、对自己最为有利的分枝,并选择该分枝的起点作为应对方案。这是一个指数复杂度问题,计算量之大是目前计算机无法承受的,为了提高搜索的效率,人们提出了各种改进方案。(1)最小最大值(Minimax)搜索算法:对搜索树局面评分(如图2),设博弈双方分别为MAX和MIN,MAX的任务是增加棋盘局面的评分,MIN的减少棋盘图1搜索深度为3的五子棋博弈树收稿日期:2008-01-24作者简介:徐阳东(1982-),男,硕士,主要研究方向:进化算法及应用;刘弘(1955-),女,博士,教授,博士生导师,主要研究方向:CSCW、多Agent系统、进化计算等
7、。1275软件设计开发本栏目责任编辑：谢媛媛局面的评分,且双方都走能让使局面对自己最有利的着法[3]。图2对搜索树局面评分(2)α-β剪枝搜索算法:Minimax搜索算法虽有所改进,但存在着较大的数据冗余,效率较低,于是人们在极大极小值的基础上,提出了α-β剪枝技术。即:只要有一步好的着法,就可将博弈树中其他不需要的应对分支剪掉,从而大大减少了搜索的范围。实际中α-β剪枝技术搜索效率还是不尽理想,在此基础上,又提出了搜索节点有序化和开局优化等改进算法[4]。但这些改进算法都无法从根本上解决搜索树的指数复杂度问题。为了进一步提高效率,人们
8、开始把遗传算法引入到机器博弈中。3遗传算法与机器博弈3.1遗传算法的基础知识1975[5],后经Goldberg全面年,美国密歇根大学John·H·Holland教授和他的同事研究了具有开创意义的遗传算法理
