Three different claims are all called solved

The first player wins Hex on a board of any size. This has been known since the 1940s, the argument takes a paragraph, and it names no opening move on any board.

Nim is also solved. Given any position of any size, three exclusive-ors give the winner and one more pass gives a winning move.

Both games are described as solved and the two statements are nothing like each other.

The three senses #

The vocabulary is standard and it is worth stating exactly.

Ultra-weakly solved. The outcome from the opening is known. Nothing else: no move, no line, no method. One bit — and a bit that may have been obtained without any of the game being examined, which is what makes the category more than a formality.

Weakly solved. A strategy is known that achieves that outcome from the opening, against every defence. This is what a person means by knowing how to win.

Strongly solved. A strategy is known from every position of the game, including ones no sensible play would reach. This is what a table of values is.

Each contains the one before it and none of them is a mere refinement: the objects are different sizes and are obtained by different means. A weak solution implies the ultra-weak one, since a strategy achieving an outcome establishes the outcome; a strong solution implies the weak one, since a table covering every position covers the ones a game from the opening reaches. Neither implication runs backwards, and the gaps between them are where nearly all the interesting cases live — a game may sit at the first level for eighty years, as Hex has, with nobody able to climb to the second on a full-size board.

The argument that names no move #

Hex is the reason the first sense exists as a category, because it has the purest example of a proof that gives nothing away.

Hex cannot end in a draw — a filled board always contains a winning chain for exactly one player, which is a topological fact and a small theorem in its own right. So one of the two players has a winning strategy. Suppose it were the second player. Then the first player could steal it: make an arbitrary first move, ignore it, and follow the second player’s winning strategy thereafter. An extra stone on the board is never a disadvantage in Hex, so this wins — and now both players have winning strategies, which is impossible.

Therefore the first player wins. The argument is complete, it holds for every board size, and it contains no information whatever about what to play. On an 11×11 board it says the first player wins and nobody knows a winning strategy.

That is a genuinely strange kind of knowledge, and it is worth registering that this subject’s usual mode is the opposite. Everything else on this site computes an answer by computing the play — which is why an outcome here always comes with the machinery to act on it.

What this site’s playable figures are #

The figures here that play back are strong solutions, and it is worth being clear that this is the strongest sense and the least impressive achievement.

Every reply in that figure came from a table covering every reachable position, not from a strategy for one opening and not from a search at the moment of clicking. A reader may play any move at all, including a terrible one, and the machine has an answer prepared — which is precisely what strong means.

The reason it is affordable is that the position is tiny. A hundred and seventeen positions is nothing. Strong solutions scale with the number of positions, so they are available exactly where the game is small, and no further — and how fast “no further” arrives is worth pricing on the same game rather than asserting.

The last two rows are the ones to read twice. Going from an eight-stone board to a nine-stone one nearly quadruples the number of positions and makes the strategy smaller, from 75 nodes to 66, because a strategy answers only the lines the loser can reach and a board with more of its stones adjacent gives the loser fewer of them. The two columns are not measuring the same thing and they do not have to move together.

The site’s rule about this is the invariant that keeps the claims honest: only games small enough to be solved completely are played back. A figure that played well without being provably optimal would be making a much weaker claim, and it would be indistinguishable from this one to a reader.

Prices, measured #

The three senses are not a taxonomy for its own sake. They cost different amounts, and the amounts can be counted.

On the 3×3 Domineering board: the ultra-weak answer is one bit. The weak answer is a six-node strategy. The strong answer is 98 positions.

On Nim with heaps of 7, 11 and 13: the ultra-weak answer is one bit. The strong answer is 480 positions. The weak answer — a strategy tree from the opening — is 56,167,022 nodes, which is larger than the strong solution by a factor of a hundred thousand.

That inversion is the useful thing here. The three senses are not ordered by cost, only by what they claim. Where the loser has many replies, the tree that answers all of them is much larger than a table storing each position once, and the “weaker” claim is the expensive one to write down.

The middle row is the one that shows the mechanism rather than the size of it. Three heaps of five have fewer distinct lines than heaps of three, four and five — 486 nodes against 598 — although the position is bigger and its table is bigger, because three identical heaps make many of the loser’s replies the same reply and a strategy tree carries one branch where there were three. Transposition is what the two columns disagree about, and it can push the weak column down as well as up.

When the inversion happens, and why #

A weak solution costing a hundred thousand times a strong one is startling enough to want a rule for, and there is one: the inversion is the recursion tree against the position graph, wearing different words.

A strong solution is a table with one entry per distinct position — it is the position graph, and a position reached by twenty different routes is stored once.

