Battleship: How the Computer Finds Your Ships

Battleship was the game I played with my father as a child, which is why I wanted to design my own. As one of my high-school graduation projects, I wrote a desktop version in C#; the original code is on GitHub. That version was a plain game. The hunt & target algorithm in this post came later; today it’s how the Normal level of the game on this site plays.

At first glance Battleship looks like a game of luck. Two players hide their ships from each other and take turns calling out cells, and all anyone gets to see is splashes and hits. Yet even a computer that knows nothing about its opponent can sink the whole fleet in fewer than half the shots that someone firing blind would use. The secret is a little counting, a little probability and a few simple rules.

In this post we’ll get to know the computer opponent in this site’s game, one difficulty level at a time: Easy fires at random, Normal plays hunt & target, and Hard counts every place the ships could still be hiding. You don’t need to know any maths: I’ll explain every formula and every symbol in plain words the first time it shows up. Every board, chart and simulation result in the post is also computed by the game’s own code while the site is built: when a figure says the computer fires at E5, the game really did pick E5.

The rules of the game

The board is a 10 × 10 grid, so 100 cells. The columns are lettered A to J from left to right and the rows are numbered 1 to 10 from top to bottom; E5 is the cell where column E meets row 5. Each player has five ships: a carrier of five cells, a battleship of four, a cruiser and a submarine of three each, and a destroyer of two. Together they cover 17 cells.

Ships lie inside the board, either horizontally or vertically. On this site they may touch each other but never overlap. The player whose turn it is calls out a cell, and the other side answers “miss” or “hit”. When the last cell of a ship is hit, that ship sinks, and the game shows where the sunk ship was, so from then on you know exactly which cells it covered.

Before we look at how the computer plays, let’s do a little counting exercise. The numbers will come in handy later.

How many places can a single ship hide?

Let’s call each place where a ship could sit on the board a position. How many positions does one ship have? Let’s count them together. We’ll do the sum for every board and every ship at once, and for that two short names are enough: call the number of cells along one side of the board $n$ , and the length of the ship $L$ . On our board $n = 10$ , and for the cruiser $L = 3$ . Wherever you see the letters, you can think of those numbers.

Step one: a single row. Number the cells of a row from left to right: 1, 2, …, $n$ . A ship of length $L$ covers $L$ cells side by side in the row. Its place is fixed by the cell it starts in, that is, its leftmost cell; call that cell’s number $k$ . The ship starts in cell $k$ and runs on for $L$ cells:

k,\; k + 1,\; \dots,\; k + L - 1.

For example, a cruiser that starts in cell 4 covers cells 4, 5 and 6; its last cell is $4 + 3 - 1 = 6$ . For the ship not to hang off the board, the number of its last cell can be at most $n$ (the sign $\le$ means “less than or equal to”):

k + L - 1 \le n, \quad \text{that is,} \quad k \le n - L + 1.

(We got the version on the right by taking $L - 1$ away from both sides of the one on the left.) Since $k$ is at least 1, the ship can start in cells 1, 2, …, $n - L + 1$ . So a row holds exactly $n - L + 1$ positions. For the cruiser that’s $10 - 3 + 1 = 8$ .

Every position of the cruiser (

L = 3

) in one row, as the game’s code lists them. There is one position for each starting cell

k

, and

k

runs from 1 to 8. The numbers in the bottom row show how many of these positions pass over each cell. The highlighted cell 5 is covered by three positions: the ones that start at

k = 3

, 4 and 5.

Step two: every row. The board has $n$ rows, each with $n - L + 1$ positions. Adding the same number up $n$ times is the same as multiplying it by $n$ ; that’s the multiplication rule of counting. So the number of horizontal positions is

n\,(n - L + 1).

(In maths, writing two things side by side with no sign between them means multiplying them. The dot $\cdot$ between two numbers is a multiplication sign too.) For the cruiser, $10 \cdot 8 = 80$ .

Step three: the columns. The board is square, so the same sum works for the columns. Imagine turning the board through 90 degrees: the rows become columns, and horizontal ships become vertical ones. So there are also $n\,(n - L + 1)$ vertical positions; 80 again for the cruiser.

