Imperfect-information game AI

Stratego

The classic capture-the-flag game, played against a bot that has to infer what your pieces are. It sees exactly what you'd see across a table — which pieces have moved, what every battle revealed — and nothing else. No difficulty setting lets it peek at your ranks.

Opponent

Your army

Pieces

Status

Arrange your four back rows, then start the game.

Opponent 40 pieces

You 40 pieces

Click any two of your pieces to swap them. The generated formation is already a sound one — the flag is sealed behind bombs, scouts are forward, miners are held back.

The pieces

10 Marshal ×1 Beats everything. Falls only to the Spy on the attack.
9 General ×1 Second in command.
8 Colonel ×2
7 Major ×3
6 Captain ×4
5 Lieutenant ×4
4 Sergeant ×4
3 Miner ×5 The only piece that can defuse a Bomb.
2 Scout ×8 Moves any distance in a straight line, and may strike on the same turn.
S Spy ×1 Defeats the Marshal, but only when the Spy attacks first. Loses to everything else.
B Bomb ×6 Never moves. Destroys any attacker except a Miner.
F Flag ×1 Never moves. Lose it and you lose the game.

How it plays

Pieces move one square at a time, orthogonally. Scouts are the exception — they slide any distance in a straight line and may strike on the same turn, which is what makes them the natural probing piece.

Move onto an enemy piece to attack. Both ranks are revealed and the lower one is removed; equal ranks trade off. Bombs and the Flag never move. The two lakes in the middle of the board are impassable.

You win by capturing the Flag — or by leaving your opponent with no legal move at all. A piece may not shuffle back and forth between the same two squares forever.

How the bot thinks

Stratego is an imperfect-information game, so straight minimax doesn't apply: the bot can't evaluate a position it can't see. The standard workaround, and the one used here, is to maintain a belief over every unseen enemy piece and collapse it to a single suspected rank before searching.

That belief updates only from things you could observe too — which pieces have moved (so they aren't bombs or the flag), what every battle revealed, how long a piece has sat still, and where unmoved clusters suggest a flag is buried. The bot then runs alpha-beta search over that reconstruction.

Hard adds one more read, the kind an experienced opponent makes across the table: where a rank is usually placed. Scouts get pushed forward, miners held back, and the marshal is rarely parked on the front rank where an opening scout run would find it — it more often sits in the middle ranks, tucked into the files behind the lakes where it can only be approached from one side. That read applies only while a piece is still on its starting square; the moment it moves, where it stands says nothing about how the army was arranged.

It's deliberately a weak signal. Your default formation is generated by this same project, so a confident placement prior would decode that army rather than reason about it. Tuning it against armies arranged on other conventions showed the benefit is concentrated on conventional play, so the prior is shrunk to about a quarter strength — enough to shade the odds, not enough to see through anything.

The three difficulties differ in search depth and in how much inference they do, not in what they can see. Easy ignores the battle history and blunders on purpose; Hard uses the full belief model and searches as deep as its time budget allows.

Seeing the bot's read

Turn on Bot's read and select one of your own pieces to see the bot's posterior over what that piece might be — the five most likely ranks, most likely first. It follows the piece as it moves and clears when the piece dies.

This is the same distribution the search runs on, not a display-only approximation, so it's a direct window into the model. Watch a piece you've never moved drift toward Bomb and Flag as the game goes on, and watch that collapse the moment you move it. It's also the honest way to see how well a bluff is working.