Paper published in a book (Scientific congresses and symposiums)
Comparison of Different Selection Strategies in Monte-Carlo Tree Search for the Game of Tron
Perrick, Pierre; Lupien St-Pierre, David; Maes, Francis et al.
2012In IEEE Conference on Computational and Intelligence in Games 2012
Peer reviewed
 

Files


Full Text
paper88.pdf
Publisher postprint (402.09 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Monte Carlo Tree Search; Selection Policy; Games
Abstract :
[en] Monte-Carlo Tree Search (MCTS) techniques are essentially known for their performance on turn-based games, such as Go, for which players have considerable time for choosing their moves. In this paper, we apply MCTS to the game of Tron, a simultaneous real-time two-player game. The fact that players have to react fast and that moves occur simultaneously creates an unusual setting for MCTS, in which classical selection policies such as UCB1 may be suboptimal. In this paper, we perform an empirical comparison of a wide range of selection policies for MCTS applied to Tron, with both deterministic policies (UCB1, UCB1-Tuned, UCB-V, UCBMinimal, OMC-Deterministic, MOSS) and stochastic policies (Epsilon-greedy, EXP3, Thompson Sampling, OMC-Stochastic, PBBM). From the experiments, we observe that UCB1-Tuned has the best behavior shortly followed by UCB1. Even if UCB-Minimal is ranked fourth, this is a remarkable result for this recently introduced selection policy found through automatic discovery of good policies on generic multi-armed bandit problems. We also show that deterministic policies perform better than stochastic ones for this problem.
Disciplines :
Computer science
Author, co-author :
Perrick, Pierre
Lupien St-Pierre, David ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore)
Maes, Francis ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Ernst, Damien  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Smart grids
Language :
English
Title :
Comparison of Different Selection Strategies in Monte-Carlo Tree Search for the Game of Tron
Publication date :
2012
Event name :
IEEE Conference on Computational and Intelligence in Games ( CIG 2012 )
Event place :
Granada, Spain
Event date :
from 10-09-2012 to 14-09-2012
Audience :
International
Main work title :
IEEE Conference on Computational and Intelligence in Games 2012
Pages :
242-249
Peer reviewed :
Peer reviewed
Available on ORBi :
since 24 October 2012

Statistics


Number of views
92 (9 by ULiège)
Number of downloads
839 (5 by ULiège)

Bibliography


Similar publications



Contact ORBi