下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 URTP申请正文_基于UCT搜索算法的亚马逊棋人机博弈软件解读

URTP申请正文_基于UCT搜索算法的亚马逊棋人机博弈软件解读.doc

URTP申请正文_基于UCT搜索算法的亚马逊棋人机博弈软件解读

何来地老天荒_
2017-11-13 0人阅读 举报 0 0 暂无简介

简介:本文档为《URTP申请正文_基于UCT搜索算法的亚马逊棋人机博弈软件解读doc》,可适用于活动策划领域

URTP申请正文基于UCT搜索算法的亚马逊棋人机博弈软件解读北京市大学生科学研究与创业行动计划立项申请书基于UCT搜索算法的亚马逊棋人机博弈软件的设计与实现团队成员:侯亮张婷学院:信息工程学院专业:计算机科学与技术指导老师:吴立成北京市大学生科学研究与创业行动计划立项申请正文目录一、立项依据„„„„„„„„„„„„„„„„„„„„„„„„„„亚马逊棋人机博弈的研究现状„„„„„„„„„„„„„„„„„项目可行性分析„„„„„„„„„„„„„„„„„„„„„„„学术价值„„„„„„„„„„„„„„„„„„„„„„„„„„团队优势„„„„„„„„„„„„„„„„„„„„„„„„„„二、研究目标、内容、关键问题及解决方案„„„„„„„„„„研究目标„„„„„„„„„„„„„„„„„„„„„„„„„„研究内容„„„„„„„„„„„„„„„„„„„„„„„„„„软件各部分简述„„„„„„„„„„„„„„„„„„„„„„„要解决的关键问题及解决方案„„„„„„„„„„„„„„„„„研究基础„„„„„„„„„„„„„„„„„„„„„„„„„„本项目的主要特色及创新之处„„„„„„„„„„„„„„„„„三、预期效果与具体成果„„„„„„„„„„„„„„„„„„„预期效果„„„„„„„„„„„„„„„„„„„„„„„„„„具体成果„„„„„„„„„„„„„„„„„„„„„„„„„„四、具体安排及进度„„„„„„„„„„„„„„„„„„„„„五、经费预算„„„„„„„„„„„„„„„„„„„„„„„„六、参考文献„„„„„„„„„„„„„„„„„„„„„„„„北京市大学生科学研究与创业行动计划立项申请正文一、立项依据亚马逊棋人机博弈的研究现状亚马逊棋(GameoftheAmazons)是由阿根廷人WalterZamkauska在年推出的两人棋类是欧美国家的一个棋种在亚洲并不常见它由国际象棋中后的走法衍生而来与著名的八皇后问题类似。亚马逊棋是计算机博弈(ComputerGames)的重要组成内容也是全国大学生计算机博弈大赛以及ICGA国际计算机博弈大赛的比赛指定棋类。年举行了国际电脑亚马逊棋锦标赛年亚马逊棋正式成为电脑奥林匹克大赛项目之一。在人类文明发展的初期人们便开始进行棋类博弈的游戏了。近几十年来随着计算机硬件和软件技术的不断发展人们开始对计算机能否战胜人脑这个话题产生了浓厚的兴趣。从开始电脑博弈便开始逐渐大规模地向人类智能发起了挑战到了年IBM超级电脑DeeperBlue击败了当时的国际象棋冠军卡斯帕罗夫成为了人工智能挑战人类智能发展的一个重要里程碑。然而计算机博弈在我国发展起步较晚年我国举办了首届中国象棋博弈大赛。在年举办的首届全国计算机博弈大赛中亚马逊棋被引入。亚马逊棋的棋盘由*的格子组成每方各拥有枚棋子(个Amazons)以不同的两色区分敌我每个棋子都相当于国际象棋中的皇后它们的行棋方法与皇后相同可以在八个方向(上、下、左、右、左上、左下、右上、右下)上任意行走但不能穿过阻碍当轮到一方行棋时此方只能而且必须移动四个Amazons中的一个并在移动完成后必须由当前移动的棋子释放一个障碍障碍的释放方法与棋子的移动方法相同(可在八个方向上释放但不能穿过阻碍)。当某方完成某次移动后使另一方四个棋子均不能再移动此时棋子不能移动一方将输掉比赛整个比赛中双方均不能吃掉对方或己方的棋子或障碍。正是由于这种特殊的走法规则导致了亚马逊棋每步的走法非常多平均在多种左右而且对大多数走法的评估也具有很大的不确定性。这些特点导致了亚马逊棋并不太适合人与人之间对弈但却非常合适用于人工智能、机器博弈方面的研究。当前亚马逊棋计算机博弈主要搜索算法有传统的负极大方法、剪枝算法、MC方法(即蒙特卡洛方法)、UCT算法、AlphaBeta搜索。其中UCT算法是机器博弈领域最新的搜索算法它很好的解决了传统搜索算法无法在亚马逊棋搜索中遍历更深层节点的问题。本软件就是基于UCT算法开发的亚马逊人机博弈程序通过提高对弈过程中计算机的搜索效率解决现有亚马逊PC博弈程序搜索时间长、运行速度慢的问题。北京市大学生科学研究与创业行动计划立项申请正文图亚马逊棋棋盘图亚马逊棋对局画面项目可行性分析项目组现已拥有大量亚马逊棋机器博弈的相关资料并且能继承和借鉴现有的亚马逊棋博弈程序的优点开发出效率更高、算法更精良的亚马逊博弈软件。大量资料表明MCUCT搜索算法在亚马逊棋搜索中能得到较好的运用。UCT是机器博弈领域最新的搜索算法它很好的解决了传统搜索算法无法在亚马逊棋搜索中遍历更深层节点的问题。JensLieberum在他自己的关于亚马逊棋评估的文章中,对亚马逊棋的评估方法做了详细的讨论这篇文章也是现在亚马逊棋评估方法的主要来源。项目组通过仔细研读相关文献对亚马逊棋博弈软件的研究有如下可行性分析。亚马逊棋的走法生成:亚马逊棋的走法分为两步首先要移动一个棋子然后由当前被移动的棋子放置一个障碍棋子的移动和障碍的放置都遵循皇后的走法所以在生成一步的所有可行走法时走法的结构中应该至少包括个数据:起点终点障碍放置点。由于亚马逊棋走法存在上述的特点导致每一步的可行走法数量十分庞大平均在多种左右第一步有种可行走法。亚马逊棋的局面评估:亚马逊棋的行棋目的是用障碍或自身棋子将对方棋子堵死使其不能移动而对于可以在八个方向任意行走的Queen来说将其堵死又谈何容易所以另一种思路则是圈地思想北京市大学生科学研究与创业行动计划立项申请正文用障碍或己方棋子为自己圈出足够大的地盘(对方棋子不能进入的区域)这样当自身获得足够的地盘时对方会因为没有地方可走而自己将自己堵死。现在用的主要是后一种控制区域(地盘)的思想当评估一个局面的好坏时主要看对方棋子控制的区域和己方棋子控制区域的多少至于什么样的区域算是己方的控制区域现在多数用QueenMove的方法。在对局初期当棋盘比较空旷时通过人的观察和判断很难确定一步棋的好坏。这时的亚马逊棋和围棋很相近都存在地盘的思想初期的许多走法更像是布局而非具体的争夺而到了对局的中后期当棋盘上的障碍逐渐增多每块地盘的形状已经明朗时亚马逊棋的行棋思路则又和象棋相近需要通过更深层的搜索来确定具体某块区域的争夺和归属情况。亚马逊棋的评估方式与围棋的不同点在于围棋更强调布局亚马逊棋则更为直观所以真人与电脑对局基本不会赢。亚马逊棋的搜索:、传统的负极大方法:用负极大方法为搜索的主体时由于亚马逊棋每步的可行走法数量十分庞大所以可以向下展开的层数很少两层就会有数百万个叶子节点。因此需要大量运用剪枝算法配合提前排序。、MC方法即蒙特卡洛方法:以蒙特卡洛方法为主体的搜索方法也在亚马逊棋中大量运用但与围棋中的MC方法不同的是亚马逊棋中的MC模拟并不模拟到局面的终了而是只模拟到一定的层数。、UCT算法:UCT算法源于围棋但同样使用于亚马逊棋。UCT方法是MC方法的发展它的实质是运用了这样一种思想就是尽量在有价值的节点上作较多的模拟对局什么是有价值的节点就是敌我对局时大家都愿意选择的节点这些节点的层层确定是通过minmax方法而这些节点的得分的获得则是通过MC方法所以UCT方法实际上是一种minmax和MC的混合使用MC模拟对局通过minmax确定路径(下一次对局选用的节点)从而使有限次模拟对局的结果更准确地反映出节点的性质。由于亚马逊棋的搜索空间很大、计算机难于处理模糊概念且难于设计学习算法造成了计算机亚马逊棋程序的搜索效率难以提高。还因为亚马逊棋特殊的规则导致了亚马逊棋平均每步的合法走法多达多种(第一步有种)如果仅向下搜索一层则所需要评估的所有节点数已经超过百万即使加入较好的剪枝算法亚马逊棋庞大的节点数仍然让传统的基于minmax的搜索方法望而却步。项目组通过对亚马逊棋的规则及算法的进一步研究吸北京市大学生科学研究与创业行动计划立项申请正文取并借鉴各搜索算法的优势为传统搜索算法无法在亚马逊棋环境中遍历更深层节点的问题找到解题的思路提高亚马逊棋人机博弈的算法效率。学术价值博弈是人工智能的重要研究主题人工智能的发展在很大程度上得益于博弈研究的发展。人类对机器博弈的研究衍生了大量的研究成果这些成果对更广泛的领域产生了重要影响。年著名的深蓝计算机战胜国际象棋世界冠军卡斯帕罗夫成为轰动一时的新闻事件。人工智能的先驱们曾认真的表明:如果能掌握下棋的本质也许就掌握了人类智能行为的核心那些能够存在于下棋活动中的重大原则或许就存在于其它任何需要人类智能的活动中。亚马逊棋近几年才传入我国是全国大学生计算机博弈大赛以及ICGA国际计算机博弈大赛的比赛指定棋类。目前在我国亚马逊棋的算法研究和搜索分析还只是刚刚起步亚马逊棋的算法研究和开发还有很广阔的空间。亚马逊棋不仅为检验人工智能发展水平提高了良好环境还有助于加强对人类认知能力的理解而且更能进一步推动计算机博弈理论的发展把亚马逊棋人人对弈的局面转到可以人机大战上来并且这对宽带娱乐、棋类教学也是非常有意义和帮助的所以亚马逊棋计算机博弈研究具有重要的理论意义和实用价值。团队优势:本团队共有两名成员全部来自计算机科学与技术专业。有着良好的专业知识基础比较好的数学基础以及软件工程基础能够熟练运用C、JAVA等高级语言为软件实现打下良好的基础。并具有较强的实践能力和创新精神在以前参赛过程中通过长期的培训和不断努力培养了团队成员坚持不懈和迎难而上的科研精神。、项目组成员成绩优秀获得过“中央民族大学专业二等奖学金”和“信息工程学院电子设计大赛一等奖”等理论知识和实践操作能力都非常优秀指导老师长期从事机器人学、智能控制、轨迹规划及试验平台研制等方面的研究在电子电路设计与软件开发方面有着多年的实践经验。曾指导本科生课外科技活动获清华大学挑战杯二等奖、“创新奖”及“最佳展示奖”(水上漂浮机器人)及“浪潮杯”首届中国计算机博弈锦标赛“新秀奖”(“棋乐无穷”象棋博弈软件)以及“北科杯”首届全国大学生计算机博弈大赛暨第五届全国计算机博弈锦标赛优秀指导教师奖和六子棋比赛“二等奖”。北京市大学生科学研究与创业行动计划立项申请正文二、研究目标、内容、关键问题及解决方案研究目标本项目将用JAVA语言开发一套亚马逊棋的人机博弈软件通过使用UCT搜索算法使博弈引擎合理优化并完成对系统的调试、测试及人机对战演练最终实现一个高水平棋力的亚马逊棋人机博弈软件。研究内容博弈界面的设计。包括对弈界面、菜单选项等的设计同时嵌入音效、动画等功能。在编程语言方面我们选择用JAVA语言进行开发它不仅具有高移植性并且拥有强大的界面制作工具和组件在界面制作方面更具有优势。搜索引擎的设计与优化。对已有的多种搜索算法进行测试、分析、调整选择并设计出最适合本博弈软件的搜索引擎我们主要采用UCT搜索算法提高软件的搜索效率。软件的调试与测试通过手动调整、自动对战、人机对战等方法对该博弈软件进行测试和优化对众多的参数权值、估值方式进行调整。软件各部分简述设计的计算机亚马逊棋博弈软件主要包括:棋盘生产、着法产生、搜索算法、估值核心四大部分。棋盘表示(BoardRepresentations)为了能快速获取个棋子的位置坐标本项目将采用*二维矩阵表示棋盘用~进行棋盘位置编码。并根据对称性对双方棋子进行编码以方便对其进行估值等操作。着法生成(MoveGeneration)软件运行时需要进行频繁、复杂的判断和搜索才能确定着法该过程是软件性能的瓶颈。着法生产模块主要解决如何快速高效地确定当前局面可能有的几十种甚至几百种着法中的最优着法的问题。本项目将采用棋盘扫描法、模板匹配法和预置表法等着法生产函数来找到一种最优的着法。评估函数(atuationFunction)对当前局面进行估值是不可缺少的它影响着博弈局势发展的趋势。我们用评估函数来对当前局面的好坏做出判断和打分。如果这个评价是不够准确甚至是有错误的那么即使搜北京市大学生科学研究与创业行动计划立项申请正文索深度很深也往往要在对战中失利。因此本项目将对传统的子力估值、棋子位置估值、棋子灵活度估值、基于QueenMove和KingMove的评估等估算函数进行研究、改进以实现对局面的更精确估值从而提升软件的性能。搜索技术(searchTechniques)为了找到评值最高的状态得到最有利的着法必须找到高效、快速的搜索算法。这是博弈程序的核心也是博弈成败的关键。传统的蛮力深度优先搜索算法只能搜索到很浅范围内的局面棋力不高。本项目将对适合亚马逊棋的UCT搜索算法和进行深入研究并结合搜索的时间及空间复杂度争取研发出更加精确地着法搜索引擎。开局库(OpeningBook)即根据人类长期的实战经验得出的定势做成开局库供程序在开局时查询和使用对给定的局面给出快速、合适的着法。开局库的类型分为树型和局面型本项目将采用哈希技术加以实现。要解决的关键问题及解决方案、UCT搜索算法在亚马逊棋中的运用UCT算法源于围棋但同样使用于亚马逊棋只是在将围棋中的算法复制到亚马逊棋中时会有一定的变化。基本步骤:由当前局面建立根节点生成根节点的子节点()(从根节点开始()(利用UCB公式计算每个子节点的UCB值选择最大值的子节点()(若此节点不是叶节点则从此节点开始重复()()(直到遇到叶节点如果叶节点曾经被模拟对局过次为这个叶节点生成子节点从此节点开始重复()()(否则对这个叶节点进行模拟对局得到胜负结果将这个收益按对应颜色更新到该节点及它的每一级祖先节点上去()(回到()除非时间结束或者达到预设循环次数()(从根节点的子节点中挑选平均收益最高的作为最佳点UCB公式:北京市大学生科学研究与创业行动计划立项申请正文ln()parentcountUCBX=k*nodecountX:由模拟对局输赢次数决定表现该节点基本性质k:常数系数k取大表示希望模拟更多的兄弟节点取小表示希望走入更深的层中parentcount:父节点被模拟对局的次数nodecount:该结点被模拟对局的次数。亚马逊棋中使用UCT算法需要额外确定的一些参数和变化:()节点被模拟多少次后决定展开:当一个节点被模拟对局一定次数后才能初步得到此节点的统计学信息并展开节点。()提前剪枝:亚马逊棋中每步的着法过于庞大一般在步左右而许多着法可以很容易的判定为垃圾所以一般进行提前剪枝保留步左右的着法。()决定展开节点后子节点需要用提前剪枝后的顺序排列并且并不生成所有的子节点而是按顺序先生产一定数量的子节点在父节点的访问量突破一定数量时再决定下一步生产的子节点。()模拟对局层数的决定:一般选择至层。()底层评估方法:一种为返回输赢一种为返回输赢程度。(开局库的设计亚马逊棋人机博弈开局库数据量相当大且是完善的博弈软件中不可缺少的一部分为了减少程序占用的存储空间、精简程序内容如何对这些大量的数据进行压缩、裁剪同时保证一定高水平的棋力是另一个需要解决的重要问题。研究基础收集并整理了国内外关于亚马逊棋人机博弈相关方面大量的研究资料对亚马逊棋人机博弈的发展历史、发展现状以及现在开发的难点和关键问题有了较详细的了解。掌握现有的亚马逊棋PC人机博弈软件的C源代码并已对其性能、算法和优缺点进行了详细的分析明确了下一步的开发方向。对其他棋类的PC博弈软件的开发流程作了较详尽、深入的分析和研究基本掌握了软件开发的基本方法、流程及开发工具的使用为本次程序的开发提供了一个很好的参考。北京市大学生科学研究与创业行动计划立项申请正文本项目的主要特色及创新之处项目成果是一款能在计算机上运行并具有能和高水平棋手对弈棋力的亚马逊棋博弈软件。通过对搜索引擎的优化设计采用高效的MCUCT搜索算法提高对弈过程中计算机的搜索效率解决现有亚马逊PC博弈软件搜索时间长、运行速度慢的问题。本软件采用JAVA语言编写。JAVA语言是一种相当简洁的“面向对象”程序设计语言。它省略C语言中所有的难以理解、容易混淆的特性例如头文件、指针、结构、单元、运算符重载、虚拟基础类等。它更加严谨、简洁并且JAVA语言还具有高移植性。使用JAVA编程语言编写的程序只要做较少的修改甚至有时根本不需修改就可以在不同平台上运行。对PC博弈软件界面及功能进行合理优化保证程序在计算机中运行的良好性能。在人机对弈情况中减少用户等待时间使博弈软件更加人性化、智能化。三、预期效果与具体成果预期效果所开发的亚马逊棋PC博弈软件能在计算机上运行有较为人性化操作功能和友好的界面。本博弈软件能使用开局库并对开局进行特殊的处理和开局库的合理优化。所开发的亚马逊棋PC博弈软件用JAVA语言编写具有较高的棋力并且能实现局面估算搜索的演示与验证。程序采用高效的MCUCT搜索算法能与高水平的亚马逊棋爱好者对弈搜索效率高、运行速度快。具体成果(高棋力亚马逊棋PC博弈软件套(研制报告一份包括系统总体及各部分的设计书、软件源代码、仿真文件以及试验结果等。北京市大学生科学研究与创业行动计划立项申请正文四、具体安排及进度软件的设计和编写:,原有亚马逊棋程序的消化,计算、测试估值函数的准确性,测试选择最优的搜索算法并组成搜索引擎,软件代码编写:、界面开发第一阶段、搜索引擎代码编写(个月)、算法代码实现、组员共同讨论对程序的优化和完善。,对软件整合后进行运行测试解决运行中发现的问题并修改不便之处,检验运行成功软件初成品开发完成。系统的初测试:让系统与性能低的亚马逊棋软件博弈大约对弈到局记录第二阶段全部对弈数据(个半月)让系统与性能高亚马逊软件对弈记录全部对弈数据系统优化:,分析前期系统与各亚马逊棋软件的对弈数据列出具体的缺陷和不足第三阶段,借鉴其他软件的优势修改和补充系统的缺陷和不足再次提高系统(个月)的性能,通过和其他软件进行对比优化操作界面使操作更人性化。人机博弈:第四阶段,请棋手与系统进行对弈测试系统的性能(半个月),咨询棋手了解系统的性能、界面和软件是否存在“低级错误”。项目总结:第六阶段,总结整个项目的开发过程和经验(个月),撰写论文和研究报告。五、经费预算项目说明经费购买其他高水平PC亚马逊软件和与开发的亚马逊软件购买人机博弈软件进行对弈测试。计划有:KadonEnterprises开发的“Amazons”购买书籍、论文及影印资料费等。资料费赴外地参加计算机博弈大赛差旅交通费火车票:*=北京市大学生科学研究与创业行动计划立项申请正文食宿费:*=市内交通费:参加全国大学生计算机博弈大赛报名费参赛报名费总计六、参考文献乔治,黄鸿亚马逊棋博弈技术研究R北京理工大学,JensLieberum:AnevaluationfunctionforthegameofamazonsTheoreticalComputerScience()JConway:OnNumbersandGames,AcademicPress,NewYork,RichardJLorentz:AmazonsDiscoverMonteCarloDepartmentofComputer,USAScience,CaliforniaStateUniversity,NorthridgeCAJulienKloetzer,HiroyukiIida,andBrunoBouzy:TheMonteCarloApproachinAmazonsResearchUnitforComputersandGamesJapanAdvancedInstituteofScienceandTechnology书中横卧着整个过去的灵魂卡莱尔人的影响短暂而微弱书的影响则广泛而深远普希金人离开了书如同离开空气一样不能生活科洛廖夫书不仅是生活而且是现在、过去和未来文化生活的源泉库法耶夫书籍把我们引入最美好的社会使我们认识各个时代的伟大智者史美尔斯书籍便是这种改造灵魂的工具。人类所需要的是富有启发性的养料。而阅读则正是这种养料雨果

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/15

URTP申请正文_基于UCT搜索算法的亚马逊棋人机博弈软件解读

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利