Battleship Search Algorithms: Parity Grids and Bayesian Probability Density

Battleship, originating as a World War I pencil-and-paper naval game known as Broadsides or Salvo and standardized by Milton Bradley in 1967, represents a classic problem in Hidden Markov Modeling, Parity Grid Sampling, and Bayesian Search Theory. While casual players fire randomly or sweep in linear rows, modern artificial intelligence engines solve Battleship through a rigorous bifurcated state machine: Parity-Optimized Hunt Mode to locate enemy vessels with minimum probes, and Bayesian Probability Density Functions (PDF) to sink ships with frame-perfect efficiency.

In our digital strategy suite, Naval Battleship provides the classic $10 \times 10$ naval radar grid. By studying parity reduction formulas and probability heatmaps, players can consistently sink enemy fleets in under 42 shots while fortifying their own fleet defense against enemy radar sweeps.

1. Mathematical Architecture: Fleet Dimensions and Hidden States

A standard Battleship game is played on two identical $10 \times 10$ Cartesian grids consisting of 100 cells each: $(x, y) \in [0, 9] \times [0, 9]$.

Each player deploys a fleet of five distinct naval vessels occupying a total of 17 cells:

                  THE STANDARD FIVE-VESSEL FLEET
   Vessel Class              Length (Cells)   Symbolic Footprint
   ─────────────────────────────────────────────────────────────
   Aircraft Carrier          5 cells          [ ■ ■ ■ ■ ■ ]
   Battleship                4 cells          [ ■ ■ ■ ■ ]
   Cruiser                   3 cells          [ ■ ■ ■ ]
   Submarine                 3 cells          [ ■ ■ ■ ]
   Destroyer (Patrol Boat)   2 cells          [ ■ ■ ]
   ─────────────────────────────────────────────────────────────
   Total Occupied Territory: 17 cells / 100 cells (17% Grid Density)

Ships can be placed strictly horizontally or vertically; diagonal placement is forbidden. Ships cannot overlap.

The fundamental challenge of Battleship is Imperfect Information with Zero Direct Sensor Data: every shot returns only a binary response: HIT or MISS. The game is solved by constructing mathematical models that maximize the information yield of every salvo.

2. Phase 1: Hunt Mode and the Parity Search Reduction

When no active damaged ship is currently under bombardment, the player operates in Hunt Mode. The objective is to locate the first hit on an enemy vessel using the fewest possible probes.

       NAIVE FULL SCAN (100 SHOTS)              PARITY STRIDE-2 SCAN (50 SHOTS MAX!)
       ┌───┬───┬───┬───┐                        ┌───┬───┬───┬───┐
       │ ? │ ? │ ? │ ? │                        │ X │   │ X │   │  (Checkerboard Pattern)
       ├───┼───┼───┼───┤                        ├───┼───┼───┼───┤
       │ ? │ ? │ ? │ ? │                        │   │ X │   │ X │  Every 2-cell ship MUST
       ├───┼───┼───┼───┤                        ├───┼───┼───┼───┤  intersect at least one
       │ ? │ ? │ ? │ ? │                        │ X │   │ X │   │  target cell!
       └───┴───┴───┴───┘                        └───┴───┴───┴───┘

The Parity Stride Invariant

Consider the smallest ship in the fleet: the Destroyer (Length 2).

• Any straight 2-cell ship placed horizontally or vertically on a grid must occupy two orthogonally adjacent cells $(x_1, y_1)$ and $(x_2, y_2)$.
• In an alternating checkerboard pattern, one of these cells will always have an even coordinate sum, and the other will have an odd coordinate sum: $$(x_1 + y_1) \not\equiv (x_2 + y_2) \pmod 2$$

Therefore, a player who fires exclusively into cells where $(x + y) \equiv 0 \pmod 2$ is mathematically guaranteed to hit every single ship in the fleet, including the 2-cell Destroyer! $$\text{Max Probes Required} = \frac{100}{2} = 50 \text{ shots}$$

By applying checkerboard parity, you eliminate 50% of the board without ever risking missing a hidden ship.

Dynamic Stride Expansion (Stride-3 and Stride-4)

If you successfully locate and sink the Destroyer early in the match, the smallest surviving ship is now the Cruiser or Submarine (Length 3).

• You can immediately upgrade your search grid to Stride-3 Parity ($(x + y) \equiv 0 \pmod 3$).
• This reduces the remaining search space from 50 cells down to only 33 cells.
• If both 3-cell ships are sunk, search stride expands to 4, slashing the required search volume to just 25 cells.

3. Phase 2: Target Mode and Bayesian Probability Density Functions (PDF)

The instant a salvo registers a HIT, the engine shifts immediately from Hunt Mode to Target Mode.

                BAYESIAN PROBABILITY DENSITY HEATMAP
   Current State: HIT registered at Coordinate (4, 4)
   
                 (3, 4) [Prob: 8]  <-- Highest Probability Vector!
                   ▲
                   │
   (4, 3) [Prob: 5] ◄─── [ HIT (4,4) ] ───► (4, 5) [Prob: 8]
                   │
                   ▼
                 (5, 4) [Prob: 2] (Obstructed by known MISS)

