AlphaGo Zero 引起巨大社会轰动
只告诉机器围棋的基本规则,但是不告诉它人类摸索了上千年才总结出来的定式等围棋战术,让机器完全依靠自学,打败人类。这个题目不仅新鲜,而且热辣。
上周 DeepMind AlphaGo 人工智能围棋团队的一篇新论文,题目是“Mastering the Game of Go without Human Knowledge”。
这篇论文不仅被顶级学术期刊 Nature 发表,而且立刻被媒体反复报导,引起社会热议。
这篇论文让人惊艳的亮点有四,
不过,有些关于AlphaGo Zero 的评论,似乎渲染过度,把它的算法,说得神乎其神。本文尝试用大白话,通俗地解释一下 AlphaGo Zero 的算法。
AlphaGo Zero 的算法,说来并不复杂。理解清楚 Monte Carlo Tree Search、深度学习启发函数和置信上限,这三个概念就行了。
Monte Carlo Tree Search:不穷举所有组合,找到最优或次优位置
围棋棋面总共有 19 * 19 = 361 个落子位置。假如电脑有足够的计算能力,理论上来说,我们可以穷举黑白双方所有可能的落子位置,找到最优落子策略。
但是,如果穷举黑白双方所有可能的落子位置,各种组合的总数,大约是 250^150 数量级。这个数太大了,以至于用当今世界最强大云计算系统,算几十年也算不完。
有没有不穷举所有组合,就能找到最优或者次优落子策略的算法呢?有,Monte Carlo Tree Search 就是这样一种算法。
刚刚开始教机器下围棋的时候,机器除了规则,对围棋一无所知。让两台机器对弈,分别执黑子与白子。只要不违反规则,以均等概率,在所有合法的位置上,随意选择一个地点落子。
黑方先行,它有 361 个合法投子位置。黑方先随机考虑一个候选位置,譬如天元(9,9)。开局是否投子在天元呢?取决于假如投子在此,是否有可能赢得胜利。如何估算赢得胜利的可能性呢?黑方模拟对局。
假如黑方第一手投子天元,那么白方的第二手会投子哪里呢?根据均等概率的初步策略,白方有 360 个合法位置,在任何一处投子的概率均等。假如白方的第二手投子在棋盘的最边缘(0,0)。
接下去,黑方在剩余的 359 个合法位置中,随机选择一个落子位置。接下去白方投子。如此重复,直到终局。
完成这样一次对局模拟的过程,上限是 361 手,计算成本很低。
假如黑白两个机器,以黑方投子天元开局,一路乱走,最终以黑方胜利。那么根据 Monto Carlo Tree Search 算法,投子天元的开局,有可能获胜,那么第一手,就真的投子天元。
假如一路乱走,最终黑方失败,那么黑方就换一个候选位置,再次模拟对局。假如第二次模拟对局以黑方获胜,就投子在第二个位置。假如失败,那就再换到第三个候选位置,第三次模拟对局。如此重复。
这样反复乱走,收集到了第一批棋谱,当然,这些棋谱的水平,惨不忍睹。
水平之所以惨不忍睹,是因为 “以均等概率,在所有合法的位置上,随意选择一个地点落子” 的下棋策略。
如何通过自学,不断改进下棋策略?
AlphaGo Zero 用深度学习神经网络来解决这个问题。
用深度学习网络实现启发函数
AlphaGo Zero 用 CNN 来改进围棋投子策略。具体到 CNN 的系统架构,AlphaGo Zero 用的是 Residual 架构 ResNet。而 Residual 架构是其时任职于微软亚洲研究院的中国人 Kaiming He、Xiangyu Zhang、Shaoqing Ren、Jian Sun,于 2015 年发明的。
ResNet 的输入是当前的棋面 S_{t} 。它的输出有两个,
AlphaGo Zero 只用机器自我对弈的棋谱,来训练 ResNet。
当然,也可以用人类棋手的棋谱来训练 ResNet。理论上来说,用人类棋手的棋谱来训练 ResNet,AlphaGo Zero 的水平,会在更短时间内,获得更快提升。
但是,即便不用人类棋手的棋谱,只用机器自我对弈的棋谱,来训练 ResNet,在短短 40 天内,AlphaGo Zero 就已经超越人类棋手的水平。这个速度,实在让人惊艳。
ResNet 训练好了以后,仍然用 Monte Carlo Tree Search,继续让机器自我对弈。只不过把投子的策略,从均等概率的随机投子,改为根据 ResNet 的指导,来决定下一手的投子位置。
论文配图:MCTS 使用神经网络模拟落子选择的过程
具体策略如下,
用改进了投子策略的 Monte Carlo Tree Search,继续让机器自我对弈,这样得到更多棋谱。然后,用这些棋谱,再次训练 ResNet,提高赢率和投子概率的估算精度。如此循环重复,不断提高 ResNet 的精度。
定式(Joseki)与投子位置热力图
投子概率 P( a_{t+1} | S_{t} ) ,反应了下一手投子位置的热力图。各个位置被投子的概率非常不均等,其中某些位置被投子的概率,比其它位置显著地高。
这些位置,加上前面几手的落子位置和相应的棋面,就是围棋定式(Joseki)。
论文补充材料:训练中AlphaGo Zero偏好的投子位置热力图
AlphaGo Zero 在五天以内,就通过机器自我对弈,总结出了常见的定式。
而人类发现这些定式,花费了几百年。
更加令人惊艳的是,AlphaGo Zero 还发现了新的定式,而这些定式,人类迄今为止并没有发现。
点击查看大图:在 2 小时时间限制下,AlphaGo Zero (20 个残差模块,训练 3 天) 对战 AlphaGo Lee 的 20 局,每局展示了前 100 步棋。
总结一下,AlphaGo Zero 的算法非常简洁,Monte Carlo Tree Search + ResNet。
与传统的 A* 算法比较一下,Monte Carlo Tree Search 只是 A* 算法中的树拓展的一种特例,而 ResNet 是 A* 算法中启发函数的一种特例。
将深度强化学习和蒙特卡洛树搜索用于智能医疗
除了下围棋,深度强化学习和蒙特卡洛树搜索已经用于智能医疗,给医生推荐最佳后续化验和检查项目,补充病情描述,用最小的代价,找到诊断金指标,提高诊断精度。