Beating Bomberman with Artificial Intelligence

  • Juarez Monteiro PUCRS
  • Roger Granada PUCRS
  • Rafael C. Pinto IFRS
  • Rodrigo C. Barros PUCRS

Resumo


Artificial Intelligence (AI) seeks to bring intelligent behavior for machines by using specific techniques. These techniques can be employed in order to solve tasks, such as planning paths or controlling intelligent agents. Some tasks that use AI techniques are not trivially testable, since it can handle a high number of variables depending on their complexity. As digital games can provide a wide range of variables, they become an efficient and economical means for testing artificial intelligence techniques. In this paper, we propose a combination of a behavior tree and a Pathfinding algorithm to solve a maze-based problem using the digital game Bomberman of the Nintendo Entertainment System (NES) platform. We perform an analysis of the AI techniques in order to verify the feasibility of future experiments in similar complex environments. Our experiments show that our intelligent agent can be successfully implemented using the proposed approach.

Referências


Cui, X. and Shi, H. (2011). A*-based pathfinding in modern computer games. International Journal of Computer Science and Network Security, 11(1):125–130.

Holmgard, C., Liapis, A., Togelius, J., and Yannakakis, G. N. (2014). Personas versus clones for player decision modeling. In Pisan, Y., Sgouros, N., and Marsh, T., editors, Entertainment Computing – ICEC 2014, volume 8770 of Lecture Notes in Computer Science, pages 159–166. Springer Berlin Heidelberg.

Idrees, H., Zamir, A. R., Jiang, Y.-G., Gorban, A., Laptev, I., Sukthankar, R., and Shah, M. (2017). The fTHUMOSg challenge on action recognition for videos “in the wild”. Computer Vision and Image Understanding, 155:1–23.

Liapis, A., Yannakakis, G., and Togelius, J. (2013). Generating map sketches for strategy games. In Proceedings of 16th European Conference on Applications of Evolutionary Computation, pages 264–273, Berlin, Heidelberg. Springer Berlin Heidelberg.

Lucas, S. M. (2008). Computational intelligence and games: challenges and opportunities. International Journal of Automation and Computing, 5(1):45–57.

Miranda, M., Sánchez-Ruiz, A. A., and Peinado, F. (2016). A neuroevolution approach to imitating human-like play in ms. pac-man video game. In Proceedings of the 3rd Congreso de la Sociedad Espa˜nola para las Ciencias del Videojuego, CoSeCiVi’16, pages 113–124. CEUR-WS.org.

Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540):529–533.

Newborn, M. and Newborn, M. (1997). Kasparov versus Deep Blue: Computer chess comes of age. Springer-Verlag New York, Inc., Secaucus, NJ, USA.

Ortega, J., Shaker, N., Togelius, J., and Yannakakis, G. N. (2013). Imitating human playing styles in super mario bros. Entertainment Computing, 4(2):93–104.

Rogers, S. (2014). Level Up! The guide to great video game design. John Wiley & Sons.

Russell, S. J. and Norvig, P. (1995). Artificial Intelligence: A Modern Approach. Ed. Prentice Hall, New Jersey, 2nd edition.

Schuurmans, D. and Zinkevich, M. A. (2016). Deep learning games. In Advances in Neural Information Processing Systems 29, pages 1678–1686. Curran Associates, Inc.

Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., and Hassabis, D. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484–489.

Wang, H., Wang, N., and Yeung, D.-Y. (2015). Collaborative deep learning for recommender systems. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1235–1244, New York, NY, USA. ACM.

Publicado
22/10/2018
MONTEIRO, Juarez; GRANADA, Roger; PINTO, Rafael C.; BARROS, Rodrigo C.. Beating Bomberman with Artificial Intelligence. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 15. , 2018, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . p. 353-364. ISSN 2763-9061. DOI: https://doi.org/10.5753/eniac.2018.4430.