What does optimal Battleship look like?

1Small boards, solved

A fixed hunt has no dice: the same information always produces the same shot, so it has layouts it finds last. A mixture is a lottery over fixed hunts, drawn in secret before the game, so a hider cannot know which layouts it will find last. Recipes like the three opening hunts are hand-written rules: they may roll dice for small choices but are not optimized mixtures.

Until section 3 the fleet we focus on is two 3-cell ships and a 2-cell ship, written {3,3,2}. On 5×5 it can be hidden 8,000 ways; that is the largest board we could bring close to perfect play. Our near-perfect strategies come from a loop that alternates an exact best reply, the hunt that wins the most races against a placement distribution (a lottery over where the hider puts the fleet), with a linear program, a standard optimization that can be solved exactly:

q ← any placement distribution
pool ← empty
repeat:
    # exact, by dynamic programming over all 181 million states (5×5)
    h ← best reply to q
    add h to pool
    # best mixture of the pool, and the hider's best placements against it
    mixture, q ← linear program over pool

One caveat: because the game is a race, every step maximizes the chance of winning the race, not the average number of shots to finish.

To test a finished strategy we compute its best reply, built knowing exactly how it plays and free to change both where it hides and how it hunts; what it gains over 50% is the strategy's exploitability. On the smaller 4×4 board our player is the optimal decoupled strategy to within 0.02 points: a best reply that hides and hunts independently gains almost nothing against it. A best reply that couples hiding and hunting, tuning its hunt to where it hid its own fleet, gains 0.14 points. Raced against a copy of itself, our 5×5 player never wins less than 49.9% on any layout, and its best reply gains 1.4 points.

Near-perfect play is remarkably flat: on 5×5 its average ranges only from 13.7 to 14.4 shots across all 1,009 distinct layouts (counting rotations and reflections as one). It is also slightly faster than the heat map, 14.1 shots on average against 14.4, so the heat map wins only 45.1% of their races. Against an adversary the gap is dramatic: on its worst layout the heat map wins only 4.1% of races against near-perfect play's pace, while near-perfect play never drops below 49.9%. Simple rules lose on both counts: plain 3-parity by hand needs 15.4 shots and wins 35.3% head-to-head and 19.9% on its worst layout, and the best hand-written rule we tried, the three-ship core of smart 3-parity in section 3, wins 36.0% and 22.1% and needs 16.4 shots on its slowest layout.

Value of context

"Solved" here means the game in which each player uses only their own progress: their own hits and misses, and the sizes of the ships they sink. Real Battleship offers more context: you see where the opponent shoots and which of your ships they have hit, you may know who goes first, and you can couple where you hide to how you hunt. Context lets you play the score: if the opponent has already hit most of your fleet, it can pay to switch to a riskier hunt that finishes fast when it gets lucky. Against a frozen near-perfect 5×5 opponent the gain is real but small: knowing which of your ships are hit is worth 0.38 points of win rate, and letting your hunt also depend on where you hid and who goes first (in a variant where the players take turns) brings it to 1.1. Even knowing in advance when the opponent will sink your last ship, the most anyone could learn about how far behind they are, would be worth only 1.6. One reason it stays small: a player whose hunt does not depend on where it hid gives nothing away through its shots, a classic idea from Aumann and Maschler's work on private information (see Hart 2006).

Context is also expensive. Without it, an exact best reply on 5×5 is one pass over 181 million states of knowledge, about 8 seconds and 100 GB of memory on a 56-core machine. Knowing which of your ships have been hit splits every state by the history of those hits, and the same reply takes 45 minutes and about 280 GB. A gain of about a point is not worth that on bigger boards, so we drop context: from here on every strategy hides independently of how it hunts and uses only its own shots and the sink announcements. It is an open question whether context matters more on larger boards (the gains we measured grew from 4×4 to 5×5), and whether simple heuristics, such as taking more risk when behind, could capture some of it without this blowup in states.

Without context the two hunts never interact, so a strategy can be scored against the spread of its opponent's finishing times alone, which we call the pace. On these small boards the pace is that of the strong player you race, with both fleets hidden the way it hides its own.

Watch how often the hunter in the replay ignores the hottest cell, the one most likely to hold a ship; the heat map's worst board, near the top, shows why.

