UCT算法
UCT算法（Upper Confidence Bound Apply to Tree），即上限置信区间算法，是一种博弈树搜寻算法，该算法将蒙特卡洛树搜寻(Monte—Carlo Tree Search，MCTS)方法与UCB公式结合，在超大规模博弈树的搜寻过程中相对于传统的搜寻算法有着时间和空间方面的优势。
基本介绍
- 中文名：上限置信区间算法
- 外文名：Upper Confidence Bound Apply to Tree
- 别称：树图置信算法
- 提出者：Levente Kocsis与Csaba Szepesvári
- 提出时间：2006
- 套用学科：计算机科学
- 适用领域範围：计算机博弈
提出
早些年．计算机博弈对于棋类游戏的研究集中在基于模式识别和专家系统的方法上(最典型的是基于静态评估函式的仅一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 =
。 UCT 算法与传统搜寻技术的最大区别在于不同的分支可以有不同的搜寻深度， 如图 2 所示。 UCT 算法在不同的深度获取评估值． 对于最有“ 希望”求解问题的分支， UCT 算法的搜寻深度可以很深（ 远大于 d）， 而对于“ 希望” 不大的分支， 其搜寻深度可以很浅（ 远小于 d） 。 当最有“希望”求解问题的分支数量远少于“ 希望” 不大的分支数量时， UCT 算法就可以把搜寻资源有效地用于最有“希望”求解问题的分支， 从而获得比传统搜寻算法更深的有效深度 d′。这个具有神奇力量的“希望”是由树内选择策略计算的．从根节点开始， 对于每一个非叶子节点 n的孩子
∈ ch（ n） ， 树内选择策略计算一个评估值
， 并根据 值选择一个孩子节点进行下一步选择， 直到到达叶子节点。 如果当前节点为最大节点（ Max Node） 时， 树内选择策略选择 值最大的孩子进行下一步选择； 如果当前节点为最小节点（ Min Node） 时， 树内选择策略选择 值最小的孩子进行下一步选择。 的计算公式是：
图1 α－β剪枝
图2 UCT算法 =
式中：
是以节点 为根节点的子树的所有仿真结果的平均值， 反映了根据目 前仿真结果观测到的节点 能提供的回报值的期。
是节点 的访问次数， 也是节点 被树内选择策略选中的次数。
是节点 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 值． 其公式为：
=
即父节点的访问次数 T是所有子节点访问次数 之和， 观测回报值 v 是所有子节点观测回报值
的加权平均， 权值为子节点被访问的比例
． 结果回传从叶子节点开始， 沿搜寻路径逐级向上更新， 直到根节点。