Waycool
Waycool,
a massive parallel chess program from California Institute of Technology, Pasadena, California, running on nCUBE/10 concurrent computer with hypercube topology, written in the 80s by Ed Felten, Steve Otto and Rod Morison, at times supported by Rob Fatland. Waycool played three ACM North American Computer Chess Championships, the ACM 1986, ACM 1987 and ACM 1988, as well the WCCC 1989 in Edmonton, Alberta, Canada [2] [3] .
Contents
Description
Abstract of Chess on a Hypercube [4]
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.
Selected Games
WCCC 1989, round 1, Waycool - Mephisto X [5]
[Event "WCCC 1989"] [Site "Edmonton, Canada"] [Date "1989.05.28"] [Round "1"] [White "Waycool"] [Black "Mephisto X"] [Result "1-0"] 1.e4 d6 2.d4 Nf6 3.Nc3 c6 4.Nf3 Bg4 5.h3 Bh5 6.Bd3 e6 7.Rg1 Be7 8.g4 Bg6 9.e5 dxe5 10.dxe5 Nd5 11.Nxd5 cxd5 12.Be2 O-O 13.c3 Nc6 14.Qb3 Na5 15.Qa4 Qb6 16.Nd4 Nc6 17.Nxc6 bxc6 18.b3 Qc5 19.Rg3 Bc2 20.Qd4 Qa5 21.Bd2 Rab8 22.c4 Qb6 23.Qxb6 axb6 24.cxd5 cxd5 25.Rc1 Be4 26.Rc7 Bd8 27.Ra7 Bh4 28.Rc3 Ra8 29.Rxa8 Rxa8 30.a4 h6 31.Be3 Rb8 32.Kf1 Bg5 33.f4 Bd8 34.Bb5 g5 35.Kf2 gxf4 36.Bxf4 Bg5 37.Be3 f6 38.exf6 Bxe3+ 39.Kxe3 Kf7 40.Rc6 Kxf6 41.Kd4 Bg6 42.Be2 Be8 43.Rd6 Bf7 44.h4 Rb7 45.Ba6 Rb8 46.Bf1 Rb7 47.Bg2 Rb8 48.Bf3 Bg8 49.Bh1 Bf7 50.Bg2 Ke7 51.Ke5 b5 52.a5 b4 53.a6 Rb5 54.Bf1 Ra5 55.Rb6 d4+ 56.Rb5 Ra1 57.Bd3 Be8 58.Rb7+ Kf8 59.Rxb4 Kg7 60.Rxd4 Ra5+ 61.Kd6 1-0
Publications
- Ed Felten, Steve Otto (1988). Chess on a Hypercube. The Third Conference on Hypercube Concurrent Computers and Applications, Vol. II-Applications
- Ed Felten, Steve Otto (1988). A Highly Parallel Chess Program. Conference on Fifth Generation Computer Systems
External Links
Chess Program
Misc
- nCUBE from Wikipedia
- Hypercube from Wikipedia
- Cool (aesthetic) from Wikipedia
- Jesus Was Way Cool from Wikipedia
References
- ↑ Complex polytope p-generalized 5-cube of 1024 nodes, Image by Tomruen, September 19, 2016, Wikimedia Commons
- ↑ Waycool's ICGA Tournaments
- ↑ King Moves - Welcome to the 1989 AGT World Computer Chess Championship. Edmonton, Alberta, Canada, Courtesy of Peter Jennings from The Computer History Museum, pdf
- ↑ Ed Felten, Steve Otto (1988). Chess on a Hypercube. The Third Conference on Hypercube Concurrent Computers and Applications, Vol. II-Applications
- ↑ Edmonton 1989 - Chess - Round 1 - Game 5 (ICGA Tournaments)