UCD: Upper Confidence Bound for Rooted Directed Acyclic Graphs

Méhat, Jean; Cazenave, Tristan; Saffidine, Abdallah

Méhat, Jean; Cazenave, Tristan; Saffidine, Abdallah (2010), UCD: Upper Confidence Bound for Rooted Directed Acyclic Graphs, International Conference on Technologies and Applications of Artificial Intelligence, IEEE, p. 467-473

Type

Communication / Conférence

Date

2010

Titre du colloque

TAAI 2010

Date du colloque

2010-11

Ville du colloque

Hsinchu City

Pays du colloque

Taïwan

Titre de l'ouvrage

International Conference on Technologies and Applications of Artificial Intelligence

Éditeur

IEEE

Isbn

978-1-4244-8668-7

Pages

467-473

Résumé (EN)

In this paper we present a framework for testing various algorithms that deal with transpositions in Monte-Carlo Tree Search (MCTS). When using transpositions in MCTS, a Directed Acyclic Graph (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 LeftRight an abstract single player game and on Hex. For both games, original configurations of our algorithms improve on state of the art algorithms.