Learn › Small boards, deep games › State spaces for beginners

State spaces for beginners: counting the games inside a game

Every game you own contains more games than you think — vastly, absurdly more. Counting them is called measuring the state space, it needs no math beyond multiplication, and it changes how you see every board you'll ever play. Bring curiosity; leave the calculator, we'll do the astonishment by hand.

The idea in one glass of water

A "state" is just a snapshot: the board, frozen mid-game, exactly as it stands. The state space is every snapshot the game could ever legally produce. Think of a game as a country and each position as a town: the state space is the map of all towns, and a single game you play is one road trip through a handful of them.

Why count towns? Because the count answers real questions. How long before I've seen everything this game has? (Almost always: never — that's the point.) Could a computer check every possibility? (Depends entirely on the count — this is the solving question.) Is this small board actually shallow? (Usually not, and the count is why.) The state space is the game's honest size — not the box, not the board, the country inside it.

Counting tic-tac-toe by hand

Start with the one game small enough to actually count, because the method scales even when the numbers stop being countable.

Each of the nine squares holds one of three things: X, O, or nothing. Three choices, nine squares: multiply three by itself nine times and you get 19,683 raw arrangements. That's the ceiling — but it's dishonest, because most arrangements can't happen in a real game. A board of nine X's and no O's? Impossible; players alternate. Filter to arrangements where the counts make sense and no one has two winning lines at once, and roughly 5,478 legal positions survive. Fold together boards that are mirror images or rotations of each other — strategically identical twins — and you're down to just 765 genuinely different situations. And if you count complete games (every distinct road trip from empty board to ending), the answer is 255,168.

Three lessons hide in that little exercise. Raw counts always overshoot — legality taxes them hard. Symmetry shrinks things further. And even after all shrinking, a nine-square children's game still holds a quarter-million distinct games — your first hint of how fast these numbers grow when boards get real.

The ladder of astonishment

Now climb, one game at a time, with something human at each rung to hold onto.

Connect Four: about 4.5 trillion positions. Count one per second and you'd need over 140,000 years — humanity has existed for less time than that job takes. This is the rung computers could still conquer by brute cleverness, which is why 1988 happened.

Checkers: roughly five hundred billion billion positions (a five followed by twenty zeros). The solving computation ran, on and off, for nearly two decades — the longest sustained siege in game research — and this rung is near the practical summit of what's ever been solved.

Chess: the position count is estimated around ten to the forty-fourth — comfortably more chess positions than grains of sand on Earth, multiplied by the number of stars in our galaxy. The game tree (distinct full games) is famously estimated at ten to the hundred-twentieth: more chess games than atoms in the observable universe, squared, with room left over. Nobody solves this. Nobody needs to.

Go: the legal-position count on the full board was computed exactly — a number about 170 digits long. There is no physical comparison left; the universe ran out of things to count several rungs ago. Twenty-five centuries of play have visited a rounding error of it.

The ladder's shape is the takeaway: each rung isn't bigger — it's unrecognizably bigger, because possibility multiplies where intuition adds. Which brings us to the tool making that happen.

Positions versus journeys: the tree

One distinction upgrades your fluency immediately. The state space counts snapshots. The game tree counts journeys — every distinct sequence of moves from the opening position to every possible ending. The tree is always vastly larger, because many roads visit the same town: thousands of different move orders can produce one identical position.

Each count answers its own question. Solving cares mostly about positions (visit every town once, label it won-drawn-lost, done — the method behind every solved game). Playing cares about the tree, because you experience games as journeys, and your lookahead is a walk down its branches: if a position offers twenty sensible moves and each reply twenty more, seeing three exchanges ahead means facing sixty-four million twig-ends. Human lookahead drowns within a handful of moves in any real game — which is why mastery everywhere shifts from calculation to pattern recognition and judgment. The tree is why games stay games instead of becoming arithmetic.

What displacement does to the count

Here's the section this site can't resist, because the mathematics is the mechanism behind a game it knows well. Consider a 6×6 placement duel. Raw ceiling: each square empty, red, or blue — three to the thirty-sixth power, about 150 quadrillion arrangements, before legality trims it. Respectable. But the interesting number is the tree, and this is where the push rule earns its keep: in a quiet placement game, one move changes one square — many move orders converge to identical positions, and the tree collapses toward the state space. When every placement also shoves up to eight neighbors, near-identical positions diverge violently with each move; convergence plummets, journeys stop collapsing into each other, and the tree balloons toward its ceiling.

That's the formal version of a feeling players report: displacement games feel bigger than their boards. They are. Interaction doesn't just add depth-per-move — it multiplies futures-per-move, which is the same thing measured by a mathematician instead of a rating ladder. (The three-multiplier model in the small-boards article is this section wearing its practical clothes.)

