甜野猫|组合游戏系列4: AlphaGo Zero 强化学习算法原理深度分析( 二 ) AlphaGoZero是Deepmind最后一代AI围棋

- Selection：从根节点出发，根据现有统计的信息和selection规则，选择子节点递归向下做决定，后面我们会详细介绍AlphaGo的UCB规则。图中节点的数字，例如根节点11/21 ，分别代表赢的次数和总模拟次数。从根节点一路向下分别选择节点 7/10, 1/6直到叶子节点3/3 ，叶子节点表示它未被探索过。
- Expansion：由于3/3节点未被探索过，初始化其所有子节点为0/0 ，图中3/3只有一个子节点。后面我们会看到神经网络在初始化子节点的时候起到的指导作用，即所有子节点初始权重并非相同，而是由神经网络给出估计。
- Simulation：重复selection和expansion ，根据游戏规则递归向下直至游戏结束。
- Backpropagation：游戏结束在终点节点产生游戏真实的价值，回溯向上调整所有父节点的统计状态。
权衡 Exploration 和 Exploitation在不断扩张决策树并收集节点统计信息的同时， MCTS根据规则来权衡探索目的（采样不足）或利用目的来做决策，这个权衡规则叫做Upper Confidence Bound（UCB）。典型的UCB公式如下：w表示通过节点的赢的次数， n表示通过节点的总次数， N是父节点的访问次数， c是调节Exploration 和 Exploitation权重的超参。
传统UCB
假设某节点有两个子节点s1, s2 ，它们的统计指标为 s1: w/n = 3/4 ， s2: w/n = 6/8 ，由于两者输赢比率一样，因此根据公式，访问次数少的节点出于Exploration的目的胜出， MCTS最终决定从s局面走向s1 。
从第一性原理来理解AlphaGo Zero前一代的AlphaGo已经战胜了世界冠军，取得了空前的成就， AlphaGo Zero 的设计目标变得更加General ，去除围棋相关的处理和知识，用统一的框架和算法来解决棋类问题。

无人工先验数据改进之前需要专家棋手对弈数据来冷启动初始棋力
无特定游戏特征工程无需围棋特定技巧，只包含下棋规则，可以适用到所有棋类游戏
单一神经网络统一Policy Network和Value Network ，使用一个共享参数的双头神经网络
简单树搜索去除传统MCTS的Rollout 方式，用神经网络来指导MCTS更有效产生搜索策略

搜索空间的两个优化原则尽管理论上围棋是有解的，即先手必赢、被逼平或必输，通过遍历所有可能局面可以求得解。同理，通过海量模拟所有可能游戏局面，也可以无限逼近所有局面下的真实输赢概率，直至收敛于局面落子的确切最佳结果。但由于围棋棋局的数目远远大于宇宙原子数目， 3^361 >> 10^80 ，因此需要将计算资源有效的去模拟值得探索的局面，例如对于显然的被动局面减小模拟次数，所以如何有效地减小搜索空间是AlphaGo Zero 需要解决的重大问题。 David Silver 在Deepmind AlphaZero - Mastering Games Without Human Knowledge 中提到AlphaGo Zero 采用两个原则来有效减小搜索空间。