蒙特卡洛树搜索MCTS

2019-11-26 本文已影响0人我只要喝点果粒橙

跟围棋的关联

AlphaGo Zero

蒙特卡洛树搜索——内含用于树遍历的 PUCT 函数的某些变体
残差卷积神经网络——其中的策略和价值网络被用于评估棋局，以进行下一步落子位置的先验概率估算。
强化学习——通过自我对弈进行神经网络训练

AlphaGo Zero跟AlphaGo的最大区别是抛弃人类棋谱的，完全通过自我对弈来学会下棋的，并且仅用40小时就到达了AlphaGo的棋力。

过程是这样，首先生成棋谱，然后将棋谱作为输入训练神经网络，训练好的神经网络用来预测落子和胜率。如下图：

2018031214442364.jpg

在AlphaGo Zero中蒙特卡洛树搜索主要是用来生成棋谱的

蒙特卡洛树搜索

Q:MCTS干了什么?

A:给出一个「游戏状态」并选择「胜率最高的下一步」

适用于有限两人零和回合制游戏

MCTS算法是一种决策算法，每次模拟（simulation）分为4步：

Tree traversal(树的遍历):
$UCB1(S_{i})=\overline{V_{i}}+c \sqrt{\frac{\log N}{n_{i}}}, c=2$
其中，表 $\overline{V_{i}}$ 示 $S_i$ 状态的平均value(下面会进一步解释）
Node expansion(拓展节点)
Rollout (random simulation)(模拟)
Backpropagation(方向传播)

蒙特卡洛计算过程

UCB(Upper Confidence Bounds置信上限)其实就是UCT(UCB for Tree)中需要计算的值，而UCT是根据UCB值来迭代的算法

第一、二步的流程（遍历、拓展节点）：

1.从状态S0开始，要在下面两个动作中进行选择（假设只有两个动作可选），选择的标准就是 $UCB1(S_{i})$ 值，选择最大化 UCT 的节点作为下一个节点。初始情况两个 $UCB1(S_{1})=UCB1(S_{2})=\infty$ ,按顺序选择S1
2.判断目前的结点S1(current node)是不是叶节点，这里叶节点是指其没有被展开（expansion）过。
3.接下来，按照流程图，需要判断结点S1被访问的系数是否为0。是0，则要进行Rollout。(Rollout其实就是在接下来的步骤中每一步都随机采取动作，直到停止点（围棋中的对局结束），得到一个最终的value。)==>假设Rollout最终值为20.
4.Backpropagation，即利用Rollout最终得到的value来更新路径上每个结点的T,N值。(之后把Rollout的结果删除：MCTS的想法就是要从出S0发不断的进行迭代，不断更新结点值，直到达到一定的迭代次数或者时间。)
5.如果没有达到一定的迭代次数或者时间，继续从根节点进行1-4

20171024211039397.png

第三步rollout模拟:

/*这个函数接受一个表示博弈状态的参数，然后返回下一步行动。实际上，它被设计得非常快，从而可以让很多模拟快速进行——默认的 rollout policy 函数是一个均衡分布的随机数生成函数。*/
Rollout(S_i):
    loop forever:
     /* 如果当前状态结点是个终止结点 */
     if S_i is a terminal state:
         /* 那么直接返回它的value值*/
         return value(S_i)
     /* 找到下一个动作 */
     A_i = random(available-actions(S_i))
     /* 选择下一个状态进行拓展 */
     S_i = simulate(A_i,S_i)

例子说明见:蒙特卡洛树搜索（MCTS）算法-计算过程，视频讲解见B站:【MCTS】Youtube上迄今为止最好的蒙特卡罗树搜索讲解

相比极大极小法（minimax）。这个策略假定你的对手发挥了最好的博弈水平，然后以此调整策略来最大化你的收益。简单地说，给定状态，你想要找到一个能产生最大收益的 move ，假定你的对手想要最小化你的收益（最大化他自己的收益）。因此，名字叫作极小化极大。

极小化极大算法的最大劣势是，需要扩展整个博弈树。对于分支因子较高的博弈（例如围棋或者国际象棋），这会导致庞大的博弈树从而失败。