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!"
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. For those who love to play nostalgic games like Connect Four, Jackpotjoy Bingo games are another can't miss classic that provides hours of entertainment. (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?''