蒙特卡罗搜索树基本思想

10.1　蒙特卡罗搜索树基本思想

蒙特卡罗树搜索是把离线学习的知识与在线搜索的过程相结合的一种最优有限的搜索方法。在蒙特卡罗树搜索过程中，我们沿用UCT方法进行在线搜索过程；同时加入离线的知识提高UCT方法的搜索效率。由于在线搜索过程以UCT算法为基础，所以，蒙特卡罗树搜索主要包括如下4个方面的主要内容。

（1）搜索：通过UCT算法，递归的从博弈树的根节点向下搜索直至当前的叶子节点。

（2）扩展：对当前的博弈树叶子节点进行扩展。

（3）模拟：从当前的博弈树叶子节点开始进行蒙特卡罗模拟。

（4）更新：把蒙特卡罗模拟的结果更新到搜索过程中博弈树的每一个节点上。

在这4个不同的方面，我们都可以加入离线学习的经验知识，使UCT算法升级为蒙特卡罗树搜索算法。

（1）搜索：使用知识进行UCT算法的初始化。

（2）扩展：使用知识控制博弈树的扩展，从具体情况上看又可以分为如下3种情况。

①可选落子点的排序策略：一般情况下，由于UCT算法的搜索时间是有限的，叶子节点的访问次数很少。在同一层中，那些被排在后面的关键节点有可能由于位置的原因而不能被充分探索到。所以，一个好的排序策略应该保证双方最强的应手在有限时间内均能被搜索到。这就要求我们利用知识，把那些在实际对战中更有利于获胜的可选点排在所有节点的前列。实际应用中，Elo评分系统根据离线知识，可以静态的对可下点进行排序，提高关键点被探索的可能性。

②可选落子点的扩展策略：从UCT算法的主要内容我们可以知道，如果当前节点为博弈树的叶子节点，则我们就会对其进行扩展，所有被扩展出的节点形成新的叶子节点。但是，一次性扩展所有节点很有可能造成时间和空间资源的浪费。这是显而易见的：假设现在的叶子节点为Lp，我们扩展了它的k个叶子节点LC_i，那么，我们不得不再次经过Lp这条路径k次才有机会扩展Lp儿子的儿子节点。这样做，使得我们花更多的时间去观察那些表现平平的节点，同时还不得不为它们提供存储的空间，而这些空间很有可能会因为该节点从未被访问而成为被浪费掉的空间。所以，在实际应用中，我们通过逐渐扩展技术先扩展最强的落子点，然后根据访问时间，逐步扩展其他节点。具体细节我们将在第10.2节介绍。

③可选落子点的剪枝策略：在博弈树上进行剪枝，是加快搜索效率的有效办法。将那些通过剪枝策略判定后确定不好的节点从博弈树中除去之后再考虑是否进行扩展，可以很好地缩小搜索的范围，提高搜索的速度。具体细节我们将在第10.3节介绍。

（3）模拟：使用知识指导蒙特卡罗模拟。

（4）更新：保持与UCT算法的一致性，这样可以将离线知识和在线搜索的信息都返回搜索过程中博弈树的每一个节点上。