Battleship Probability Calculator: Methodology
The Battleship Probability Calculator checks all possible ship configurations for the given board layout and determines the probability of a ship being on each square. Alternatively, if it's early in the game and there are too many configurations to check all of them in the maximum processing time (3 seconds), it uses a randomized Monte Carlo algorithm to sample possible configurations.
The best square is the one that had a ship on it the most often. When the time's up, the results are displayed as a heat map with the best square highlighted. (If more than one square tied for the top spot, it returns multiple squares.)
The Problem With Battleship
There are a surprisingly large number of ways that the ships could be arranged: for example, a blank board with the usual 5 ships has 30,093,975,536 possible configurations. Although my code is as speed-optimized as I could manage (see below), it can still only run through about 270,000 configurations per second. At that rate, it would take 40 hours of non-stop processing to find the probabilities for a blank board.
Random samples are the only solution while the first couple of ships remain unsunk, because the probabilities are not easy to calculate mathematically. It would be nice if there were a simple formula that could act as a shortcut around all of those iterations, but if there is, no one seems to have figured it out yet.
Randomness
When sampling ship locations, the algorithm assumes that all possible ship locations are equally likely – in other words, it's assumed that your opponent placed their ships randomly. This could be considered a weakness, especially early in the game: if your opponent knows how the algorithm works, they'll place their ships away from the squares they know you'll try first. But as the game proceeds, this strategy will be less and less effective as your enemy's ships are restricted to the outer edges of the board.
Also, when the simulator is taking random samples early in the game, the numbers of samples sometimes represent a tiny fraction of the number of possible ship configurations, which means the simulator will occasionally produce odd results. For example, if you run the program twice for the same layout, sometimes you'll get two different answers for the best square.
However, I did check the probabilities against a completely rigourous program I wrote in the much faster language, C (which means no fancy web version, sorry), and found that the random method produces satisfyingly accurate results.
Optimization
In an earlier version of the program, sample ship configurations were generated naively – that is, by choosing spots on the board without first considering the user input – and then each new configuration was checked against the user's current board layout before getting counted. This turned out to be a terrible idea: a huge number of configurations ended up getting rejected, which meant a lot of processing time was being wasted.
The solution to this problem was to start with a list of all possible locations for each ship, eliminate locations that are impossible given the user input, then draw ship locations from this reduced list when testing configurations. This elimination process is pretty complex (386 lines of code!), but it runs in less than a hunredth of a second, and it's better to do it all at once rather than repeating that logic once for each of a hundred thousand iterations.
Here are some examples of ways possible ship locations can be eliminated:
- A 'miss' square disqualifies a bunch of intersecting locations.
- A square where a ship has been marked 'sunk' disqualifies any other ships from crossing that square.
- A ship that's been sunk has to cross the square where it was sunk.
- Sunk ships cannot cross any square that is not a 'hit'.
- Ships that are not sunk can't be located entirely on 'hit' squares.
- If a certain spot on the board could only hold one certain ship, no other ships can cross any of those squares.
- If a 'hit' square is surrounded by misses in 3 directions, there must be a ship pointing in the fourth direction.
And there are a whole lot of other ways I've optimized the code:
- A list of 'hit' squares is used to check the configurations against, rather than going through all 100 squares each time.
- Originally, when a possible configuration was found, the program checked all 100 squares to find the hits. Now, it simply saves the 5 ship locations for that configuration. Then, at the end of the code, the ship location frequencies are used to calculate the squares' hit frequencies all in one go.
- If any ship's location can be deduced, it gets removed from the random sampling process.
- PHP's natural sluggishness is mitigated through various technical means: using 'for' instead of 'foreach', getting required array values before starting loops, passing extra arguments instead of relying on global variables, and so on.
Pseudocode
for each ship from 1 to x {
for each square from 1 to 100 {
for each orientation from vertical to horizontal {
if the ship would overhang the board, continue
if the ship would overlap a "miss" square, continue
* see above for other ways to eliminate impossible ship locations
add this ship location to the list of possible locations
}
}
}
for each ship {
for each possible ship location {
for every other ship {
for every possible other-ship location {
if the two ships would overlap, save to list of incompatible locations
}
}
}
}
create array locationFrequencies
create int validConfigurationsCounted
for y times [loop A] {
for each ship {
select one random possible ship location
if location is incompatible with any other selected locations, continue loop A
}
if this configuration conflicts with the current board state (e.g. a "hit" square is not covered by a ship)
continue loop A
for each selected ship location {
++locationFrequencies[this ship location]
}
++validConfigurationsCounted
}
create array squareFrequencies
for each possible ship location {
for each square covered by this ship location {
squareFrequencies[this square] += locationFrequencies[this ship location]
}
}
divide each element in squareFrequencies by validConfigurationsCounted
Options
Auto-update: With this option turned off, the simulator will wait for the user to press the "Update" button before starting another simulation.
Show percentages: Shows each square's measured hit probability. The selected best squares are indicated with green text.
Diagonal skew: At the end of most games of Battleship, you've found the 4 biggest ships and you're left hunting around for the little one. The best way to handle this is to plan ahead from the start by (when possible) hitting only half of the squares: either the light ones or the dark ones in the image below.
If the skewing option is selected and the smallest ship has not yet been sunk, squares in this pattern are given a 20% boost to their chances of being selected as the "best" square. (Whether to favour the light or dark squares is decided based on the squares you've already tried.) This option does not affect the heat map colours or the reported numerical probabilities.
Game Version
In the html5 game, the AI has three possible play modes:
- Learning Mode uses player ship placement data from all other played games as well as the probabilistic approach described above to choose a square.
- Probability Mode uses the pure probabilistic approach to choose a square, with a four-second processing time and the "diagonal skewing" option turned on.
- Random Mode chooses squares at random, even after it gets a hit.
At the end of every game, anonymous data about the results (time, winner, number of moves, AI ship locations, player ship locations, AI Mode, and whether or not the player had "play for me" turned on) are saved to a database, which is then used to generate all the pretty graphs on the stats page. The player's ship placements are also added to the record for use in the "Learning" AI Mode.
If you're still reading this and you have any ideas about more interesting ways I could use all of that data, let me know!