Sampling battleships boards for hit estimation using Monte Carlo Tree Search - Naslausky, Eduardo; Figueiredo, Daniel Ratton (Anais do Encontro Nacional de Inteligência Artificial e Computacional (ENIAC); 2025: Anais do XXII Encontro Nacional de Inteligência Artificial e Computacional, 2025)
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.