GridChess

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * GridChess

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]:

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 [7].

Selected Games

WCCC 2007, round 8, GridChess - Shredder [8]

[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 

Authors

See also

Publications

Forum Posts

External Links

Chess Entity

Misc

References

  1. 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
  2. Chrilly Donninger, Alex Kure, Ulf Lorenz (2004). Parallel Brutus: The First Distributed, FPGA Accelerated Chess Program. IPDPS’04
  3. David Levy (2003). The State of the Art in Man vs. “Machine” Chess. ICGA Journal, Vol. 26, No. 1
  4. PhD Project of Kai Himstedt (Dipl.-Inform.)
  5. Kai Himstedt (2012). Optimistische verteilte Spielbaumsuche am Beispiel des Computerschachs. Dissertation (German)
  6. GridChess' ICGA Tournaments
  7. Kai Himstedt (2012). GridChess: Combining Optimistic Pondering with the Young Brothers Wait Concept. ICGA Journal, Vol. 35, No. 2
  8. Amsterdam 2007 - Chess - Round 8 - Game 6 (ICGA Tournaments)
  9. Download - Cluster Toga 1.4b5c based on Fruit 2.1 UCI

Up one level