A weak solution is a strategy tree. It has a branch for every line the loser might play, so a position reached by twenty routes appears twenty times, once under each.

So the ratio between the two is exactly the ratio between routes and destinations, and it is large precisely when a game transposes heavily. Nim transposes about as much as a game can — the heaps commute, so any order of the same moves reaches the same position — and 56 million nodes over 480 positions is that redundancy counted.

Which reverses the intuition the vocabulary invites. Weak sounds like less, and it is less as a claim and can be enormously more as an object. A reader told that a game has been weakly but not strongly solved should not conclude that the weaker result was the cheaper one to obtain; on a transposing game it is the harder, and the strong solution is what somebody would produce first if they could produce either.

That also says where the inversion does not happen. The 3×3 Domineering board’s weak solution is six nodes against 98 positions, because a strategy needs only the lines the loser can actually reach and most of the board’s positions are not among them. A game with little transposition and a short winning line gives a weak solution that is genuinely small — which is the case the vocabulary was built around, and the case Nim is not.

Two families in opposite directions is a contrast rather than a law, so it is worth a third, chosen for sitting between them. Toads and Frogs is written as a strip and no two strips are ever the same position, so it looks at first like the case with no transposition at all; what it has instead is many routes to the same strip, which is the quantity that matters.

Set the three side by side and the rule states itself as a number. The ratio of the weak column to the strong one is about 117,000 on the largest Nim position, about 70 on the largest Toads and Frogs strip, and about a thirtieth on the largest Domineering board. That ordering is the ordering of how heavily each family transposes, and nothing else about the three games — not their sizes, not their branching, not whether they are partizan — predicts it.

A fourth sense, which combinatorial game theory quietly adds #

The three-way vocabulary was built for games that end in a win, a loss or a draw, and this subject routinely produces something stronger than any of the three.

A value is not a strategy and not an outcome. It is an algebraic object that says how much the position is worth, and it composes: a position known to be worth $\uparrow$ can be dropped into any sum whatever and the total follows by addition. No solution in the three-way sense does that. A weak solution of Checkers says nothing about Checkers-plus-something-else, because there is no such thing; a value of a Domineering region says everything about that region in every board it ever appears in.

So the site’s own tables are strong solutions and something the vocabulary has no word for: reusable components rather than answers. That is why the expensive search is worth paying for once, and it is the difference between solving a game and understanding it.

The distinction shows up sharply in what each kind of result survives. A strong solution of the 4×4 board is worth nothing at all on 4×5. A value of a 2×3 region is worth exactly as much inside a 40×40 board as inside a 4×5 one.

That is the arithmetic this site draws most often: several independent components, each with a value found once, and a total that is their sum. Each value was expensive to compute and free thereafter, and the addition at the end costs nothing at all — which is the sense in which a value outlives the position it was computed for, and the sense in which none of the three senses of solved is an object of that kind.

What published solutions actually are #

Set some real claims beside the vocabulary and the value of the distinction is immediate.

Nim is strongly solved, by a formula, at every size. This is the ideal case and it is rare: the solution is a closed form, it is instant, and it needs no storage at all.

Checkers was announced as weakly solved in 2007 by Schaeffer’s group, after eighteen years of computation: the game is a draw with best play, and a strategy from the opening was established. It is not strongly solved — most positions in the game have never been evaluated, and the published result covers what perfect play can reach.

Connect Four was weakly solved twice independently in 1988, by Allen and by Allis, and small enough versions of it have since been done strongly.

Hex is ultra-weakly solved for every board size and weakly solved only for small ones, by computation, board size by board size.

Domineering has published results for a good many board shapes, obtained by search, not by formula. Every one of them is a claim about a particular board, which is exactly what a hardness result leaves room for.

The pattern is that weak is what large-scale computation produces, strong is what small games permit, and ultra-weak is what an argument occasionally hands over for free.

Where this site stops #

The honest column has an entry, and it belongs in this essay rather than in a footnote.

Sprouts from three spots is not solved by anything on this site. One and two spots are settled here completely; the search from three spots passes a million positions without closing, and the honest report of that is a stopping point rather than a result. The published answer exists — the result is known, and has been for decades — and quoting it beside a figure that could not reach it would be exactly the kind of borrowed authority the site refuses. Closing the gap needs canonicalisation of planar maps up to relabelling, which is a piece of work rather than a parameter change.

So the site’s own solution status, stated the way this essay asks other people to state theirs: Nim, strongly, by formula, at any size. Cutcake and green Hackenbush, strongly, by formula. Domineering, Clobber, Toads and Frogs, strongly, by search, on the boards drawn. Sprouts, on one and two spots only. That list is short, and every entry on it says how.

