A Board Game More Complex Than Chess

Quoridor is played on a 9 by 9 board. Each player has one pawn and ten walls. You move one square or you place one wall, you may not seal anybody off from their goal, and the first pawn to reach the far side wins. That is the whole game. You can teach it to someone in about ninety seconds.

The number of different games you can play on it is around 10¹⁶².

Chess, the game everybody reaches for when they want to say "complicated", comes in at 10¹²³. So Quoridor is ahead. Not by a bit. The gap between those two numbers is thirty nine zeros.

Where that number actually comes from

Nobody sat down and counted. The measure is called game-tree complexity, and it is an estimate with a very simple recipe: take the average number of legal moves available on a turn, and raise it to the power of how many turns a game lasts.

For Quoridor those two numbers are roughly 60 and 91. About sixty legal moves on an average turn, about ninety one turns in an average game. Sixty to the power of ninety one is 10¹⁶². The figures come from a 2006 analysis of the game out of Maastricht University, and they have stood as the standard reference since.

Run the same recipe on chess and you get about 35 legal moves across about 80 turns. That is 10¹²³, a figure Claude Shannon first put on paper in 1950 and which still carries his name.

So the entire gap between the two games comes out of two modest looking differences. Quoridor gives you a bit under twice as many options per turn, and its games run about eleven turns longer. Compound those together ninety times over and you get thirty nine orders of magnitude.

Both rows are averages over complete games, and both are estimates. The point is not the third decimal place. It is that a wider turn and a longer game multiply, and multiplication at this scale is violent.

What 10¹⁶² looks like next to things that are not board games

Numbers this size stop meaning anything, so here is the usual ladder.

There are roughly 10¹⁹ grains of sand on Earth. There are about 10⁶⁸ ways to shuffle a deck of cards, which is already more than most people are comfortable with. The observable universe contains somewhere near 10⁸⁰ atoms.

Quoridor's 10¹⁶² sits above all of it. Square the number of atoms in the observable universe, which is a strange thing to do but bear with it, and you get 10¹⁶⁰. Still short. You would have to multiply that by another hundred to reach the number of games available on a board that fits in a small box.

The part where chess wins

Here is the honest complication, and it is the most interesting thing in the whole comparison.

There is a second way to measure a game, called state-space complexity. Instead of counting games it counts positions: how many distinct arrangements of the board can legally exist. On that measure Quoridor loses. Chess has about 10⁴⁴ legal positions. Quoridor has about 10⁴². Chess is ahead, a hundred times over.

So "more complex than chess" depends on which question you ask. Chess has more positions. Quoridor has more games. If you only ever hear one number about a game it is usually the game-tree one, because that is the number which predicts how hard the game is to actually play and to write an engine for. On that number Quoridor is comfortably ahead.

Why the walls do this

A Quoridor position is a small thing to write down. Two pawns somewhere on 81 squares, up to twenty walls sitting in a set of 128 possible slots, and a count of how many walls each player has left. That is it. No piece types, no promotion, no castling rights, no capture history. Hence the modest 10⁴².

The tree explodes anyway, and the reason is that walls do not move. They get placed once, permanently. Which means the order you place them in does not change where they end up.

Put a wall at A and then one at B, or B and then A, and the board in front of you is identical. Those are two different games that arrived at the same place. With twenty walls down there are up to twenty factorial orderings landing on that exact arrangement, and twenty factorial is about 2.4 × 10¹⁸.

That is the mechanism. A staggering number of distinct games funnel into a comparatively small number of distinct boards. The game tree is vast, and it is vast largely in ways a player mercifully does not have to care about.

There is a second thing going on, which is that the options stay open. In chess the board empties out as pieces come off, and a game that starts with 20 legal moves generally narrows as it goes. Quoridor opens with 131 legal moves, three pawn steps and 128 legal wall placements, and stays near that level for the first twenty turns or so while both players still hold walls. We measured how that decays in an earlier post on why Quoridor and chess are inverted problems.

And yes, Go is bigger

Go has about 10³⁶⁰ possible games and roughly 10¹⁷⁰ positions. It beats both of these games by a distance nothing else has closed, and anyone making a "most complex board game" argument has to deal with it.

But look at what Go needs to get there. A 19 by 19 grid, 361 intersections, stones that can go almost anywhere and be captured in groups. It earns its number through sheer size.

Quoridor reaches 10¹⁶² with 81 squares, two pawns and twenty walls. That is the interesting part. It is not a big game. It is a small game with an unusually nasty branching structure, and it gets within reach of things far larger than itself.

What this means when you sit down to play

Practically, it means you cannot calculate your way through Quoridor, and you can stop feeling bad about that. The tree is not searchable by you and it is not really searchable by a computer either. Our own engines hit this constantly. Depth is cheap to buy and does not help much, because the move you needed was one of the hundred wall placements that got pruned away to afford the depth.

What works instead is treating walls as a budget rather than a sequence. You get ten. They never come back. The order you spend them in mostly does not matter, which is what the 10¹⁶² figure is quietly telling you. So the only question that counts is which ten, and how much each one costs your opponent compared to what it costs you.

Ninety seconds to learn. More possible games than the square of every atom in the sky. That is a decent trade for a board that fits on a coffee table.