跟围棋的关联
AlphaGo Zero
- 蒙特卡洛树搜索——内含用于树遍历的 PUCT 函数的某些变体
- 残差卷积神经网络——其中的策略和价值网络被用于评估棋局，以进行下一步落子位置的先验概率估算。
- 强化学习——通过自我对弈进行神经网络训练
AlphaGo Zero跟AlphaGo的最大区别是抛弃人类棋谱的，完全通过自我对弈来学会下棋的，并且仅用40小时就到达了AlphaGo的棋力。
过程是这样，首先生成棋谱，然后将棋谱作为输入训练神经网络，训练好的神经网络用来预测落子和胜率。如下图：
2018031214442364.jpg
在AlphaGo Zero中蒙特卡洛树搜索主要是用来生成棋谱的
蒙特卡洛树搜索
Q:MCTS干了什么?
A:给出一个「游戏状态」并选择「胜率最高的下一步」
适用于有限两人零和回合制游戏
MCTS算法是一种决策算法，每次模拟（simulation）分为4步：
- Tree traversal(树的遍历):
其中，表示
状态的平均value(下面会进一步解释）
- Node expansion(拓展节点)
- Rollout (random simulation)(模拟)
- Backpropagation(方向传播)
蒙特卡洛计算过程
UCB(Upper Confidence Bounds置信上限)其实就是UCT(UCB for Tree)中需要计算的值，而UCT是根据UCB值来迭代的算法
第一、二步的流程（遍历、拓展节点）：
1.从状态S0开始，要在下面两个动作中进行选择（假设只有两个动作可选），选择的标准就是值，选择最大化 UCT 的节点作为下一个节点。初始情况两个
,按顺序选择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 ，假定你的对手想要最小化你的收益（最大化他自己的收益）。因此，名字叫作极小化极大。
极小化极大算法的最大劣势是，需要扩展整个博弈树。对于分支因子较高的博弈（例如围棋或者国际象棋），这会导致庞大的博弈树从而失败。
UCT算法——树的置信上限(UCB for Trees)
Upper Confidence Bounds(置信上限)
UCT是一个让我们从已访问的节点中选择下一个节点来进行遍历的函数，也是MCTS的核心函数。
exploitation component(利用)
第一部分是 ，也称作exploitation component
可以看做是子节点Vi的胜率估计（总收益/总次数=平均每次的收益）。但是不能只选择胜率高的下一步，因为这种贪婪方式的搜索会很快导致游戏结束，这往往会导致搜索不充分，错过最优解。
举个简单的例子。现在假设MCTS的UCT函数只用了探索成分，从根节点开始，我们对所有子节点进行了一次模拟，然后在下一步中只访问至少赢了一次的子节点。那么在第一次模拟中那些不幸未被选中的节点（实际中rollout策略函数通常是随机的）将会被立刻抛弃
exploration component(探索)
，这个成分更倾向于那些想对较少被探索的节点N(Vi)小。
参数c是exploitation和exploration之间的折中系数。
MCTS的终止
终止条件(or)：
- 达到一定的迭代次数
- 达到规定的搜索时间
当MSCT程序结束时，最佳的移动通常是访问次数最多的那个节点，也是UCT最大的点。
参考:
【MCTS】Youtube上迄今为止最好的蒙特卡罗树搜索讲解
网友评论