A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://tromp.github.io/c4/c4.html below:

John's Connect Four Playground

John's Connect Four Playground The first person to (weakly) solve the game of Connect-4 was James D. Allen, as announced in a rec.games.programmer posting on Oct 1 1988.

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 I've started a project to count the number of possible positions in standard 7x6 connect-4. So far, I've obtained the following results for smaller boards. Independent verification is more than welcome! height 8 9 13343 8424616 1104642469 7 8 4587 1417322 135385909 14171315454 6 7 1571 235781 15835683 1044334437 69173028785 4531985219092 5 6 537 38310 1706255 69763700 2818972642 112829665923 4 5 179 6000 161029 3945711 94910577 2265792710 54233186631 3 4 58 869 12031 158911 2087325 27441956 362940958 2 3 18 116 741 4688 29737 189648 1216721 1 2 5 13 35 96 267 750 2118 1 2 3 4 5 6 7 8 width Googling for the final result, 4531985219092, shows that it was already determined back in 2008 by Stefan Edelkamp and Peter Kissmann in their paper Symbolic Classification of General Two-Player Games (also see Perfect Hashing for State Spaces in BDD Representation and BDDs for Minimal Perfect Hashing: Merging Two State-Space Compression Techniques). I didn't expect independent verification so quickly! Corresponding entry in OEIS. Useful connect-4 linksExpert Play in Connect-Four Back to my home page.
john.tromp@gmail.com

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4