- title = "Consistency Modifications for Automatically Tuned {Monte-Carlo} Tree Search",
- author = "Vincent Berthier and Hassen Doghmen and Olivier Teytaud",
- booktitle = "Learning and Intelligent OptimizatioN, LION 4",
- year = "2010",
- editor = "Roberto Battiti",
- address = "Venice",
- month = jan # " 18-22",
- keywords = "genetic algorithms, genetic programming, Game Go, Mathematics/Optimization and Control, Monte-Carlo Tree Search Consistency Ko-fights",
-
URL = "
http://hal.archives-ouvertes.fr/docs/00/43/71/46/PDF/consistency.pdf",
-
URL = "
HAL:http://hal.archives-ouvertes.fr/inria-00437146/en/",
- bibsource = "OAI-PMH server at hal.archives-ouvertes.fr",
- identifier = "HAL:inria-00437146, version 1",
- language = "EN",
- oai = "oai:hal.archives-ouvertes.fr:inria-00437146_v1",
-
abstract = "Monte-Carlo Tree Search algorithms (MCTS [4, 6]),
including upper confidence trees (UCT [9]), are known
for their impressive ability in high dimensional
control problems. Whilst the main test bed is the game
of Go, there are increasingly many applications [13,
12, 7]; these algorithms are now widely accepted as
strong candidates for high-dimensional control
applications. Unfortunately, it is known that for
optimal performance on a given problem, MCTS requires
some tuning; this tuning is often handcrafted or
automated, with in some cases a loss of consistency,
i.e. a bad behavior asymptotically in the computational
power. This highly undesirable property led to a stupid
behavior of our main MCTS program MoGo in a real-world
situation described in section 3. This is a big trouble
for our several works on automatic parameter tuning [3]
and the genetic programming of new features in MoGo. We
will see in this paper:
-- A theoretical analysis of MCTS consistency;
-- Detailed examples of consistent and inconsistent known algorithms;
-- How to modify a MCTS implementation in order to ensure consistency, independently of the modifications to the scoring module (the module which is automatically tuned and genetically programmed in MoGo);
-- As a by product of this work, we'll see the interesting property that some heavily tuned MCTS implementations are better than UCT in the sense that they do not visit the complete tree (whereas UCT asymptotically does), whilst preserving the consistency at least if consistency modifications above have been made.",
- notes = "LION4 http://lion.disi.unitn.it/intelligent-optimization//LION4/program.php",
