Sampling battleships boards for hit estimation using Monte Carlo Tree Search

• Eduardo Naslausky UFRJ
• Daniel Ratton Figueiredo UFRJ

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

Resumo

Batalha Naval é um jogo clássico de tabuleiro com duas pessoas. Um dos problemas fundamentais do jogo é determinar a próxima posição do tabuleiro a ser revelada pelo adversário. Intuitivamente, a posição escolhida deveria corresponder a um barco (acerto), tendo em vista o objetivo do jogo de afundar todos os barcos do adversário. Este trabalho utiliza o algoritmo de Monte Carlo Tree Search para gerar amostras de tabuleiros válidos com todos os barcos a partir de um tabuleiro inicial (configuração atual do jogo). A probabilidade de acerto de cada posição oculta do tabuleiro é calculada utilizando as amostras geradas. Para avaliar a qualidade deste algoritmo, partidas foram simuladas onde cada jogada utiliza a posição de maior probabilidade de acerto do turno anterior. Resultados indicam que a acurácia (top-1) depois de uma jogada é cerca de 65% e cresce monotonicamente, chegando a 80% depois de 10 jogadas.

Referências

Arkin, E. M., Meijer, H., Mitchell, J. S., Rappaport, D., and Skiena, S. S. (1993). Decision trees for geometric models. In ACM Annual Symposium on Computational Geometry, pages 369–378.

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.

Crombez, L., da Fonseca, G. D., and Gerard, Y. (2020). Efficient algorithms for Battleship. In International Conference on Fun with Algorithms (FUN 2020), pages 11:1–15.

Fiat, A. and Shamir, A. (1989). How to find a battleship. Networks, 19(3):361–371.

Hainzl, E.-M., Löffler, M., Perz, D., Tkadlec, J., and Wallinger, M. (2022). Finding a battleship of uncertain shape. In 38th European Workshop on Computational Geometry.

Moser, Joseph M. Kramer, F. (1982). Lines and parabolas in taxicab geometry. Pi Mu Epsilon Journal, 7(7):441–448.

Port, A. C. and Yampolskiy, R. V. (2012). Using a ga and wisdom of artificial crowds to solve solitaire battleship puzzles. In International Conference on Computer Games (CGAMES), pages 25–29. IEEE.

Sevenster, M. (2004). Battleships as a decision problem. ICGA Journal, 27(3):142–149.

Smith, B. M. (2006). Constraint programming models for solitaire battleships. Technical report, University College Cork, Ireland.

Świechowski, M., Godlewski, K., Sawicki, B., and Mańdziuk, J. (2023). Monte carlo tree search: A review of recent modifications and applications. Artificial Intelligence Review, 56(3):2497–2562.