Understanding Sampling Style Adversarial Search Methods
By Raghuram Ramanujan, Ashish Sabharwal, Bart Selman. 2012
24 citations recorded by the source corpus.
UCT has recently emerged as an exciting new adversarial reasoning technique based on cleverly balancing exploration and exploitation in a Monte-Carlo sampling setting. It has been particularly successful in the game of Go but the reasons for its success are not well understood and attempts to replicate its success in other domains such as Chess have failed. We provide an in-depth analysis of the potential of UCT in domain-independent settings, in cases where heuristic values are available, and the effect of enhancing random playouts to more informed playouts between two weak minimax players. To provide further insights, we develop synthetic game tree instances and discuss interesting properties of UCT, both empirically and analytically.
Subfields: Artificial Intelligence, Economics and Econometrics, Reinforcement Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Sergey Levine
- Yuxi Li
- Pieter Abbeel
- Yoshua Bengio
- Timothy P. Lillicrap
- David Silver
- Ruslan Salakhutdinov
- Quoc V. Le
In Economics and Econometrics
- Yuxi Li
- Arthur Guez
- Ashish Sabharwal
- Timothy P. Lillicrap
- David Silver
- Marc Lanctot
- Thore Graepel
- Demis Hassabis
In Reinforcement Learning
- Sergey Levine
- Pieter Abbeel
- Timothy P. Lillicrap
- Yuxi Li
- David Silver
- Jimmy Ba
- Shimon Whiteson
- R´emi Munos
Citations in the corpus
- Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm (2017, methodology): “However, chess programs using traditional MCTS were much weaker than alpha-beta search programs, (4, 26); while alpha-beta programs based on neural networks have previously been unable to compete with faster, handcrafted evaluation functions.”
- Guiding Combinatorial Optimization with UCT (2012, background): “[10] demonstrated this in the game of Chess where, unlike Go, very strong heuristic functions are available.”
- A Survey of Monte Carlo Tree Search Methods (2012, methodology): “This algorithm is the same as AMAF but also updates nodes that can be reached by permutations of moves in the simulation that preserve the eventual state reached [101].”