Solving the board game Quoridor

2026-05-25<br>Solving Quoridor

This post significantly improves the state of the art in solving the board game Quoridor. I describe novel techniques that enable fully solving almost all board configurations with area ≤ 28 (e.g. 5x5, 8x3, 7x4, etc) for most wall counts on a consumer laptop.

Background

I was introduced to the board game Quoridor back in 2014 and was immediately taken by it.

I usually spend a weekend returning to Quoridor once every couple years, writing different forms of AI bots to play it. This last weekend, I made a breakthrough that enables both much stronger bots, and much more complete solving.

Rules

The game is pretty simple:

Pawns start on opposite sides of the 9x9 board

Your goal is to get your pawn to the far side

You have 10 walls

On your turn, you can move your pawn 1 square, or place a wall

You can jump over the opponent's pawn

You can't place a wall that makes it impossible for a pawn to get to its goal

That last rule is where all the performance complexity comes from. You might be planning on blocking your friend's straight shot — making him take the long way around — but he places a wall that cuts off the long route, so now it's illegal for you to block the short route!

The "pawn jumps over opponent's pawn" rule creates interesting parity/zugzwang situations.

In addition to the typical 9x9 board with 10 walls, many papers have analyzed smaller boards and wall counts, since the full game is currently intractable.

Major Results

Parity Advantage vs Tempo Advantage

Many have speculated that Quoridor might be a 2nd player win on odd-height boards due to pawn jump parity. This work shows that odd-height Quoridor boards are not always 2nd player wins.

They are always 2nd player wins with few walls, but typically turn into 1st player wins at a sufficiently high wall count. For example, 5x5 is a 2nd player win at ≤4 walls per player, but 1st player win at >4 walls.

The intuition here is that odd-height boards have a jump parity advantage for 2nd player, but 1st player still has a tempo advantage, so a sufficient number of walls makes the 1st player tempo advantage dominate the 2nd player's jump advantage.

There are a few notable exceptions discussed below.

Relatedly, we find that even-height boards are uniformly 1st player wins at all wall counts because 1st player has the jump parity advantage and the tempo advantage.

Forced Draws

It was known that forced draws by repetition were possible to contrive, but this work shows that the 8x3 board with 3 walls per player is a draw from the starting position.

Both players must just dance left and right forever. If either player deviates from this repetition, the other player has a forced win, therefore the optimal strategy is draw by repetition.

Weird geometries

There are some geometries with outlier results. For example:

4x7 is a 2nd player win for 0 or 1 wall, 1st player win for 2 walls, then back to 2nd player for 3 walls, then 1st player beyond that.

7x3 never transitions into a 1st player win at any wall count.

3x5 is a 2nd player win at all wall counts except 3

8x3 is a 2nd player win at all wall counts except 3 (where it's a draw, as noted above).

Full results table

Note: even-heights omitted, they are all 1st player win at all wall counts and geometries.

W x H012345678910<br>2 x 321111111111<br>3 x 322222222222<br>4 x 322211111111<br>5 x 322211111111<br>6 x 322221111111<br>7 x 322222222222<br>8 x 3222D2222222<br>9 x 322222221111<br>2 x 522222222222<br>3 x 522212222222<br>4 x 522221111111<br>5 x 522222111111<br>2 x 722111111111<br>3 x 722222111111<br>4 x 72212111????<br>2 x 922222222222<br>3 x 9222221111??

You can reproduce the results of this work by running the code in this repository. The smaller configurations finish almost instantly, the largest ones in the table take up to 30 minutes on my M3 MacBook Pro. I have 128GB of RAM and the largest configurations use a sizeable chunk of that to store all the precomputed data and transposition table.

Complexity

Quoridor has two main complexifiers.

The "illegal to fully block goal" rule makes enumerating legal moves hard. Naively, you have to do a pathfinding search for every candidate move. This means move generation is several orders of magnitude slower than a game like chess.

Adding to this pain, the branching factor pretty high. On any given turn there are typically 4 pawn moves and about 100 possible wall moves. So not only are the wall moves super slow to check the legality of, there are also a ton of them.

This huge branching factor makes naive alpha-beta negamax pretty weak. It takes a decent amount of work to get a bot searching to depth 6 or so.

Beyond the giant branching factor, the horizon effect is harder to deal with. In chess, you can deal with the horizon effect pretty easily with quiescence search where you search only the "interesting" moves (i.e. captures, checks) until no such moves remain and the position is "quiet".

In Quoridor, there are very...