When counting matters — and when it beautifully doesn't

The counts decide three real things. Solvability: under ~10 trillion-ish positions with friendly structure, modern computation can contemplate a siege; beyond, no. The counts are the reason tic-tac-toe fell to children, Connect Four to 1988, checkers to 2007 — and chess and Go to nobody. AI style: small-count games get perfect databases; huge-count games get judgment machines (the AlphaGo story is a state-space story at heart). And marketing honesty: when a tiny game claims "endless possibilities," the arithmetic lets you check. Usually the claim is, if anything, an undersell.

And here's when the counts don't matter: the moment play begins. A human exhausts no game whose tree exceeds a few million journeys, and every game on this shelf exceeds it by lifetimes. Past that threshold, extra zeroes are free depth you'll never touch — Go's 170 digits and a 6×6 duel's mere quadrillions are, from the chair you sit in, the same size: bottomless. The counting's real gift isn't choosing between deep games. It's the calibration of awe — knowing, with numbers, that the little board in your pocket is a country you will never finish visiting, and that this was true before you were born and will be true after.

Count one yourself: a state space at the kitchen table

Reading about counts is one thing; producing one is better, and there's a game small enough to census by hand tonight. Take the last-coin game from the zugzwang article: nine coins, remove one or two per turn, last coin loses. What's its state space?

A position is just two facts: how many coins remain (nine down to zero — ten possibilities) and whose turn it is (two). Twenty states, total. You can draw the entire country on a napkin: twenty towns, with arrows showing which towns each town can reach. Do it — it takes four minutes — and then, working backward from the end, label each town winning or losing for the player to move. You will have strongly solved a game, personally, using the exact method (backward induction over the state space) that cracked checkers; yours just needed a napkin instead of two decades. The point of the exercise isn't the little game — it's the felt understanding of what solvers do, and why the method that finishes twenty towns in four minutes needs geological time for five hundred billion billion.

Three stories the counts explain

With the scale ladder in your head, several famous moments in gaming history snap into focus as counting stories.

Why tic-tac-toe was the first computer game. One of the earliest graphical computer games ever built — in the early 1950s, on a machine the size of furniture — played perfect tic-tac-toe. Not because the pioneers lacked ambition, but because 765 essential positions fit inside the memory of a machine with less capacity than a greeting card. The state space chose the game.

Why checkers took two decades. The solving team ran computations across years of hardware generations — the count sat right at the edge of feasible, so the siege had to wait for computers to grow mid-campaign. A game's count, held against the curve of computing power, predicts its solving date to within a few years. Connect Four in 1988, checkers in 2007: the ladder, converted to a calendar.

Why Go needed intuition machines. At 170 digits, exhaustive methods aren't late — they're never coming. The AlphaGo breakthrough had to abandon counting for judgment, machines learning to evaluate positions they could never enumerate. The state space didn't just resist the old method; it forced the invention of a new kind of machine. Numbers that large bend history.

The pocket estimator: three steps for any game

Want to ballpark any game's size in your head? Step one — states: count what each location can hold (empty, or each piece type per player), raise it to the number of locations. That's the raw ceiling. Step two — the legality haircut: knock off a generous fraction — piece-count limits, unreachable setups; even keeping one position in a million leaves astronomical remainders on any real board. Step three — branching for the tree: estimate sensible moves per turn, raise to typical game length. Twenty moves a turn over forty turns dwarfs the state count instantly. Run it on anything — the app store puzzle, the new duel, the family classic — and you'll have, in thirty seconds, a defensible sense of whether you're holding a pond or an ocean. Spoiler for the road: nearly everything with real decisions and real interaction is an ocean. The ponds announce themselves by drying up in an afternoon.

Questions people ask

Are these numbers exact? Mixed: tic-tac-toe's are exact, Go's legal count was computed precisely, chess's are estimates with error bars wider than some games. For everything this article uses them for — scale, feasibility, awe — the error bars change nothing: an ocean with uncertain depth is still not a pond.

Does a bigger state space mean a better game? No — it means a bigger container. Plenty of huge games are dull and some tiny containers are dense; quality lives in the multipliers (depth, not complexity), not the raw count. The count only guarantees you'll never run out — the rest is design.

Why do people say Go has more positions than atoms in the universe? Because it's true and then some: atoms in the observable universe run about eighty digits; Go's legal positions run about 170. The comparison actually undersells by ninety orders of magnitude — the rare marketing claim that's cosmically too modest.

What's the one-sentence takeaway? The board is the object; the state space is the game — and for every board on this shelf, the game is a country larger than you'll ever map, which is precisely why it fits in a pocket and lasts a lifetime.