Why the weakest claim is sometimes the only one available #

There is a reason ultra-weak solutions exist as a category rather than as a curiosity, and Hex is not the only example.

Some arguments establish who wins by showing that the alternative is impossible, and impossibility arguments hand over nothing constructive by their nature. Strategy stealing is one shape: assume the second player wins, derive a contradiction. A parity or symmetry argument is another — a player who can mirror everything the opponent does never runs out of moves, which settles a great many symmetric positions without naming a first move either.

The subject here has its own version, and it is the outcome classes themselves. Knowing that a position is a second-player win is an ultra-weak solution of it, and this site produces them in quantity as a by-product of computing values. The difference is that here the argument is the computation, so the strategy comes with it and the weakest claim is never the only one on offer.

Which is worth stating as the general point. Ultra-weak results come from arguments that do not compute; the value-based apparatus of this site computes, so it never stops at ultra-weak. The two ways of knowing a game are genuinely different in kind, and the cheap one produces the fact while the expensive one produces the method.

What the distinction cannot settle #

Two limits, and both come from the word known.

A solution has to be checkable to be worth anything. Checkers’ weak solution is not a document a person can read; it is a body of computation with a proof of correctness about the method. Whether that counts as knowledge is a real question and not a rhetorical one — the answer accepted in practice is that the method is verifiable even where the object is not, which is the same standard applied to this site’s own tables.

Strong solutions rot in a particular way. A table is only as good as the program that built it, and a table cannot be spot-checked by inspection. This site’s answer is to check the machinery before anything is published — every reply in every playable figure is required to leave the opponent in a lost position, exhaustively, and a failure stops the figure being drawn rather than reporting a warning. The alternative, an unaudited table that looks fine, is the way a strong solution silently becomes a strong claim.

The three families this site settles completely divide along exactly that line. Nim and green Hackenbush are solved in the strongest sense by theorems, at every size, and cost nothing to store because there is nothing to store. Domineering is solved board by board, by search, and the number of positions on a board is what decides how far the searching can go — which is why its entries are a list of boards rather than a statement about the game.

Reading a claim in the wild #

The practical use of all this is a short checklist for anybody meeting the sentence this game has been solved.

Which sense? If the announcement gives an outcome and no method, it is ultra-weak. If it gives play from the opening, it is weak. If it answers from anywhere, it is strong. Announcements very often do not say, and the shape of the computation usually gives it away: eighteen years of cluster time produces weak solutions, and a formula produces strong ones.

At what size? Board games are families, and a solution is usually of one member. “Domineering is solved” is not a sentence anybody should accept without dimensions attached, since the family as a whole is PSPACE-complete and will not be solved in general by anybody.

By formula or by table? A formula extends to sizes nobody has run; a table does not extend at all. This is the difference between Nim being settled at any size and a board being settled once.

Checkable how? A closed form is checkable by argument. A table is checkable only by re-deriving it or by auditing the machinery that built it, which is a weaker but not worthless standard.

Four questions, and the announcement that answers all four is rare enough that noticing which one it dodges is usually the fastest way to understand what was actually achieved.

A game solved in one sense and not the other #

Hex is the sharpest instance of the distinction on this site: it is ultra-weakly solved at every board size by a four-line argument, and weakly solved at almost no size at all.

Who drew the distinction #

The three-way vocabulary is Allis’s, from his 1994 thesis on searching for solutions in games, and it was introduced because the field needed to compare announcements that were not comparable. It has been standard ever since, and the discipline it imposes is entirely in the requirement to say which one is meant.

The strategy-stealing argument for Hex is older and is usually credited to Nash, around 1949, though John’s and Hein’s names attach to the game itself. It remains the standard example of the first category because it is so total: an argument that settles every board size, gives nothing, and cannot be improved into a strategy by any known route.

There is one more reason the vocabulary caught on, and it is sociological rather than mathematical. Announcements of solved games are news, and news compresses. A result that is careful in its own paper — weakly solved, drawn with best play, given the opening book below — becomes checkers is solved by the time it has been through a headline, and the compression loses exactly the information a reader would need to know what was proved. Having three words rather than one at least makes the loss visible to anybody who looks for them.

Combinatorial game theory sits at the other end. Its ambition is to compute values, which is a strong solution by construction — and the cost of that ambition is the whole of this field. The next rung is about what happens when the exact answer is out of reach and the theory still has something to offer: a bound rather than an answer, proved rather than hoped for, and measured over 440 lines of play.