John's Connect Four Playground

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:

height
11	=
10	=	=
9	=	=	+
8	=	=	-	+
7	=	=	+	=	+
6	=	=	-	+	-	-
5	=	=	=	=	+	+	+
4	=	=	-	=	-	-	-	-
	4	5	6	7	8	9	10	11	width

+ is a first player win, = a tie, and - a second player win.
New results and independent verification more than welcome! The 9x6 result just finished in Nov 2005, requiring examination of about 2E13 positions, which took some 2000 hours of computation on a 1.4Ghz Opteron 840. One curious observation is that in the 6xh games, the winning starting moves are NEVER in the central columns.

Useful connect-4 links