Step four: all of them together. A ship lies either horizontally or vertically, never both at once. To count two groups that don’t mix, we simply add their sizes (that’s the addition rule):

n\,(n - L + 1) + n\,(n - L + 1) = 2n\,(n - L + 1).

For the cruiser, $2 \cdot 10 \cdot (10 - 3 + 1) = 2 \cdot 10 \cdot 8 = 160$ .

(This only works for ships at least two cells long: a one-cell ship would sit in the same position whether “horizontal” or “vertical”, and the formula would count every position twice. Luckily, the fleet has no one-cell ship.)

The ships of the fleet are 5, 4, 3, 3 and 2 cells long. For them the formula gives 120, 140, 160, 160 and 180 positions, 760 in all.

Ship	Cells	Positions
Carrier	5	2 · 10 · 6 = 120
Battleship	4	2 · 10 · 7 = 140
Cruiser	3	2 · 10 · 8 = 160
Submarine	3	2 · 10 · 8 = 160
Destroyer	2	2 · 10 · 9 = 180
Fleet	17	760

The five ships and how many positions each one has on an empty board. The game’s code counts them one by one, and every count matches the formula

2n\,(n - L + 1)

How many ways can the whole fleet be arranged?

A single ship has at most 180 positions. So in how many different ways can all five ships be arranged together?

If ships could overlap, the answer would be easy. Each ship would choose its place without caring about the others, and the multiplication rule would do the job again: for each of the carrier’s 120 positions, the battleship’s 140 positions; for each of those, the cruiser’s 160 positions; and so on. The result would be 120 · 140 · 160 · 160 · 180 = 77,414,400,000.

But ships can’t overlap, and that changes everything. Where one ship fits depends on where the others are: if the carrier sits in the middle of the board, there’s less room left for the battleship. That’s why no simple formula gives the answer in one line. So I had the computer count them. First I placed the three biggest ships (the carrier, the battleship and the cruiser) in every way they fit without overlapping, one arrangement at a time. For each arrangement I counted the positions left free for the submarine and for the destroyer and multiplied the two counts (the multiplication rule once more); then I took away the pairs in which the submarine and the destroyer land on top of each other. The result: 30,093,975,536 different fleets. In other words, forbidding overlaps leaves only 39% of the arrangements we counted a moment ago.

One detail: the cruiser and the submarine are both three cells long, but they are different ships, so swapping the two counts as a new arrangement.

No player, human or program, goes through that many fleets one by one. On top of that, every shot rules some of those fleets out, and it’s far from easy to say which. That’s why all the strategies below think about each ship on its own, not about the fleet as a whole.

A yardstick: firing at random

Let’s start with the simplest opponent. The Easy computer picks, at random, a cell it hasn’t fired at yet; it’s like aiming with your eyes shut. We’ll use this level as a yardstick for how clever the other levels are. The question is: on average, how many shots does someone firing at random need to sink the whole fleet?

Let’s call the number of shots a game lasts $T$ . $T$ comes out different in every game: sometimes luck is on your side, sometimes the last ship cell is the very last cell left. So instead of one game, we ask about the average of many games. If we played countless games and averaged their $T$ values, that average would settle on a particular number. That number is called the expected value of $T$ and is written $\mathbb{E}[T]$ (the E stands for “expected”).

Why work this number out? For two reasons. First, it’s the number the cleverer levels have to beat. Second, it lets us check the simulation at the end of the post: the average of the Easy games the computer played there should come out very close to the number the formula gives. And it does: 95.4 shots in the simulation, 95.4 shots from the formula.

Now let’s work it out. Picture a deck of 100 cards: 17 of them are red (the ship cells), and the other 83 are black (empty water). Firing at random is like shuffling the deck well and turning the cards over one by one. The game ends the moment the last red card turns up.

The red cards split the black ones into heaps: the heap before the first red card, the heaps between each red card and the next, and the heap after the last red card. With 17 red cards, that makes 18 heaps; some of them may be empty. A well-shuffled deck favours no heap, so on average every heap holds the same number of cards: the 83 black cards are shared among 18 heaps, $83/18$ (83 divided by 18) per heap on average, or about 4.6 cards.

