2022-12-20 Update - There is now an accompanying webapp!

I’ve been playing battleship a lot recently. My friends and I have given up on playing pool and are pretty much exclusively playing this game.

After winning a ton of games by luck, I figured I could do even better using a strategy.

Rules⌗

Since there are a few different rulesets, here’s a quick overview of the ruleset I was playing with on GamePigeon’s iMessage version of the game.

  1. The board is 10x10 squares.
  2. There are 1 len-4, 2 len-3, 3 len-2, and 4 len-1 ships.
  3. You cannot place ships adjacent or diagonal to another ship.

Naive Strategy⌗

An obvious strategy for Battleship is to shoot where the ships are most likely to be placed. To calculate this probability, we can enumerate over all the possible ships on the board.

While we do this, count the number of times a ship occupies each specific square. Then, we can make that array into a heat map that shows the probability of a ship being in that particular square.

Since there are 1 len-4, 2 len-3, 3 len-2, and 4 len-1 ships, we will increment each square by the number of ships that could be placed there. That’s why the squares are incrementing by values other than 1.

We end up with a heatmap that looks like this:

Dark squares are less likely to have a ship, and pink squares are more likely.

We can do this mid-game to get a heatmap specific to that board:

All the dark squares are confirmed hits/misses.

We’ll be referring to these values as “probability scores” from here on out. Just remember that “probability scores” are the number of ships that could occupy a square.

Information Gain⌗

Since you cannot place a ship adjacent or diagonal to another ship, all the squares around a hit ship are guaranteed to be a miss. We can exploit this aspect of the game by tracking how many ship positions would be eliminated if a ship occupied that square.

Add up the probabilities surrounding a hit to get an information gain for that square

Information gain can be combined with the Naive Strategy in order to calculate both the probability of a hit, along with the value that hit would provide (how many possible positions it would eliminate).

This is what we do for a 2x1 ship

For each square in each ship position, we add up the surrounding probabilities for that position.

As a heatmap:

With this heatmap, the center 4 squares are the best place for your first shot

Again, we can do this process mid-game to get a recommendation on where to fire next.

Compared to the naive strategy, this new strategy shows stronger preferences for certain squares

Sinking Ships⌗

Once we have a hit, what do we do next?

We already know the squares surrounding our hit are eliminated, so let’s pick the next square by only looking at the probability scores for the squares that weren’t already eliminated.

Get the sum of these squares to find the most promising second shot.

Add them together to get the scores for each direction.

Since the upper pink squares are the brightest, they have the best probability. Let’s fire in the upper direction.

That was a hit. Now that we know the ship is vertically oriented, only consider up and down as valid directions.

Continue until we discover the whole ship.

Optimal Sunk-cost Strategy⌗

The Sinking Ships step says we should fire upwards.

We can adjust the previous step to account for the remaining ships. For example, in a situation like the one above, a hit says we should fire upwards. However, if we know there are only len 3 ships left, we can instead fire directly to the right twice for the maximum info gain.

Implementing the relative probability of each ship length occupying the n+1th square, we get the best possible algorithm that I can come up with.

Firing to the right is the best shot according to the algorithm.

Closing Thoughts⌗

This was a fun hobby project. Feel free to try out the code on your own and make pull requests to improve it.

Play around with the webapp version here.

Github Repo

A wish-list item I have is to create a simulator that implements these strategies and measure how well they do against random board layouts. Feel free to tackle this if you have a spare weekend. I’d love to add it to the repo.