In detail: the 5×5 page has the exact machinery, every hand-written rule we scored, where the near-perfect player hides and fires, the full value of context, and the 4×4 board.

2Scaling up with self-play

Past 5×5 we cannot solve the game, but with the {3,3,2} fleet we can still score a hunt on all 240,669 distinct layouts of 10×10. Finding the best hunt is the hard part, so we use a form of self-play in which the strategy sets its own pace:

pool ← a few fixed hunts
pace ← a starting pace
repeat:
    # one linear program, with the pace held fixed:
    #   mixture = best win rate on the worst layout against the pace
    #   q = the hider's lottery over layouts that hurts mixture most
    mixture, q ← linear program over pool
    h ← a hunt that beats mixture against q  # by search, not exactly
    if no such hunt is found, or the round budget is spent: stop
    add h to pool
    pace ← halfway to mixture's finishing times

The search step is where the heat map comes back: against a known lottery q, firing where a ship is most likely is already a strong reply. One such hunt is easy to exploit, as the opening showed, but the loop adds a different one for each q, and the mixture over many of them holds up on its worst layout. Each round runs several searches at once: beam searches that keep the best few partial hunts, a two-shot lookahead, and one aimed at the hider's hardest layout.

Game theorists call this loop column generation, a one-sided version of the double-oracle method (McMahan, Gordon and Blum 2003): only the hunts' pool grows, since every layout is already in the program.

The result is flat: on its worst layout, the finished 10×10 mixture still wins 49.95% of races against its own pace. Flat is not fast, though: a player who fires at random also wins half its races against itself. So we checked from outside. On 5×5, a mixture built this way, without ever seeing a near-perfect player, wins 48.5% head-to-head against one and 48.4% on its worst layout. On 10×10, the best counter-strategy our searches found gains under 1 point against it. Speed points the same way: head-to-head, no hand-written rule we tried wins even half its races against the mixture (the heat map 48.2%, the best rule 48.6%; chart below). The mixture gives up almost no speed for its safety.

In detail: the 10×10 page has how the self-play run converged and how its searches work, how we checked it, what the mixture does, and every rule we raced against it.

3The classic fleet: the best strategy we found

Now the real game: 10×10, with a carrier (5 cells), a battleship (4), two 3s and a 2. There are about 15 billion ways to hide this fleet, too many to score, so every worst case from here on comes from a search and is an upper bound. The sheer number of layouts also stalls the column-generation loop of section 2: its linear program can hold every layout only while there are millions of them.

So we tried many different approaches, 70 in all. In the end the best thing to do was to hunt the two 3s and the 2 as well as possible and assume we would find the 4 and the 5 along the way.

The hunt for the small ships is section 2's 10×10 {3,3,2} self-play mixture, used unchanged:

Why does a three-ship strategy win? A 4 or a 5 crosses every set of every-third diagonals, just like a 3, and that is where the small-ship hunt spends most of its search shots, so it usually makes the first hit on the big ships itself: on the carrier in 90% of games and on the battleship in 87%. The three-ship game could be checked against every layout, so the small ships are guaranteed to be found efficiently wherever they hide, and the randomized hunt that finds them leaves the 4 and the 5 little room to hide. Self-play on the full fleet produced the classic-board self-play mixture, which is faster than the best strategy on average (46.4 shots) but performs poorly against adversarial placement: it wins at most 26.3% of races on its worst board found.

The best strategy needs 47.3 shots on average, against 49.3 for 3-parity and 51.4 for the checkerboard. Its finishing times on 32,000 random boards are the pace for every classic strategy on this page, so by definition it wins 50% on average, and at most 43.9% on its worst board found (Table 1). Racing a strategy against its own games can flatter it (section 2), but against the classic-board self-play mixture's faster pace it still holds ≤ 41.0% on its worst board found.

Behind each point on that chart is a whole spread of finishing times; the next figure shows five of them.

Smart 3-parity: the pencil-and-paper version

The rule to beat is plain 3-parity from the opening: 49.3 shots on average and ≤ 34.1% on its worst board found (Table 1). Smart 3-parity keeps its set of every-third diagonals but uses it better. It is the best simple rule we found for the three-ship game, with a sweep for the big ships added; the full recipe is on the card at the bottom:

# before the game
S ← every third diagonal, direction at random
A, B ← S's dark-square and light-square diagonals, in random order
# each shot
if a hit is not yet explained by a sink:
    extend a line of hits, else fire next to one