Since the game ends with the last red card, the only heap never turned over is the very last one. So in an average game, only the last heap’s worth of the 100 cards stays face down:

\mathbb{E}[T] = 100 - \frac{83}{18} \approx 95.4 .

(The sign $\approx$ means “roughly equal to”.) Careful: 95.4 is not a percentage, it’s a number of shots. It only looks like a percentage because the board happens to have exactly 100 cells. What it says is this: someone firing at random combs through almost the whole board before the fleet goes down; on average only 4.6 cells are never touched.

We can go beyond the average, too. What is the chance that the game is over within 85 shots? That means all 17 red cards are among the first 85 cards. In a shuffled deck, the places where the red cards land are 17 places chosen at random out of 100. The symbol $\binom{100}{17}$ stands for the number of different ways to choose 17 things out of 100 (the order they’re chosen in doesn’t matter). All of these choices are equally likely, and in $\binom{85}{17}$ of them every red card lands in the first 85 places. The probability is the ratio of the two:

\binom{85}{17} \bigg/ \binom{100}{17} .

That probability is only 4.8%. The same sum works for any number of shots in place of 85; the dotted curve in the chart at the end of the post shows it. If you lined the games up from shortest to longest, the one right in the middle would last 97 shots (that’s called the median). Random fire does sink the fleet in the end, but usually only after combing through almost all the water.

Hunt and target

Even someone who knows no theory at all plays far better than chance. What do you do after a hit? You fire around it until the ship sinks. And while you have no hit to follow up, you spread your shots over the board. That’s exactly what the Normal computer does. We call the first part target and the second hunt; let’s look at each on its own.

Target mode: finishing a ship

A hit tells you there is a ship on that cell. Ships are straight, so the rest of it has to be in the same row or the same column. That’s why the computer tries the hit’s four neighbours: above, below, left and right. Once a second hit lands next to the first, the ship’s direction is known. The computer now extends the run of hits at both ends; when one end runs into a miss or the edge of the board, it carries on from the other end.

Shot	Cell	Result	Then
1	E5	hit	Target
2	E4	miss	Target
3	E6	miss	Target
4	F5	hit	Line
5	G5	miss	Line
6	D5	hit, sunk	Hunt

Miss, numbered in order
Hit, numbered in order
Sunk ship

The Normal computer finishing off a cruiser. After the hit at E5 it tries E4 and E6, and both miss. F5 hits and reveals that the ship lies horizontally. G5 tries to extend the line but misses; D5, at the other end, sinks the ship. With no hits left to chase, the computer goes back to hunting.

There are two more subtle points. First, while chasing one ship, the computer can hit another one, for example when two ships lie side by side. So it never keeps “the ship I’m chasing” in mind. It looks at every hit on a ship that hasn’t sunk yet; let’s call these open hits. Second, when a ship sinks, the game shows which cells it was on, and the hits on those cells are closed. Any open hits left over belong to another ship, and the computer goes after that one next. It only goes back to hunting when no open hit is left.

Hunt mode: parity

So where should you fire when there’s no hit to chase? Firing right next to a miss is a bit of a waste: the miss has already ruled out every ship position that would cover both cells, so a ship is less likely to turn up next door.

Think of it this way: colour the board black and white like a chequerboard. Two cells side by side always have different colours. Even the shortest ship is two cells long, so every ship covers at least one black cell. Someone who fires only at black cells therefore misses no ship, and has 50 cells to search instead of 100. We can pick out the black cells as the ones whose row and column numbers add up to an even number; in a moment we’ll write that down the way a mathematician would.

Couldn’t even fewer cells do? No. You can cover the board, with no gaps, with 50 dominoes, each two cells side by side, and the destroyer could be hiding under any one of them. Anyone who wants to catch the destroyer wherever it is has to fire at a cell of every single domino. So at least 50 cells are needed.

