The Cilkchess Parallel Chess Program
Announcements

Cilkchess competes in the

1999 World Computer Chess Championship, June 14-20



Cilkchess

Computer chess provides a good testbed for understanding dynamic multithreaded computations. The parallelism in computer chess is derived from a dynamic expansion of a highly irregular game tree, which makes computer chess difficult to express, for example, as a data-parallel program. Our chess program helps us investigate how to program this sort of dynamic MIMD-style application.

Implementing a state-of-the-art parallel chess program has had a marked influence on the design of Cilk, which is targeted as a platform delivering both high performance and ease of programming. Cilk-5 incorporates inlets and aborts, features that turned out to be indispensible for cleanly expressing the speculative parallelism of a chess program. Writing algorithms such as Jamboree search and Young Brothers Wait has become a joy with Cilk-5. Currently, we are looking further into how speculative parallelism in search algorithms can be expressed efficiently.

Cilkchess is a complete rewrite of our previous chess program, *Socrates. It is based on

  • New language features of Cilk-5,
  • The Jamboree version of MTD(f), a new, simpler, minimax search algorithm, and,
  • (most importantly) a carefully redesigned evaluation function.
The parallel search algorithm uses a form of Jamboree-search to control parallel search overhead: at each node the first successor is searched serially. If it does not cause a cutoff, the remaining successors are searched in parallel. The transposition table is stored in 32 gigabytes of shared memory. Entries are not locked. (Although this goes against common parallel programming practice, it certainly is fast and seems to work well in practice.) In the late middle game, Cilkchess typically looks more than 15 ply (half moves) ahead and performs 5-11 million make-moves per second on a 256-processor SGI Origin 2000. The evaluation function is built for speed, uses only knowledge which is known to work, few extensions, and null-move based forward pruning. In the latest version, the weights of the evaluation function are tuned using a temporal-coherence learning algorithm.

The Cilkchess team:

(with the help and support of the rest of the Cilk team).

Publications



Last updated $Date: 1999/06/09 14:41:30 $ by $Author: prokop $.
This page should be maintained by Don Dailey.