Author: john tromp
Date: 09:54:47 12/03/04
A new version of the Fhourstones benchmark is available at http://www.cwi.nl/~tromp/c4/fhour.html Full source is provided for both Java and C versions (each under 500 lines). Fhourstones solves positions in the game of Connect 4, as played on a 7x6 board (or other sizes with a simple redefine). The benchmark runs the solver on 4 positions of increasing difficulty, the last of which is the starting position, thus solving the game. This takes about half an hour on modern PCs. The program uses 64-bit bitboards and a 10 million entry transposition table. Of the 49 bits that completely describe a connect-4 position, the 32 highest bits are stored in the table to detect all collisions (the 17 least significant bits are subsumed in the table index). The remaining 8 bits per table entry store the result (-,<,=,>,+) in 3 bits and amount of work (log of #table accesses during search) in 5 bits. The table index is computed with a prime modulus, which a smart compiler could implement with 2 multiplies if modulo is too slow. (the DEC Alpha compiler used to be very good at that). Testing for four-in-a-row is done with two shift+and operations per direction, and the 49-bit key is computed with 2 additions. The solver is currently being used to solve connect-4 on bigger board sizes. Unfortunately, avoiding collisions while storing only 32-bit locks requires a lot of memory, more than I have access to. For instance, 7x8 and 9x6 boards both require 63-bit keys, which means the table size must exceed 2^(63-32)=2G, taking 10Gb memory. If anyone has a fast 64-bit machine with that much memory, I'd appreciate your help in extending the results! That leaves the 8x7 board, with a 64-bit key, taking 20G of memory and no doubt many weeks of computation time. Current results (verification welcome!) may be found at http://www.cwi.nl/~tromp/c4/c4.html Happy benching! regards, -John
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.