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. A subset of this database, namely the 67557 unfinished and unforced positions, is available as a dataset for machine learning experiments. 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.

If you see no PLAY! button right below this line, then your browser has Java absent or disabled; I suggest you try this Javascript based solver instead, which also sports a more conventional interface.

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. Dominikus Herzberg offers this detailed explanation for the benefit of his students.

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. In late 2015 I finished solving 8x8 to a 2nd player win. The necessary code, accompanied by an opening book, is available at github.com/tromp/fhourstones88. One curious observation is that in the 6xh games, the winning starting moves are NEVER in the central columns.

Number of connect-4 positions

Useful connect-4 links