Computer chess provides a good testbed for understanding dynamic MIMD-style computations. To investigate the programming issues, we engineered a parallel chess program called *Socrates, which running on the NCSA's 512 processor CM-5, tied for third in the 1994 ACM International Computer Chess Championship ( games). *Socrates uses the Jamboree algorithm to search game trees in parallel and uses the Cilk 1.0 language and run-time system to express and to schedule the computation. In order to obtain good performance for chess, we use several mechanisms not directly provided by Cilk, such as aborting computations and directly accessing the active message layer to implement a global transposition table distributed across the processors. We found that we can use the critical path C and the total work W to predict the performance of our chess programs. Empirically *Socrates runs in time $T \approx 0.95 C + 1.09 {W}/{P} $ on P processors. For best-ordered uniform trees of height h and degree d the average available parallelism in Jamboree search is $\Theta((d/2)^{h/2})$. *Socrates searching real chess trees under tournament time controls yields average available parallelism of over 1000.
See also related abstract by Christopher Joerg, who will be present for the Man-Machine Chess Match. Sample *Socrates games.
"We evaluate more chess positions by 12:15 AM than most programs do all day!"