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

Abstract

Battleships is a classic board game for two people. One of the main problems of the game is to determine the next position on the board to take your turn and be revealed by the opponent. Intuitively, the chosen position should contain a boat (hit), seen as the objective of the game is to sink all enemy boats. This work uses Monte Carlo Tree Search algorithm to sample valid boards with all boats from a given initial empty board (current game state). The hit estimation for every hidden board cell is made by using the sampled boards. To evaluate the quality of this algorithm, matches have been simulated where every turn uses the best estimated hit coordinate from the previous turn. Results indicate a 65% acuracy for the top-1 coordinate after one turn and it grows monotonically, reaching 80% after 10 turns.

References

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.