首先, AlphaGo和李世石之间的对决是不公平的,AlphaGo的逻辑模块只能用于下围棋,相当于李世石用他的人类大脑挑战一个专门训练成只能用于下围棋的大脑。去年10月在英国挑战樊麾的时候AlphaGo的核心数是1200个CPU和170个GPU,而挑战李世石的时候AlphaGo用了1920个CPU。围棋界有个Elo的参数用来评价围棋手,李世石Elo为3532,去年10月的AlphaGo的Elo值为3168,值得注意的是中国棋手柯洁的Elo为3634。

AlphaGo总体来讲用了Google DeepMind的Policy Network 和 Value Network指引Monte Carlo算法,相当于用深度学习的技术来引导一个高明的搜索。(其实还有一个Fast Rollout用来快速走子,感谢@dlfall的提醒,总体来说是四个部分:决策网络、价值网络、快速走子和蒙特卡洛树搜索)

蒙特卡洛树搜索

蒙特卡洛树搜索(Monte Carlo Tree Search),是一种人工智能领域的求最优决策的方法,经常由于机器博弈领域,其实可以用于<状态—行动>关系的任何领域作决策。MCTS的过程如下图:(图源维基百科)

"MCTS ENG"

Selection: 从Root开始递归选择最优子节点,直到选到叶节点

Expansion:如果选的最后的叶节点不会导致游戏终止,就创建更多的叶节点(一个或多个),然后选择其中的一个叶节点

Simulation:从Expansion选择的那个叶节点开始模拟游戏(没有玩家参与),直到游戏结束,查看结果。

Backpropagation: 从Simulation的结果来更新当前各个节点的权值。

蒙特卡洛其实就是基于随机的搜索搭配高效的剪枝,把所有结果模拟一遍,所以需要的计算量非常大。蒙特卡洛这个词就是用来指随机的,特点就是它的第一个字:蒙特卡洛做题法 :) 蒙特卡洛把妹法 :)

节点的选择

然而Monte Carlo不能直接用于围棋,或者说直接用于围棋需要大量的计算能力并且会浪费大部分。早在几年前Mogo,一个机器围棋程序,用了树形UCB搜索+Monte Carlo,UCT:Upper Confidence Bounds for Trees

UCB是Upper Confidence Bounds,用来对节点估值,UCB公式 Wi是第i步后赢的次数,Ni是第i步后模拟的次数,C是个可调整常量,我一般取0.44,听说正常取根号2。t是总模拟次数

UCT就是Monte Carlo + UCB,就算蒙特卡洛的一个Mod。UCT具有通用性,稍加修改就可以用于各种博弈游戏上。

搜索速度

蒙特卡洛会执行相当多次迭代才能收敛到一个较优解,而围棋的搜索深度可能比象棋高百万倍,所以Google DeepMind采用了Policy Network和Value Network来引导蒙特卡洛树搜索,已达到搜索的高度优化。不用人工智能算法的优化还有快速行动价值估算

AlphaGo局限

攻破阿尔法狗:AlphaGo的搜索深度在刚开局时的时候是最大的,过半局之后搜索量就大大减少,所以想要打败AlphaGo,除了首先要有世界级的水平之外,在前半句就要努力占到绝对的优势,一旦前半局打得疲软,后半场越往后下落子点就越少,AlphaGo就是无敌的!
AlphaGo用了Deep Learning + Monte Carlo Tree Search就决定了它只能用于“状态-行动”估值和最优策略,从本质上讲就是一个专门下围棋的机器。那么为什么很多人已经在考虑人工智能替代人类然后准备失业了呢???

Demo

这是我做的UCT围棋DEMO。首先申明我我一点都不会下围棋,但是通过UCT我可以写出和普通的围棋手一样水准的机器棋手。看上去机器打的还可以 :) (图挂了。。)
betago betago2

 


 

当然,光有蒙特卡洛做不了AlphaGo那么强大的围棋机器,搭配UCT也只能打打普通围棋选手。如果要做AlphaGo,你需要类似Policy Network 和Value Network的深度学习算法,并且有大量的计算能力(像Google那样不缺钱的那种)。