else if a 3 is afloat:
    if the first 3 just sank: jump ← true in 35% of games
    # section 4 shows why jumping helps
    if jump and B has cells left:
        fire at a random cell of B
    else:
        fire at a random cell of A, then of B
else if the 2 is afloat:
    # on the more-fired checkerboard color, where a 2 fits:
    fire first beside unshot cells of the other half,
    then at the rest of this color's half, then anywhere on it
else:
    sweep for the 4 and the 5

Why it beats plain 3-parity: the set's diagonals alternate between the two checkerboard colors, and every 2-cell ship covers a square of each color. So the heuristic sweeps one color's half of the set first, and once both 3s are down it hunts the 2 on that already well-covered color, only where a 2 still fits, instead of sweeping the rest of the set and then a second one. It starts with the cells beside unshot cells of the other half, where the 2 can still lie in the most ways. The occasional jump keeps a hider from exploiting that order (section 4).

Smart 3-parity needs 47.8 shots and holds ≤ 37.6% on its worst board found, about 6 points short of the best strategy (Table 1). Its order for the 2 comes from the large-board analysis of section 4: without it, the first version of the heuristic won about 0.7 points fewer races, both on random boards and on the hardest boards a stronger search found (≤ 36.1% against ≤ 36.8%). Is it the best rule a person can play? It is the best simple one we found: three close variants tie with it within the search's noise, and the stronger search holds it to ≤ 36.8%, where Table 1's search found ≤ 37.6%. Only strategies that need a computer sit noticeably higher on the classic chart above.

In detail: the classic-fleet page has how the races and the search for hard boards work, all 70 strategies, how many shots each needs, the best strategy in depth, why self-play on the full fleet stalled, and the rules a person can play.

4The large-board limit

Now let the board grow without limit and keep the fleet of two 3s and a 2. Finishing a ship after its first hit then costs a few shots that vanish next to the board's size, and edges stop mattering, so what is left is small enough to compute almost exactly.

Every third diagonal. One set of every-third diagonals, a third of the board, touches every 3-cell ship exactly once, and no pattern does it with fewer cells (Dumitrescu and Tkadlec 2024); one checkerboard color touches every 2-cell ship. The set's diagonals alternate between the colors: call its half on dark squares A (a sixth of the board), its half on light squares B (a sixth), and the remaining dark squares C (a third). Every sensible hunt is a choice of order over A, B and C; the rest of the board never needs a search shot.

Three plans. The plain plan sweeps A and B together in random order, then C. It needs exactly 33⅓ shots per 100 cells on average wherever the ships are, so a hider has nothing to aim at; on a big board the opening's 3-parity is exactly as fast. The adaptive plan, smart 3-parity in a game where it does not jump, sweeps A, then B while a 3 is afloat, then the rest of the checkerboard: about 32 shots per 100 cells on average, but a hider who knows the rule can still make it spend 33⅓. Always jumping from A to B as soon as the first 3 sinks is worse: 38 shots per 100 cells in the worst case. The adaptive plan and always jumping each have a layout that hurts them: if the two 3s lie in opposite halves, jumping after the first sink finds the second one sooner; if they share a half, jumping sends you to search the half with no 3.

Beating the plain plan. Take the plain plan's finishing times as the pace: against them the plain plan itself wins exactly half its races on every layout. Can anything guarantee more? A little, and one extra rule does most of it. Keep the plain plan, sweeping B in long runs along its diagonals, until both 3s are down; then hunt the 2 first in the cells of C that touch an unshot cell of B, then in the rest of A, then in the rest of C. A cell of C next to an unshot B cell can still hold the 2 in more ways than one whose B neighbors are already shot. That plan wins exactly 37/72, about 51.4%, on every layout. Changing only where you search for the 3s does less: the adaptive plan and always jumping can each be held below 49%, and the best coin between them, jumping in about a third of games, about as often as smart 3-parity does, reaches only 49.4%. Searching part of B after the first sink, instead of tossing a coin, lifts one plan to 51.8%, mixing such plans gives 51.95%, and ordering every shot inside each part gives at least 52.14%; no strategy can guarantee more than 19/36, about 52.8%, against this pace.