Once the destroyer has sunk, the shortest ship is three cells long, and a pattern even sparser than the chequerboard will do. To see the general rule, let’s number the rows and columns from 0 this time (column A is 0, column B is 1, …; row 1 is 0, row 2 is 1, …); that’s how the game’s code counts too. Call the row number $r$ and the column number $c$ , and pick a number $m$ , such as 2 or 3.

A piece of notation helps a lot here: mod. It means looking only at the remainder after dividing by $m$ , the way a clock does. A clock starts again after 12, so 15:00 and 3:00 point the same way. Mathematicians write this as $15 \equiv 3 \pmod{12}$ and read it “15 is congruent to 3 mod 12”. So two numbers are congruent mod $m$ when they leave the same remainder when divided by $m$ , and the numbers that leave remainder 0 are the multiples of $m$ : 0, $m$ , $2m$ , …

Now the search pattern fits on one line. We pick the cells whose row and column numbers add up to a multiple of $m$ :

\Lambda_m = \lbrace\, (r, c) : r + c \equiv 0 \pmod{m} \,\rbrace .

( $\Lambda$ is the Greek letter lambda; here it is just the pattern’s name.) For $m = 2$ these are the cells where $r + c$ is even: the chequerboard from before. That’s where the name parity comes from: a number’s remainder when divided by 2, whether it is even or odd.

So why does every ship get caught? Along a horizontal ship the row number stays the same and the column number goes up by one from cell to cell; along a vertical ship it is the other way round. So if the sum is $s$ at a ship’s first cell, the sums along a ship of length $L$ go like this:

s,\; s + 1,\; s + 2,\; \dots,\; s + L - 1 .

The remainders of consecutive numbers mod $m$ go round in turn, like the hour hand of a clock: …, $m - 2$ , $m - 1$ , 0, 1, … So any $m$ numbers in a row leave each of the remainders $0, 1, \dots, m - 1$ exactly once, and one of them is always 0. We can even say which one: if $s$ leaves remainder $a$ , then $k = (m - a) \bmod m$ cells along, $s + k \equiv 0 \pmod{m}$ , and $k$ is at most $m - 1$ . So every ship at least $m$ cells long ( $L \ge m$ ) passes over at least one cell of $\Lambda_m$ .

For a ship shorter than $m$ that guarantee is gone. With $m = 3$ , a destroyer whose first sum is $s \equiv 1 \pmod{3}$ leaves remainders 1 and 2 on its two cells, never 0, so it slips through the pattern. The figure below has exactly such a destroyer: at G2–H2, $s = 1 + 6 = 7 \equiv 1 \pmod{3}$ .

The Normal computer takes $m$ to be the length of the shortest ship still afloat. As long as the destroyer is afloat, $m = 2$ : the chequerboard. When the destroyer sinks, $m = 3$ , and the pattern thins out to the 34 cells on every third diagonal.

m = 2 · 50 cells

m = 3 · 34 cells

Pattern cell
Pattern cell the ship covers
A destroyer that slips through

The search patterns for

m = 2

and

m = 3

, with the pattern cells shaded. On the left, the destroyer at H2–H3 covers one pattern cell, H2; on the right, the cruiser at B7–D7 covers D7. Every ship at least

m

cells long covers a pattern cell; while the site is built, this is checked one by one for every position of every such ship. A destroyer, being shorter than three cells, can slip between the diagonals of the

m = 3

pattern (the dashed destroyer at G2–H2). That’s why the pattern follows the shortest ship afloat.

This is easier to watch in a real game than to explain. Below, the Normal computer plays game number 743 of the simulation at the end of the post, from the first shot to the last. I didn’t pick this game for being lucky: its totals are very close to the averages we’re about to see. We’ll sort the shots into two kinds: a shot fired while there is no open hit is a hunt shot, and every other shot is a target shot.

Hunting

With parityWithout parity

Shot: 21 of 49
Latest shot: E7 · hit
Shot type: Hunt shot
Search pattern: m = 2 · 50 cells
Hunt shots: 17
Target shots: 4
Ships sunk: 1 of 5

