GridChessOptimisticPondering
[ A grid applied within an image [1] 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, a YBWC 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, then affiliated with the Paderborn University and the Paderborn Center for Parallel Computing, made contributions concerning the parallel search.
Description
given in 2007 from the ICGA tournament site [6]:
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 [7].
Selected Games
WCCC 2007, round 8, GridChess - Shredder [8]
Authors
- Kai Himstedt
- Ulf Lorenz
- Thomas Gaksch, Toga parts
- Fabien Letouzey, Fruit parts
- Robert Hyatt, Crafty parts
See also
Publications
- Kai Himstedt (2005). An Optimistic Pondering Approach for Asynchronous Distributed Games. ICGA Journal, Vol. 28, No. 2
- Kai Himstedt, Ulf Lorenz, Dietmar P. F. Möller (2008). A Twofold Distributed Game-Tree Search Approach Using Interconnected Clusters. Euro-Par 2008, Springer
- Kai Himstedt (2012). Optimistische verteilte Spielbaumsuche am Beispiel des Computerschachs. Dissertation (German)
- Kai Himstedt (2012). GridChess: Combining Optimistic Pondering with the Young Brothers Wait Concept. ICGA Journal, Vol. 35, No. 2 » Pondering, Young Brothers Wait Concept
Forum Posts
- grid chess at the wccc: supercharged toga? by ozziejoe, CCC, June 16, 2007
- Cluster Toga based on Fruit Source Code by Kai Himstedt, CCC, June 07, 2010 [9]
External Links
Chess Entity
- PhD Project of Kai Himstedt (Dipl.-Inform.)
- GridChess’ ICGA Tournaments
- The chess games of GridChess from chessgames.com
Misc
- Grid computing from Wikipedia
- Grid (graphic design) from Wikipedia
- The Grid - Figure of 8 (1992), YouTube Video
References
- ↑ Drawing simplified from a woodcut from the Divina Proportione, Luca Pacioli 1509, Venice, depicting proportions of the human face. The golden ratio does not appear in the drawing. Grid (graphic design) from Wikipedia, Wikimedia Commons
- ↑ Chrilly Donninger, Alex Kure, Ulf Lorenz (2004). Parallel Brutus: The First Distributed, FPGA Accelerated Chess Program. IPDPS’04
- ↑ David Levy (2003). The State of the Art in Man vs. “Machine” Chess. ICGA Journal, Vol. 26, No. 1
- ↑ PhD Project of Kai Himstedt (Dipl.-Inform.)
- ↑ Kai Himstedt (2012). Optimistische verteilte Spielbaumsuche am Beispiel des Computerschachs. Dissertation (German)
- ↑ GridChess’ ICGA Tournaments
- ↑ Kai Himstedt (2012). GridChess: Combining Optimistic Pondering with the Young Brothers Wait Concept. ICGA Journal, Vol. 35, No. 2
- ↑ Amsterdam 2007 - Chess - Round 8 - Game 6 (ICGA Tournaments)
- ↑ Download - Cluster Toga 1.4b5c based on Fruit 2.1 UCI