Emil Juul Jacobsen
Rasmus Greve
Julian Togelius
ABSTRACT
Monte Carlo Tree Search (MCTS) is applied to control the player character in a clone of the popular platform game Super Mario Bros. Standard MCTS is applied through search in state space with the goal of moving the furthest to the right as quickly as possible. Despite parameter tuning, only moderate success is reached. Several modifications to the algorithm are then introduced specifically to deal with the behavioural pathologies that were observed. Two of the modifications are to our best knowledge novel. A combination of these modifications is found to lead to almost perfect play on linear levels. Furthermore, when adding noise to the benchmark, MCTS outperforms the best known algorithm for these levels. The analysis and algorithmic innovations in this paper are likely to be useful when applying MCTS to other video games.
- S. Bojarski and C. Congdon. Realm: A rule-based evolutionary computation agent that learns to play mario. In Computational Intelligence and Games (CIG), 2010 IEEE Symposium, pages 83--90, 2010.Google Scholar
Cross Ref
- C. Browne, E. Powley, D. Whitehouse, S. Lucas, P. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton. A survey of monte carlo tree search methods. Computational Intelligence and AI in Games, IEEE Transactions on, 4(1):1--43, 2012.Google Scholar
- G. M. J. Chaslot, M. H. Winands, H. J. V. D. HERIK, J. W. Uiterwijk, and B. Bouzy. Progressive strategies for monte-carlo tree search. New Mathematics and Natural Computation, 4(03):343--357, 2008.Google ScholarCross Ref
- D. Churchill, A. Saffidine, and M. Buro. Fast heuristic search for rts game combat scenarios. Proceedings of AIIDE, 2012.Google Scholar
- M. Ebner, J. Levine, S. Lucas, T. Schaul, T. Thompson, and J. Togelius. Towards a video game description language. Dagstuhl Follow-up. To appear., Preprint available at http://www. idsia. ch/\ tom/publications/dagstuhl-vgdl. pdf, 2013.Google Scholar
- M. Genesereth, N. Love, and B. Pell. General game playing: Overview of the aaai competition. AI magazine, 26(2):62, 2005.Google ScholarDigital Library
- S. Karakovskiy and J. Togelius. The mario ai benchmark and competitions. IEEE Transactions on Computational Intelligence and AI in Games, 2012.Google ScholarCross Ref
- C.-S. Lee, M.-H. Wang, G. Chaslot, J.-B. Hoock, A. Rimmel, O. Teytaud, S.-R. Tsai, S.-C. Hsu, and T.-P. Hong. The computational intelligence of mogo revealed in taiwan's computer go tournaments. Computational Intelligence and AI in Games, IEEE Transactions on, 1(1):73--89, 2009.Google Scholar
- T. Pepels and M. H. Winands. Enhancements for monte-carlo tree search in ms pac-man. In Computational Intelligence and Games (CIG), 2012 IEEE Conference on, pages 265--272. IEEE, 2012.Google ScholarCross Ref
- D. Perez, P. Rohlfshagen, and S. M. Lucas. Monte-carlo tree search for the physical travelling salesman problem. In Applications of Evolutionary Computation, pages 255--264. Springer, 2012. Google ScholarDigital Library
- E. Powley, D. Whitehouse, and P. Cowling. Monte carlo tree search with macro-actions and heuristic route planning for the physical travelling salesman problem. In Computational Intelligence and Games (CIG), 2012 IEEE Conference on, pages 234--241, 2012.Google ScholarCross Ref
- S. Samothrakis, D. Robles, and S. Lucas. Fast approximate max-n monte carlo tree search for ms pac-man. Computational Intelligence and AI in Games, IEEE Transactions on, 3(2):142--154, 2011.Google Scholar
- F. W. Takes and W. A. Kosters. Solving samegame and its chessboard variant. In Proceedings of the 21st Benelux Conference on Artificial Intelligence (BNAIC'09)(eds. T. Calders, K. Tuyls, and M. Pechenizkiy), pages 249--256, 2009.Google Scholar
- J. Togelius, S. Karakovskiy, and R. Baumgarten. The 2009 mario ai competition. In Proceedings of the IEEE Congress on Evolutionary Computation, 2010.Google ScholarCross Ref
Index Terms
- Monte Mario: platforming with MCTS
Recommendations
Using evaluation functions in Monte-Carlo Tree Search
For decades the game playing algorithms of choice have been based on the mini-max algorithm and have had considerable success in many games, e.g., chess and checkers. Recently a new algorithmic paradigm called Monte-Carlo Tree Search (MCTS) has been ...
Toolification of games: achieving non-game purposes in the redundant spaces of existing games
ACE '15: Proceedings of the 12th International Conference on Advances in Computer Entertainment TechnologyGamification is the use of game elements and game design techniques in non-game contexts. Serious games is the use of complete games for non-entertainment purposes. A major criticism of them is that it is difficult to realize an appropriate game balance ...
Applying and Improving Monte-Carlo Tree Search in a Fighting Game AI
ACE '16: Proceedings of the 13th International Conference on Advances in Computer Entertainment TechnologyThis paper evaluates the performance of Monte-Carlo Tree Search (MCTS) in a fighting game AI and proposes an improvement for the algorithm. Most existing fighting game AIs rely on rule bases and react to every situation with predefined actions, making ...
Comments