Battleship Monte-Carlo Solver

An AI that plays Battleship by sampling millions of possible board configurations and firing at the most statistically likely cell, every single turn.

Play Against It → View Source

# The problem

There are 30 billion+ possible ship arrangements on a 10×10 grid (source). Computing exact per-cell probabilities across all of them, conditioned on every hit and miss, is NP-hard — far too expensive for real-time play.

So we sample: draw thousands of random legal configurations, tally which cells appear most often, and fire at the highest-frequency target. This frequentist approach assumes all valid boards are equally likely — a simplifying assumption, since real players have placement biases — but uniform sampling is the most principled starting point without a bias model, and in practice it plays surprisingly well.

# How it works

  1. Encode legal placements as bitboards

    Every position each ship could occupy is stored as an integer, one bit per cell. A 10x10 board fits in 128 bits.

  2. Sample, count, fire, prune

    Each turn: draw thousands of random boards consistent with all hits and misses, tally cell frequencies, and fire at the highest-probability unseen cell. After each shot, impossible placements are pruned and the search space shrinks.

  3. Converge

    As ships sink the solver's confidence increases and shots become near-deterministic.

# The tricks

Trick 01

Bitboard representation

All data (placements, hits, misses, boards) is encoded as Python integers. Overlap tests, unions, and checks compile to C-level bigint operations, eliminating set and dictionary overhead entirely.

overlap = (ship_a & ship_b) != 0

Trick 02

Carry-chain bit counting

Instead of iterating through set bits one by one, a carry-chain counter tracks per-tile counts across all positions simultaneously using bitwise AND/XOR on full-width integers. This replaces thousands of method calls with a handful of bigint ops.

counter[j] = (counter[j] ^ board) & carry

Trick 03

Incremental board filtering

Previously sampled boards are tested with a single bitwise check each. Only the deficit is regenerated, avoiding redundant sampling when the game state changes minimally.

valid = [b for b in pool if (b & new_miss) == 0]

Trick 04

Constraint propagation

After every shot, placements contradicting the known state are permanently discarded. Misses remove all placements touching the missed cell; hits remove those that don't cover confirmed cells. The rejection-sampling search space shrinks with every turn.

poss = [p for p in poss if not (p & miss_bit)]

Trick 05

Placement ordering

Ships are sorted by constraint count (fewest legal positions first) before board generation. The most constrained ship is placed first, maximizing early rejection and cutting wasted sampling attempts.

ships.sort(key=lambda s: len(s.placements))

Trick 06

Cython & xorshift64* PRNG

The rejection-sampling inner loop is compiled to C via Cython using 128-bit bitboards (two uint64_t fields) and a xorshift64* PRNG. The GIL is released for the entire sampling phase, yielding roughly 8-11x speedup over pure Python.

with nogil: # rejection loop in typed C