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!"
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.
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?''