About Battleship Calculator

How to Use It

Click once on a square to mark it as a miss. Click again to mark it as a hit. Click a third time to clear it. Toggle the boats to tell the algorithm which ones have been sunk.

After any click, the grid will update with a heat map of where boats are likely to be. The darker the green, the more likely a boat will be there. The most likely squares are marked yellow, to make them stand out more. The numbers in each square is the probability of a boat being there.

The number of iterations listed is how many random positions were collected that went into the heat map (see next section for more details).

If after a click, the board is all 0's and the number of iterations is 0, that means the board is in an impossible state. For example, marking the carrier as sunk when only four hits are on the board.

How the algorithm works

The calculator randomly generates a board position that matches all of the available data — every hit, every miss, and every boat you've marked as sunk — while keeping track of which squares the boats land on. It then repeats this many times, building up a heat map of which squares are most likely to contain a boat.

Right now the algorithm is kind of inefficient with how it handles highly constrained positions. With the way my algorithm works, it's very hard for it to actually find a position that matches all the constraints. So with a highly constrained position, it may not find enough solutions to make a reasonable heat map.

For example, put a hit in each corner and one more somewhere in the middle of the board. On my computer, I only get somewhere between 0-5 iterations ☹️ However, I'm currently too lazy to do anything about it.

Known shortcomings

This approach has a couple of known weaknesses.

The first is that in a real game, it generally isn't a good idea to place two boats so that they're touching. But this algorithm searches through every possible configuration, weighting "touching" arrangements just as heavily as non-touching ones.

The second is that right now there's a way to tell the algorithm which boats were sunk, but not which hits corresponded to which boat. This can lead to an incorrect analysis. For example, suppose you've already sunk the patrol boat and correctly marked it as sunk. But then, later in the game, you start sinking another ship — say, the carrier. After your second hit on the carrier, the algorithm gets confused and says "whoa, hold on: I know the patrol boat is sunk, but I don't know which hits correspond to it." So it'll suddenly start suggesting squares next to the sunken patrol boat — squares you know are unlikely to be a hit.

Inspiration

This analysis was inspired by this blog post.

That said, I think the algorithm they use in the blog post is kind of weird, and likely has a bug in it. In their walkthrough section (the last section), their move 5 and move 6 suggestions seem absolutely bananas to me. We have two hits in a row — just keep extending them! They claim that "at this point, it's just as likely that the two hits could be from two parallel up/down ships as one side to side," which I find extremely hard to believe. In fact, my algorithm strongly agrees with my normal human intuition here.

Further down the game, when the blog's algorithm is choosing move 32, you can see from their heat map that it's suggesting positions for the carrier that are mathematically impossible (the 2×4 block of squares at the top). This points to some bug in their algorithm — or at the very least, there's something I'm misunderstanding.