It might seem odd to describe a game like Draughts (US: Checkers) as being solved, but mathematically and scientifically it makes perfect sense.

A screenshot showing the Thinking Machine 4 chess engine deciding on a move.

A game is described as solved if it is possible for a player with knowledge of the solution to play a perfect game – to win (or at least draw) every time, no matter what moves their opponent makes. Theorists describe a game as being solved in two ways: a weak solution provides a fail-safe method from the game’s standard starting positions (e.g. in chess with all pieces on their “home” squares) and a strong solution provides a fail-safe method given any starting point.

The largest game solved so far is Draughts. It was weakly solved in April 2007 by a team led by Jonathan Schaeffer*, and their solution was implemented in a computer Draughts program called Chinook. It is mathematically impossible to play Chinook at Draughts and win – the only possible options are to lose or draw (if you don’t believe me, you can play against Chinook online).

Not all solved games result in a draw. In Connect Four the first player can force a win, whereas the second player will always win if playing Sim/Hexi or Chopsticks.

There are many important games that remain unsolved. Chess is only partially solved (for three to six piece endgames) and Go, perhaps one of the most computationally complex games, is only solved for board sizes up to five-by-five (standard games take place on a nineteen-by-nineteen board). It is estimated that with current technology it is impossible to solve either of these games.

This post was inspired by the excellent Relatively Prime podcast’s episode about Chinook.

* Jonathan Schaeffer et al, “Checkers is Solved,” Science 317 (2007): 1518-1522. DOI: 10.1126/science.1144079.