Connect Four™

Hasbro and Sterling Publishing hired me to write the The Complete Book of Connect 4. I did put quite a bit of effort into this book, so if you're interested in Connect-Four, please buy it! It's finally available:
ISBN number: 1-4027-5621-6; 978-1-4027-5621-4.

Among reviews for the book, Eliten, Connect-4 champion of Sweden wrote:
"James D. Allen, if you're reading this, you have my explicit love. It's a great book!"



Errata for The Complete Book of Connect 4

I'll use this page to record errors in the book as they show up. Please e-mail me with any other errors, questions or comments. Be sure to mention the page number in the book.

There are also several mistakes regarding the "!" symbol in the diagrams. Let me offer a very big thank you to René Michorius for checking all the digrams in the book and calling these oversights to my attention.

Connect-Four (trademark of Hasbro) is a game in the Tic-Tac-Toe family; the object is to get four stones in a row horizontally, vertically or diagonally. There is a "gravity" rule: you can play only in the bottom-most unoccupied cell in a column. This means Zugzwang can arise, where you'd rather pass than play if the rules allowed it. Because of this, it isn't even a clear advantage to move first.

Many years ago I became interested in Connect-Four. It may seem like a trivial child's game, but that was part of the appeal. I noticed that ordinary people who memorized a few openings or principles could win consistently, even playing against people who were expert at harder games, like chess. As I explored the game my interest increased. I discovered puzzle positions which even a Connect-Four expert wouldn't be able to solve. Eventually I proved by computer that the first player can force a win, but paradoxically when I play against an experienced human, I almost always win moving second, while the opponent sometimes salvages a draw when I move first.

Another thing that made the game of Connect-Four appealing to a computer programmer was that its complexity was "just right." Using a brute-force search method with standard heuristics (alpha-beta, killer move, transposition cache), computer solution might take several years, but careful work on the heuristics can whittle that down to a few weeks. (Because of the exponential complexity of deep tree search, minor changes in game size or heuristics have a magnified effect on total search time.) A slightly simpler game could be solved without improved heuristics, while a slightly harder game might require centuries on a supercomputer, at least  with only the standard heuristics and "routine" improvements.

I was actually the first programmer in the world to solve Connect-Four, although Victor Allis solved it a few weeks later. He deserves the credit: while I had a peculiar  fascination with the game itself, he used it as a test bed for non-routine heuristics which he has since applied successfully to much harder games like Go-Moku. We solved Connect-Four in 1987.

Victor and I had never heard of each other until I posted news of my solution on an Internet bulletin board, and certainly didn't know we were engaged in a race! Nevertheless I am proud that I completed my solution a few weeks before Victor. The ``proof'' of that fact is very simple: I'd wasted several days of computer time looking for First Player victory in the opening D1 e1 E2 e3 E4. (This search was fruitless: First Player has already misplayed in this variation.) Victor was engaged in the same fruitless search and responded to my bulletin with ``How should First Player respond after D1 e1?''


Return to my Home Page.