Two-player games get “solved”

Two-player games raise a question: if both sides play their best, what happens in the end? Does the player who moves first always win, or is it always a draw? When a computer has settled this completely, we say the game is “solved”. This page looks at the site’s eight two-player games and separates what is known from what is still unclear.

There are levels of “solved”. If we know a way to play from the starting position that never loses, the game is “weakly solved”. If we know the best move from every position, it is “strongly solved”. A solved game is not necessarily a dull one for people. Hardly anyone plays perfectly.

Three in a Row

Players take turns putting O and X on a 3×3 grid, and three in a row wins. With best play from both sides it is always a draw. The board is small enough that every possible game can be checked, and that is what shows it.

A similar game is said to have been played in ancient Rome (with pieces that move, so it was a different game from today’s). A story about a roof tile in ancient Egypt is also told, but the evidence is weak, so we leave it out. A three-in-a-row program written in 1952 for a Cambridge University computer is often called one of the earliest computer games.

This site’s program checked that, stopping a game as soon as it is decided, there are 5478 reachable boards, and 16 of the finished boards are draws. It also checked that the starting position is a draw with best play, and that the “strong” computer never loses, whether it moves first or second (tic-tac-toe/engine.test.ts).

Dots and Boxes

Players take turns drawing a line between two dots. Whoever draws the fourth side of a box takes that box, and then moves again. The site’s board has 3×3 = 9 boxes and 24 lines in all.

The French mathematician Édouard Lucas wrote about the game in the 19th century under the name “la pipopipette”. We only say “late 19th century” for the year. The key idea is the “chain”, a long run of connected boxes. Drawing the first line into a chain lets your opponent take box after box. So the player forced to open a chain first is often at a disadvantage.

This site’s program checked that there are 24 lines and 9 boxes, that the 12 inner lines are shared by two neighboring boxes, that taking a box keeps your turn, how chains are counted, and that at the end every box belongs to someone exactly once (dots-and-boxes/engine.test.ts).

Gravity Four

Seven columns, six rows. You drop a stone from the top and it falls to the lowest free spot. Four in a row, in any direction, wins. It became a popular product in the 1970s; we do not use its brand name here.

The game was solved in 1988: James Allen did it on October 1, and Victor Allis independently about 15 days later. On the usual 7×6 board, the player who moves first wins with correct play. This is an example of “weakly solved”: the winning way to play was found, and later work went on to examine every position.

This site’s program checked that there are exactly 69 ways to make four (none sticking out of the board or wrapping around a row), that a full column rejects a stone, and that the computer picks winning moves and blocks (gravity-four/engine.test.ts).

Hex Connections

On a board of hexagons, Red tries to join top and bottom with a chain of stones, and Blue tries to join left and right. The Dane Piet Hein presented it in a newspaper in 1942. The mathematician John Nash is also said to have come to the game around 1948. Accounts differ about who was first, so we only say that the two arrived at the same game in different places.

The big feature of Hex is that there are no draws. When the board is full, exactly one of Red and Blue is connected. This site’s program checked that exactly one color is connected on all 512 ways to fill a 3×3 board, and on 2000 random full 7×7 and 9×9 boards (hex-game/engine.test.ts).

With no draws, we can tell that the first player wins. Here is the idea. Suppose the second player had a winning plan. The first player could place one stone anywhere, then pretend to be the second player and copy that plan. (The extra stone never hurts: having an additional stone on the board cannot make things worse.) Then the first player would win too, and both sides could not win. So the winner must be the first player. This is called a “strategy-stealing argument”.

But the argument only says that a winning plan exists. It does not say how to play. Only small boards have actually been solved in full. Because moving first is so strong, there is sometimes a rule that lets the other side swap places after the first move.

Reversi

Sandwich your opponent’s stones and they turn to your color. In 1883 in England, Lewis Waterman and John Mollett each claimed to have invented it. Nobody knows who really did. In Japan, a version with a fixed starting layout became a product in the 1970s and is now the standard. We do not use its brand name here.

In 2023 a paper showed that the regular 8×8 game is a draw with best play. People had played it for about 140 years, so this was big news. It is a paper by researchers, so we say “was shown”.

This site’s program checked how stones are flipped (including several directions at once), passing when there is no move, the end when neither side can move, and how draws are decided (reversi/engine.test.ts).

Mancala

You pick up the seeds from a pit and sow them one at a time, counter-clockwise. If the last seed lands in your own big pit, you move again. If it lands in an empty pit of yours, you take the seeds from the pit opposite.

“Mancala” is not one game but a name for a whole family of sowing games. Over 800 traditional names are said to exist. Many old boards have been found, but researchers disagree about which is the oldest, so we cannot say “thousands of years old”. It is clear that the games are widely played in Africa, but where they began is not known.

This site’s program checked that the total number of seeds never changes, that you move again when the last seed lands in your own big pit, and when the opposite pit is captured (mancala/engine.test.ts). Some mancala variants have been shown to be first-player wins, but the answer changes with small rule differences, so we cannot say anything here about this site’s rules.

Five in a Row

The first player to line up five stones wins. As far as the records go, the game can be traced back to Edo-period Japan. It reached Britain in the 19th century as “Go Bang”. China has wuziqi and Korea has omok, among many relatives.

Strong players in Japan long said that moving first is an advantage. In the 1990s computers confirmed it. On a 15×15 board, under the rule where six or more in a row also wins (with no forbidden moves), the first player was shown to win. This applies only to the limited rule sets the paper studied. It does not carry over directly to “renju”, which has forbidden moves, or to other variants. In professional games, special opening rules are used to reduce the first player’s edge.

This site’s game counts six or more as a win and has no forbidden moves. Its program checked that five in a row wins horizontally, vertically and on both diagonals, that four is not enough, and that lines do not connect across the edge of the board (gomoku/engine.test.ts).

Nine Men’s Morris

Each player has nine pieces. You take turns placing them on points of the board, then slide them along the lines. Three in a straight line is a “mill”, and you remove one of your opponent’s pieces. With three pieces left, you may fly to any empty point.

The board was popular in medieval Europe and is said to be carved into seats in English church cloisters. A story that a board cut into an Egyptian temple dates to about 1400 BC also exists, but its dating has been questioned, so we leave it out.

In the 1990s Ralph Gasser solved the game and showed it is a draw with best play. Between people there will still be a winner. “Draw” means that perfect play from both sides gets a draw. Small rule differences might change the result.

This site’s program checked that the board has 24 points and 16 possible mills, that pieces in a mill are protected when other pieces can be taken, that flying is allowed with exactly three pieces (not four), and that the same position three times is a draw (nine-mens-morris/engine.test.ts).

Spot the differences

• Three in a Row: a draw with best play. It is small enough for a person to read out completely.
• Hex Connections: no draws, so the first player wins by argument alone. But a way to win is only known for small boards.
• Gravity Four and Five in a Row: on the usual boards, computers showed that the first player wins.
• Reversi and Nine Men’s Morris: a draw with best play.
• Dots and Boxes and Mancala: the answer depends on small rule differences, so we do not claim one for this site’s boards.

“Solved” is different from “you can win”. Even if you know how to force a draw in Three in a Row, you cannot win unless your opponent slips. Try the reading and out-thinking in the games.