Performance of Monte Carlo Tree Search Algorithms when Playing the Game Ataxx

Leonardo F. R. Ribeiro; Daniel R. Figueiredo

doi:10.5753/eniac.2018.4423

Leonardo F. R. Ribeiro UFRJ
Daniel R. Figueiredo UFRJ

DOI: https://doi.org/10.5753/eniac.2018.4423

Resumo

Monte Carlo Tree Search (MCTS) has recently emerged as a promising technique to play games with very large state spaces. Ataxx is a simple two-player board game with large and deep game tree. In this work, we apply different MCTS algorithms to play the game Ataxx and evaluate its performance against different adversaries (e.g., minimax2). Our analysis highlights one key aspect of MCTS, the trade-off between samples (and accuracy) and chances of winning the game which translates to a trade-off between the delay in making a move and chances of winning.

Referências

Abramson, B. (1990). Expected-outcome: A general model of static evaluation. IEEE transactions on pattern analysis and machine intelligence, 12(2):182–193.

Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235–256.

Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen,

P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S. (2012). A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43.

Chaslot, G., Bakkes, S., Szita, I., and Spronck, P. (2008). Monte-carlo tree search: A new framework for game ai. In AIIDE.

Cuppen, E. (2007). Using monte carlo techniques in the game ataxx. B.Sc. Thesis, Maastricht University.

Heyden, C. (2009). Implementing a computer player for carcassonne. Master’s thesis, Department of Knowledge Engineering, Maastricht University.

Jacobsen, E. J., Greve, R., and Togelius, J. (2014). Monte mario: platforming with mcts. In Proc. Annual Conference on Genetic and Evolutionary Computation, pages 293–300.

Lorentz, R. J. (2008). Amazons discover monte-carlo. In International Conference on Computers and Games, pages 13–24.

Nijssen, J. (2007). Playing othello using monte carlo. Strategies, pages 1–9.

Russell, S. J. and Norvig, P. (2016). Artificial intelligence: a modern approach. Pearson Education.

Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016). Mastering the game of go with deep neural networks and tree search. Nature, 529(7587).

Wikipedia (2018). Monte carlo tree search - Wikipedia. [Online; accessed May-2018].