25,161
edits
Changes
no edit summary
=Description=
Abstract of ''Chess on a Hypercube'' <ref>[[Ed Felten]], [[Steve Otto]] ('''1988'''). ''[httphttps://portalwww.acmsemanticscholar.org/citation.cfmpaper/Chess-on-a-hypercube-Felten-Otto/78f89caaf173e52524b5f75ed3a4529e1b3fa1f5?idtab=63088 abstract Chess on a Hypercube]''. The Third Conference on Hypercube Concurrent Computers and Applications, Vol. II-Applications</ref>
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|alpha-beta]] pruned game tree, [[Iterative Deepening|iterative deepening]], [[Transposition Table|transposition]] and [[History Heuristic|history]] tables, specialized endgame evaluators, and so on. The [[Search Tree|search tree]] is decomposed onto the [https://en.wikipedia.org/wiki/Hypercube hypercube] (an [[nCUBE]]) using a [[Recursion|recursive]] version of the [[Parallel Search#PrincipalVariationSplitting|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 [[Shared Hash Table|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 [[Node Types#CUT|type 2]] or a [[Node Types#ALL|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 1987|ACM North American Computer Chess Championship]].
=Selected Games=
=Publications=
* [[Ed Felten]], [[Steve Otto]] ('''1988'''). ''[httphttps://portalwww.acmsemanticscholar.org/citation.cfmpaper/Chess-on-a-hypercube-Felten-Otto/78f89caaf173e52524b5f75ed3a4529e1b3fa1f5?idtab=63088 abstract Chess on a Hypercube]''. The Third Conference on Hypercube Concurrent Computers and Applications, Vol. II-Applications* [[Ed Felten]], [[Steve Otto]] ('''1988'''). ''[https://www.semanticscholar.org/paper/A-Highly-Parallel-Chess-Program-Felten-Otto/8883761d14be691f6b50d91346cb15af65762710 A Highly Parallel Chess Program]''. Conference on Fifth Generation Computer Systems
=External Links=
==Chess Program==
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=359 Waycool's ICGA Tournaments]
==HypercubeMisc==
* [https://en.wikipedia.org/wiki/NCUBE nCUBE from Wikipedia]
* [https://en.wikipedia.org/wiki/Hypercube Hypercube from Wikipedia]
