Article (Scientific journals)
Monte Carlo search algorithm discovery for single-player games
Maes, Francis; Lupien St-Pierre, David; Ernst, Damien
2013In IEEE Transactions on Computational Intelligence and AI in Games, 5 (3), p. 201-213
Peer Reviewed verified by ORBi
 

Files


Full Text
tcaig2013.pdf
Publisher postprint (2.16 MB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Monte-Carlo Search; Algorithm Selection; Grammar of Algorithms
Abstract :
[en] Much current research in AI and games is being devoted to Monte Carlo search (MCS) algorithms. While the quest for a single unified MCS algorithm that would perform well on all problems is of major interest for AI, practitioners often know in advance the problem they want to solve, and spend plenty of time exploiting this knowledge to customize their MCS algorithm in a problem-driven way. We propose an MCS algorithm discovery scheme to perform this in an automatic and reproducible way. We first introduce a grammar over MCS algorithms that enables inducing a rich space of candidate algorithms. Afterwards, we search in this space for the algorithm that performs best on average for a given distribution of training problems. We rely on multi-armed bandits to approximately solve this optimization problem. The experiments, generated on three different domains, show that our approach enables discovering algorithms that outperform several well-known MCS algorithms such as Upper Confidence bounds applied to Trees and Nested Monte Carlo search. We also show that the discovered algorithms are generally quite robust with respect to changes in the distribution over the training problems.
Disciplines :
Computer science
Author, co-author :
Maes, Francis
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)
Ernst, Damien  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Smart grids
Language :
English
Title :
Monte Carlo search algorithm discovery for single-player games
Publication date :
September 2013
Journal title :
IEEE Transactions on Computational Intelligence and AI in Games
ISSN :
1943-068X
eISSN :
1943-0698
Publisher :
Institute of Electrical and Electronics Engineers, United States - New Jersey
Volume :
5
Issue :
3
Pages :
201-213
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 16 September 2013

Statistics


Number of views
337 (44 by ULiège)
Number of downloads
382 (38 by ULiège)

Scopus citations®
 
8
Scopus citations®
without self-citations
7
OpenCitations
 
5

Bibliography


Similar publications



Contact ORBi