25,161
edits
Changes
Created page with "'''Home * Engines * GridChess''' FILE:Divina proportione.png|border|right|thumb| A grid applied within an image <ref>Drawing simplified from a [https://en..."
'''[[Main Page|Home]] * [[Engines]] * GridChess'''
[[FILE:Divina proportione.png|border|right|thumb| A grid applied within an image <ref>Drawing simplified from a [https://en.wikipedia.org/wiki/Woodcut woodcut] from the [https://en.wikipedia.org/wiki/Divina_proportione Divina Proportione], [https://en.wikipedia.org/wiki/Luca_Pacioli Luca Pacioli] 1509, [https://en.wikipedia.org/wiki/Venice Venice], depicting proportions of the [https://en.wikipedia.org/wiki/Face human face]. The [https://en.wikipedia.org/wiki/Golden_ratio golden ratio] does not appear in the drawing. [https://en.wikipedia.org/wiki/Grid_(graphic_design) Grid (graphic design) from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''GridChess''',<br/>
a prototypical implementation of a twofold [[Parallel Search|distributed game-tree search]] approach.
[[Young Brothers Wait Concept]] (YBWC) parallelized chess programs running on a [https://en.wikipedia.org/wiki/Computer_cluster cluster], where optimistic [[Pondering|pondering]] performs a second parallel approach on top of several clusters which can be used to achieve a further speedup.
=Cluster Toga=
''see main article [[Cluster Toga]]''.
The scheduling per cluster node is implemented based on the [https://en.wikipedia.org/wiki/Message_Passing_Interface Message Passing Interface (MPI)] by a [https://en.wikipedia.org/wiki/Cilk#Work-stealing work-stealing] mechanism to [https://en.wikipedia.org/wiki/Load_balancing_%28computing%29 balance the load] dynamically. Each worker at the intra-cluster level is represented by [[Cluster Toga]], a YBWC version of [[Toga]] by [[Thomas Gaksch]] based on [[Fruit]] by [[Fabien Letouzey]].
All processors on the same cluster node [[Shared Hash Table|share]] their [[Transposition Table|hash table]]. New hash table entries are permanently replicated between all cluster nodes in a similar way as described for [[Brutus]] <ref>[[Chrilly Donninger]], [[Alex Kure]], [[Ulf Lorenz]] ('''2004'''). ''Parallel Brutus: The First Distributed, FPGA Accelerated Chess Program''. [http://dl.acm.org/citation.cfm?id=645610&picked=prox IPDPS’04]</ref>.
<span id="OptimisticPondering"></span>
=Optimistic Pondering=
The asynchronous optimistic [[Pondering|pondering]] is applied not only during the opponent’s thinking time but also during the own thinking time, and schedules cluster nodes (workers) with consecutive [[Root|root-nodes]] along the [[Principal Variation|principal variation]] (PV), which is most often available in a stable form at early stages of the search. This is based on the same observation, [[David Levy]] proposed his ''[[PV Extensions#Multiple|Multiple Extensions]]'' algorithm to treat the often early stable part of a PV as a single [[Ply|ply]] to achieve higher [[Depth|search depths]] <ref>[[David Levy]] ('''2003'''). ''The State of the Art in Man vs. “Machine” Chess''. [[ICGA Journal#26_1|ICGA Journal, Vol. 26, No. 1]]</ref>.
If a change is detected in a PV within the first two plies, the actual searching ahead of the according worker is canceled and a new search for the current PV is started immediately.
=Ph.D. Project=
GridChess with focus on optimistic pondering was Ph.D. project of [[Kai Himstedt]] at [[University of Hamburg]] <ref>[http://www.informatik.uni-hamburg.de/TIS/index.php/de/projekte/phd-projects/79/ PhD Project of Kai Himstedt (Dipl.-Inform.)]</ref> <ref>[[Kai Himstedt]] ('''2012'''). ''[http://www.shaker.de/de/content/catalogue/index.asp?ID=8&ISBN=978-3-8440-0803-6 Optimistische verteilte Spielbaumsuche am Beispiel des Computerschachs]''. Dissertation (German)</ref>. [[Ulf Lorenz]], then affiliated with the [[Paderborn University]] and the ''Paderborn Center for Parallel Computing'', made contributions concerning the [[Parallel Search|parallel search]].
=Description=
given in 2007 from the [[ICGA]] tournament site <ref>[https://www.game-ai-forum.org/icga-tournaments/program.php?id=520 GridChess' ICGA Tournaments]</ref>:
GridChess is composed of two major components: 1) The proxy chess engine ([[Crafty]] based) performs no tree search itself but has some kind of a master role to control the optimistic pondering with distributed worker clients. As a simplified explanation of optimistic pondering here, one can imagine the worker clients forming a pondering pipeline with expected opponent moves extracting this information from the principal variations provided by the chess engines. 2) Real chess engines (controlled by distributed worker clients), Fruit/Toga based, parallelized with Young Brothers Wait Concept (YBWC). This way a combination of two parallel concepts was realized building the complete GridChess system: The parallel Fruit/Toga base engines using the YBWC may run on high performance clusters, each cluster representing a worker client for the proxy chess engine. Several such clusters are then used for an asynchronous distributed game-tree search with the optimistic pondering method.
=Tournament Play=
GridChess played the [[IPCCC 2006]], and shared third place at the [[WCCC 2007]]. The proxy chess engine component of GridChess is based on [[Crafty]] by [[Robert Hyatt]] and performs no tree search itself but has some kind of a master role to control the optimistic pondering with distributed workers. However, the participation at the [[WCCC 2008]] was restricted to the use of Cluster Toga as a "stand alone" component, because there was a licensing issue in connection with the use of some parts of Crafty <ref>[[Kai Himstedt]] ('''2012'''). ''GridChess: Combining Optimistic Pondering with the Young Brothers Wait Concept''. [[ICGA Journal#35_2|ICGA Journal, Vol. 35, No. 2]]</ref>.
=Selected Games=
[[WCCC 2007]], round 8, [[GridChess]] - [[Shredder]] <ref>[https://www.game-ai-forum.org/icga-tournaments/round.php?tournament=173&round=8&id=6 Amsterdam 2007 - Chess - Round 8 - Game 6 (ICGA Tournaments)]</ref>
<pre>
[Event "WCCC 2007"]
[Site "Amsterdam, The Netherlands"]
[Date "2007.06.16"]
[Round "8"]
[White "GridChess"]
[Black "Shredder"]
[Result "1-0"]
1.e4 c5 2.Nf3 d6 3.d4 cxd4 4.Nxd4 Nf6 5.Nc3 a6 6.Be2 e6 7.Be3 Qc7 8.Qd2 b5 9.a3 Be7 10.f4 Bb7
11.Bf3 Nbd7 12.f5 e5 13.Nb3 Rc8 14.Qf2 h5 15.O-O-O d5 16.exd5 Bxa3 17.Kb1 Bxb2 18.d6 Qxc3 19.Rd3
Qc4 20.Bxb7 Rb8 21.Kxb2 Rxb7 22.Ra1 Rb8 23.Rxa6 Rc8 24.Na5 Qe4 25.Nc6 b4 26.Ne7 Ra8 27.Rxa8+ Qxa8
28.Qe1 Qb8 29.Qa1 Qb7 30.Qa4 Ne4 31.Rb3 Nc3 32.Qa5 Nd1+ 33.Kb1 Nxe3 34.Rxe3 Qb6 35.Qa8+ Qb8 36.Qd5
Kf8 37.Nc6 Qa8 38.Qc4 Qc8 39.Re4 Nb6 40.Qxb4 Nd7 41.Rc4 Qe8 42.Ne7 g6 1-0
</pre>
=Authors=
* [[Kai Himstedt]]
* [[Ulf Lorenz]]
* [[Thomas Gaksch]], [[Toga]] parts
* [[Fabien Letouzey]], [[Fruit]] parts
* [[Robert Hyatt]], [[Crafty]] parts
=See also=
* [[Cluster Toga]]
* [[Crafty]]
* [[Fruit]]
* [[GridGinkgo]]
* [[GridProtector]]
* [[Pondering]]
* [[Toga]]
* [[Young Brothers Wait Concept]]
=Publications=
* [[Kai Himstedt]] ('''2005'''). ''[https://content.iospress.com/articles/icga-journal/icg28203 An Optimistic Pondering Approach for Asynchronous Distributed Games]''. [[ICGA Journal#28_2|ICGA Journal, Vol. 28, No. 2]]
* [[Kai Himstedt]], [[Ulf Lorenz]], [https://www.informatik.uni-hamburg.de/TIS/index.php/de/mitarbeiter/dietmar-p-f-moeller Dietmar P. F. Möller] ('''2008'''). ''[https://link.springer.com/chapter/10.1007/978-3-540-85451-7_62 A Twofold Distributed Game-Tree Search Approach Using Interconnected Clusters]''. [https://link.springer.com/book/10.1007/978-3-540-85451-7 Euro-Par 2008], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [[Kai Himstedt]] ('''2012'''). ''[http://www.shaker.de/de/content/catalogue/index.asp?ID=8&ISBN=978-3-8440-0803-6 Optimistische verteilte Spielbaumsuche am Beispiel des Computerschachs]''. Dissertation (German)
* [[Kai Himstedt]] ('''2012'''). ''[https://content.iospress.com/articles/icga-journal/icg35202 GridChess: Combining Optimistic Pondering with the Young Brothers Wait Concept]''. [[ICGA Journal#35_2|ICGA Journal, Vol. 35, No. 2]] » [[Pondering]], [[Young Brothers Wait Concept]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=14495 grid chess at the wccc: supercharged toga?] by ozziejoe, [[CCC]], June 16, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=34780 Cluster Toga based on Fruit Source Code] by [[Kai Himstedt]], [[CCC]], June 07, 2010
=External Links=
==Chess Entity==
* [http://www.informatik.uni-hamburg.de/TIS/index.php/de/projekte/phd-projects/79/ PhD Project of Kai Himstedt (Dipl.-Inform.)]
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=520 GridChess' ICGA Tournaments]
* [http://www.chessgames.com/perl/chessplayer?pid=107843 The chess games of GridChess] from [http://www.chessgames.com/index.html chessgames.com]
==Misc==
* [https://en.wikipedia.org/wiki/Grid_computing Grid computing from Wikipedia]
* [https://en.wikipedia.org/wiki/Grid_(graphic_design) Grid (graphic design) from Wikipedia]
* [https://en.wikipedia.org/wiki/The_Grid The Grid] - [https://en.wikipedia.org/wiki/Evolver_(The_Grid_album) Wake up] (1994), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=-HDLlljuVTI|alignment=left|valignment=top}}
=References=
<references />
'''[[Engines|Up one level]]'''
[[Category:Cluster]]
[[Category:Music]]
[[FILE:Divina proportione.png|border|right|thumb| A grid applied within an image <ref>Drawing simplified from a [https://en.wikipedia.org/wiki/Woodcut woodcut] from the [https://en.wikipedia.org/wiki/Divina_proportione Divina Proportione], [https://en.wikipedia.org/wiki/Luca_Pacioli Luca Pacioli] 1509, [https://en.wikipedia.org/wiki/Venice Venice], depicting proportions of the [https://en.wikipedia.org/wiki/Face human face]. The [https://en.wikipedia.org/wiki/Golden_ratio golden ratio] does not appear in the drawing. [https://en.wikipedia.org/wiki/Grid_(graphic_design) Grid (graphic design) from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''GridChess''',<br/>
a prototypical implementation of a twofold [[Parallel Search|distributed game-tree search]] approach.
[[Young Brothers Wait Concept]] (YBWC) parallelized chess programs running on a [https://en.wikipedia.org/wiki/Computer_cluster cluster], where optimistic [[Pondering|pondering]] performs a second parallel approach on top of several clusters which can be used to achieve a further speedup.
=Cluster Toga=
''see main article [[Cluster Toga]]''.
The scheduling per cluster node is implemented based on the [https://en.wikipedia.org/wiki/Message_Passing_Interface Message Passing Interface (MPI)] by a [https://en.wikipedia.org/wiki/Cilk#Work-stealing work-stealing] mechanism to [https://en.wikipedia.org/wiki/Load_balancing_%28computing%29 balance the load] dynamically. Each worker at the intra-cluster level is represented by [[Cluster Toga]], a YBWC version of [[Toga]] by [[Thomas Gaksch]] based on [[Fruit]] by [[Fabien Letouzey]].
All processors on the same cluster node [[Shared Hash Table|share]] their [[Transposition Table|hash table]]. New hash table entries are permanently replicated between all cluster nodes in a similar way as described for [[Brutus]] <ref>[[Chrilly Donninger]], [[Alex Kure]], [[Ulf Lorenz]] ('''2004'''). ''Parallel Brutus: The First Distributed, FPGA Accelerated Chess Program''. [http://dl.acm.org/citation.cfm?id=645610&picked=prox IPDPS’04]</ref>.
<span id="OptimisticPondering"></span>
=Optimistic Pondering=
The asynchronous optimistic [[Pondering|pondering]] is applied not only during the opponent’s thinking time but also during the own thinking time, and schedules cluster nodes (workers) with consecutive [[Root|root-nodes]] along the [[Principal Variation|principal variation]] (PV), which is most often available in a stable form at early stages of the search. This is based on the same observation, [[David Levy]] proposed his ''[[PV Extensions#Multiple|Multiple Extensions]]'' algorithm to treat the often early stable part of a PV as a single [[Ply|ply]] to achieve higher [[Depth|search depths]] <ref>[[David Levy]] ('''2003'''). ''The State of the Art in Man vs. “Machine” Chess''. [[ICGA Journal#26_1|ICGA Journal, Vol. 26, No. 1]]</ref>.
If a change is detected in a PV within the first two plies, the actual searching ahead of the according worker is canceled and a new search for the current PV is started immediately.
=Ph.D. Project=
GridChess with focus on optimistic pondering was Ph.D. project of [[Kai Himstedt]] at [[University of Hamburg]] <ref>[http://www.informatik.uni-hamburg.de/TIS/index.php/de/projekte/phd-projects/79/ PhD Project of Kai Himstedt (Dipl.-Inform.)]</ref> <ref>[[Kai Himstedt]] ('''2012'''). ''[http://www.shaker.de/de/content/catalogue/index.asp?ID=8&ISBN=978-3-8440-0803-6 Optimistische verteilte Spielbaumsuche am Beispiel des Computerschachs]''. Dissertation (German)</ref>. [[Ulf Lorenz]], then affiliated with the [[Paderborn University]] and the ''Paderborn Center for Parallel Computing'', made contributions concerning the [[Parallel Search|parallel search]].
=Description=
given in 2007 from the [[ICGA]] tournament site <ref>[https://www.game-ai-forum.org/icga-tournaments/program.php?id=520 GridChess' ICGA Tournaments]</ref>:
GridChess is composed of two major components: 1) The proxy chess engine ([[Crafty]] based) performs no tree search itself but has some kind of a master role to control the optimistic pondering with distributed worker clients. As a simplified explanation of optimistic pondering here, one can imagine the worker clients forming a pondering pipeline with expected opponent moves extracting this information from the principal variations provided by the chess engines. 2) Real chess engines (controlled by distributed worker clients), Fruit/Toga based, parallelized with Young Brothers Wait Concept (YBWC). This way a combination of two parallel concepts was realized building the complete GridChess system: The parallel Fruit/Toga base engines using the YBWC may run on high performance clusters, each cluster representing a worker client for the proxy chess engine. Several such clusters are then used for an asynchronous distributed game-tree search with the optimistic pondering method.
=Tournament Play=
GridChess played the [[IPCCC 2006]], and shared third place at the [[WCCC 2007]]. The proxy chess engine component of GridChess is based on [[Crafty]] by [[Robert Hyatt]] and performs no tree search itself but has some kind of a master role to control the optimistic pondering with distributed workers. However, the participation at the [[WCCC 2008]] was restricted to the use of Cluster Toga as a "stand alone" component, because there was a licensing issue in connection with the use of some parts of Crafty <ref>[[Kai Himstedt]] ('''2012'''). ''GridChess: Combining Optimistic Pondering with the Young Brothers Wait Concept''. [[ICGA Journal#35_2|ICGA Journal, Vol. 35, No. 2]]</ref>.
=Selected Games=
[[WCCC 2007]], round 8, [[GridChess]] - [[Shredder]] <ref>[https://www.game-ai-forum.org/icga-tournaments/round.php?tournament=173&round=8&id=6 Amsterdam 2007 - Chess - Round 8 - Game 6 (ICGA Tournaments)]</ref>
<pre>
[Event "WCCC 2007"]
[Site "Amsterdam, The Netherlands"]
[Date "2007.06.16"]
[Round "8"]
[White "GridChess"]
[Black "Shredder"]
[Result "1-0"]
1.e4 c5 2.Nf3 d6 3.d4 cxd4 4.Nxd4 Nf6 5.Nc3 a6 6.Be2 e6 7.Be3 Qc7 8.Qd2 b5 9.a3 Be7 10.f4 Bb7
11.Bf3 Nbd7 12.f5 e5 13.Nb3 Rc8 14.Qf2 h5 15.O-O-O d5 16.exd5 Bxa3 17.Kb1 Bxb2 18.d6 Qxc3 19.Rd3
Qc4 20.Bxb7 Rb8 21.Kxb2 Rxb7 22.Ra1 Rb8 23.Rxa6 Rc8 24.Na5 Qe4 25.Nc6 b4 26.Ne7 Ra8 27.Rxa8+ Qxa8
28.Qe1 Qb8 29.Qa1 Qb7 30.Qa4 Ne4 31.Rb3 Nc3 32.Qa5 Nd1+ 33.Kb1 Nxe3 34.Rxe3 Qb6 35.Qa8+ Qb8 36.Qd5
Kf8 37.Nc6 Qa8 38.Qc4 Qc8 39.Re4 Nb6 40.Qxb4 Nd7 41.Rc4 Qe8 42.Ne7 g6 1-0
</pre>
=Authors=
* [[Kai Himstedt]]
* [[Ulf Lorenz]]
* [[Thomas Gaksch]], [[Toga]] parts
* [[Fabien Letouzey]], [[Fruit]] parts
* [[Robert Hyatt]], [[Crafty]] parts
=See also=
* [[Cluster Toga]]
* [[Crafty]]
* [[Fruit]]
* [[GridGinkgo]]
* [[GridProtector]]
* [[Pondering]]
* [[Toga]]
* [[Young Brothers Wait Concept]]
=Publications=
* [[Kai Himstedt]] ('''2005'''). ''[https://content.iospress.com/articles/icga-journal/icg28203 An Optimistic Pondering Approach for Asynchronous Distributed Games]''. [[ICGA Journal#28_2|ICGA Journal, Vol. 28, No. 2]]
* [[Kai Himstedt]], [[Ulf Lorenz]], [https://www.informatik.uni-hamburg.de/TIS/index.php/de/mitarbeiter/dietmar-p-f-moeller Dietmar P. F. Möller] ('''2008'''). ''[https://link.springer.com/chapter/10.1007/978-3-540-85451-7_62 A Twofold Distributed Game-Tree Search Approach Using Interconnected Clusters]''. [https://link.springer.com/book/10.1007/978-3-540-85451-7 Euro-Par 2008], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [[Kai Himstedt]] ('''2012'''). ''[http://www.shaker.de/de/content/catalogue/index.asp?ID=8&ISBN=978-3-8440-0803-6 Optimistische verteilte Spielbaumsuche am Beispiel des Computerschachs]''. Dissertation (German)
* [[Kai Himstedt]] ('''2012'''). ''[https://content.iospress.com/articles/icga-journal/icg35202 GridChess: Combining Optimistic Pondering with the Young Brothers Wait Concept]''. [[ICGA Journal#35_2|ICGA Journal, Vol. 35, No. 2]] » [[Pondering]], [[Young Brothers Wait Concept]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=14495 grid chess at the wccc: supercharged toga?] by ozziejoe, [[CCC]], June 16, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=34780 Cluster Toga based on Fruit Source Code] by [[Kai Himstedt]], [[CCC]], June 07, 2010
=External Links=
==Chess Entity==
* [http://www.informatik.uni-hamburg.de/TIS/index.php/de/projekte/phd-projects/79/ PhD Project of Kai Himstedt (Dipl.-Inform.)]
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=520 GridChess' ICGA Tournaments]
* [http://www.chessgames.com/perl/chessplayer?pid=107843 The chess games of GridChess] from [http://www.chessgames.com/index.html chessgames.com]
==Misc==
* [https://en.wikipedia.org/wiki/Grid_computing Grid computing from Wikipedia]
* [https://en.wikipedia.org/wiki/Grid_(graphic_design) Grid (graphic design) from Wikipedia]
* [https://en.wikipedia.org/wiki/The_Grid The Grid] - [https://en.wikipedia.org/wiki/Evolver_(The_Grid_album) Wake up] (1994), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=-HDLlljuVTI|alignment=left|valignment=top}}
=References=
<references />
'''[[Engines|Up one level]]'''
[[Category:Cluster]]
[[Category:Music]]
