Battleship

The Problem

A standard Battleship board is 10x10 (100 cells) with a fleet of 5 ships occupying 17 total cells. The goal is to sink all enemy ships in as few shots as possible. Since ship positions are unknown, this becomes a probabilistic search problem.

1. Random Firing

The simplest strategy: pick any unknown cell at random. This averages ~95-97 shots to win. It's a baseline, but terrible.

2. Hunt and Target

Two modes:

• Hunt mode: Fire randomly until you get a hit
• Target mode: Once you hit, fire at adjacent cells until the ship sinks, then return to hunt

This reduces average shots to ~65-70. Most humans play this way intuitively.

3. Parity (Checkerboard)

Since the smallest ship (Destroyer) is 2 cells long, it must occupy at least one "dark" square on a checkerboard pattern. During hunt mode, you can skip 50% of cells and still guarantee hitting every ship eventually.

4. Probability Density Function (PDF)

The "Heat Map" approach, popularized by DataGenetics. This is what the solver below implements.

For each remaining ship, enumerate all valid placements (positions where the ship fits on the board and doesn't overlap any misses). Count how many placements pass through each unknown cell. Cells with higher counts are more likely to contain a ship.

For cell $(r,c)$, let $N(r,c)$ be the number of valid placements passing through it. The normalized probability is:

When hits exist, cells adjacent to hits receive a multiplier boost (target mode heuristic). This averages ~42-45 shots to win.

Limitations:

• Greedy: Fires where a ship is most likely, not where information gain is highest
• Individual ships: Counts each ship separately, ignoring "blocking" between ships
• Heuristic targeting: The adjacency boost is a rule of thumb, not mathematically derived

5. Shannon Entropy (Information Gain)

Instead of maximizing $P(hit)$, maximize information gain. Let $S$ be the set of all valid board configurations. Firing at cell $(r,c)$ partitions $S$ into $S_{hit}$ (configurations where the cell has a ship) and $S_{miss}$ (where it doesn't).

The entropy of a probability distribution measures uncertainty. For the set of valid board states:

Firing at $(r,c)$ partitions the state space. The expected entropy after is:

Information gain is $H - H'$. Pick the cell that maximizes this.

Example: a cell with 50% hit probability eliminates half the search space either way. An 80% cell is "more likely" to hit but reveals less when it misses. The 50% cell may be the better shot.

6. Monte Carlo with Joint Distribution

The theoretically optimal approach. Exhaustively counting every valid fleet configuration is intractable (~$10^{14}$ combinations), so we sample:

1. Generate thousands of random valid board layouts matching current hits/misses
2. Count how often each cell contains a ship across all samples
3. This naturally handles ship-to-ship "blocking" that PDF ignores

Combined with entropy-based shot selection, this achieves ~35-38 shots on average.

Strategy Comparison