In this thesis, research is presented on the trade-off between memory and search. The domain under investigation is the domain of two-player zero-sum games, in particular the games of chess and domineering. The trade-off between memory and search is enhanced by the increase in availability of computer memory and the increase in processor speed.
Currently, the prices of computer memory are decreasing. Therefore, acquiring larger memory configurations is no longer an obstacle, making it easier to equip a computer with more memory. A depth-first search algorithm (such as alpha-beta search) uses little memory. The large amount of remaining memory can be used, e.g., to prevent the re-search of transpositions (identical positions in the tree). For this purpose, a transposition table, holding the results of previous searches, is maintained in the remaining memory. The trade-off transpires in more memory to be used, in favour of less searching. This leads to the formulation of the first problem statement.
In Chapter 2 three methods for improving the efficiency of a transposition table are described. The first method addresses the use of an adequate replacement scheme. When a conflict arises, a replacement scheme decides which positions to keep in the table, and which positions to discard. Experiments show that in this area improvements can still be found. A new replacement scheme, called TwoBig1, based on a two-level table and the number of nodes of the subtree investigated, outperforms all other schemes. It enabled us to solve the game of domineering for several boards, including the standard board. The second method addresses doubling the number of positions in the transposition table. Experiments show that doubling the number of positions is a good method for improving the efficiency of a transposition table. However, beyond a certain table size not much is to be gained from doubling the number of positions. Therefore, the third method concentrates on using the remaining memory not for doubling the number of positions of the table, but for enlarging the size of an entry, by storing more information in an entry. A limited set of experiments show that -- beyond a certain table size -- this method gains more than doubling the number of positions in the table, although more experiments are needed to substantiate this claim.
In Chapter 3 proof-number search (pn search) is described. This is a best-first search algorithm, storing the complete search tree in memory. Experiments show that pn search is suitable for solving mate problems in chess. However, there are two drawbacks: (1) a solution cannot be found if the search tree takes up all memory, and (2) identical positions in the search tree (and their subtrees) are doubly searched. These drawbacks are taken care of in Chapters 4 and 5.
Every year there is a large increase in computer speed. Increasing computer speed causes acceleration of search algorithms. A best-first search algorithm (such as pn search) stores the complete search tree in memory. After a relatively short search time no more memory is available since the fast search has generated too many nodes. The increase in computer speed can also be used to do more search at nodes, thereby gaining more knowledge per node. The trade-off transpires in more searching, in favour of less memory to be used. This leads to the formulation of the second problem statement.
In Chapter 4 the pn2-search algorithm is presented. The concept behind this algorithm is that the leaves are not evaluated by an evaluation function, but by a secondary pn-search process. Several experiments with different sizes of the secondary search tree show that much can be gained by choosing the right size of the secondary search tree. The conclusion is that the pn2-search algorithm is a good method to use the increase in computer speed for additional searching, thereby gaining a better assessment of the values of the leaves.
As mentioned above, in pn search identical positions in the search tree (and their subtrees) are doubly searched. In depth-first search algorithms the re-search of a transposition is avoided by implementing a transposition table. A logical way to avoid the re-search of a transposition in best-first search is to store a transposition only once, thereby transforming the tree into a Directed Cyclic Graph (DCG). However, an important aspect of a position is the path leading to it (the history). Ignoring the history of a position introduces the graph-history-interaction (GHI) problem. This leads to the third problem statement.
In Chapter 5 the GHI problem is analyzed in the domain of pn search. A different implementation of a DCG is suggested, and the pn-search algorithm is modified to be able to search this DCG implementation. The new BTA (Base-Twin Algorithm) algorithm is based on the distinction of two types of nodes, termed base nodes and twin nodes. The purpose of these types is to distinguish between equal positions with different history. Experiments with this pn-search algorithm for DCGs confirm our solution of the GHI problem. In the test positions submitted the BTA algorithm solves them all and hence outperforms other attempts to overcome the GHI problem as well as the standard tree algorithm.
Summarizing, the main contributions of this thesis are as follows.