Monte Carlo Beam Search
- 15 March 2012
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computational Intelligence and AI in Games
- Vol. 4 (1) , 68-72
Abstract
Monte Carlo tree search is the state of the art for multiple games and for solving puzzles such as Morpion Solitaire. Nested Monte Carlo (NMC) search is a Monte Carlo tree search algorithm that works well for solving puzzles. We propose to enhance NMC search with beam search. We test the algorithm on Morpion Solitaire. Thanks to beam search, our program has been able to match the record score of 82 moves. Monte Carlo beam search achieves better scores in less time than NMC search alone.Keywords
This publication has 10 references indexed in Scilit:
- Combining UCT and Nested Monte Carlo Search for Single-Player General Game PlayingIEEE Transactions on Computational Intelligence and AI in Games, 2010
- Beam-ACO for the travelling salesman problem with time windowsComputers & Operations Research, 2010
- Monte Carlo Tree Search in HexIEEE Transactions on Computational Intelligence and AI in Games, 2010
- Utilisation de la recherche arborescente Monte-Carlo au HexRevue d'intelligence artificielle, 2009
- Parallel Nested Monte-Carlo search2009
- CadiaPlayer: A Simulation-Based General Game PlayerIEEE Transactions on Computational Intelligence and AI in Games, 2009
- A Parallel Monte-Carlo Tree Search Algorithm2008
- Parallel Monte-Carlo Tree Search2008
- Single-Player Monte-Carlo Tree Search2008
- Combining online and offline knowledge in UCT2007