幻影围棋非完美信息机器博弈问题关键算法研究

《幻影围棋非完美信息机器博弈问题关键算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文幻影围棋非完美信息机器博弈问题关键算法研究作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：李洪业马宗民教授东北大学信息科学与工程学院硕士学科类别：工学计算机软件与理论2014年6月论文答辩日期：2014年6月2014年7月答辩委员会主席：王兴伟乔建忠、李贵东北大学2014年6月万方数据AThesisinComputerSoftwareandTheoryStudyonKeyAlgorithmsforGameswithImperfectInformationandPhantomGoB

2、yLiHongyeSupervisor：ProfessorMaZongminNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：西恢丝H期：∥彩一石^>7学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校

3、有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口学位论文作者签名：李l多＼也签字日期：wf弘一5／歹]豁郑飙例旷伊7民．衫央阿垦两孙签币Jiy万方数据东北大学硕士学位论文摘要幻影围棋非完美信息机器博弈问题关键算法研究摘要机器博弈是人工智能领域‘一个既古老义具有挑战的问题，为人工智能成果的验证提供丫‘个良好的平台。非完美信息博弈问题是机器博弈问题的‘一个重要的分支，由于这类博弈问题

4、具有非完美信息，即参与者需要在只知道对手的部分信息的情况下做决策，因此，更接近现实世界中的决策问题，具有更高的研究价值。本文针对非完美信息博弈n_】j题的关键算法进行了研究，尤其是具有大空问和高复杂度的非完美信息拓展型博弈问题，并在幻影刖棋中对本文提⋯的算法的性能进行了分析，比较了不同算法的效果。本文以非完美信息拓展型博弈问题为挂础和基本模型，给fI：了基于信念状态的非完美信息博弈问题的数学模型。在此模型的基础，卜，对非完美信息博弈问题的关键算法进行研究，提出了利用信念状态树的数据结构表示非完美信息博弈问题的博弈过程，以蒙特卡洛树搜索算法为基础，

5、提出了信念状态．蒙特卡洛树搜索算法并应用于处理具有非完美信息的博弈决策问题。本文在信念状态．蒙特卡洛树搜索算法的基础上，提出了两种基于对手模型的信念学习算法，分别是基于部分偏执的信念学习算法和基于随机最优反应估计的信念学习算法，旨往利用非完美信息博弈问题的隐藏信息通过建立对手模型的使参与者获得更高的收益。之后，将信念状态一蒙特卡洛树搜索算法应用到幻影围棋搏弈IⅥ题一卜’1提出了幻影围棋博弈问题I{I信息的处理方法，并结合幻影围棋博弈问题的特，k给出了基于信念状态一蒙特卡洛树搜索算法在幻影围棋博弈问题中的改进算法进行了研究，提出了j三种改进算法，包

6、括混合策略、AMAF启发算法和信息探测。最后，在幻影围棋博弈问题下，对信念状态．蒙特卡洛树搜索算法的性能进行了分析，对两种信念学习算法的性能和效果进行了分析和对比，并且，对基于幻影围棋博弈问题的改建算法的效果进行了测试。关键词：非完美信息博弈；幻影围棋；对手模型；蒙特卡洛树搜索：信念状态万方数据东北大学硕士学位论文AbstractStudyonKeyAlgorithmsforGameswithImperfectInformationandAbstractComputergameisanancientandchallengingtopicinAIf

7、ield，whichformsagoodtestingplatformforAI．Theimperfectinformationgameisanimportantsubfieldofcomputergamesandisaproblemthatisworthresearching，forthatplayerscanreadonlypartoftheinformationaboutopponents，SOitismoreclosetodecision—makingproblemsinrealworld．Thisthesisstudieskeyalgo

8、rithmsforgameswithimperfectinformation，especiallyforthosewithlargesc