Battleship on 5×5

1The board, the fleet and the race

Each player hides two 3-cell ships and a 2-cell ship on a 5×5 board: straight, inside the board, touching allowed, overlapping not. Every round both players fire one shot, answered "miss", "hit", "sank a 3" or "sank a 2" (the size only, never which ship). The first to sink the whole fleet wins the race; a finish in the same round counts half.

Every strategy here uses only what these rules announce, except where section 7 prices extra information.

The fleet covers 8 of the 25 cells. It can be hidden 8,000 ways, or 1,009 distinct layouts if rotations and reflections count as one. On a random layout a ship covers the center 40.55% of the time and a given corner only 21.45%, because fewer placements fit over a corner.

Terms, as in the essay:

• Fixed hunt: a hunt with no dice; the same information always produces the same shot.
• Mixture: a lottery over fixed hunts, drawn in secret before the game.
• Hider (a placement distribution): the lottery a player uses to decide where to hide its fleet.
• Hand-written rule: a recipe such as the checkerboard, 3-parity or the heat map (section 5); it may roll dice for small choices but is not an optimized mixture.
• Win rate: the share of races won, a same-round finish counting half; differences are in points (percentage points).
• Pace: the spread of the opponent's finishing times; without extra information, a race depends on nothing else. Here it is a near-perfect player's, its fleet hidden the way it hides its own.
• Head-to-head: the win rate against that player, both fleets hidden the way it hides its own.
• Worst case: the win rate against the pace when the fleet you hunt sits on the layout where your hunt races worst; all 1,009 are scored, so no search is needed.
• Best reply: the strategy that wins the most races against a given opponent, built knowing exactly how it plays. What it wins above 50% is the opponent's exploitability.

2States of knowledge and the exact best reply

A hunter's state of knowledge is the set of layouts still consistent with everything it has seen. Games that leave the same set are the same state, which keeps the count small enough to compute. The whole set is needed because sinks are announced by size only, and their timing carries information.

Suppose a hunter fires at C1, C2 and C3 in that order, hits all three, and hears one "sank a 2". If the sink came with the second shot, the 2 was C1–C2 and C3 belongs to a live 3; if with the third, the 2 was C2–C3 and the live 3 runs through C1. Only the set of layouts keeps these apart.

On 5×5, with rotations and reflections folded together, there are 180,655,921 states in 26 layers, one per shot count. The graph takes about 100 GB of memory and rebuilds identically in about 10.5 minutes.

Against a fixed opponent, the best reply is one backward pass of dynamic programming. On a 56-core cloud machine a pass takes 6 to 8 seconds and up to 185 GB of memory.

# backward, from the last layer to the first
for each state s, reached after t shots:
    if every ship is sunk in s:
        # the race credit
        V(s) ← P(opponent needs more than t)
               + ½ · P(opponent needs exactly t)
    else:
        V(s) ← max over allowed cells c of
               Σ over answers a of
                   P(a | s, c) · V(next(s, c, a))
# P(a | s, c): the opponent's hider's weight on the
# layouts in s that answer a at c, divided by its
# weight on all of s

Two rules decide which cells are allowed: never fire at a cell that can no longer hold a ship, which costs nothing; and while a hit is not yet explained by a sink, fire only next to a hit, the finish-what-you-hit rule. Together they keep 28.8% of the moves (a move is a state and a cell to fire at): 659 million of 2.29 billion.

The second rule is a real restriction: the best unrestricted hunter sometimes leaves a wounded ship to probe elsewhere. The cost was small where measured (0.03 and 0.09 points on 4×4, 0.06 for one strong 5×5 hunt) but is unknown for the 5×5 best reply, so every 5×5 guarantee here holds among hunts that finish what they hit.

Why stop at 5×5? A best reply visits every state of knowledge, 181 million here, and beyond 5×5 the count puts exact best replies out of reach. The essay switches to self-play there, and so does the 10×10 page.

3The best-reply loop

Our near-perfect players come from the loop of the essay's section 1, which alternates an exact best reply with a linear program over the hunts found so far. The loop that actually ran also carried a pace and added many hunts per round:

q ← any placement distribution
pace ← a starting pace
pool ← empty
repeat:
    # one exact backward pass against q and pace
    add the best reply and its variants to pool
    mixture, q ← linear program over pool,
                 against pace
    pace ← halfway to the mixture's finishing times

Each pass produced 265 candidate hunts, the best reply and variants with other first shots or other handling of the first hits, and the loop kept the distinct ones. Moving the pace only halfway toward the mixture's finishing times damps it so that it does not swing.

