
UCD : Upper confidence bound for rooted directed acyclic graphs
Cazenave, Tristan; Méhat, Jean; Saffidine, Abdallah (2012), UCD : Upper confidence bound for rooted directed acyclic graphs, Knowledge-Based Systems, 34, p. 26-33. 10.1016/j.knosys.2011.11.014
Type
Article accepté pour publication ou publiéDate
2012Journal name
Knowledge-Based SystemsVolume
34Publisher
Elsevier
Pages
26-33
Publication identifier
Metadata
Show full item recordAuthor(s)
Cazenave, TristanLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Méhat, Jean
Laboratoire d'Informatique Avancée de Saint-Denis [LIASD]
Saffidine, Abdallah
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
In this paper we present a framework for testing various algorithms that deal with transpositions in Monte-Carlo Tree Search (MCTS). We call this framework Upper Confidence bound for Direct acyclic graphs (UCD) as it constitutes an extension of Upper Confidence bound for Trees (UCT) for Direct acyclic graphs (DAG).When using transpositions in MCTS, a DAG is progressively developed instead of a tree. There are multiple ways to handle the exploration exploitation dilemma when dealing with transpositions. We propose parameterized ways to compute the mean of the child, the playouts of the parent and the playouts of the child. We test the resulting algorithms on several games. For all games, original configurations of our algorithms improve on state of the art algorithms.Subjects / Keywords
Monte-Carlo Tree Search; Transpositions; UCT Algorithm; Direct acyclic graph; Game tree search; Heuristic searchRelated items
Showing items related by title and author.
-
Méhat, Jean; Cazenave, Tristan; Saffidine, Abdallah (2010) Communication / Conférence
-
Cazenave, Tristan; Saffidine, Abdallah; Schofield, Michael John; Thielscher, Michael (2016) Communication / Conférence
-
Saffidine, Abdallah; Cazenave, Tristan (2012) Communication / Conférence
-
Méhat, Jean; Cazenave, Tristan (2010) Article accepté pour publication ou publié
-
Buron, Cédric; Cazenave, Tristan; Jouandeau, Nicolas; Saffidine, Abdallah (2014) Communication / Conférence