Computer Chess Club Archives


Search

Terms

Messages

Subject: Fhourstones benchmark -- solving Connect-4

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.