Solved in 2007: Checkers, and the Champion Who Lost Seven Games in 45 Years

We have been working up a ladder. Tic-tac-toe collapses to 765 essentially different positions, few enough to fit in a notebook. Connect Four has four and a half trillion, which needed a computer but only a 1988 one. Checkers has roughly 500 billion billion — 5 followed by twenty zeros — and it took eighteen years and a small army of machines to finish it off.

The result, announced in 2007 by Jonathan Schaeffer and his team at the University of Alberta, is the quiet one: with perfect play from both sides, checkers is a draw. Neither player has an advantage. The first move is worth nothing. Every game you have ever won or lost was decided by a mistake.

It is worth being precise about what was proved, because the word “solved” covers two quite different achievements. Checkers is weakly solved: the result of the opening position under perfect play is known, and a line of play exists that guarantees at least a draw from there. It is not strongly solved — nobody has computed the correct result for every position the board can hold. That distinction is why a checkers program can still be surprised by a bizarre position you would never reach by playing sensibly, and why the proof was possible at all.

The method was to attack the game from both ends and meet in the middle. Working backwards, the team built endgame databases: every position with ten or fewer pieces on the board, solved exhaustively and stored — some 39 trillion of them, compressed hard enough to be usable. Working forwards, a search explored the opening moves until it reached positions the database already knew the answer to. When the two halves touched, the proof closed. Chinook, the program that did it, ran on anything from a handful of workstations to dozens of machines over nearly two decades of on-and-off computation.

But the reason anyone outside computing knows this story is a mathematics professor from Florida named Marion Tinsley, who is the strongest evidence we have that a human being can be nearly perfect at something.

Tinsley was world champion, on and off, from 1955 until his death in 1995, and in roughly forty-five years of competitive play he lost something on the order of seven games. Not seven matches — seven games, in a career of thousands. He was not merely the best checkers player alive. By most accounts he was so far ahead of everyone else that the usual ranking machinery stopped being meaningful.

Part of that is the game itself, and part of it is him. Checkers between two strong players is mostly drawn, so a career without losses is more achievable than it would be in a decisive game. But being hard to beat is not the same as being unbeatable, and the players trying to beat Tinsley were the best in the world and generally failing.

When Chinook came for the title in 1990, the checkers federation initially would not let a computer compete for the world championship, so a special match was arranged. Tinsley beat it. In the 1992 rematch in London, over forty games, Tinsley won four, Chinook won two, and the rest were drawn — those two remain among the small handful of losses in his life. He had, by then, been beaten more often by a computer than by any person in decades.

The 1994 rematch is where the story turns. Six games were played, all drawn, and then Tinsley withdrew on medical advice. He had been diagnosed with pancreatic cancer. He died the following year, and Chinook was awarded the title by default — a result Schaeffer has been notably unwilling to celebrate, because the match was never finished and everybody knew it.

There is one anecdote from these years that gets retold constantly, and it is worth repeating with a note attached. In a 1990 game, Chinook made its tenth move, and Tinsley reportedly looked at the board and said, “You’re going to regret that.” The program went on to lose, and later analysis suggested the move had indeed thrown the game away, dozens of moves before the loss became visible to anything else in the room. The story is usually told with a precise number of moves attached, and those numbers vary between tellings, so treat the detail as folklore and the substance as real: he saw it, and he said so out loud, and he was right.

So what actually makes checkers hard, if the answer is a draw? The engine of the whole game is one rule: captures are compulsory. If a jump is available, you must take it, and if a jump chains into another, you must keep going. That single constraint turns the board into a machine for setting traps, because your opponent’s forced moves are as predictable as your own — and predictable is exploitable.

This is what checkers players call a shot: you deliberately give away a piece, your opponent is compelled to take it, and the resulting position hands you a multiple capture that wins two or three back. A two-for-one shot is the most common decisive idea in the game, and learning to see one coming is roughly the checkers equivalent of learning to spot a fork in tic-tac-toe. It is the same lesson at a larger scale — the move that loses is rarely the move where the pieces disappear.

The rest of the practical advice is short. Fight for the centre; pieces on the edge of the board have half the moves and half the threats. Do not break up your back row early, because those four squares are what stop your opponent from crowning a king, and a king that can move backwards is worth around three ordinary pieces. Count before you trade: an even exchange when you are a piece up is good for you, and the same trade when you are a piece down is not. And when you are ahead in material, simplify — trade pieces off and your advantage grows relative to what is left.

As with the previous two, it is only fair to say what the computer opponent here actually is. It runs a minimax search with alpha-beta pruning, four plies deep — two of its moves and two of yours. It counts material with a king worth three men, and gives an ordinary piece a small bonus for having advanced up the board, which encourages it to push for a crown. Forced captures are enforced exactly as the rules require, chains included.

That makes it a solid tactical opponent at close range and a poor strategic one. It will never miss a capture available right now, and it will happily take material you leave hanging. But four plies is not enough to see a two-for-one shot being assembled, and its fondness for kings means it can be tempted into an advance that costs it the back row. Set the trap two moves before it can see it and it walks in, which is the same weakness the Connect Four opponent has and, honestly, the same weakness most human beginners have.

Which is the argument for playing a solved game at all. Nobody sits down to checkers hoping to discover a new opening. You play it because it is the cheapest possible demonstration that a position can already be lost while it still looks fine, and because the skill it teaches — giving something up now for something bigger two moves later — transfers to nearly everything else on this site and a fair amount that is not.

Play a few games at cerdikcerdik.com/games/checkers. Try to win a piece by giving one away rather than by waiting for a blunder, and switch to pass-and-play when someone else is around, because a person will set traps a four-ply search cannot. If you want the same ideas on smaller boards, we wrote up the 1988 proof at cerdikcerdik.com/blog/connect-four-first-player-wins and the fork that decides every game of noughts and crosses at cerdikcerdik.com/blog/tic-tac-toe-solved-game.