The Mathematical Heatmap Generation Algorithm

Advanced AI solvers compute a Probability Density Function (PDF) across all remaining open cells:

1. The engine takes every surviving enemy ship $S \in \text{Fleet}_{\text{alive}}$.
2. For every open coordinate $(x, y)$ on the board, the engine tests whether ship $S$ could legally fit horizontally or vertically across that cell without overlapping known MISS cells or already sunk ships.
3. Every time a valid placement covers cell $(x, y)$, the cell’s probability score increments: $$\text{Score}(x, y) = \sum_{S \in \text{Fleet}} \sum_{\text{Valid Configurations } C} \mathbb{I}\left( (x, y) \in C \text{ and } \text{Hits} \subseteq C \right)$$
4. The engine fires its next salvo at the coordinate with the highest absolute PDF score: $$(x^, y^) = \arg\max_{(x, y)} \text{Score}(x, y)$$

In Target Mode, configurations that contain the registered HIT are weighted by a massive factor ($1,000\times$), compelling the AI to sweep along the ship’s primary axis until the vessel reports SUNK.

4. Fleet Placement Strategy: Avoiding the Perimeter Trap

Most casual players place their ships around the outer perimeter edges (Row 0, Row 9, Column 0, Column 9), believing the edges are “hidden”. In naval game theory, this is the Perimeter Clustering Trap.

       POOR DEFENSIVE PLACEMENT                   OPTIMAL ASYMMETRIC SCATTER
    ┌───────────────────────────┐              ┌───────────────────────────┐
    │ ■ ■ ■ ■ ■ (Carrier)       │              │       ■ ■ ■ (Cruiser)     │
    │                           │              │                           │
    │ ■ ■ ■ ■ (Battleship)      │              │   ■ ■ ■ ■ (Battleship)    │
    │                           │              │                           │
    │ ■ ■ ■   (Cruiser)         │              │                           │
    │                           │              │ ■ ■ (Destroyer)           │
    │ ■ ■     (Destroyer)       │              │             ■ ■ ■ ■ ■     │
    └───────────────────────────┘              └───────────────────────────┘
   (Predictable edge clustering;               (Irregular spacing forces
    easily wiped by edge sweeps)                maximum hunt-mode probes)

The Edge Vulnerability:

• Ships packed against walls have restricted degrees of freedom. Once an opponent finds one hit along an edge, they have only two possible directions to explore instead of four, doubling their targeting speed.
• Ships clustered adjacent to one another create Collision Overlap: an opponent targeting an Aircraft Carrier will accidentally strike an adjacent Submarine, giving them dual targets without returning to Hunt Mode.

The Asymmetric Island Defense:

1. Maintain a 1-Tile Buffer: Never place two ships directly touching, even corner-to-corner.
2. Scatter Across Diverse Parity Tracks: Place ships irregularly across both even and odd diagonal axes.
3. Anchor the Destroyer in the Interior: The 2-cell Destroyer is the hardest ship to find. Hide it in the open central sea rather than against a wall.

5. Technical Comparison: Naval and Grid Warfare Systems

The following structural matrix compares state spaces, detection models, and computational search properties across browser strategy and deduction titles:

6. Actionable Salvo Protocol for High Win Rates

To sink enemy fleets consistently in Naval Battleship:

1. Fire on Checkerboard Coordinates: For your opening 20 shots, fire exclusively into cells where $(x + y)$ is even. Never fire into an odd cell during Hunt Mode unless the Destroyer is already sunk.
2. Follow the Vector of Confirmation: When you register two consecutive hits (e.g., $(4, 4)$ and $(4, 5)$), you have established the ship’s orientation (Horizontal). Immediately cease firing vertically. Continue firing along the established horizontal axis until the ship sinks.
3. Punctuate Around Sunk Ships: The moment an enemy ship sinks, mentally mark all surrounding diagonal and orthogonal cells as low-probability zones. Ships cannot occupy the same physical space.

Frequently Asked Questions

What is the theoretical minimum number of shots required to win Battleship?

The absolute theoretical minimum is 17 shots, achieved only if every single salvo strikes an occupied ship cell with zero misses (5 hits for Carrier, 4 for Battleship, 3 for Cruiser, 3 for Submarine, 2 for Destroyer). Under Bayesian probability search against human players, elite algorithms achieve an average win in 38 to 44 shots.

Why is the 2-cell Destroyer considered the most dangerous ship in Battleship?

While the 5-cell Aircraft Carrier carries the highest prestige, it is mathematically the easiest ship to find: its massive 5-cell span makes it virtually impossible to hide from a parity search. The 2-cell Destroyer, by contrast, occupies a tiny footprint that easily slips between search strides. Games are frequently won or lost based entirely on how long it takes to locate the enemy Destroyer.

Does firing in a spiral or diagonal pattern work better than checkerboard parity?

No. Diagonal and spiral patterns are intuitive human aesthetics, but they lack mathematical optimality. A checkerboard parity grid is provably optimal because it guarantees that no contiguous straight line of length $\ge 2$ can fit between sampled cells, mathematically ensuring that no ship can remain hidden once the parity sweep is complete.