Searching Deeper Fixed Nothing: Notes From Building a Quoridor Engine

Our Quoridor engine had a list of 182 positions where it saw a threat, searched past it, and still played the losing move. The obvious fix was to search deeper. So before writing any code, we re-ran all 182 positions at one and then two extra plies. Depth 6 fixed two of them. Depth 7 fixed none, and took six times as long to get the same wrong answer.

That one afternoon of measurement killed a project we had already scheduled, and it changed how we think about the engine. This post is the record: how we grade a Quoridor bot without letting it grade itself, what the depth experiment showed, what randomness costs, and a game where our strongest bot built its own cage. Blocade is a Quoridor-style game, so all of this comes from an engine that ships in the app's practice mode. If you don't know the game, the rules take five minutes.

Quoridor is a race on a 9×9 board. Each turn you move your pawn one square or place one of your ten walls, and the first pawn to the far side wins. The engine is a plain alpha-beta search with a transposition table. Its evaluation is the number most Quoridor programs use: the length of my shortest path to goal, minus the length of yours, computed by breadth-first search over the walls on the board. On top of that sits some tuning for wall counts and move parity. The shipped practice bots run this search between depth 1 and depth 5, with node budgets up to 200,000, and the strongest of them plays somewhere around 1700 to 1800 against rated humans.

The branching factor is the problem. A pawn has at most five moves, but there are up to 128 legal wall placements on an empty board. Every extra ply of search costs a lot, so the question of whether depth actually buys strength matters more here than it does in chess.

The first thing we got wrong was measurement. Self-play looks like a test but isn't one, because both sides share the same evaluation, so any blind spot cancels out. Grading a move by the engine's own search value is circular: the move the bot picked is by definition the argmax of the grader. For months every instrument we had was one of those two things, and "the eval is blind" was an unfalsifiable complaint.

So we built two instruments that never consult the evaluation. The first is a bank of 579 defensive positions, each taken from a real game, where a single wall by the opponent lengthens the bot's route by a known amount. The judge is breadth-first search and the rules, nothing else: did the bot's move leave that threat on the board, yes or no. The second is a corpus of games by strong humans. Not high-rated players, because ratings can be inflated by farming weak opponents, but players with at least 40 ranked games against other humans and a win rate of 68% or better against them. That gave 63 players, and their moves are the external anchor everything else is checked against.

On the 579-position bank, the shipped configuration (depth 5, 60,000 nodes) defends 320 positions, or 55%. Of the 259 it misses, 77 are generation failures: the right wall was never on the list of candidates the search looked at. The other 182 are worse. The right wall was a candidate, the search looked at it, and the engine still preferred something else.

An architecture review had named those 182 as the target for a quiescence search on wall moves, on the theory that the damage sat one ply past the horizon. If that theory were right, a plain deeper search should fix most of them. So we re-searched all 182 at depth 6 and depth 7 before building anything.

The obvious objection is that the deeper searches were starved of nodes and quietly did the same work. We checked. On 80 sampled positions, depth 6 picks a different move from depth 5 about 10% of the time, and depth 7 differs from depth 6 another 10%. The deeper searches were doing different work. They just arrived at the same wrong leaf.

Two later attempts to fix the leaf evaluation directly also failed, one of them badly: a change that priced sealing walls higher took a 12-out-of-12 test set to 0 out of 12. What is left is a learned evaluation, which we have not built, or accepting the ceiling. We accepted it, for now.

The human corpus explains why the evaluation is wrong in the direction it is wrong. Some numbers from 1,142 walls placed by the 63 strong players:

That last one has a strange corollary. The engine over-walls in general, and yet when it is losing it hoards. It ends full-length lost games holding an average of 3.28 of its 10 walls, because from behind, no single wall shows a gain on the shortest-path metric, so it places none. Humans in the same spot spend them.

A deterministic engine plays the same game every time, which is bad for a game people replay. So the engine can sample among moves whose search value sits within a small margin of the best. The question was what that costs. We replayed 1,060 engine moves from 50 games, once deterministic and once with sampling, and graded each pair on ground truth: the bot's route length minus the human's after the human's best single reply wall.

Sampling changed the move 11.3% of the time, and the average cost was 0.032 tempi per move, about 0.8 tempi over a whole game. Small. But the average hid the shape of it.

The whole tax was one substitution. When the deterministic best move was a wall and sampling replaced it with a pawn move, the result was worse 34 times out of 39 and better zero times. The reverse swap was mildly good for the engine. Everything else was noise. The reason is the same underpricing of walls from the previous section: the evaluation's noise band is biased against walls, so sampling inside that band is systematically anti-wall.

The fix was two lines. If the best move is a wall, only sample among walls. Same 1,060 moves with the flag on: cost per move fell 87%, the worst-case outliers went from 10 to 1, and 86% of the move variety was kept.

Numbers say what happens on average. One game shows what it looks like. In September the strongest practice bot, Kof, played the same human three times. It won the first two. The third is below, with the bot in red moving down the board and the human in green moving up.

At plies 8, 10, 14 and 22 the bot placed four horizontal walls to slow the human. Each one, on its own, was priced as a gain on the shortest-path metric. Together they cut the bot's own board in half. After the fourth, the bot could reach its goal row only through the left three columns or the right two. A pair of human walls on the left costs it 8 extra squares, and a single wall on the right closes the other side. The bot did not choose badly between two openings. It spent the middle game deleting its own.

The wall that did it was the fourth one, at ply 22. Searches at depth 2, 3 and 4 all play it. Depth 5, 6 and 7 all reject it and advance the pawn instead. The phone was running Kof at a 1.5 second budget, which on that position is effectively depth 4. And a sweep from every ply confirms where the game was lost: a tempo-correct two-wall defender beats the bot from 44 of 93 continuations at ply 22 and from 0 of 84 at ply 24, and never again after that.

One more thing from this game, because it is the kind of thing that looks like a bug and isn't. From ply 28 the bot retreats. It walks its pawn back up the board for seven moves. Our first read was horizon paralysis, and we went looking for the defect. But a depth 7 search plays the same retreat, and so does depth 11. In an isolated test with the same continuation on both sides, forcing the advance at ply 28 loses at ply 69 and the retreat wins at ply 72. The retreat was right. The game was already gone at ply 22, and everything after was the engine playing the least-bad line.

The open problem is the leaf evaluation. Shortest-path difference is a good metric for an engine that walls in the right places, and a bad one for deciding where those places are. The human data says the answer involves walls that do nothing now and everything two moves later, and we do not yet have a cheap way to price that.

If you want the numbers behind the game itself rather than the engine, we published what 3.4 million recorded moves say about Quoridor, including a first-player win rate of 49.8% across 33,165 ranked human games. And if you want to try beating Kof, it is in the app.

F

Francis

CREATOR OF BLOCADE

Francis is the solo developer who designed and built Blocade — its bots, ranked ladder, and daily puzzles. These guides come straight from the person who made the game.