棋盘游戏 vs 街机游戏
智能体行动的环境，很多都可以归入如下两类：
- 一类是两方博弈的棋盘游戏，不包含随机性，胜负可以由棋盘上的状态一眼看出，比如围棋、象棋；
- 另一类是智能体适应/对抗环境的“街机游戏”，可能包含随机性，得分可能不是最终状态的函数，而是每一步行动奖励的过程积累，例子包括典型的强化学习测试环境，包括 FrozenLake（这是最简单的环境）, Atari Game 大类等。
棋盘游戏和接机游戏中使用的两种的算法显现出了有趣的区别。
- 棋盘游戏的智能体使用的算法主要是搜索类算法，以蒙特卡洛树搜索 (MCTS) 为例，它采用的是 “一路模拟到底分出胜负，然后回溯更新” 的蒙特卡洛法（注意到它无需改动就能适应棋盘游戏中最终状态定胜负的奖励机制）
- 与之相对的，用于一般强化学习的 Q-Learning 或 Deep Q-Learning 采用方法是每模拟一步，都根据环境给予这一步的奖励和下个状态的估值函数来计算当前状态目标估值的 TD (Temporal-Difference) learning 时序差分学习法，在最终结果出来之前就根据目标估值 (TD Target) 更新参数。
为两种环境设计的智能体的相通之处在于，
- 二者都包含探索与利用的权衡 Exploration vs Exploitation。MCTS 算法每个节点选择行动时，是根据信心上界（Upper Confidence Bound）这个兼顾探索和利用的指标来选择行动的。在 Q-Learning 中也有类似的权衡，训练时在每个状态采取的下一步是 epsilon-greedy 的，即以 epsilon 的概率随机选择（探索），其余情况贪心选择（利用）。这种例子不胜列举。
- 经常会定义估值函数 value(·) 和/或策略函数 policy(·) 来辅助决策。这些函数的实现可能是一张表格（如 Q-Learning），也可能用神经网络来建模（如 DQN, AlphaGo 中）
蒙特卡洛树搜索为什么在棋盘游戏中成功
在棋盘游戏中，局面估值是智能体的核心问题，因为一旦解决了局面估值问题，自然就解决了最佳策略问题。
如果棋盘游戏的状态空间较小，完全可以以当前局面为树根，通过 MinMax（极大极小过程）以深度优先的方式穷尽每种可能（若使用 alpha-beta 剪枝，则为有效可能），给出一个确定的估值。然而，绝大多数有意思的棋盘游戏状态空间都是爆炸的，不可能用这种方法。
蒙特卡洛思想在于使用带有随机性的对局模拟（rollout）来避免状态空间爆炸的问题（它的用时正比于 MinMax 搜索树的高度）。它的简洁是惊人的，然而其精度作为最终结果也是不令人满意的。
蒙特卡洛树搜索的威力在于将 MinMax 搜索和随机对局模拟两种办法结合了起来——使用迭代改进、渐进生长而非试图全局统筹、一蹴而就的方法来构造搜索树：传统的 MinMax 深度优先搜索在没有完成之前，无法给出关于根节点的任何有效信息，而 MCTS 每轮迭代之后都会得到一颗比之前多一个节点、估值更精确的搜索树，而节点上更准确的估值将帮助下一轮迭代。
具体而言，每轮迭代都树根出发，路径上的每个节点依次替自己代表的玩家选择一个落子（由于节点上的估值是不精确的，选择落子位置时需要兼顾探索和利用，这一点可以与 MinMax 形成对比），直到到达一个子节点未扩展齐全的节点或提前分出胜负。如果到达了子节点不齐全的节点，则为其扩展一个子节点，通过随机对局模拟分出胜负。最后，根据胜负情况，更新路径上节点的统计数据。
节点 i 选择落子位置的标准是挑选信心上界 UCB 最高的选择：
UCB_j = w_j/N_j + c*sqrt(2*ln(N_j)/N_i)
w_j is the accumulated reward for choosing j
N_j is the number of times node j is chosen
N_i is the number of times node i is chosenAlphaGo 对 MCTS 的优化：模仿人类棋手
鉴于 MCTS 在棋盘游戏上的亮眼表现，研究人员试图在其基础上改进。一个改进方向是限制搜索树的宽度，比如依据 policy(·) 函数，仅仅探索概率高的落子位置；另一个改进方向是提高随机对局模拟的可靠程度，在对局模拟中两个玩家都通过高质量的 policy(·) 函数采样落子。
AlphaGo（最初版本，排除 AlphaGo Zero） 在对局中使用的就是沿着上述思路改进的 MCTS。Deepmind 的研究者预先训练好三个神经网络：一个用于落子的 policy_sigma(·) 网络、一个更小的用于快速对局模拟落子的 policy_pi(·) 网络（这两个网络都监督学习自人类棋手对局数据）和一个局面估值网络 value(·)，供 AlphaGo 使用。
对于 MCTS 的每条边（在棋盘状态 s 采取落子 a），AlphaGo 需要存储的变量是估值 Q(s,a)、被选中次数统计 N(s,a) 和先验概率 P(s,a)。估值 Q(s,a) 加权平均了预训练的局面估值函数和 MCTS 的估计，具体计算方式为：
Q(s,a) = (1-lambda) * value(s) + lambda * w(s,a)/N(s,a)
w(s,a) is the accumulated reward for choosing action a at s节点选择落子位置的方式是最大化Q(s,a)+u(s,a)，体现了探索和利用的权衡：
u(s,a) = P(s,a)/(1+N(s,a))
where P(s,a) = policy_sigma(s,a)其中 P(s,a) 通过落子函数计算，等于 policy_sigma(s,a)，思想是鼓励 AlphaGo 探索人类棋手落子概率高的位置。
通过借鉴人类棋手的落子概率来筛选哪些落子位置值得探索、通过采样人类棋手的落子分布并依此执行更可靠的随机对局（rollout），AlphaGo 巧妙地模仿了人类棋手的行为。
AlphaGo 的策略和估值函数：当下策略与前序策略博弈
AlphaGo 使用局面估值函数 value(·) 参与了 MCTS 中的估值。然而上一节并没有讲述如何得到 value(·)。为了训练 value(·)，Deepmind 颇费周折：首先使用强化学习的方法得到一个强大的策略函数 policy_rho(·)，然后让该策略函数自我博弈，作为 value(·) 的训练数据。
为了得到强大的策略函数 policy_rho(·)，Deepmind 首先将 policy_rho 初始化为监督学习自人类的落子策略 policy_sigma。然后，使用强化学习中的策略梯度方法进一步改进该策略：不断迭代 policy_rho，每一代策略都要与随机采样得到的前序策略博弈，因而提升。之所以与所有前序策略博弈，而非上一轮迭代中的策略博弈，是因为后者可能造成当前策略针对战胜上一代这一种策略做出过拟合。
最后，让提升后的 policy_rho(·) 自我博弈，从每轮赛局中选取一个局面，标注上胜负情况，用来训练局面估值函数 value(·)。之所以只选取一个局面，是因为倘若包每一个赛局中的所有局面，估值函数 value(·) 会学习到虚假的关联，记住训练数据中该赛局的胜负，而非“完美的全知的玩家”从该局面继续博弈导致的胜负。
为什么不把 policy_rho(·) 作为最终产品对阵人类棋手，而是如此间接地转换为 value 函数服务 MCTS 的计算呢？大概是因为 policy_rho(·) 作为神经网络的前向求值，效果不如 MCTS 模拟和推演。从计算资源的角度，使用前者可能只需要一个带显卡的台式机，而后者的分布式实现在对阵人类冠军时动用的是计算集群。后者可以通过计算资源换取决策质量（在落子时间、计算资源允许的范围内采用最大的迭代次数），前者不可以。
+-------+ +-------+ +-------+ +-------+
|Rollout| |SL | |RL | |Value |
|Policy | |Policy +--Policy Gradient->+Policy | |Network|
+ ---+--+ + --+---+ +---+---+ +---+---+
/|\ /|\ | /|\
| | Self-Play Regression
\ / \|/ |
Human Expert Positions Self-Play Positions（AlphaGo Policy 和 Value 网络训练过程的示意图，请用等宽字体显示，转写自Mastering the game of Go with deep neural networks and tree search）
References
- Deep RL Course, https://huggingface.co/learn/deep-rl-course
- Mastering the game of Go with deep neural networks and tree search, https://www.nature.com/articles/nature16961
Leave a Reply