【一文读懂AlphaGo Zero算法】白话蒙特卡洛树搜索和ResNet
AlphaGo Zero 引起巨大社会轰动
只告诉机器围棋的基本规则，但是不告诉它人类摸索了上千年才总结出来的定式等围棋战术，让机器完全依靠自学，打败人类。这个题目不仅新鲜，而且热辣。
上周 DeepMind AlphaGo 人工智能围棋团队的一篇新论文，题目是“Mastering the Game of Go without Human Knowledge”。
这篇论文不仅被顶级学术期刊 Nature 发表，而且立刻被媒体反复报导，引起社会热议。
这篇论文让人惊艳的亮点有四，
- 只告诉机器围棋规则，但是不告诉它定式等等人类总结的围棋战术，也不让它读人类棋手比赛的棋谱，让机器完全自学成才。
- 机器完全靠自己摸索，自主总结出了定式等等围棋战术，而且还发现了人类上千年来没有发现的定式。
- 从零开始，机器自学了不到 40 天，就超越了前一版 AlphaGo（AlphaGo Master），而 AlphaGo Master 几个月前，曾以 60 : 0 的战绩，战胜了当今几乎所有人类围棋高手。
- AlphaGo Zero 的算法，比 AlphaGo Master 简练很多。
不过，有些关于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} 。它的输出有两个，
- 当前棋面 S_{t} 的赢率，v( S_{t} )，赢率就是最终获胜的概率，是一个数值。