Miss, numbered in order
Hit, numbered in order
Latest shot
Ship afloat
Sunk ship
Pattern cell

Shots in this game

With parity

3613

Without parity

4316

Hunt shots
Target shots

The Normal computer sinking the fleet of game number 743 from the simulation. The shaded cells are the pattern the computer is hunting on at that moment, and the numbers give the order of the shots; dashed outlines show ships still afloat, and filled shapes show sunk ships. The board opens just after shot 21: the destroyer is about to sink, and the pattern is still the chequerboard. With shot 22 the destroyer sinks, and the pattern thins out to every third diagonal. Step through the game shot by shot with the buttons or the slider, or press play and watch. The toggle switches the pattern off, so you can watch hunt & target sink the same fleet without it; the bars underneath compare the shots of the two games.

In this game the pattern saved 10 shots (49 instead of 59), and most of the difference comes from the hunt shots: 36 hunt shots instead of 43, and 13 target shots instead of 16.

One game could be down to luck, but the average of 1,000 games says the same thing. In the simulation at the end of the post, the pattern saves 9.8 shots a game on average: hunt & target lasts 60.3 shots on average without the pattern and 50.5 with it. The pattern halves the cells to search, yet the game is nowhere near halved: only the hunt shots benefit from the pattern, and even they are not halved; the shots that finish off ships are much the same either way. The pattern also improves the worst case: the longest of the 1,000 games took 74 shots with it and 100 without.

The state machine

Put the pieces together and the Normal computer becomes a small state machine. The name sounds complicated, but the idea is simple: at any moment the computer is in one of a few states, just as a traffic light shows green, amber or red, and the result of each shot moves it on to the next state.

Hunt & target as a state diagram. Target and Line together make up the Targeting state. Every sinking passes through the Sunk step: it removes the sunk ship from the fleet (and changes the search pattern if the shortest ship has changed) and picks the next state.

The code keeps no note of “which state am I in right now”. Before every shot, the computer works out its state afresh by looking at the board: if there is no open hit, it is hunting. If two open hits lie side by side and a cell not yet fired at sits at one end of their run, it is following a line. Otherwise it is targeting. Because the state is read off the board every time, it can never disagree with the board.

The Sunk step is the only moment the computer learns more than miss or hit.

Probability density

Hunt & target uses just one fact about the fleet: the length of its shortest ship. The Hard computer uses the length of every ship afloat. Before every shot it asks, for every cell: without contradicting anything I’ve seen so far, in how many different ways could the remaining ships cover this cell? Then it fires at the cell with the biggest count; if several cells tie, it picks one of them at random.

Counting positions

Let’s call a position consistent if it doesn’t contradict anything seen so far: it lies inside the board and passes over no miss and no cell of a sunk ship. (A position made up only of hits doesn’t count either, because a ship with every cell hit would already have sunk.) We’ll call the density of a cell that hasn’t been fired at yet $d$ for short. While there are no hits, the definition is very simple: $d$ is the number of consistent positions of all the ships afloat that pass over that cell. Once hits come into play, we’ll give the positions points; we’ll get to that shortly.

LowHigh
Highest density

The density before the first shot. The number in each cell is how many positions of the five ships pass over it: 10 in the corners, 34 in the four central cells. The Hard computer fires its first shot at one of these four cells.

We can find these two numbers ourselves. A corner cell is covered by a single horizontal and a single vertical position of each ship: the ones with an end in that corner. For five ships that’s $5 \cdot 2 = 10$ . Each of the four central cells, on the other hand, is covered by $L$ horizontal and $L$ vertical positions of a ship of length $L$ , because the cell can be the ship’s first, second, … or last cell. For the five ships that makes $2 \cdot (5 + 4 + 3 + 3 + 2) = 2 \cdot 17 = 34$ . No cell can collect more than that; as we saw with the cruiser, the count drops towards the edges.

That’s also where the method gets its name: divide a cell’s count by the total number of positions (760), and you get the probability that a position picked at random from all of them passes over that cell.

Misses rule positions out, and the density drops around them:

Miss, numbered in order
LowHigh
Highest density

