25,161
edits
Changes
Created page with "'''Home * Engines * Waycool''' FILE:4-generalized-5-cube.svg|border|right|thumb| [https://en.wikipedia.org/wiki/Complex_polytope#Quasiregular_polyhedra P-..."
'''[[Main Page|Home]] * [[Engines]] * Waycool'''
[[FILE:4-generalized-5-cube.svg|border|right|thumb| [https://en.wikipedia.org/wiki/Complex_polytope#Quasiregular_polyhedra P-generalized] [https://en.wikipedia.org/wiki/5-cube 5-cube] <ref>[https://en.wikipedia.org/wiki/Complex_polytope Complex polytope] p-generalized [https://en.wikipedia.org/wiki/5-cube 5-cube] of 1024 nodes, [https://commons.wikimedia.org/wiki/File:4-generalized-5-cube.svg Image] by [https://commons.wikimedia.org/wiki/User:Tomruen Tomruen], September 19, 2016, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''Waycool''',<br/>
a massive [[Parallel Search|parallel]] chess program from [https://en.wikipedia.org/wiki/California_Institute_of_Technology California Institute of Technology], [https://en.wikipedia.org/wiki/Pasadena,_California Pasadena, California], running on [[nCUBE|nCUBE/10]] concurrent computer with [https://en.wikipedia.org/wiki/Hypercube 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 Championship|ACM North American Computer Chess Championships]], the [[ACM 1986]], [[ACM 1987]] and [[ACM 1988]], as well the [[WCCC 1989]] in [https://en.wikipedia.org/wiki/Edmonton Edmonton], [https://en.wikipedia.org/wiki/Alberta Alberta], [https://en.wikipedia.org/wiki/Canada Canada] <ref>[https://www.game-ai-forum.org/icga-tournaments/program.php?id=359 Waycool's ICGA Tournaments]</ref> <ref>[http://www.computerhistory.org/chess/full_record.php?iid=doc-434fea055cbb3 King Moves - Welcome to the 1989 AGT World Computer Chess Championship.] Edmonton, Alberta, Canada, Courtesy of [[Peter Jennings]] from [[The Computer History Museum]], [http://archive.computerhistory.org/projects/chess/related_materials/text/3-1%20and%203-2%20and%203-3%20and%204-3.1989_WCCC/1989%20WCCC.062302028.sm.pdf pdf]</ref> .
=Description=
Abstract of ''Chess on a Hypercube'' <ref>[[Ed Felten]], [[Steve Otto]] ('''1988'''). ''[http://portal.acm.org/citation.cfm?id=63088 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=
[[WCCC 1989]], round 1, [[Waycool]] - [[Mephisto|Mephisto X]] <ref>[https://www.game-ai-forum.org/icga-tournaments/round.php?tournament=14&round=1&id=5 Edmonton 1989 - Chess - Round 1 - Game 5 (ICGA Tournaments)]</ref>
<pre>
[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
</pre>
=Publications=
* [[Ed Felten]], [[Steve Otto]] ('''1988'''). ''[http://portal.acm.org/citation.cfm?id=63088 Chess on a Hypercube]''. The Third Conference on Hypercube Concurrent Computers and Applications, Vol. II-Applications
=External Links=
==Chess Program==
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=359 Waycool's ICGA Tournaments]
==Hypercube==
* [https://en.wikipedia.org/wiki/NCUBE nCUBE from Wikipedia]
* [https://en.wikipedia.org/wiki/Hypercube Hypercube from Wikipedia]
* [https://en.wikipedia.org/wiki/Cool_%28aesthetic%29 Cool (aesthetic) from Wikipedia]
* [https://en.wikipedia.org/wiki/Jesus_Was_Way_Cool Jesus Was Way Cool from Wikipedia]
=References=
<references />
'''[[Engines|Up one level]]'''
[[FILE:4-generalized-5-cube.svg|border|right|thumb| [https://en.wikipedia.org/wiki/Complex_polytope#Quasiregular_polyhedra P-generalized] [https://en.wikipedia.org/wiki/5-cube 5-cube] <ref>[https://en.wikipedia.org/wiki/Complex_polytope Complex polytope] p-generalized [https://en.wikipedia.org/wiki/5-cube 5-cube] of 1024 nodes, [https://commons.wikimedia.org/wiki/File:4-generalized-5-cube.svg Image] by [https://commons.wikimedia.org/wiki/User:Tomruen Tomruen], September 19, 2016, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''Waycool''',<br/>
a massive [[Parallel Search|parallel]] chess program from [https://en.wikipedia.org/wiki/California_Institute_of_Technology California Institute of Technology], [https://en.wikipedia.org/wiki/Pasadena,_California Pasadena, California], running on [[nCUBE|nCUBE/10]] concurrent computer with [https://en.wikipedia.org/wiki/Hypercube 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 Championship|ACM North American Computer Chess Championships]], the [[ACM 1986]], [[ACM 1987]] and [[ACM 1988]], as well the [[WCCC 1989]] in [https://en.wikipedia.org/wiki/Edmonton Edmonton], [https://en.wikipedia.org/wiki/Alberta Alberta], [https://en.wikipedia.org/wiki/Canada Canada] <ref>[https://www.game-ai-forum.org/icga-tournaments/program.php?id=359 Waycool's ICGA Tournaments]</ref> <ref>[http://www.computerhistory.org/chess/full_record.php?iid=doc-434fea055cbb3 King Moves - Welcome to the 1989 AGT World Computer Chess Championship.] Edmonton, Alberta, Canada, Courtesy of [[Peter Jennings]] from [[The Computer History Museum]], [http://archive.computerhistory.org/projects/chess/related_materials/text/3-1%20and%203-2%20and%203-3%20and%204-3.1989_WCCC/1989%20WCCC.062302028.sm.pdf pdf]</ref> .
=Description=
Abstract of ''Chess on a Hypercube'' <ref>[[Ed Felten]], [[Steve Otto]] ('''1988'''). ''[http://portal.acm.org/citation.cfm?id=63088 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=
[[WCCC 1989]], round 1, [[Waycool]] - [[Mephisto|Mephisto X]] <ref>[https://www.game-ai-forum.org/icga-tournaments/round.php?tournament=14&round=1&id=5 Edmonton 1989 - Chess - Round 1 - Game 5 (ICGA Tournaments)]</ref>
<pre>
[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
</pre>
=Publications=
* [[Ed Felten]], [[Steve Otto]] ('''1988'''). ''[http://portal.acm.org/citation.cfm?id=63088 Chess on a Hypercube]''. The Third Conference on Hypercube Concurrent Computers and Applications, Vol. II-Applications
=External Links=
==Chess Program==
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=359 Waycool's ICGA Tournaments]
==Hypercube==
* [https://en.wikipedia.org/wiki/NCUBE nCUBE from Wikipedia]
* [https://en.wikipedia.org/wiki/Hypercube Hypercube from Wikipedia]
* [https://en.wikipedia.org/wiki/Cool_%28aesthetic%29 Cool (aesthetic) from Wikipedia]
* [https://en.wikipedia.org/wiki/Jesus_Was_Way_Cool Jesus Was Way Cool from Wikipedia]
=References=
<references />
'''[[Engines|Up one level]]'''
