Battleship is by all accounts one of the dullest games ever created. But it’s amazing what one is driven to on a plane without internet access or a good book. In this case, one is driven to build a Javascript simulation of Battleship in order to measure the value of basic Battleship strategic insights.
A screenshot of the simulation is below. An asterisk represents an empty square, “>” represents a ship placed horizontally, and “v” represents a ship placed vertically. Player 2 always fires at a random square. His primary purpose in the simulation is to serve as a foil (and baseline) for our increasingly intelligent player 1. Ship placement is randomly generated for each game, like so:
Figure 1 – Random Board Layout
In the first simulation, both players fire at random squares. The random firing continues even when a player scores a hit. Across 20,000 trials, player 1 won 50.4% of the time – a 50/50 toss-up, as expected. The average length of a game was 182.1 turns, which means that players had to hit over 90% of the game’s 200 squares before finishing a game. Although it’s not really a “strategy”, it is interesting to measure the value of going first. When player 1 always takes the first turn, she wins 53.6% of the time across 20,000 trials. Here is an example of the scorched-earth board at the conclusion of a random game:
Figure 2 – Finished Game, Firing at Random Squares
Surely we can make this game shorter! Things start to get more fun when we give player 1 her first strategic insight. Specifically, when player 1 scores a hit, she now searches the immediately-adjacent squares until she sinks a ship. More specifically, player 1 begins by searching left until (i) she hits an already-struck square or goes out of bounds, in which case she will reverse direction, or (ii) sinks a boat, in which case she will return to firing at random. Here, player 1 has just hit the rightmost square of player 2’s four boat:
Figure 3 – Adjacent Search
The initial hit:
She begins working left:
Until she sinks:
After the sink, player 1 begins randomly searching again. There’s just one problem with this strategy: player 1 doesn’t have a very good memory. Although she will doggedly search nearby – first going horizontally, then vertically – until she sinks a ship, she doesn’t know when she’s hit multiple boats. Here’s an example. The initial hit is to a boat placed vertically:
Figure 4 – The Problem With Naïve Adjacent Search
The initial hit:
She searches left, hitting another boat followed by an empty square, then searches right:
Upon failing to sink left and right, she starts searching vertically at the location of the original hit:
Until she sinks a ship:
At this point, player 1 will begin to fire randomly, because she isn’t programmed to remember the other non-sinking, horizontal hit. Even with this flaw, however, searching adjacent squares makes an enormous improvement to player 1’s record. Over 20,000 trials, she now wins 92.1% of the time. Average game length drops by about 50 turns to 132.3 turns.
So what happens when we make player 1 a little bit smarter, enabling her to remember multiple hits that don’t result in a sink? Things get pretty ugly for player 2. Across 20,000 trials, player 1 wins 98.1% of the time. Ouch.
The final tweak is to make player 1’s random guesses a little more shrewd. Since the smallest boat size is 2, she only has to guess every other square in order to guarantee that she’ll find all of player 2’s boats. Look at this diagram and you’ll see what I mean. No two boat could hide in this pattern:
Figure 5 – Ignore Alternate Squares
With this change in place, player 1 wins an overwhelming 99.4% of games she plays, and brings the average game length down to a far more tolerable 97 turns. Here’s how performance compares across each of these scenarios:
Figure 6 – Games Won and Average Game Length
Now, if your opponent knows all of these same strategies… we’re back to a coin-flip game and the snoozefest that is Battleship resumes.
