Pruning in UCT Algorithm
Pruning in UCT Algorithm
复制标题
DOI：
10.1109/taai.2010.38
复制
发表时间：
2010-11
期刊：
影响因子：
--
通讯作者：
Jing Huang;Zhiqing Liu;Benjie Lu;Feng Xiao
中科院分区：
文献类型：
--
作者：
Jing Huang;Zhiqing Liu;Benjie Lu;Feng Xiao
UCT是一种蒙特卡洛计划算法，在给定的时间内，它为大型状态空间的马尔可夫决策过程计算了近乎最佳的解决方案。自2006年出版以来，由于搜索社区的搜索社区从那里引起了很多关注，并且由于其对蒙特卡罗规划计算的有效性的显着提高，因此它已在许多应用程序中使用。本文提出了对UCT算法的修改，该算法可以修改Marte-Carlo计划计算过程中某些马尔可夫决策过程及其相关状态。基于UCT基础UCB算法的属性进行动作和状态的修剪。本文证明，在UCT算法返回的解决方案路径中，修剪的动作和状态极不可能使修剪修改几乎与原始算法一样好。此外，修剪修饰可以减少马尔可夫决策过程状态空间的大小，从而提高原始算法的有效性。计算机GO中的实验结果证明了UCT算法中修剪的有效性。
UCT is a Monte-Carlo planning algorithm that, with in a given amount of time, computes near-optimal solutions for Markovian decision processes of large state spaces. It has gained much attention from there search community and been used in many applications since its publication in 2006, because of its significant improvement of the effectiveness of Monte-Carlo planning computation. This paper proposes a modification of the UCT algorithm, which can prune certain Markovian decision process actions and their associated states during the Monte-Carlo planning computation. The pruning of actions and states is performed based on properties of underlying UCB algorithms of UCT. This paper proves that it is highly unlikely for the pruned actions and states to be in the solution path returned by the UCT algorithm, making the pruning modification almost just as good as the original algorithm. Additionally, the pruning modification may reduce the size of the Markovian decision process state space, and thus improves the effectiveness of the original algorithm. Experimental results in computer GO demonstrate the effectiveness of pruning in the UCT algorithm.