Chess on a hypercube

Edward W. Felten, Steve W. Otto

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

We report our progress on computer chess last described at the Second Conference on Kypercubes. Our program follows the strategy of currently successful sequential chess programs: searching of an alpha-beta pruned game tree, iterative deepening, transposition and history tables, specialised endgame evaluators, and so on. The search tree is decomposed onto the hypercube (an NCUBE) using a recursive version of the principal-variationsplitting algorithm. Roughly speaking, subtrees are searched by teams of processors in a self-scheduled manner. A crucial feature of the program is the global hashtable. Hashtables are important in the sequential case, but are even more central for a parallel chess algorithm. The table not only stores knowledge but also makes the decision at each node of the chess tree whether to stay sequential OI to split up the work in parallel. In the language of Knuth and Moore, the transposition table decides whether each node of the chess tree is a type 2 or a type 3 node and acts accordingly. For this data structure the hypercube is used as a shared-memory machine. Multiple writes to the same location are resolved using a priority system which decides which entry is of more value to the program. The hashtable is implemented as "smart" shared memory. Search times for related subtrees vary widely (up to a factor of 100) so dynamic reconfiguration of processors is necessary to concentrate on such "hot spots" in the tree. A first version of the pro- gram with dynamic load balancing has recently been completed and out-performs the non-load-balancing program by a factor of three. The current speedup of the program is 101 out of a possible 256 processors. The program has played in several tournaments, facing both computers and people. Most recently it scored 2-2 in the ACM North American Computer Chess Championship.

Original languageEnglish (US)
Title of host publicationProceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988
EditorsGeoffrey Fox
PublisherAssociation for Computing Machinery, Inc
Pages1329-1341
Number of pages13
ISBN (Electronic)0897912780, 9780897912785
DOIs
StatePublished - Jan 3 1989
Externally publishedYes
Event3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988 - Pasadena, United States
Duration: Jan 19 1988Jan 20 1988

Publication series

NameProceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, C3P 1988
Volume2

Other

Other3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988
CountryUnited States
CityPasadena
Period1/19/881/20/88

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Computer Graphics and Computer-Aided Design
  • Software
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Chess on a hypercube'. Together they form a unique fingerprint.

Cite this