人工智能–AlphaGo浅析（3）

人工智能之AlphaGo浅析(3)

前言： 蒙特卡罗树搜索MCTS在AlphaGo（阿尔法狗）中起着举足轻重的作用,MCTS是一个算法框架而非具体的算法,而具体实现的算法是UCT(置信上界树搜索)算法！

上一篇，我们知道在AlphaGo框架中，蒙特卡罗树搜索MTCS是用来快速评估围棋棋面位置价值的,蒙特卡罗树搜索MTCS中非常著名的一个算法是UCT(置信上界树搜索)算法。

今天就跟大家介绍一下UCT(置信上界树搜索)算法。

早些时候，计算机博弈对于棋类游戏的研究集中在基于模式识别和专家系统的方法上，在国际象棋、中国象棋等项目中获得了成功。但是对于围棋来说，这些传统方法一直无法取得满意的结果。

围棋是一种特殊的完备信息博弈，具有复杂度高，且极具欺骗性，对算法和程序提出了巨大的挑战。由于围棋有很大的分支系数（BranchFactor），传统搜索技术一直没有在计算机围棋领域取得有意义的成果 ，2006年UCT算法改变了这种局面。

2006年秋季，两位匈牙利研究人员（列文特·科奇什和乔鲍·塞派什瓦里）合作提出了一种新算法-UCT算法，它的胜率比现有最佳算法提高了5%，能够在围棋等棋类的比赛中与人类职业棋手抗衡。

UCT概述：

UCT算法是英文UpperConfidence Bound Apply toTree的缩写，翻译成中文是置信上界树搜索。UCT算法是一种博弈树搜索算法，该算法将蒙特卡洛树搜索MCTS方法与UCB公式结合，采用以上限置信值为依据的先深于先广搜索相结合的方法。在超大规模博弈树的搜索过程中相对于传统的搜索算法有着时间和空间方面的优势。在与风险评估模型相结合的基础上,可以在可控的时间内得到当前局势下的相对较优的解决方案。

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

UCT本质：

蒙特卡罗树搜索MTCS是一种方法，是一个框架，用于解决完备、非完备信息博弈。

列文特·科奇什和乔鲍·塞派什瓦里构建的是一个完备的MCTS算法，通过扩展UCB到 minimax 树搜索，这其实是用在当前众多MCTS实现中的算法版本。

UCT被描述为MCTS的一个特例：

UCT = MCTS + UCB

UCT可以看成是UCB(Upper Confidence Bound)在Tree Search上的应用。而UCB本来是为了解决吃角子老虎机问题(Bandit Problem)而产生的。

UCB公式表示为：

机器到目前为止的平均收益 + ( 2*log(所有机器目前被测试的总次数)/机器被测试的次数 )1/2

考虑了“利用”和“探索”之间的平衡。加一个参数C进行调节：

将UCB算法应用到计算机围棋AlphaGo中，用于选择可落子点。可落子点不是随机选择的，而是根据UCB公式选择置信上限最大的节点。

总之，UCT算法是根据统计学的置信区间公式，使用了置信区间的上限值来计算一个落子步骤的价值。这个方法只需要每个步骤的访问数和获胜数就OK了。使用置信区间的上限值带来的一个好处是：如果当前选择的最优子步骤在多次失败的模拟后，这个值会变小，从而导致另一个同级的子步骤可能会变得更优。

UCT算法思想：

UCT算法是一种特殊的蒙特卡洛搜索算法，它由树内选择策略、缺省仿真策略和仿真结果回传三部分组成。

1）树内选择策略：传统搜索技术都有搜索深度d和分支系数b。当搜索达到深度d 时，搜索算法从评估函数取得评估值，而搜索算法负责找到让评估值最大的分支。与搜索树叶子节点数 N 的关系为:N = b^d(b的d次访)。UCT算法与传统搜索技术的最大区别在于不同的分支可以有不同的搜索深度。UCT 算法在不同的深度获取评估值。对于最有“ 希望”求解问题的分支，UCT算法的搜索深度可以很深（远大于d），而对于“ 希望”不大的分支，其搜索深度可以很浅（远小于d）。当最有“希望”求解问题的分支数量远少于“ 希望” 不大的分支数量时，UCT算法就可以把搜索资源有效地用于最有“希望”求解问题的分支，从而获得比传统搜索算法更深的有效深度 d′。这个具有神奇力量的“希望”是由树内选择策略计算的。

2）缺省仿真策略:这一过程就是随机模拟，相当于在博弈树上当前节点向下随意选择一条路径走到头，看是谁获胜。被模拟的节点或者是终止节点，或者是新扩展的节点。

3）仿真结果回传：从新扩展的节点或者终止节点，逐层向上更新收益和访问次数，沿搜索路径逐级向上更新，直到根节点。

UCT算法优点：

1）减小探索分支，提高了系统的搜索速度和深度；

2）容易精确控制时间；工作在任何时间方式，可以在任意时刻停止算法，其性能都不差；

3）算法是稳健的，没有任何人工评估干预情况下，以平稳方式自动处理不确定性；

4）树是用不均匀的方式生长的；好的棋步探索得更多；

5）兼顾局面模拟的探索和利用，避免遗漏了一些潜在的有利局面；

6）更强的灵活性和高效性,更适用于解决需要大规模搜索的复杂问题。

UCT算法缺点：

1)如果置信区间宽度选择很宽时，被选次数很少，还不确定，此时算法比较冒险；

2)如果置信区间宽度选择很窄时，被选次数很多，比较确定，此时算法比较保守。

UCT算法应用：

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

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

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

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

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

2016年3月围棋软件AlphaGo以4比1战胜围棋世界冠军、职业九段棋手李世石。

2017年初围棋软件AlphaGo在中国棋类网站上以“大师”（Master）为注册帐号与中日韩数十位围棋高手进行快棋对决，连续60局无一败绩。

2017年5月围棋软件AlphaGo以3比0战胜排名世界第一的世界围棋冠军、职业九段棋手柯洁。

围棋界公认AlphaGo围棋的棋力已经超过人类职业围棋顶尖水平。

小结：

UCT算法是一种博弈树搜索算法，该算法将蒙特卡洛树搜索MCTS方法与UCB公式结合，在超大规模博弈树的搜索过程中相对于传统的搜索算法有着时间和空间方面的优势。在与风险评估模型相结合的基础上,可以在可控的时间内得到当前局势下的相对较优的解决方案。UCT算法是一种特殊的蒙特卡洛搜索算法，它由树内选择策略、缺省仿真策略和仿真结果回传三部分组成。将UCB算法应用到计算机围棋AlphaGo中，用于选择可落子点。UCB算法助力AlphaGo围棋棋力超过人类职业围棋顶尖水平。

（未完待续）

------以往文章推荐-----