Why a lottery over whole hunts rather than one strategy that rolls dice move by move? A state of knowledge forgets the order of its shots, and Kuhn's equivalence between the two (Kuhn 1953) needs a player who remembers everything. A single move-by-move strategy trained by counterfactual regret minimization (CFR+), the self-play method behind strong poker programs, stalled on 4×4: its best reply still won 58.4% of races.

By round 346 the pool held a mixture that won at least 50.00% on every layout against the loop's pace, needing 13.81 to 14.40 shots across the layouts. Winning half against its own pace is necessary, not sufficient (a random shooter does too), so the remaining rounds went into lowering what an exact best reply gains.

The loop stopped at round 2,120 with 12,609 hunts in its pool, while the linear program still reported hunts that would raise its value. Nor did the pool hold the true best reply: against the final player's hiding, the best hunt in it gains 0.26 points and the exact hunting reply 0.86, both at the run's pace (0.85 at the player's own, the value used elsewhere on this page).

A small player exists: with 1,009 layout constraints, some optimal mixture uses at most 1,010 hunts (Carathéodory's theorem). Ours is diffuse instead: nearly all of its roughly 12,600 hunts carry some weight, none more than 0.35%.

4The near-perfect player

This section is about our best player, from round 2,120 of the best-reply loop.

Its worst layout

Against the pace the run was using when it stopped, the best player never wins less than 49.87% on any layout, a guarantee the linear program proves (the essay's 49.9%). Raced against its own exact finishing times, its worst layout gives 49.85%.

That worst layout is the corner pack: both 3s stacked in the top-left corner (A1–C1, A2–C2) and the 2 in the top-right (E1–E2), drawn in Figure 5. Its average there is ordinary, 14.03 shots, but it rarely finishes fast (Figure 3): within 12 shots in 10.7% of games against 24.0% overall. A best reply hides for exactly this: what hurts is the spread of the opponent's finishing time, not its average.

How exploitable it is

The joint best reply, which chooses where to hide and how to hunt, gains 1.44 points (among hunts that finish what they hit): it hides on the corner pack and hunts with the exact best reply. The hunt-only reply keeps the player's hiding and gains about 0.85; the hide-only reply keeps its hunting and gains 0.13 (0.15 against its own exact finishing times).

Much of the strength is in the hiding: had the player hidden its fleet uniformly at random, a hunting best reply would gain 3.11 points against it, against 0.86 with its real hider at that same pace.

How it hides and where it opens

The hider moves weight from the middle toward the edges (Figure 1): a corner holds a ship 26.2% of the time against 21.45% at random, an edge middle 39.0% against 36.0%, the center only 30.0% against 40.55%. Every distinct layout gets weight 0.009% to 0.30% (a family of eight gets 0.10% at random).

Its favorite is the corner pack, at 3.0 times the random weight, as for the hider of the reference player (the snapshot section 5 scores the rules against); all five of its favorites put a 3 along an edge from a corner, where a heat-map hunter looks last.

The hunter opens near the middle instead: the replay player's first shot is never a corner and lands next to the center 50.4% of the time, on the center 9.0% and on an edge middle 30.5%.

Call the hottest cell the one most likely to hold a ship given everything announced and how the opponent hides (here, the same near-perfect hider). Before the first shot those are the four edge middles (39%), so the 30.5% are exactly its first shots at the hottest cell. Over a game it fires there on only 55% of its shots, rising to 80% of 14th shots.

Conditioned on the whole game so far, not just the state of knowledge, the lottery can be replayed as dice rolled at each move (Kuhn 1953): of its 14.07 shots, 6.19 are random choices on average, and 88.6% go to the cell it is most likely to pick.

Flat and fast

Flatness is the clearest mark of near-perfect play (Figure 2): the best player's expected shots range only from 13.72 to 14.35 across the 1,009 layouts, the middle 80% within 14.00 to 14.16. For every rule in the figure the middle 80% alone is wider than that whole range, and the heat map's layouts run from 9.44 to 18.15 shots.

Flat does not cost speed: the player averages 14.07 shots, fewer than the fastest rule, the heat map (14.42 under the reference player's hider), and only 0.1% of its games need more than 19 (Figure 3).

5Hand-written rules on 5×5

Every rule is scored against the reference player (round 1,963), head-to-head and on its worst layout against that player's pace. The rules come in families, with the short names used below:

• Checkerboard by hand and 3-parity by hand: fire at random cells of one color, or of one set of every-third diagonals (direction and order drawn at random), then the next; after a hit, extend a line or fire next to it.
• Smart 3-parity, three-ship core (the essay's section 3 rule without its sweep for the 4 and the 5; by hand): split one set of every-third diagonals into its dark-square and light-square diagonals, A and B, and fire at random in A, then in B. In 35% of games (a coin before the game) it jumps to B as soon as the first 3-cell ship sinks. Once both 3s are down it plays the zone final for the 2: on the checkerboard color fired at more, whose half (A or B) it calls its own, it fires at random where a 2 still fits, first at that color's cells outside its half that touch an unshot cell of the other half, then at the rest of its half, then at the rest of the color. After a hit, it extends a line or fires next to it.
• + computer finish (the essay's "heat-map finishing"; needs a computer): after a hit, fire at the hottest cell.
• + late near-miss cells (light or strong): within the set, a cell next to a miss is fired later. Each cell is drawn with weight e^(−α × share of its neighbors already missed), α = 0.5 (light) or 1.5 (strong).
• Densest first: commit to one diagonal direction and fire the cell of the set where the most placements still fit.
• Heat map: always fire at the hottest cell; the particle filter estimates that map from about a thousand sampled layouts.

There is a cliff: every rule wins at most 22.1% of races on its worst layout, the self-play mixture 48.4%, and nothing lands in between (Table 1, plotted in the essay's section 1). The heat map is the best rule head-to-head (45.1%) and the worst on its worst layout (4.1%).

The best rule on both worst-case measures is one you can play by hand, smart 3-parity's three-ship core: 22.1% on its worst layout (21.2% before the zone final) and 16.45 shots on its slowest. In shots the gap is plain: the best player's slowest layout needs 14.35, about 2.1 fewer in a game of about 14. The coin is what lifts the rule: never jumping (20.4%) and always jumping (21.0%) each do worst on a different layout, and drawing one or the other each game hedges between them. The computer version, which hunts the 2 on the color with fewer unshot cells instead, reaches 22.2%.

Of the rules that need a computer, the best are the two 3-parity rules with late near-miss cells: 20.4% (light) and 19.6% (strong) on their worst layouts, 16.72 and 16.69 shots on their slowest.

The "both adversarial" column also lets the rule hide its own fleet where the reference player hunts worst: its worst case rises by 7 to 14 points, to at most 30.8% (smart 3-parity's core).

The cliff deepens as the board grows (Figure 4): from 4×4 to 5×5 the rules that chase density (heat map, particle filter, 3-parity densest first) lose 11 to 15 points of worst case, the two rules played by hand only 2 to 3. The heat map falls from 19.5% to 4.1%.

The heat map's trap

The heat map is fast on ordinary layouts because it fires where ships usually are. Fewer placements fit over an edge or corner, so it rates those cells low and reaches them last. On the corner pack it needs 18.15 shots instead of 14.42 and wins 4.1% of races; the particle filter and the checkerboard densest first share that worst layout.

The near-perfect hunter's hardest race is on the same layout, yet it still wins 49.85% there: a hunt that randomizes leaves a hider nothing to aim at. On the classic board the same trap holds the heat map to at most about 4 races in 100 (the essay's opening, classic page).

6A mixture built by self-play

Past 5×5 the essay builds its strategies by self-play (section 2): the loop sets its own pace and adds hunts found by search instead of exact best replies. On 5×5 we can check how close that gets. The run tried 22,010 hunts and kept 318, which win 49.97% against their own pace on the worst layout (exact: computed on every layout, not estimated).

Against the reference player it wins 48.54% head-to-head, each player hiding its fleet its own way, and 48.36% on its worst layout; on its own worst layout the reference player still wins 51.32% against the mixture's pace. So the near-perfect player is ahead on every count, by about 1.5 points, and the mixture is a little slower (14.18 shots on average, 14.43 on its slowest layout).

The two hiders barely resemble each other (correlation 0.08 over the 1,009 layouts), yet swapping them moves the head-to-head result by just 0.03 points: both hunters are nearly flat, so the hiding place matters little to either.

The run climbed steadily: on its worst layout, against its final pace, it won 48.26% at round 281, 49.59% at 969 and 49.97% at 1,799, where it hit its budget of 1,800 rounds with gains leveled off. Flat is not perfect, since a random shooter is flat too, but on 5×5 self-play lands within 1.5 points of near-perfect play, the evidence for trusting it on larger boards (10×10 with three ships).

7What context is worth

Real Battleship offers more than the rules-only game: you see which of your ships have been hit, you may know who goes first, and you know where you hid. Context lets you play the score: when behind, a riskier hunt can pay. To price it, we freeze an opponent and compute the exact best reply with and without the extra information.

On 5×5 the frozen opponent is the best player's hider with the replay player's 255 hunts; on 4×4, a separately tightened near-perfect 4×4 player. Each best reply's win rate is an upper bound against an opponent who adapts. The gains shown here are differences of two such win rates, so they are not bounds of either sign, and against an adapting opponent the information could be worth less.

The 5×5 base is looser: its context-free best reply already gains 0.90 points (0.001 on 4×4), and the 5×5 gains come on top.

• Which of your ships are hit: after each round, how many of your two 3s carry a hit and whether your 2 does (six possible states). Hits counted ship by ship gives the count on each ship.
• Memoryless: the same signal, but the hunt sees only its current value, not when it changed.
• Where you hid: the hunt may depend on your own layout, which tells it how the opponent's hunt is likely to go.
• Taking turns: a variant rule in which you know your seat (whether you move first or second, which also decides a same-round finish) and the second mover sees the first mover's shot.
• The ceiling: knowing in advance the shot on which your fleet will fall. No rule announces it, so it is a bound, not a strategy: every signal about your fleet, and where you hid it, acts only through that time.

Which ships are hit is worth 0.38 points on 5×5 and 0.23 on 4×4, about a quarter of the ceiling on both boards. A memoryless hunt keeps 66% of that on 5×5 (59% on 4×4), and counting hits ship by ship adds only 0.05. Using where you hid brings it to 0.78, against a ceiling of 1.57 points on 5×5 and 1.01 on 4×4.

Taking turns, which also tells you your seat (worth only 0.03 points alone on 5×5), brings it to 1.12; with the seat known the ceiling is higher, 2.12 points on 5×5 and 1.50 on 4×4.

Why so small?

Every signal about your own fleet acts only through when it falls, and even knowing that exactly is worth only 1.57 points. A hunt aimed at a known deadline beats the player's chance of finishing by then by at most 4.3 points, at 16 shots (Figure 6, bottom). Not knowing the deadline, a player must compromise among these hunts, and that compromise is all the information can buy back.

On 3×3 with two 2-cell ships, knowing which of your ships are hit or sunk and seeing the opponent's shots is worth 0.55 points against the usual equilibrium. Against the equilibrium of the variant in which each player knows its seat, whose hunt depends on where it hid, it is worth 16.6: that opponent's shots give its layout away (Aumann and Maschler; see Hart 2006).

Context is also expensive (Table 2). A signal splits every state by its history, so the exact reply for the simplest signal, which ships are hit, takes 45 minutes, roughly 340 to 450 times as long as without context; the study cost about $142 of cloud computing. That is why the essay drops context beyond 5×5.

8Smaller boards, open questions, reproducing

Smaller boards

On 4×4 the same fleet hides 804 ways (103 distinct), and our near-perfect 4×4 player finishes in 11.23 shots on average. Its exact best reply, which picks a hiding place and the hunt that goes with it, wins 50.14%; a reply that hides and hunts independently gains under 0.02 points, so almost all of the 0.14 comes from coupling (essay, section 1). Measured separately against the tightly converged 4×4 player of an earlier context study, a reply that tunes its hunt to where it hid its own fleet gains 0.12 points, and 0.30 if it also chooses that hiding place. The later context study (section 7) froze another tightened 4×4 player, against which the context-free hunting reply gains 0.001 points.

On 3×3 we used a different fleet, two 2-cell ships ({2,2}), which hides 44 ways (7 distinct). That game is solved to within 0.3 points: the equilibrium hunter is a lottery over 264 fixed hunts and always finishes in 4 to 8 shots, while any fixed firing order can be forced to fire all nine cells and so wins 0% on its worst layout.

Open questions

• The last 1.4 points. The best player's loop had not converged when it stopped.
• The targeting rule. Its cost to the 5×5 best reply is unmeasured.
• Seeing the opponent's shots was not priced on 4×4 or 5×5; the ceiling bounds it.
• Both players adapting to context was not solved even on 3×3; four exact approaches failed.
• A compact player. The mixture is diffuse; distilling it into a small network was started on 4×4 only.

Reproducing and replaying

The graph rebuilds identically in about 10.5 minutes. The best player is stored as its hider and its exact finishing times on every layout; the replay player's 255 hunts (re-derived bit for bit from their recipes), its recorded shots on all 8,000 layouts and every context strategy are stored and replay exactly.

No playable 5×5 opponent is on these pages; the essay's Replay 1 shows the replay player at work.

The page draws on four strong players: three snapshots of the one best-reply run, frozen at different rounds for different studies, with average finishing times within 0.01 shots, and the self-play mixture (Table 3).