The first 12 shots of a game on Hard, all of them misses, and the density worked out for shot 13. The code doesn’t even mention a chequerboard, yet none of these shots is next to another. The highest density is now at C8 and E9, in the corner the misses haven’t reached yet.

A miss wipes out every position that passes over it, and it lowers its neighbours’ counts the most. That’s why the next peak usually turns up a little further away. The density finds the chequerboard idea all by itself, without anyone telling it. It even knows more: that the edges are poor hunting ground, and that a gap too narrow for the remaining ships in one direction can only hold them in the other.

Weighting the hits

Now suppose the computer hits E5. If every position counted as 1, nothing would change: the positions through E5 are still possible, just as they were before, so every cell would keep its old count. Yet a hit is the most valuable thing the computer knows, and a plain count can’t see it. That’s what the weight is for.

The rule is this: a position that touches no open hit scores 1 point, and a position that passes over one open hit scores 35 points. A position that passes over two open hits at once scores 35 · 35 points, and so on. A cell’s density is the total score of the consistent positions that pass over it. Let’s give this number, 35, a name: $w$ . It’s worked out from the lengths of the ships afloat: twice their total length, plus one. For the full fleet, 1 + 2 · 17 = 35.

Why this number? As we just counted, with the full fleet no cell is covered by more than 34 positions, and $w$ is exactly one more than that. So however many ordinary 1-point positions pile up on a cell, they can never catch up with the score of a single position through a hit. As ships sink, both this ceiling and $w$ get smaller, but $w$ always stays one above the ceiling.

This works a lot like the digits we learned about at school. In our base-ten system a digit is at most 9, so the ones digit can never catch up with even a single ten. When we compare 472 with 469, we look at the hundreds first, then the tens; the ones only get a say if the tens are equal too. The density works the same way, except that the base isn’t 10 but $w$ :

d = N_0 + N_1 \cdot w + N_2 \cdot w^2 + \cdots

Here $w^2$ means $w \cdot w$ . $N_0$ is the number of positions through the cell that touch no open hit; $N_1$ is the number that pass over exactly one open hit, $N_2$ the number that pass over two open hits at once, and the dots at the end mean “and so on”. Since at most $w - 1$ positions pass over a cell in all, each of these numbers stays between 0 and $w - 1$ : they are the digits of the number $d$ in base $w$ , just as $472 = 2 + 7 \cdot 10 + 4 \cdot 10^2$ . Comparing two cells starts from the top digit, just like comparing two numbers. The computer first asks: what’s the largest number of open hits a position through this cell can touch? The number of positions only decides between cells that tie on that question.

One hit

F5 and E6: 12 · 35 + 22 = 442

Two hits in a line

D5 and G5: 7 · 35² + 5 · 35 + 21 = 8,771

Hit
LowHigh
Highest density

The density after a single hit at E5, and after a second hit at F5. Under each board, the peak value is written in base

w

(here 35); its top digit counts the positions through the peak that touch the most hits.

After the single hit at E5, the peak is at F5 and E6: 12 · 35 + 22 = 442. Read it like this: of the positions through each of these cells, 12 also pass over E5 and bring in 35 points each; 22 don’t, and bring in 1 point each. E5’s other neighbours, E4 and D5, are just behind, on 441 points: E5 isn’t quite in the middle of the board, and there’s a little less room above it and to its left. After the second hit, positions that pass over both hits can only go through the cells that continue the line, so the top digit of those cells moves up to the $w^2$ place. The peak is now at the two ends of the line, D5 and G5: 7 · 35² + 5 · 35 + 21 = 8,771.

Nobody wrote the rule “extend the line” into the Hard computer; it comes out of the arithmetic on its own. So does most of the state machine above: the top digit of the largest density does the job of the state. If that digit is in the ones place, the computer is hunting; in the $w$ place, it is targeting; in the $w^2$ place or higher, it is working its way along a line of hits. It even goes straight for a single cell not yet fired at between two hits, such as F5 between E5 and G5; for the Normal computer, that cell is just one of the neighbours. When a ship sinks, its hits are closed, $w$ gets smaller and the digits rearrange themselves.