On a real board. On 10×10 with this fleet, in shots on the worst layout found for each rule, the opening's 3-parity and the adaptive rule are level, always jumping is worst and jumping in about a third of games is best. The self-play mixture of section 2 opens like the plain plan (the second replay).

In detail: the large-board page has the model in full: why every third diagonal, the exact laws of the three plans, the hider's patterns and the plans that beat 3-parity. The 10×10 page plays the model's rules on a real board.

How to hunt

How to hide

Hide at random, unless you know how your opponent hunts. Random hiding gives a hunter nothing to aim at, and the strongest hunts barely notice it: the near-perfect player of section 1's chart wins 50.04% of races against a randomly hidden 5×5 fleet, and on the classic board no hiding rule we tried moves the best strategy we found by more than 3.4 points.

Against the heat map, use the edges and corners, where it looks last (its worst board is near the top of the page). Putting just the 2 in a corner cuts its win rate from 57.1% to 28.5%. Don't pack everything into one corner, though: that cuts it only to 50.6%, and helps the pattern hunts.

Against a pattern hunt (plain 3-parity, the checkerboard, smart 3-parity), edges help the hunter. Keep your ships apart and off the edges instead, and above all keep the 2 from touching another ship: that takes 7 to 9 points off these hunts.

Against an opponent who won't adapt, the best all-round rule we tried is the 2 in a corner with ships apart: it beat random hiding against 12 of the 13 hunts we raced. But a habit is information. On 10×10 with the {3,3,2} fleet, a hunter that knows your rule wins 67% to 89% of races against such habits, against 54% when you hide at random.

Related work and further reading

As far as we found, the race analysis on this page is new: scoring hunts by their worst board, the solved small boards, the self-play mixtures, the classic-board strategies and the large-board plans. Its ingredients are older.

Battleship

• The box rules (Hasbro 2002) alternate single shots and name the ship on every hit and sink, so our hunters hear less.
• Berry (2011), the best-known analysis of Battleship hunts, finds the heat map fastest on random boards and describes the checkerboard "parity" trick.
• Sakuta and Iida (2002) scored strategies by race win rates and found that ships hidden along the edges beat an attacker that fires at the likeliest cell.
• Audinot, Bonnet and Viennot (2014) split the game into two separate hunts and computed the fastest hunts against randomly hidden ships on small boards; Silver and Veness (2010) and Grand et al. (2026) use Battleship to test AI planners and language-model agents, also against randomly hidden ships.

Hiding and searching

• Alpern and Gal (2003) is the standard book on search games, where one side hides, the other searches, and the answers are lotteries.
• Ferguson (2005) sets 3×3 Battleship as a textbook exercise; Farina et al. (2019) compute equilibria of a Battleship scored by damage dealt, not by who finishes first, on boards of at most six cells.
• Lidbetter (2013): when hidden objects have no shape, shooting in random order is optimal (about 95 shots for the classic fleet's 17 cells), so everything a good hunt saves comes from the ships' shapes.

Covering patterns

• Golomb (1954) colored the chessboard along diagonals so that every straight three-cell piece covers one cell of each color, the three sets of every-third diagonals behind 3-parity; Dumitrescu and Tkadlec (2024) prove that one cell in k is the least any pattern can use to hit every straight k-cell ship.
• A folklore problem in a Russian children's math magazine (Kvantik 2016) shows that every fourth diagonal, 24 shots, is the fewest that guarantee a hit on a 4-cell ship on 10×10.

Game theory and self-play

• von Neumann (1928) proved the minimax theorem; Kuhn (1953) showed that a lottery drawn before the game equals fresh dice before every move, for players who remember everything.
• McMahan, Gordon and Blum (2003) introduced the double-oracle method, which Lanctot et al. (2017) generalized to policy-space response oracles (PSRO) and Halvorson, Conitzer and Parr (2009) applied to a hide-and-seek game.
• Hart (2006) explains Aumann and Maschler's theory of when a player should reveal what it knows and when it should conceal it.

Average strength and worst case in AI

• Timbers et al. (2022) argue that head-to-head results and exploitability are complementary scores for game-playing programs.
• Gleave et al. (2020) and Wang et al. (2023) show that agents strong on average, up to a superhuman Go program, lose to adversaries trained against them.
• Perolat et al. (2022): DeepNash plays Stratego close to equilibrium and randomizes its setup to stay unexploitable.