PhD Projects

PhD Project of Kai Himstedt (Dipl.-Inform.)

Project Description

Even sophisticated classical approaches to parallelize game-tree search are restricted to using one single cluster at most. One further idea to speed up the game-tree search is to extend the cluster on the lowest level with specialized hardware components. Two well-known examples for this idea are the FPGA based Hydra system and IBM’s Deep Blue. In my PhD project a contrasting idea is investigated taking computer chess as an example: A parallelized chess program running on a cluster forms a base component. With a second parallel approach on top several clusters can be used to achieve a further speedup.

The project is supported by my PhD advisors Prof. Dr.-Ing. Dietmar P. F. Möller (University of Hamburg, Department of Informatics) and Dr. habil. Ulf Lorenz (Technical University Darmstadt, Department of Mathematics). For more detailed information see “Himstedt, Kai. An Optimistic Pondering Approach for Asynchronous Distributed Game-Tree Search. In: ICGA Journal. Vol. 28 No. 2 (2005):77-90” and “Himstedt, Kai, Ulf Lorenz, Dietmar P. F. Möller. A Twofold Distributed Game-Tree Search Approach Using Interconnected Clusters. In: Emilio Luque, Tomàs Margalef, Domingo Benítez (Eds). Euro-Par 2008 – Parallel Processing: Proceedings of the 14th International Euro-Par Conference, Gran Canaria, Spain, August 26-29, 2008. Springer LNCS. Berlin, Heidelberg. Vol. 5168 (2008):587-598”.

Combining Optimistic Pondering at the Inter-cluster Level with the Young Brothers Wait Concept at the Intra-cluster Level

The prototypical GridChess implementation 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 workers. As a simplified explanation of Optimistic Pondering here, one can imagine the workers forming a pondering pipeline with expected opponent’s moves extracting this information from the principal variations provided by the chess engines. This procedure is very similar to a pipeline within a processor using branch prediction. The principal variation (PV) is a sequence of successive half moves (the move of one player, named a ply), assuming that each player will make the move that best improves his own position. The actual PV is provided by all typical chess programs, as Cluster Toga in our case, during their tree search and contains a forecast for the game.

2) Real chess engines (acting as distributed workers), Fruit/Toga based (i.e. Cluster Toga), parallelized with the Young Brothers Wait Concept (YBWC) at the intra-cluster level. This way a combination of two parallel concepts was realized building the complete GridChess system: The parallel Cluster Toga base engines using the YBWC may run on high performance clusters (a shared memory support is not mandatory), each cluster representing a worker for the proxy chess engine. Several such clusters are then used for an asynchronous distributed game-tree search with the Optimistic Pondering method at the inter-cluster level. Since Optimistic Pondering does not need high communication bandwidths, these clusters may be located at different places (e.g. Paderborn and Hamburg).

Using YBWC as State of the Art Parallelization at the Intra-cluster Level

Cluster Toga is a Young Brothers Wait Concept (YBWC) parallelized version of Toga based on Fruit capable to run on a high performance cluster and participated for example in the 17th International Paderborn Computer Chess Championship (IPCCC) 2007 and the 16th World Computer-Chess Championship (WCCC) 2008 in Beijing. In fact Cluster Toga is a “stand alone” base engine of the GridChess system which participated for example in the 15th World Computer-Chess Championship (WCCC) 2007 in Amsterdam but is limited to use a single cluster. If you are interested, click here to download the source code of Cluster Toga (i.e. Cluster Toga 1.4b5c based on Fruit 2.1 UCI, cluster parallelization by Kai Himstedt and Dr. habil. Ulf Lorenz of Toga by Thomas Gaksch, which is based on Fruit by Fabien Letouzey) as an email attachment (in a single compressed file). For some automated testing functionalities (benchmarking the system in batch mode) Cluster Toga uses (source code is included) the argtable2 library of Stewart Heitmann for accessing the command line arguments. The Cluster Toga implementation also uses the Message Passing Interface (MPI) which you will find here. For an experienced programmer it should be no problem to successfully compile the sources and build an executable program which is usable in the MPI environment. Up to now Cluster Toga has been tested under several Linux derivatives, Windows Server 2003 Compute Cluster Edition and Windows Clusters built from COTS (commodity off-the-shelf) components. For two points I have to ask for your understanding: a) Since I am extremely busy with my PhD thesis I would have absolutely no time left to give any support right now. b) It is not yet planned to publish the source code of the complete GridChess system, i.e. the Optimistic Pondering implementation for the inter-cluster level parallelization. GridChess is a potential World Computer-Chess Championship (WCCC) candidate. I would like to keep this “GridChess-advantage” for a while.


Dr. Kai Himstedt

Universität Hamburg
Department Informatik
Gebäude F
Vogt-Kölln-Str. 30
D-22527 Hamburg

Tel.: +49-(0)40-42883-2550
Fax: +49-(0)40-42883-2552