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.
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.
- The board is 10x10 squares.
- There are 1 len-4, 2 len-3, 3 len-2, and 4 len-1 ships.
- You cannot place ships adjacent or diagonal to another ship.
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:
We can do this mid-game to get a heatmap specific to that board:
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.
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.
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).
For each square in each ship position, we add up the surrounding probabilities for that position.
As a heatmap:
Again, we can do this process mid-game to get a recommendation on where to fire next.
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.
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.
Continue until we discover the whole ship.
Optimal Sunk-cost Strategy⌗
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.
This was a fun hobby project. Feel free to try out the code on your own and make pull requests to improve it.
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.