Solved Games: Tic-Tac-Toe, Connect Four, Checkers and Why Not Chess

By Dawid Siedlarz · · 8 min read

Play Four in a Row free →

Short answer: A game is "solved" when we know the result with perfect play from both sides. Tic-tac-toe is a draw, Connect Four is a win for the first player (if they start in the middle column, proved in 1988), checkers is a draw (proved in 2007 after 18 years of computing), and Othello is a draw (2023). Chess and Go are not solved and may never be, because they have far more positions than any computer could ever examine.

The maths of classic games, part 1 of 4
  1. Solved games: tic-tac-toe, Connect Four, checkers (you are here)
  2. Sudoku by the numbers
  3. The maths of shuffling
  4. Solitaire odds: how many deals can be won?

Every game of pure skill, with no dice and no hidden cards, has a definite answer. If both players always make the best possible move, the game must end in a win for the first player, a win for the second, or a draw, and that result is fixed before the first move is made. Mathematicians proved this for chess-like games in the early twentieth century. The hard part is finding out which of the three it is. That is what "solving" a game means, and it has turned out to be one of the great challenges of computer science.

Three ways to solve a game

The Dutch computer scientist Victor Allis, who solved Connect Four himself, described three levels in his 1994 thesis:

  1. Ultra-weakly solved: we know who wins with perfect play, but not how. Hex, a board game where two players race to connect opposite sides, is the classic example: a short mathematical argument shows the first player must win, without telling you what to play.
  2. Weakly solved: we know a strategy that guarantees the result from the starting position. Checkers and Othello are solved this way.
  3. Strongly solved: we know the best move from every possible position, even after mistakes. Tic-tac-toe and Connect Four are solved this strongly.

The first solved game: Nim

The oldest complete solution belongs to Nim, the matchstick game that the Nimrod computer played at the Festival of Britain in 1951 (see the first video games). In 1901 the mathematician Charles Bouton showed how to win it with arithmetic: write the size of each pile in binary, combine them with a rule now called the "nim-sum", and always move so that the nim-sum becomes zero. Whoever can do that wins. This is why a 1951 computer could beat almost every visitor: it was simply following Bouton's formula.

Tic-tac-toe: a draw

Tic-tac-toe is small enough to check by hand. Counting every possible game, move by move, until someone wins or the board is full gives exactly 255,168 games. Of those, 131,184 are won by the first player, 77,904 by the second and 46,080 end in a draw. Those numbers make the first move look like a big advantage, but they count every game, including terrible ones. With perfect play from both sides, every game is a draw. Our Tic-Tac-Toe is for two people, so whether the draw happens depends on you; the guide how to win (or never lose) shows the few rules that make you unbeatable.

Connect Four: the first player wins

A blue Connect Four stand with red and yellow discs in a seven-column, six-row grid
Connect Four's standard board: 7 columns and 6 rows. With perfect play, the player who starts in the middle column wins.Photo: Popperipopp, CC BY 3.0, via Wikimedia Commons

Connect Four was solved twice in October 1988, a few weeks apart, by two people working independently: the American programmer James Dow Allen and Victor Allis in the Netherlands. Their result: on the standard 7 × 6 board, the first player wins, but only by dropping the first disc in the middle column. Start in one of the two columns next to it and the second player can force a draw; start further out and the second player can win.

Later, computer scientist John Tromp counted the positions that can occur on the board: 4,531,985,219,092, about four and a half trillion. That sounds like a lot, but it is small enough for modern computers to store the best move for every one of them, so today Connect Four is strongly solved.

Our Four in a Row uses the same 7 × 6 board, but the computer is not a perfect player. On Easy it takes a winning move or blocks yours and otherwise plays at random; on Medium it looks two moves ahead and on Hard four. That is why you can beat it, and why the middle column is the strongest place to start against it too. The Connect 4 strategy guide explains how to set up threats it cannot see.

Checkers: a draw, after 18 years

Black-and-white photograph of Marion Tinsley, wearing glasses, resting his chin on his hands behind a checkerboard
Marion Tinsley in 1988. He held the world checkers title for most of four decades and was almost unbeatable.Photo: Mark T. Foley, State Archives of Florida, public domain, via Wikimedia Commons

