History of Connect 4: Milton Bradley, 1974, and the 1988 Solution

Three in a row, five in a row, and then gravity

Three men’s morris needs a board of nine points and three counters for each player. You take turns placing them, then slide them along the lines, and the first to make a row of three wins. The U.S. National Park Service, which teaches the game to visitors at Morristown, traces it to a board cut into a temple roof slab in ancient Egypt and says it was very popular in the fourteenth century. Stone boards are hard to date and their rules are harder to recover, so treat the oldest claims with care.

Other games stretch the line. Tic-tac-toe asks for three on a 3×3 grid, and careful play always ends in a tie. Go-moku asks for five on a lattice of 15×15 points. The researcher Victor Allis, who appears again later in this history, wrote that go-moku’s roots lie in China and Japan and that it spread because pencil and paper are all it needs.

Connect 4 belongs to this family and changes one thing. In the older games you may mark any empty point. Here the board stands upright, so a disc falls to the lowest empty space in its column. You have at most seven choices on a turn, and every choice also decides which space opens up next. That single rule is the source of the threats, traps and timing battles covered in the strategy chapter.

A sea story without a ship’s log

In 1992, a mail-order catalog called Past Times offered a four-in-a-row set under the name The Captain’s Mistress. The catalog said that, according to legend, Captain James Cook spent so many hours on the game during his voyages that his crew joked he had a mistress aboard. The name and the story have traveled with wooden versions of the game ever since, and they are often repeated as the origin of Connect 4.

Alan W. Smith looked into the claim for the Captain Cook Society and published what he found in its journal, Cook’s Log, in 1997. He wrote to the publishers of the catalogs that carried the game, one of them connected with the museum at Greenwich. None could offer anything to support the tale, and he filed it among the false trails in Cook’s biography.

The idea of an older shipboard game still circulates. A note on a Connect 4 set at The Strong National Museum of Play says a similar game was played on ships with wooden racks long before 1974, without naming a source. Neither the catalogs nor the museum note cites a journal, a letter or a surviving set from Cook’s time. Until someone produces one, the Captain’s Mistress is best read as a sales story from the late twentieth century.

A toy inventor’s vertical checkers game

The firm record begins in 1974. Milton Bradley Company applied to register the name Connect Four on April 26 of that year and gave February 11, 1974, as the date the name was first used in commerce. The registration describes the product as an apparatus for playing a checkers game. A 1974 set in the collection of The Strong National Museum of Play carries the same idea in its title, Connect Four Vertical Checkers Game.

The toy inventor Howard Wexler says he invented the game in 1973 and that Milton Bradley licensed it and brought it out the following year. The museum’s 1974 set was his gift and names him as inventor. Its record for a later edition lists two designers, Howard Wexler and Ned Strongin. The public record is thin on how the two men divided the work, and Wexler’s own account names only himself.

By Wexler’s telling, the company first treated the game as a variety of checkers. There was no television advertising, and the catalog placed it beside checkers sets and school supplies. He says sales began to climb in 1979. The first television commercial showed a girl beating her brother with a diagonal line he had not seen coming, and his reply, “Pretty sneaky, sis,” became a catchphrase.

One trademark, many names

Hasbro bought Milton Bradley in 1984, and the Connect Four registration now belongs to Hasbro, Inc. The name began with the number spelled out and is now usually written with the numeral, as Connect 4. Because the name is a trademark, the same game appears elsewhere under plain descriptions such as four in a row. Researchers in the 1980s wrote it as Connect-Four.

The original set left one point open. Allis’s 1988 description gives each player twenty-one discs, one set yellow and one red, and notes that no rule said which color starts. He called the players White and Black to get around it. LarkSpark plays the standard board of 7×6 and settles the question simply. Red always moves first.

Hasbro has built other ways to play on the same grid. Its current instructions for the basic set list three: the original game, Pop Out, and Pop 10, in which players remove checkers and the first to collect ten wins. Connect 4x4 doubles the grid, adds blockers and seats up to four players. Many more editions have been sold. These are the ones whose published instructions we could read.

Two solutions in one month

