设为首页 - 加入收藏
广告 1000x90
您的当前位置:二四六天天好彩308K文字资料 > 博弈树搜索 > 正文

UCT算法

来源:未知 编辑:admin 时间:2019-07-01

  声明:百科词条人人可编辑,词条创建和修改均免费,绝不存在官方及代理商付费代编,请勿上当受骗。详情

  UCT算法(Upper Confidence Bound Apply to Tree),即上限置信区间算法,是一种博弈树搜索算法,该算法将蒙特卡洛树搜索(Monte—Carlo Tree Search,MCTS)方法与UCB公式结合,在超大规模博弈树的搜索过程中相对于传统的搜索算法有着时间和空间方面的优势。

  早些年.计算机博弈对于棋类游戏的研究集中在基于模式识别和专家系统的方法上(最典型的是基于静态评估函数的仅一B博弈树方法),并在国际象棋、中国象棋等项目中获得了成功。但是对于围棋类的项目,传统的方法一直无法取得满意的结果。在2000年前后,世界上最高水平的计算机围棋软件的棋力还比不上人类的业余初段。

  围棋作为一种特殊的完备信息博弈,由于其本身的非完备特性,也成为了蒙特卡罗方法应用的载体之一。但是,由于围棋的复杂度高,且极具欺骗性,对计算机程序提出了巨大的挑战。为了处理如此众多的可能情况,人工智能专家已经设计出一些算法,来限制搜索的范围,但它们都无法在大棋盘的比赛中战胜实力稍强的人类棋手。2006年秋季,两位匈牙利研究人员报告了一种新算法,它的胜率比现有最佳算法提高了5%,能够在小棋盘的比赛中与人类职业棋手抗衡。这种被称为UCT(UpperConfidenceboundsappliedtoTrees)的算法,是匈牙利国家科学院计算机与自动化研究所(位于布达佩斯)的列文特·科奇什(LeventeKocsis)与加拿大阿尔伯塔大学(UniversityofAlberta,位于埃德蒙顿)的乔鲍·塞派什瓦里(CsabaSzepesvári)合作提出的,是著名的蒙特卡罗方法(MonteCarlomethod)的扩展应用。

  法国南巴黎大学的数学家西尔万·热利(SylvainGelly)与巴黎技术学校的王毅早(YizaoWang,音译)将UCT集成到一个他们称之为MoGo的程序中。该程序的胜率竟然比先前最先进的蒙特卡罗扩展算法几乎高出了一倍。2007年春季,MoGo在小棋盘的比赛中击败了实力强劲的业余棋手,在大棋盘比赛中也击败了实力稍弱的业余棋手,充分展示了能力。热利认为UCT易于实现,并有进一步完善的空间。科奇什预言,10年以后,计算机就能攻克最后的壁垒,终结人类职业棋手对围棋的统治。

  哈工大深圳研究生院智能计算中心也是国内最早探索非完备信息博弈的机构之一。经过3年的研究,已经取得了一定成功,并在此基础上开发了一套拥有完整人机交互界面并具有较强智能水平的四国军棋博弈系统。

  由于围棋有很大的分支系 数(BranchingFactor),传统搜索技术一直没有在计算机围棋领域取得有意义的成果 ,2006 年 UCT算法改变了 这种 局 面。UCT算 法是一种特殊的蒙特卡洛搜索算法,它由树内选择策略、缺省仿真策略和仿真结果回传三部分组成。

  如图 1所示, 传统搜索技术都有搜索深度 d 这个参数. 当搜索达到深度

  d 时, 搜索算法从评估函数取得评估值, 而搜索算法负责找到让评估值最大的分支。 这种在同一深度 d 获取评估值的方式, 让搜索深度d, 分支系数 b,与搜索树叶子节点数 N 的关系为 N =

  值选择一个孩子节点进行下一步选择, 直到到达叶子节点。 如果当前节点为最大节点( Max Node) 时, 树内选择策略选择

  值最大的孩子进行下一步选择; 如果当前节点为最小节点( Min Node) 时, 树内选择策略选择

  为根节点的子树的所有仿真结果的平均值, 反映了根据目 前仿真结果观测到的节点

  是节点 n 的访问次数。c 是一个手工设定的常数。 c 的作用是平衡 UCT 算法的利用需求(exploitation)和探索需求( exploration)。

  当搜索到达叶子节点时, UCT 算法执行扩展操作( Expansion): 把此叶子节点允许的所有合法下一步产生的子节点, 作为新的叶子节点加入到搜索树中, 并正确初始化其 v 值和 T 值。 UCT 算法并没有使用额

  外的评估函数来获取新叶子节点的评估 v 值, 而是使用缺省仿真策略来继续搜索直到游戏进入结束状态。此时, 棋盘上每一个位置都有明确的归属, 黑方赢还是白方赢可以很容易地计算出 来. 叶子结点的评估值就是当黑方胜时为 1, 白方赢为 0。 最简单的缺省仿真策略就是在所有的合法下一步中, 均匀地随机选择下一步。 用随机策略作为缺省仿真策略产生的程序棋力不高, 因此大多数棋力不错的程序都采用了更加复杂的缺省仿真策略。 这些实际使用的缺省仿真策略, 考虑了气( liberty ) 、形(pattern ) 、定式( joseki ) 、攻击模式

  ( attack patterns ) 、防守模式( defense patterns ) 等一些重要的围棋基本概念。 此外, 为了获得更加可靠的评估值, 每次到达叶子结点, UCT 算法可以使用 k 次仿真的平均结果作为评估 v 。 k 的值可以是几百或者几千。

  当叶子节点通过仿真获得新的 v 值和 T 值时, UCT 算法通过结果回传更新搜索路径上的所有内部节

  点( internal nodes ) 的 v 值和 T 值. 其公式为:

  我们可以在算法执行过程中的任何时间突然终止算法,UCT 算法可以返回一个差不多理想的结果。当然如果给与更为充分的时间的话,算法结果会非常逼近实际的最优值。但是这一点在 alpha-beta 搜索中是绝对行不通的。图 3-3 展现了如果我们突然中断 alpha-beta 搜索程序,某些处于根节点之下的第一层的节点都还没有被计算,这样的结果时此时 alpha-beta 搜索程序的返回结果很有可能和实际地最优解相去甚远。而图 3-2 是一个典型的中断时的 UCT 搜索树的情况,我们可以通过两幅图片的比较看出 UCT 算法的时间可控性的原因。当然,传统的搜索算法也有一些优化策略来增加其时间可控性,例如设置初始化搜索深度。但不可否认的是,UCT 的任意时间终止特性更加强大,这可以使它在应用于特定的博弈系统中的时候能够非常方便的控制走步产生的最大时间。这是传统的搜索算法所无法比拟的。

  这是因为它使用一种平滑的方式处理搜索过程中的不确定性。在每个节点,其计算值取决于它的搜索节点序列上的所有子节点的计算值,其值是一个经过平滑的最大值的估计值。这样,由于每个子节点的计算过程都经过重新的抽样计算,不会因为个别严重偏离事实的抽样结果而对最终的结果产生致命性的影响。同时,由于算法在确定计算的节点序列时,依赖于第一层子节点的估值以及该估值的可信度。也就是说,如果某一个子节点有一个远大于其他子节点的估值,那么相对于其他节点,它就有机会更为频繁的被搜索和计算,UCT 算法对这个“最大值”节点会进行最为频繁的搜索。在非完备信息博弈问题的条件下,与蒙特卡罗抽样算法相结合的 UCT 算法中,频繁的搜索意味着频繁的抽样,而大量的抽样次数正式保证估计值能够尽量逼近真值的唯一途径。同时,如果有两个子节点拥有相近的估值并大于其他节点,那么 UCT 算法会均衡的对两个节点进行搜索。这样的搜索方式有一个优势,那就是 UCT 算法最后的作为搜索结果的节点以及次优节点一定是经过多次抽样的具有较高估值可信度的节点。

  这样做有两个好处。首先,传统的博弈树扩展方式,仍然以 alpha-beta搜索树为例,每向下扩展一层都意味着博弈书规模的指数型增长以及搜索时间的指数型增加。对于内存和 CPU 性能都有限的个人电脑来说,这一问题有的情况下是致命的。而在 UCT 算法搜索过程中,每次对于更深一层的扩展仅局限于搜索序列的最后一个节点。这样的 UCT 算法可以在扩展节点的同时不断的动态释放计算过的节点内存,使得算法运行的时间复杂性和空间复杂性可以被更好的控制。其次,正因为上述特性,对于较好的作为被选候补的节点,算法往往可以进行更为深入的搜索,这点可以在图一中体现出来,同时,这种非对称性扩展完全是在算法的执行过程中自动进行的。因此,和传统的博弈树算法相比较,UCT算法有着其独有的优势,特别是当博弈树规模非常大的时候。UCT算法首次应用的围棋博弈系统,以及本文即将讨论的四国军棋博弈系统都属此例。因此,UCT搜索算法在本系统中的使用是切合实际的。

  2006年第一个基于UCT算法的围棋程序MoGo在9×9棋盘上达到了专业棋手的水平。

  2009年8月基于UCT的开源程序Fuego在9×9棋盘上战胜了周俊勋九段。

  2012年6月计算机围棋程序Zwn19S在19×19棋盘上达到了KGS的6段评级。

  2013年3月围棋软件CrazyStone在受让四子的情况下。战胜日本棋手石田芳夫九段,其棋力已达到业余五、六段的水平。

  1997年,美国超级计算机“深蓝”以2胜1负3平战胜了当时世界排名第一的国际象棋大师卡斯帕罗夫。“深蓝”的运算能力当时在全球超级计算机中居第259位,每秒可运算2亿步。

  在今天看来,“深蓝”还算不上足够智能,主要依靠强大的计算能力穷举所有路数来选择最佳策略:“深蓝”靠硬算可以预判12步,卡斯帕罗夫可以预判10步,两者高下立现。

  比赛中,第二局的完败让卡斯帕罗夫深受打击,他的斗志和体力在随后3局被拖垮,在决胜局中仅19步就宣布放弃。

  2006年,中国超级计算机“浪潮天梭”同时迎战柳大华、张强、汪洋、徐天红、朴风波5位中国象棋特级大师。在2局制的博弈中,浪潮天梭以平均每步棋27秒的速度,每步66万亿次的棋位分析与检索能力,最终以11:9的总比分险胜。

  张强坦承:“以往和人比赛,到了最后时刻就是意志和心态的对决了,看谁能坚持到最后,谁能不犯错误。但是计算机没有这样的问题。”

  2011年,“深蓝”的同门师弟“沃森”在美国老牌智力问答节目《危险边缘》中挑战两位人类冠军。虽然比赛时不能接入互联网搜索,但“沃森”存储了2亿页的数据。“沃森”可以在3秒内检索数百万条信息并以人类语言输出答案,还能分析题目线索中的微妙含义、讽刺口吻及谜语等。“沃森”还能根据比赛奖金的数额、自己比对手落后或领先的情况、自己擅长的题目领域来选择是否要抢答某一个问题。“沃森”最终轻松战胜两位人类冠军,展示出的自然语言理解能力一直是人工智能界的重点课题。

本文链接:http://mzi-ads.com/boyishusousuo/615.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top