试析基于uct算法的非完备信息多人军棋博弈系统

《试析基于uct算法的非完备信息多人军棋博弈系统》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、工学硕士学位论文基于UCT算法的非完备信息多人军棋博弈系统张加佳哈尔滨工业大学2008年12月国内图书分类号：TP393.1国际图书分类号：621.3工学硕士学位论文基于UCT算法的非完备信息多人军棋博弈系统硕士研究生：张加佳导师：王轩教授申请学位：工学硕士学科、专业：计算机科学与技术所在单位：深圳研究生院答辩日期：2008年12月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP393.1U.D.C:621.3DissertationfortheMasterDegreeofEngineeringUCTAlgorithminImperfectInfo

2、rmationMulti-PlayerMilitaryChessGameCandidate:ZhangJiajiaSupervisor:Prof.WangXuanAcademicDegreeAppliedfor:MasterofEngineeringSpecialty:ComputerScienceAffiliation:ShenzhenGraduateSchoolDateofDefence:Dec,2008Degree-Conferring-Institution:HarbinInstituteofTechnology摘要摘要博弈游戏的分类方法之一是根据其游戏的

3、参与者是否拥有完备的游戏信息。据此，博弈游戏可以被分为完备信息博弈和非完备信息博弈两个大类。在非完备信息博弈过程中，每个游戏者拥有自己单独的信息集，也就是说，他只拥有整个游戏的部分信息。围绕着完备信息博弈的研究已经取得了相对成熟的结果。很多人工智能程序的核心架构是：当电脑走棋的时候，根据当前棋局创建一个部分的博弈树，利用估值函数对叶结点进行估值，通过估值的结果来进行极大极小值搜索，找到一个在根结点的最佳走步。然而，迄今为止非完备信息下的非常成功的人工智能博弈程序很少。非完备信息博弈问题的解决技术和完备信息有很大的差异，应用于完备信息的技术不一定能够成功的应用到非完

4、备信息博弈中。蒙特卡罗抽样算法是现今应用于非完备信息博弈中的一个基本方法，它通过随机抽样将非完备信息博弈问题转换为完备信息博弈问题，同时通过大规模的抽样次数来逼近真实的情况。该方法在一些非完备信息博弈游戏中，例如Alberta的桥牌程序，已经取得了较好的效果。UCT(UpperConfidenceBoundApplytoTree)：应用于博弈搜索树的上限置信区间算法。这种新兴的搜索算法采用以上限置信值为依据的先深于先广搜索相结合的方法，在超大规模博弈树的搜索过程中相对于传统的搜索算法有着时间和空间方面的优势。在与风险评估模型相结合的基础上，可以在可控的时间内得到当

5、前局势下的相对较优的解决方案。本文探讨了UCT算法在非完备信息博弈中超大规模搜索树搜索过程中的应用，并基于该算法结合蒙特卡罗抽样技术和风险评估模型实现了一个具有自动网上挂载功能的四国军棋博弈系统。本文的主要研究成果和创新之处在于：1．实现了UCT搜索算法，并将之应用为博弈系统的搜索核心。提高了系统的搜索速度和深度；2．进一步扩充和精确化了四国军旗博弈中的蒙特卡罗抽样技术；3．在已有四国军棋的框架系统上，将蒙特卡罗抽样技术、UCT算法和一个简单的风险模型有效结合成了一个具有更强的博弈能力和更高的人工智能水平的新系统。I哈尔滨工业大学工学硕士学位论文4．新的四国军棋系

6、统可以自动挂载到网络和人类玩家进行博弈，该功能解决了系统棋力客观评估的问题，同时使大规模博弈过程以及对局信息数据库的建立成为了可能。关键词：UCT算法；非完备信息博弈；蒙特卡罗抽样；风险评估模型；自动博弈II摘要AbstractOneofthewaysinwhichgamesareclassifiediswhetherornottheyareperfectorimperfectinformationgames.Inanimperfectinformationgame,theplayershavenon-singletoninformationsetwhichmea

7、nstheyhaveonlypartialknowledgeaboutthestateofthegame.Therehavebeensomerelativematureapproachesonperfectinformationgames.Whenitisthecomputer’sturntomove,itcreatessomepartofthegametreestartingatthecurrentposition,evaluatestheleavesofthispartialtreeusinganevaluationfuncion,andthendoesami

8、nimax