Optimal Strategies on Attack and Defense in the Game of Battleship

Chanbin Park
Handong International School

Abstract

Battleship is a well-known strategic guessing game played by two players. The players first place their ships and then continuously try to sink every ship of the opponent. In this paper, the act of placing ships is defined as “defense”, and the act of guessing ships is defined as “attack”. The goal of this paper was to find good attacks against bad defense and good defense against good attack strategies. First, two good attack strategies, hunt and target/probability density strategy, are introduced and are compared with a randomly guessing strategy. Especially, when implementing the probability density strategy, using bit optimization resulted in a significantly faster algorithm than a naive implementation. Then, in the final section, several good defense strategies against the two good attack strategies are shown.

Please click to read the paper.