On October 1, 1988, James D. Allen posted a message to the Usenet group rec.games.programmer. His program had searched about 6 billion positions by brute force, and it showed that the first player can force a win. Fifteen days later Victor Allis, a student at the Vrije Universiteit in Amsterdam, announced the same result. He had reached it on his own, by a different method, in a master’s thesis titled A Knowledge-based Approach of Connect-Four.

The dates come from John Tromp, who later extended the work, and they agree with the thesis. Its last section says Allen’s message appeared a few days before the text was printed and confirmed the result. Allis later dated Allen’s finding to September 1988. Either way, the two solutions arrived within weeks of each other, and neither man knew of the other’s project.

Both found that the winning first move is the bottom space of the center column. Allis proved that any other start gives the second player at least a draw. Allen’s published table of first moves is more exact. The columns on either side of the center lead to a draw with best play, and the four outer columns lose. Only one of the seven first moves keeps the win, so the first player’s advantage is real and narrow.

A program that could explain itself

Allis named his program VICTOR and built it on nine strategic rules, each proven correct. Their names are Claimeven, Baseinverse, Vertical, Aftereven, Lowinverse, Highinverse, Baseclaim, Before and Specialbefore. Each rule shows how one player can make sure a group of four spaces is never completed by the other. If the rules together cover every group the opponent could use, the position is safe without searching a single move ahead.

The simplest is Claimeven. The second player answers each move by playing directly on top of it, and so collects the spaces on the even rows. Allis tied this to zugzwang, the chess word for having to move when you would rather pass. The first player tends to get the odd rows and the second player the even ones, which is why an odd threat suits Red and an even threat suits Yellow.

The rules alone settled small boards and every first move except the center. For the center, VICTOR added search on two Sun-4 computers. The four winning lines took about 350 hours of processor time, and the whole project used more than 1,000. Allis wrote that two expert players had expected the second player to hold at least a draw. The finished program kept about half a million positions and could win every game it started, moving within seconds.

From one winning line to every position

Allen and Allis had shown how the first player wins from the empty board. John Tromp, working at the CWI research institute in Amsterdam, set out to solve the game strongly. He computed the result of every position after eight discs, which took about 40,000 hours on the institute’s workstations. Allis was already citing the database in 1994. In February 1995 Tromp gave 67,557 of its positions to the machine learning archive at the University of California, Irvine, where students still train programs on them.

With the database, a program can find the true value of any position in seconds. Tromp also counted the positions that can arise on the standard board. The total is 4,531,985,219,092, a figure Stefan Edelkamp and Peter Kissmann had reached in 2008. Public solvers followed. Pascal Pons’s scores every column in a position by how many moves remain before the game ends. A project called WeakC4 goes the other way and packs a complete winning plan for the first player into fewer than 2,600 positions.

Tromp turned the same solver on other board sizes, and the results do not follow a simple pattern. A board of 7×4 is a draw. The standard board is a first-player win. Add a column to make 8×6, or two to make 9×6, and the second player wins. The 9×6 result was finished in November 2005 after about 2 × 10¹³ positions. In late 2015 he showed that 8×8 is a second-player win as well.

A solved game is still a game

Allis gave the word solved more than one grade, and two of them matter here. A game is weakly solved when a strategy is known that secures the best result from the starting position. It is strongly solved when the same is true from every legal position. The 1988 work was a weak solution, and Tromp’s database moved Connect 4 toward the strong kind. Tic-tac-toe is strongly solved too, which shows how little the label says about how hard a game is to play. See solved game in the glossary.

For an ordinary player the practical lesson is short. Starting in the center column is correct, and it is only the first of many exact moves. The winning plan runs deep. Allis observed that most games are decided between moves 37 and 42, while the last column fills. One slip along the way hands the advantage back, and the second player wins plenty of games.

That is true on LarkSpark as well. Orion, the strongest of the eight bots, searches ten moves ahead and does not read its moves from a solved table. You can beat it with the same ideas the proofs rest on. Hold the center, count the odd and even rows, and make your opponent run out of safe moves first. The strategy chapter shows how.

The History of Connect 4