CaltechAUTHORS
  A Caltech Library Service

Chess on a hypercube

Felton, Edward W. and Otto, Steve W. (1988) Chess on a hypercube. In: C3P Proceedings of the third conference on Hypercube concurrent computers and applications. Vol.2. ACM , New York, NY, pp. 1329-1341. ISBN 0-89791-278-0. https://resolver.caltech.edu/CaltechAUTHORS:20161018-173411654

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161018-173411654

Abstract

We report our progress on computer chess last described at the Second Conference on Hypercubes. 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, specialized endgame evaluators, and so on. The search tree is decomposed onto the hypercube (an NCUBE) using a recursive version of the principal-variation-splitting 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 or 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 program 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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/63047.63088DOIPaper
http://dl.acm.org/citation.cfm?doid=63047.63088PublisherPaper
Additional Information:©1988 ACM. Eric Umland played a key role in the early stages of this effort. We would like to thank Rod Morison, Ken Barish and Rob Fätland for helping with various phases of this project. We thank Geoffrey Fox for his interest, his encouragement and for signing OUI checks. This work is partially funded by the Department of Energy under grant number DE-FGOS-85ER25009, the Program Manager of the Joint Tactical Fusion Office, and the ESD Division of the SAF, as well as grants from IBM and SANDIA.
Funders:
Funding AgencyGrant Number
Department of Energy (DOE)DE-FG03-85ER25009
Joint Tactical Fusion OfficeUNSPECIFIED
SAFUNSPECIFIED
IBMUNSPECIFIED
Sandia National LaboratoriesUNSPECIFIED
Record Number:CaltechAUTHORS:20161018-173411654
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20161018-173411654
Official Citation:E. W. Felten and S. W. Otto. 1989. Chess on a hypercube. In Proceedings of the third conference on Hypercube concurrent computers and applications - Volume 2 (C3P), Geoffrey Fox (Ed.), Vol. 2. ACM, New York, NY, USA, 1329-1341. DOI=http://dx.doi.org/10.1145/63047.63088
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71250
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:19 Oct 2016 16:19
Last Modified:03 Oct 2019 16:05

Repository Staff Only: item control page