Only 15 days later, Victor Allis announced his independently discovered solution, described in his thesis.
Inspired by these results, I set out to strongly solve the game by compiling a database of all 8-ply positions with their theoretical result. This took about 40,000 hours of computation on the Sun and SGI workstations at the CWI. The value of all 1+7+49+343+2401=2801 up to 4-ply positions turned out to make a nice illustration for my own thesis cover. With the help of this database, any position in the game can be evaluated in a matter of seconds.
This applet plays a perfect game of connect-4 with the help of the 8-ply database (read from a 12Kbyte compressed file). The applet understands the keys b, f, m, 1-7 and q for back, forward, move, play, and quit. The right mouse button takes you back or forward to when a certain stone was played.
Solving connect-4 positions also makes a decent benchmark aptly named Fhourstones as a pun on the Dhrystone benchmark. The included source is a useful guide to writing an exhaustive alpha-beta search program with a transposition table and dynamic move ordering.
This somewhat improved board logic code shows how to best represent connect-4 bitboards, test for a win with 8 shifts/ands, and encode a position in 49 bits.
Based on that code and a smarter transposition table replacement strategy, my solver is now busy compiling results on different board sizes: