一、A Naïve Tree Search Algorithm：一个普通的树搜索算法

       假设最左边的圆点是初始状态，我们假想向上走，到了位置后，再次假想向上走，此时我们可以得到一个状态，这个状态的价值为-1。现在我们回到初始状态，选择与之前不同的选择，如此循环最终获得一个搜索树，有所有的情况和这些情况对应的价值。

       只有完全的搜索树创建之后，我们才算真正开始。此时我们有所有叶子节点的价值，我们需要计算出所有节点的价值，以便于进行选择。一般选用最大值来计算未知的价值。那么我们得到中间一列的价值，这样我们就可以进行选择了。

       强化学习和树搜索的本质区别：强化学习根据已经发生的真实现实进行学习，而搜索树根据假象的模拟进行计划。

       下面搜索树中的每一个圆都相当于强化学习中的一个state在这里成为node，每一个箭头都相当于强化学习中的一个action,在这里则成为Edge相应的最初的节点称为根节点为root，尾端的节点称为叶子，即为Leaf其余的节点是普通节点为node。用同一条边连接起来的两个节点为父子节点，箭头处为子节点箭头尾部为父节点。

二、MiniMax Tree Search

        我们已经得到了所有的情况Leaf所对应的价值，那么它的父节点的价值如何计算呢。我们就是使用MiniMax算法计算。（此处对应为下棋时的情况，换一种问题算法就要随之变化）

       我们已经知道了所有的叶子节点的价值，下棋的时候一定会去选择对我们最有利的情况所以agent（蓝色的State）选择所有子节点中价值最大的作为父节点的价值，而对于Rival来说选择对它最有力的情况就是选择价值最小的，所以它选择子节点中价值最小的作为父节点的值。

Alpha-BetaPruning

我们可以使用Alpha-Beta Pruning来减少计算量。

          假定我们探索的时候从上向下探索，当我们探索完最上方的叶节点之后，我们可以得到他们的父节点的价值为5，此时我们继续探索我们得知在他们下方又一个节点的价值为6，我们很容易就可以得知价值为6的节点的价值一定>=6，此时根据MiniMax算法我们可以得知对于红色state的第一个节点来说他的价值一定小于等于5，所以蓝色state第二个节点就不用继续探索他的子节点了。同样的我们继续，可以得知蓝色第三个节点的价值为3，那么红色state的第二个节点的价值一定小于等于3所以这个红色节点就不用继续向下探索了。这样有所舍弃，就可以极大的降低算法的消耗。

三、Monte Carlo Rollout

        我们现在回到最初的State，我们在考虑下一步之后，我们的root有了几个子节点，此时我们停止对所有的节点进行探索将得到的所以有节点作为叶节点。此时对于每个叶节点我们仅选择其后的一种情况并且往后也仅考虑一种情况，一直到这一局棋结束。对于每一个叶节点我们不断重复这样的操作就可以获得N次棋局，这样就可以计算出这个叶节点的胜率，我们将胜率作为叶节点的价值。

四、蒙特卡洛树搜索

          蒙特卡洛树搜索结合了前两种算法，采用动态的形式进行计算，进行树的生长。

          和前两种算法一样，我们先考虑在初始状态，我们可以有的所有情况，并将其视作叶节点。然后对于每一个Edge都设置两个参数分别是Q和N，Q代表的是选择这个节点的价值，N代表的是选择的次数，同样的还有一个W代表的是总的价值，相对应的Q是Q=W/N。

          那么在一开始我们该怎样选择一个叶节点，这是我们需要一个函数即为Tree Policy，当我们选择出一个叶节点之后我们该怎样选择叶节点之后的Rollout节点呢，这时候我们需要一个Rollout Policy，来帮助我们进行Rollout，当我们执行完一局棋之后我们需要一个价值函数帮助我们计算价值naïve value。

          此时我们还需要一个阈值来帮助我们进行树的增长，否则情况太多，难以计算。当N>=n（n可以去任意值，这里我选择10），当某一个叶节点的N达到阈值之后我们改变其状态为普通节点，并继续进行Rollout计算，以此往复获得整个搜索树。当然这个阈值也是动态改变的。

          AlphaGo使用的就是蒙特卡洛树搜索，但它结合了神经网络进行了进化，加强。对于上面加粗斜体的三个策略，算法使用神经网络进行训练获得更加准确，有效的算法进行替代。