Anybody who has played tic-tac-toe has probably worked out that the game can always be drawn, provided neither player makes a mistake. Indeed, it is straightforward to create an algorithm that guarantees a win or draw regardless of the moves made by the opponent.
This is a trivial example of a game that has been “solved” – one in which the outcome is determined from the start. There are many others that have also been solved but plenty that have not.
For game theorists and computer scientists, the difficulty in solving a game generally depends on the number of possible positions. For example, the game of Connect 4 on a 6x7 grid has 4,531,985,219,092 possible positions. Computer scientists solved this in 1988 by showing that the player who goes first can always force a win.
Checkers (or Draughts) is significantly more complex, with 500 billion billion possible board positions. This ...
