Combining online and offline knowledge in UCT

By Sylvain Gelly, David Silver. 2007

586 citations recorded by the source corpus.

The UCT algorithm learns a value function online using sample-based search. The TD(λ) algorithm can learn a value function offline for the on-policy distribution. We consider three approaches for combining offline and online value functions in the UCT algorithm. First, the offline value function is used as a default policy during Monte-Carlo simulation. Second, the UCT value function is combined with a rapid online estimate of action values. Third, the offline value function is used as prior knowledge in the UCT search tree. We evaluate these algorithms in 9 x 9 Go against GnuGo 3.7.10. The first algorithm performs better than UCT with a random simulation policy, but surprisingly, worse than UCT with a weaker, handcrafted simulation policy. The second algorithm outperforms UCT altogether. The third algorithm outperforms UCT with handcrafted prior knowledge. We combine these algorithms in MoGo, the world's strongest 9 x 9 Go program. Each technique significantly improves MoGo's playing strength.

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

In Economics and Econometrics

In Reinforcement Learning

Citations in the corpus

Thinking Fast and Slow with Deep Learning and Tree Search (2017, methodology): “To do this, we play multiple games with the exploration policy, and select a single state from each game, as in Silver et al. [13].”
TreeQN and ATreeC: Differentiable Tree Planning for Deep Reinforcement Learning (2017, methodology): “The intuitions guiding the design of TreeQN are as applicable to policy search as to value-based RL, in that a policy can use a tree planner to improve its estimates of the optimal action probabilities (Gelly & Silver, 2007; Silver et al., 2017a).”
On the Analysis of Complex Backup Strategies in Monte Carlo Tree Search (2016, unknown): “Various modifications have been proposed to improve the exploration strategy under UCT (Gelly and Wang, 2006; Wang and Gelly, 2007) and its value estimation (Gelly and Silver, 2007; 2011; Helmbold and Parker- Wood, 2009; Feldman and Domshlak, 2014b).”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, background): “Several major improvements (such as the use of features in the random playouts, the Rapid Action Value Estimation (RAVE), the parallelization of the algorithm, and the introduction of opening books) [61, 100, 24, 106, 48, 62] enabled the MoGo program to rank among the best Computer Go programs (see ”
Achieving master level play in 9×9 computer go (2008, unknown): “An equivalence parameter k controls the number of simulations when both estimates are given equal weight (Gelly & Silver 2007).”
Bootstrapping from Game Tree Search (2009, methodology): “The TreeStrap algorithm could be applied, for example, to the heuristic function that is used to initialise nodes in a UCT search tree with prior knowledge (Gelly & Silver, 2007).”
Guiding Combinatorial Optimization with UCT (2012, background): “It has received much attention during the past few years due to its success in game playing agents, especially for Go [4, 5] and Kriegspiel [2], as well as for general game playing [3].”
Feature Selection as a One-Player Game (2010, methodology): “As in other applications of UCT [12, 15 ] however, only the current branch is updated in FUSE due to the high branching factor of nodes.”
Sample-based learning and search with permanent and transient memories (2008, methodology): “Related work The Computer Go program MoGo uses the heuristic UCT algorithm (Gelly & Silver, 2007) to achieve dan-level performance.”
Monte-Carlo Tree Search Solver (2008, background): “It is well-known that the use of an adequate simulation strategy improves the level of play significantly [11].”
Simulation-Based Approach to General Game Playing (2008, methodology): “Experiments in Go showing how UCT can benefit from using an informed playout policy are presented in ( Gelly & Silver 2007 ).”
AN ANALYSIS OF UCT IN MULTI-PLAYER GAMES (2008, methodology): “Rapid Action Value Estimate (RAVE) (Gelly and Silver, 2007) is a similar mechanism for UCT which associates the values of the states after a move instead of just the ordering of the moves.”