On Adversarial Search Spaces and Sampling-Based Planning
On Adversarial Search Spaces and Sampling-Based Planning
复制标题
关于对抗性搜索空间和基于采样的规划
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
B. Selman
中科院分区：
文献类型：
--
作者：
R. Ramanujan;Ashish Sabharwal;B. Selman
树置信上界（UCT）是一种基于Bandit的蒙特-卡罗抽样规划算法，近年来在对抗推理领域引起了人们极大的兴趣。UCT已经被证明在几个具有挑战性的领域（如围棋和Kriegspiel）中优于传统的基于极大极小的方法，尽管极大极小搜索在其他领域（如国际象棋）中仍然盛行。这项工作提供了对对抗性搜索空间属性的深入了解，这些属性在UCT和类似的基于采样的方法的成功或失败中起着关键作用。我们表明，某些“早期损失”或“浅陷阱”的配置，而不太可能在围棋，经常发生在像国际象棋游戏（即使在大师级游戏）。我们提供的证据表明，UCT，不像极大极小搜索，是无法识别这样的陷阱，在国际象棋和花费大量的时间探索更深层次的游戏比需要的。
Upper Confidence bounds applied to Trees (UCT), a bandit-based Monte-Carlo sampling algorithm for planning, has recently been the subject of great interest in adversarial reasoning. UCT has been shown to outperform traditional minimax based approaches in several challenging domains such as Go and Kriegspiel, although minimax search still prevails in other domains such as Chess. This work provides insights into the properties of adversarial search spaces that play a key role in the success or failure of UCT and similar sampling-based approaches. We show that certain "early loss" or "shallow trap" configurations, while unlikely in Go, occur surprisingly often in games like Chess (even in grandmaster games). We provide evidence that UCT, unlike minimax search, is unable to identify such traps in Chess and spends a great deal of time exploring much deeper game play than needed.