GridChess,
a prototypical implementation of a twofold distributed game-tree search approach. Young Brothers Wait Concept (YBWC) parallelized chess programs running on a cluster, where optimistic pondering performs a second parallel approach on top of several clusters which can be used to achieve a further speedup.
The asynchronous optimistic 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-nodes along the 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 “Multiple Extensions” algorithm to treat the often early stable part of a PV as a single ply to achieve higher search depths[3]. 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.
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 [8].
Table of Contents
GridChess,
a prototypical implementation of a twofold distributed game-tree search approach. Young Brothers Wait Concept (YBWC) parallelized chess programs running on a cluster, where optimistic 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 Message Passing Interface (MPI) by a work-stealing mechanism to balance the load dynamically. Each worker at the intra-cluster level is represented by Cluster Toga [1] a YBWC parallelized version of Toga by Thomas Gaksch based on Fruit by Fabien Letouzey. All processors on the same cluster node share their hash table. New hash table entries are permanently replicated between all cluster nodes in a similar way as described for Brutus [2].
Optimistic Pondering
The asynchronous optimistic 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-nodes along the 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 “Multiple Extensions” algorithm to treat the often early stable part of a PV as a single ply to achieve higher search depths [3]. 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 [4] [5]. Ulf Lorenz, affiliated with the University of Paderborn and the Paderborn Center for Parallel Computing [6], made contributions concerning the parallel search.Description
given in 2007 from the ICGA tournament site [7]: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 [8].Selected Games
WCCC 2007, round 8, GridChess - Shredder [9]Authors
See also
Publications
Forum Posts
External Links
References
What links here?
Up one level