Game Tree Evaluation
Intelligent Look-Ahead with the Help of Game Tree Search
Tree search algorithms play an important role in many applications in the field of artificial intelligence. Therefore, much work was done in the past to speed up search algorithms. Especially in the field of game tree search as used, for example, in chess playing programs, it turned out that the playing strength depends heavily on the speed of the algorithm: the faster the machine the better its play. Therefore, much research has been done to speed up game tree search algorithms e.g. by using parallel machines. For a long time, however, the sequential game tree search algorithm, the so-called alpha-beta-algorithm, seemed to be inherently sequential. Thus, the maximum speedup that could be obtained by using parallel machines was estimated to be a constant somewhere below 10. This estimate was based on the results of several implementations of parallel game tree search algorithms.These results were caused by the following overheads:
- Search Overhead
The state-of-the-art sequential algorithms searched game trees in a very efficient manner. They used several enhancements to accumulate knowledge from the search speeding up later phases of the search. It was not clear how to distribute this information in a parallel environment between the processors. - Processor Work Load
The most promising line to parallelize the alpha-beta-algorithm was to decompose the game tree to be searched and distribute subtrees to the processors for parallel evaluation. However, it turned out that the size of these subtrees was not predictable in advance which lead to severe load balancing problems. - Communication Overhead
Communication necessary to distribute information or subproblems among the processors caused several implementations to be suitable only for a small amount of processors.
We developed a distributed Min/Max tree search algorithm. Our algorithm runs efficiently even on massively parallel systems. The main reasons for this efficiency are the following:
- Dynamic load distribution in all parts of the tree
Our algorithm uses techniques for dynamically balancing the work load in the processor network. These techniques enable us to include e.g. the alpha-beta - enhancement ''iterative deepening'' or other search overhead reducing techniques. We developed a combination of local and global load distribution strategies which on the one hand turned out to guarantee a good load balancing and on the other hand keeps the communication costs small. - Local criteria, whether or not to use parallelism
We developed the ''Young Brothers Wait Concept'', which in some situations delays the use of parallelism until subtrees are available which are relevant for the final result with high probability. Thus, the YBWC prevents processors from searching irrelevant subtrees and reduces the search overhead. The use of the YBWC is possible only in combination with good load balancing possibilities. - Efficient implementation of a distributed hash table
All state-of-the-art game tree searching programs use a transposition table, which is a hash table for results already computed. This hash table is accessed during the search in order to avoid the computation of a result already known. We implemented a distributed hash table by emulating shared memory in a distributed system. Several techniques were used to keep the processors busy during the time they are communicating for transposition table access. - The choice of a suitable processor network
We showed that the choice of the underlying processor network plays an important role for the efficiency of our distributed algorithm.
Firstly, this algorithm was the heart of the chess playing program Zugzwang, vize world champion at the World Computer Chess Championships in Madrid, Spain, 1992. Later, it has been implemented into the chess program Hydra, the strongest chess entity in the world in year 2005 and 2006. Hydra was the first program achieving more than 3000 Elo.
Game Tree Evaluation - Adaptive & Selective Game Tree Search
In games like chess, checkers etc. the complete game tree of is so large that it appears unlikely a computer will ever be able to find the theoretical value of the game of chess. Thus, the search is limited in depth. The leaves of the search tree are then evaluated by a heuristic evaluation function and handled as if they were ''real'' values.In its basic form the depth oriented alpha-beta-algorithm cuts the search at a certain level in the tree, independent of the importance of the current path in the tree. Thus, irrelevant variations of the tree are searched as deep as the important ones. Moreover, in the worst case the decision at the root of the tree is based on a single static evaluation at one leaf of the game tree searched.
In order to avoid the mentioned drawbacks, we try to find algorithms, which are able to adapt the search tree to the game. Such an algorithm must determine the search tree at running time. As a result we found a game tree search algorithm, called:
'Controlled Conspiracy Number Search' (CCNS) algorithm.
Conspiracy Number search achieves selectivity in the plain search without any domain dependent knowledge.
Parallel CCNS was the heart of the chess program
P. ConNerS.
Contact
Ulf Lorenz (flulo@upb.de)Index A – Z | Impressum | Webmaster | Modified: 10.05.2005