Checkers was a much bigger task. The 8 × 8 game has about 500 billion billion (5 × 1020) possible positions. In 1989 Jonathan Schaeffer and his team at the University of Alberta in Canada started work on a program called Chinook, first to play the game, then to solve it.

Chinook's great opponent was Marion Tinsley, a mathematics professor from Florida, often called the greatest checkers player who ever lived: over four decades he lost only a handful of serious games. In 1992 he beat Chinook in a world championship match in London, 4 wins to 2, with 33 draws. In a rematch in 1994, after six drawn games, Tinsley withdrew because of illness, and Chinook was awarded the title. He died the following year.

Schaeffer's team kept computing. They built a database of every position with ten or fewer pieces on the board, around 39 trillion of them, and searched forward from the opening until every line reached that database. In 2007 they published the answer in the journal Science: with perfect play, checkers is a draw. Chinook can no longer lose a game.

Our Checkers uses the standard rules the solution was computed for: 8 × 8 board, compulsory captures and multi-jumps that must be finished. The computer looks 2 half-moves ahead on Easy, 4 on Medium and 8 on Hard, so it plays well but nowhere near Chinook. Our guide how to play checkers covers the rules and the first strategies to learn.

Othello: a draw (2023)

A green Othello board with black and white discs, some showing their white side
Othello, also sold as Reversi. In 2023 a computer search showed that perfect play from both sides ends in a draw.Photo: Paul_012, CC BY-SA 3.0, via Wikimedia Commons

Othello, the game of flipping black and white discs, was one of the last popular board games to fall. In 2023 the Japanese researcher Hiroki Takizawa published a computation showing that, on the standard 8 × 8 board, perfect play leads to a draw. Strong Othello programs had been beating the best human players since the late 1990s; solving the game took another quarter of a century.

Chess and Go: too big to solve

A tall black IBM Deep Blue computer cabinet on display in a museum
One of the two racks of IBM's Deep Blue, now at the Computer History Museum. Beating the world champion in 1997 was not the same as solving chess.Photo: Anton Chiang from Cupertino, CA, USA, CC BY 2.0, via Wikimedia Commons

In 1950 Claude Shannon, the founder of information theory, estimated that chess has around 10120 possible games, a number now called the Shannon number. The number of legal positions is smaller, about 1044, but still far beyond anything that could be stored: there are thought to be around 1080 atoms in the observable universe, yet even 1044 positions would need more memory than all the computers on Earth have.

What computers have solved are chess endings. Every position with seven pieces or fewer on the board, including the kings, has been worked out, and the tables show surprising results, such as wins that take more than 500 moves. When IBM's Deep Blue beat world champion Garry Kasparov in 1997, it was playing very well, not perfectly. Nobody knows whether chess is a win for White or a draw, although most experts expect a draw.

Black and white Go stones on a wooden board, in close-up
Go stones on a wooden board. The full 19 × 19 board has more legal positions than there are atoms in the observable universe.Photo: Dietmar Rabich, CC BY-SA 4.0, via Wikimedia Commons

Go is even bigger. In 2016 John Tromp and Gunnar Farnebäck calculated the number of legal positions on the 19 × 19 board: about 2 × 10170. The same year, DeepMind's AlphaGo beat the top professional Lee Sedol 4 games to 1 by learning good moves rather than searching all of them. Like Deep Blue, it is a superb player, not a solution.

What this means when you play

  1. In a solved game, mistakes decide the result. If perfect play is a draw, as in tic-tac-toe and checkers, a win always comes from the opponent's error. Your job is to avoid your own and set traps for theirs.
  2. The first move matters, but only if it is the right one. In Connect Four, starting in the middle column is worth the whole game; starting on the edge throws the advantage away.
  3. Computers you play against are not perfect. Game opponents look a few moves ahead so they can be beaten and are fun to play. Find the horizon they cannot see past and plan beyond it.
  4. Unsolved does not mean random. Chess and Go are still pure skill; we simply do not know the final answer.

Did you know?

  • Allis's Connect Four program was called VICTOR, and his solution was later checked by others with completely different methods.
  • International draughts, played on a 10 × 10 board with more pieces, is not solved: the bigger board multiplies the number of positions far beyond what Chinook had to handle.
  • Tic-tac-toe has only 765 essentially different positions once you treat rotations and reflections of the board as the same.

Next: Part 2: Sudoku by the numbers, from 6.67 sextillion grids to the 17-clue limit.