Try it yourself

The lab below runs the game’s density calculation in your browser. Mark misses and hits, and watch the peak move. When a ship sinks in the game you’re imagining, mark its cells as “Sunk” and untick the ship in the list: $w$ gets smaller, and the density spreads itself over the ships that are left.

Mark cells as

MissHitSunkClear

Click or tap a cell to mark it; with the keyboard, move with the arrow keys and press Enter or Space. Marking a cell again with the same tool clears it. When a ship sinks, mark its cells as sunk and untick it.

Hard fires at: E5, F5, E6, and F6 · d = 34
Cell: A1 · d = 10
Weight of a hit: w = 35

The density lab. The darker a cell’s tint, the closer its

d

is to the largest value; the dashed squares are the cells the Hard computer would fire at. The panel shows the density of the cell under the pointer or the keyboard focus; once a hit is involved, the value is written in base

w

Two things are worth trying. Put two hits side by side and watch the peak jump to both ends of the line; then add a miss at one end. Or leave the board empty and untick every ship except the carrier: with only one long ship left, see how strongly the density keeps away from the edges.

What the count leaves out

The density thinks about each ship on its own, so it also counts positions that could never appear together in a single fleet, such as a carrier and a battleship on the same cells. For the exact answer you would have to weigh, one by one, every fleet that agrees with the shots so far; before the first shot there are 30,093,975,536 of them. And even that would only be right if the opponent placed the ships completely at random. Drawing random samples from the consistent fleets would be the natural next step. Counting ship by ship, though, is cheap, easy to follow and, as the next section shows, already works well. (Someone who knows how the computer thinks could hide their ships along the edges, which the density searches last.)

How many shots?

To compare the strategies, I had each of them sink the same 1,000 fleets, placed at random by the game itself. The games are numbered, and every one of them can be replayed exactly, because both the fleet and the computer’s random choices are fixed by the game’s number. Game 743, which you stepped through above, is one of them. Besides the three levels, the table below has a fourth strategy: hunt & target without parity. That’s the Normal computer with its search pattern switched off: it hunts at random and targets like Normal.

Shots needed to sink the whole fleet, 1,000 games per strategy
Strategy	Mean	Median	Middle 80%	Best	Worst
Random (Easy)	95.4	97	89–100	63	100
Hunt & target without parity	60.3	60	42–80	22	100
Hunt & target (Normal)	50.5	51	38–62	24	74
Probability density (Hard)	44.4	43	33–57	22	71

The “Middle 80%” column of the table shows the range that is left once the fastest 10% and the slowest 10% of the games are set aside.

Probability density (Hard)
Hunt & target (Normal)
Hunt & target without parity
Random (Easy)
Random fire, exact

The share of the 1,000 games that were over within a given number of shots; the further left a curve is, the faster the strategy. The dotted curve is the exact chance for random fire at every number of shots, from the deck-of-cards sum above; the simulated Easy games follow it closely.

The biggest leap comes from targeting: from the Easy computer’s 95.4 shots on average (just as the formula says) to 60.3 for hunt & target without parity. The search pattern saves 9.8 more shots, and the density another 6.1. The Hard computer finishes 76% of its games within 50 shots, the Normal computer 47%; none of the Hard computer’s games lasted longer than 71 shots. These averages depend a little on luck too: each of them is very likely no more than 0.9 shots away from the average we would get from countless games. The gaps between the strategies are much bigger than that, so the ranking isn’t down to chance.

Three ideas

Leave the details aside and three ideas remain, each more general than the one before. A hit carries information about its neighbours, so follow it up: that’s target mode. Two shots side by side that could land on the same ship are a waste, so spread your shots over a pattern that no ship can escape: that’s parity. And instead of writing these rules one by one, count everything that is still possible and let the weights decide: that’s the probability density, and the first two rules come out of it on their own.

You can try all three levels in the Battleship game. On Hard, turn on the heat map during a battle and watch $d$ spread over your own fleet as the computer closes in. And maybe next time you play Battleship, you’ll remember the chequerboard too.