The Classic Fleet

1The yardstick: one pace, two numbers

The game is a race: both players fire one shot per round, and the first to sink the whole fleet wins (a finish in the same round counts half). Shots are answered “miss” or “hit”, and a sink announces the ship's size only; every strategy here uses only those announcements.

We drop context (where the opponent shoots and which of your ships it has hit; see the essay's section 1), so a strategy can be scored against its opponent's finishing times alone, the pace. Here the pace is the best strategy found on 32,000 random boards: every legal layout equally likely (ships straight, inside the board, not overlapping, possibly touching), each game in a random rotation or reflection.

The pace averages 47.3 shots (median 46); 90% of its games end between 33 and 65. A single game wins the share of pace games that take longer, plus half of those that tie (Figure 3, top): 77.7% at 40 shots, 51.2% at 46, 33.5% at 50 and 11.8% at 60. Near the middle, each extra shot costs 4.4 to 4.9 percentage points of win rate, “points” for short.

Why one fixed opponent? Against its own finishing times any strategy wins half its races on average, and a random shooter (about 95 shots) wins exactly half on every board. A fixed pace makes strategies comparable; since nobody knows yet how a strong player should hide this fleet, the opponent hides at random.

Each strategy gets two numbers: its win rate on random boards, on the pace's own boards (standard error about 0.2 points), and its worst case, the win rate on the hardest board a search found against it.

One caveat: the best strategy races its own finishing times, so its ≤ 43.9% measures flatness rather than speed. Two checks speak for it: on its worst board found it needs 48.3 shots, fewer than any other strategy needs on its own worst board found (51.0 at best). Against an earlier, faster pace (the classic-board self-play loop's, 46.2 shots), an earlier search held it to ≤ 41.0%, and three other strategies to ≤ 25%, ≤ 33.9% and ≤ 35.2%.

Three hunts come from the essay's introduction, the opening. The checkerboard fires at random cells of one color, 3-parity at random cells of one set of every-third diagonals, then the next, and the heat map at the cell the most remaining ship placements could cover. The first two finish the plainest way (fire next to a hit, extend a line of two); the heat map just counts again after every shot.

2Searching for hard boards

Against any hunt, a hider's best reply is a single board: a lottery over boards scores the average of its boards, never less than its worst. So searching single boards is the right adversary; only the search's reach is in doubt. Hard boards come from a local search, a descent: move one ship at a time to every legal spot (about 529 per sweep) and keep a move that lowers the win rate.

Each strategy went through up to five stages (smart 3-parity six); its worst case is the lowest value any stage found, each measured on 8,000 fresh games (standard error about 0.3 points):

1. Own search: a descent from eight start boards (four common hard boards, two found against it earlier, two random); each candidate move is tried on 8 games, the most promising on 32 and then 128.
2. Cross-play: every strategy re-scored on all 650 start and end boards of every own search.
3. First descent from the two lowest boards so far, confirmed: a move counts only if it also wins on 1,024 fresh games.
4. Tournament cross-play over 759 boards from all 136 earlier searches: every board gets 256 games, the lowest quarter 768 more, and the lowest quarter of those 3,072 more (fewer for the two self-play mixtures).
5. Second descent, confirmed the same way, from the tournament's two lowest boards.

Own descents used 0.37 to 0.78 million games per strategy (median 0.73) plus cross-play, about 19 hours on six threads for the best strategy. A stronger search might still find a harder board, so every worst case is an upper bound, written “≤” and rounded up.

Why five stages? A search that keeps the lowest of many noisy readings is fooled by luck. The own search, the only descent without per-move confirmation, accepts moves that only looked better and wanders toward boards that are not really hard. It ended 2.0 points above the final worst case on average (up to 6.9; Figure 1).

Cross-play matters as much as descent: 39 of the 70 final worst cases came from it (37 from the tournament), 26 of them on boards only other strategies' searches found.

How much noise is left? The opening's 3-parity, searched twice, came out at ≤ 34.1% and ≤ 34.8%, the checkerboard at ≤ 27.5% and ≤ 27.4%. A stronger search (section 7) lowered five rules a person can play (six entries) by 0.4 to 0.9 points. So we treat differences under about a point as noise.

3All 70 strategies

Figure 2 puts every strategy on one chart, colored by what playing it takes. There are 26 pencil-and-paper rules, 10 that add one count of where ships still fit, 18 that need a computer, 11 heat-map hunters, 2 computed mixtures of rules and 3 self-play machines. Table 1 lists the strongest of each kind and the reference hunts.

Average and worst case trade off. All 16 strategies that beat the pace on random boards hold 26.3% or less on their worst board found, the best of them the classic-board self-play mixture. The heat-map hunters are the fastest (55 to 58% on random boards) and the most exploitable (worst cases ≤ 1.5% to ≤ 24.0%). Only the best strategy pairs the pace's average with a worst case above 40%.

The strongest rules, by hand or by computer, sit between 35 and 38%. Computer finishing buys speed, not safety: after a hit, the computer fires where most of the ways the ships could explain the hits overlap. With it smart 3-parity's first version wins 49.0% on random boards, 2 points more than without, yet holds the same ≤ 36.5%. The rule mixture, a weighted die over four rules set by a linear program, is the best strategy not built by self-play (≤ 38.1%) but needs a computer and plays the heat map in about 9% of games.

4Speed against blind spots

Against a fixed pace a game's share of wins depends only on its length (Figure 3, top), so a blind spot shows up as extra shots. Figure 3 (bottom) sets random boards against the worst board found.

The best strategy needs 1.1 more shots there, smart 3-parity 3.2, 3-parity 3.3 and the checkerboard 2.9. The classic-board self-play mixture (9.4) and the earlier version of the best strategy (12.4) start about a shot faster than the best strategy and lose it all; the heat-map hunters need 10 to 24 more.

Figure 4 shows the whole spread for five of these strategies, from 8,000 new games on each one's worst board found; their averages agree with the search's within a quarter of a shot. On its worst board, every one of the heat map's 8,000 games took 60 to 75 shots; even 60 shots beats only 12% of the pace's games.

Figure 5 shows six of the worst boards found.

5The best strategy found, in depth

The best strategy found is not built for the classic fleet at all. It is a snapshot of the 10×10 {3,3,2} self-play mixture (two 3-cell ships and a 2-cell ship) from the essay's section 2 and the 10×10 page. Its 743 fixed hunts (hunts with no dice) win 49.95% on their worst three-ship layout against their own pace. Each game draws one hunt by weight and a random rotation or reflection; the hunt plays its own three-ship game, in which the carrier and the battleship are water:

# before the game
h ← one of the 743 fixed hunts, by weight
turn the board: a random rotation or reflection
# h plays its own game: two 3s and a 2;
# the 4 and the 5 are water
repeat until the fleet is sunk:
    if the announcements prove a big ship:
        # "sunk, size 4 or 5", hits no small
        # ship can explain, or 8 hits with
        # small ships afloat
        finisher: extend the line of hits
                  until every hit is
                  explained by a sink
        rewind h to just before its first
        shot at that ship; that cell now
        reads "miss"
    else if a 3 or the 2 is afloat:
        c ← the cell h asks for
        if c is known, or no ship afloat fits:
            answer h from memory  # no shot
        else:
            fire at c; tell h "miss", "hit"
            or "sunk"
    else:                    # big ships only
        fire at the cell the most placements
        of the remaining big ships could
        cover                     # heat map

The finisher only extends lines of hits. The rewind is total: every choice the hunt made after its first shot at that big ship is erased, and cells it asks for again cost nothing. The program needs about 6 GB of memory and plays about 8 games a second on six threads.

Figure 6 shows a rewind in the essay's typical 46-shot game (its third replay, in section 3, steps through every shot). At shots 30 to 32 the hunt hits E6, D6 and C6 without a sink. With one 3 afloat, a 3 covering all three hits would have been announced sunk, so a big ship has been hit. The finisher sinks the carrier at G6, and the hunt is rewound to just before E6, which now reads “miss”.

Where do its 47.3 shots go? Per game, the small-ship hunt keeps 34.3 and a rewind later erases 8.5 (5.8 of them hits on the big ships). The finisher fires 2.8 and the final heat-map hunt 1.7; another 3.7 choices are answered from memory.

Only 38% of its shots on random boards go to the hottest cell of a full-fleet heat map. The finisher's shots go there 84% of the time and the final hunt's 87%, but the small-ship hunt's only 33%.

The small-ship hunt finds the big ships itself (Table 2): in 2,000 replayed pace games it made the first hit on the carrier in 89.7% of games and on the battleship in 87.4%. A 4 or a 5 crosses every set of every-third diagonals, where the hunt spends most of its search shots. Of its pure hunting shots (a 3 afloat, no hit waiting), 72.0% land on the one set that fits that game best; that set is picked after the fact, and random shooting scores 46.4%.

Why it holds up

Inside its private game each hunt follows exactly its path on that three-ship layout alone (7,999 of 8,000 checked games do, or stop early along it). The mixture's win rate holds on every three-ship layout, averaged over rotations and reflections, so with a random orientation a hider can aim only at where the 4 and the 5 sit relative to the hunt. On one hard board the small ships alone scored 37% to 69% across the eight orientations.

The best strategy's own worst board found (Figure 5, first board) puts the 2 in a corner and a 3 against each of two edges. The big ships cost it less there than on random boards: the small-ship hunt makes the first hit on the carrier in 97% of games and on the battleship in 95%, and the final hunt runs in only 8%. Its 1.1 extra shots come from the small-ship hunt itself, 3.1 more per game, though its hunting shots stay on one set as often as ever (75.8%).

Rewinding is the key design choice. The earlier version of the best strategy used the same hunts but, after each big ship, rebuilt the hunt's picture of the small ships from the whole game so far. It also lacked the free “miss” on cells no ship afloat could occupy (about 0.2 points in an earlier test). It is a shot faster on random boards (46.4 shots, 52.7%) but holds only ≤ 20.0% on its worst board found.

Our working explanation, an inference rather than a measurement: after a rebuild every hunt restarts from a state of knowledge its own game never reaches, so the hunts converge on one picture that the three-ship guarantee does not cover.

What was tried and dropped

Tested against an earlier pace, some with a faster, approximate version of the program, so only direction and rough size carry over:

• A random final hunt instead of the heat map: just under a point worse everywhere, since what a hider exploits is how often a big ship survives the small-ship hunt.
• Handing every hit straight to the finisher before the small-ship hunt continues: about 2 points worse.
• Special rules for the last ship, one of them an exact calculation: 0.5 to 4.5 points worse.
• Skipping cells next to a sunk big ship: half a point better on random boards, but a hard board with two small ships against the carrier fell from 47% to 27%.
• Re-weighting the hunts for known hard boards only fit noise.
• A finisher that takes over at a big ship's first hit, using information the rules do not give: about half a point on random boards, a point on six hard boards, nothing on the worst of them. It bounds what fixing the rewind's waste could buy.

6Why self-play on the full fleet stalled

We ran the self-play loop of the essay's section 2 on the full fleet for 473 hours. Its linear program held one fixed placement of the 4 and the 5 for each of the 1.9 million three-ship layouts (one board in 7,800), plus the 2,706 hard boards its search found. That search never moved the small ships, tried the same 200 big-ship placements every round and used one orientation, so it could reach only about 48 million boards, 0.32% of the 15.0 billion.

The loop looked converged and was not. In its last 22 rounds its own score over the boards it knew read 42.2 to 43.1%, while each round's fresh hard boards held it to 19.0 to 27.6%. Gains per hour of compute fell from 0.37 points to 0.006. These values are against the loop's own pace at the time, not this page's.

A 6×6 test with every board scorable shows the same trap. With a fleet of 4, 3, 3 and 2 cells (633,432 boards) and the same design, the loop's own score read 49% while its true worst case was 26%. Adding the 400 hardest boards each round, found by an exact search, lifted the truth only to 40.1%, still rising. With every board in the linear program, 6×6 {3,3,2} closes normally at 49.6%, and {4,3,2}, which also has a 4, at 49.0%.

On this page's yardstick the classic-board self-play mixture needs 46.4 shots, wins 52.3% on random boards and holds ≤ 26.3% on its worst board found (Figure 5). That board lines the top and left edges: battleship A1–D1, carrier D2–H2, the 2 at F1–G1 above it, and the 3s down columns A and B. The best strategy avoids the trap by giving the linear program a game it can list completely.

7Rules a person can play

Smart 3-parity is the best simple rule we found for the three-ship game, plus a sweep for the big ships. Its full recipe follows, as on the essay's card. Rows and columns are numbered 0 to 9; a live cell is an unshot cell on a straight unshot run long enough for the smallest big ship afloat.

# before the game
D ← row + column, or row − column + 9
    # each cell's diagonal, 0–18;
    # direction at random
a ← (a six-sided die) − 1
A ← cells whose D leaves remainder a
    when divided by 6
B ← cells whose remainder differs from a by 3
jump ← true in 35% of games
    # 1–7 on a 20-sided die
F ← the four every-fourth-diagonal sets of
    one direction, chosen at random
# each shot
if a hit is not yet explained by a sink:
    if two or more such hits line up:
        fire at a random unshot cell
        extending the line
    else: fire at a random unshot neighbor
          of a hit
else if a 3 is afloat:
    if jump and one 3 is sunk and B has
       unshot cells:
        fire at a random unshot cell of B
    else: fire at a random unshot cell of A,
          then of B
else if the 2 is afloat:
    color ← the checkerboard color fired at
            more (chosen once, then kept)
    H ← the half, A or B, on that color
    fire at a random unshot cell of that
    color next to at least one unshot cell,
    taking first the cells outside H that
    touch an unshot cell of the other half,
    then those in H, then the rest
else:                    # the 4 and/or the 5
    if no set is chosen, or it has no live
       cell left:
        choose the set with the fewest live
        cells (at least one) among the six
        every-third-diagonal sets, the four
        sets of F and, with only the 5 left,
        the ten every-fifth-diagonal sets
    fire at a random live cell of the chosen set

On “sunk, size k”, the ship is taken to be k unexplained hits in a line through the cell just shot. The lazy endgame replaces the last step: pick one set of F at random before the game, then fire at its live cells, then at any live cell.

Hunting the 2 in that order is the one idea we tested from the large-board model that held up here. A cell outside H next to an unshot cell of the other half catches the 2 both across that half and off both halves, so firing there first saves 0.33 shots, worth 0.66 points on random boards. Two other ideas lost worst case: searching part of B instead of the 35% jump, up to 2.1 points; sweeping B in long runs, 0.6 to 1.1, as B has three or four short diagonals. Reading the big ships (alternate A and B once a sunk 4 or 5 crossed both) led the benchmark search at ≤ 38.5% but fell to ≤ 36.3% in the stronger one.

Is it the best rule a person can play? We found none better. In a stronger search of the five closest rules on 34 hard boards (Table 3), its first version, hunting the 2 anywhere on its color, came out on top, level with a variant. The revised card, given the same search twice and a third descent, holds ≤ 36.8% on 109 boards that include those 34, against ≤ 35.9% for the first version, which it beats on 73 of them.

With the lazy endgame the first version is as safe as the opening's 3-parity with the same endgame, and a shot faster (48.3 against 49.2 shots), so the halves and the jump buy speed without costing safety. The full endgame adds 0.7 points on the common boards, and 0.4 to the revised card (≤ 36.8% against ≤ 36.4%, at 47.8 against 48.0 shots).

How often should you jump? With the lazy endgame (Figure 7, first version), always jumping is clearly punished (≤ 27.7%), never jumping costs a little (≤ 34.3%), and jumping in a third to half of games does best. The values at 35, 40 and 50% are within noise: the curve says to mix, not exactly how often. The essay's section 4 shows why: a hider can punish either pure plan, not both.

The big-ship endgame matters too. With none (the rule keeps sweeping its checkerboard color), the first version falls from ≤ 35.9% (lazy endgame) to ≤ 33.1%; the lazy endgame lifts the opening's 3-parity from ≤ 34.1% to ≤ 35.9%. A computer counting where the big ships fit takes 3-parity to ≤ 37.2%, within noise of the card.

The fastest rule a person can play matches the best strategy's speed (47.3 shots, 48.9%) but holds only ≤ 28.1%. It sweeps half A and then half B diagonal by diagonal from one corner, never jumps, and hunts the 2 on cells with the fewest shot neighbors first. Its worst board (Figure 5) puts the 2 mid-board between the 3s, probably because fixed priorities can be aimed at. On the three-ship board, 99% of the 500 worst layouts for a related hunt for the 2 (fewest missed neighbors first) had the 2 off the edges, against 21% at random.

What does simplicity cost? Against the best strategy, smart 3-parity needs 0.6 more shots on random boards and wins 2.6 points fewer races there. On the worst boards found the gap is about 6 points, an estimate from two similar searches, not a bound.

8Heat maps and the three common hunts

The essay's opening covers the heat map's races with the checkerboard and 3-parity, and its worst board. On random boards it also beats smart 3-parity in 59.7% of races and the best strategy in 57.1%, but every heat-map hunter is predictable, and the search finds where each looks last (Figure 5).

The three-ship heat maps, which count placements of the two 3s and the 2 only, lose on the right edge (≤ 2.5% to ≤ 3.3%). Weighted by where the {3,3,2} self-play hider puts its ships, the three-ship heat map loses on a central cluster (≤ 1.5%), probably because it looks late wherever that hider rarely goes.

Luck with the 2 decides much of 3-parity's speed. Its first set meets the 2 in two games out of three, and then it finishes in 44.1 shots on average, against 59.8 shots when the first set misses the 2. Against the best strategy's pace that is 58.1% of races against 18.5%.

The worst boards of 3-parity and the checkerboard look ordinary, with no corner or edge packed, and cost them only about 3 shots (Figure 3): what hurts them is speed, not a blind spot.

9What is still open

• Hiding. Every number here is the hunter's; how a strong player should hide the classic fleet is unmeasured.
• Two-sided play. No measurement on this board has both players choosing their boards to hurt the other.
• Stronger searches. The best strategy and the computer rules have not had section 7's stronger search, and the other 68 strategies were not scored on the last boards found against the earlier version.
• A full check. The program is verified to play each hunt exactly as the three-ship linear program assumed, on every three-ship layout, only for hunts with 27.6% of the weight; the rest match on every sampled game.