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.

*Problem statement 1:*Which methods exist to improve the efficiency of a transposition table?

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.

*Problem statement 2:*Which methods exist for best-first search to reduce the need for memory by increasing the search, thereby gaining more knowledge per node?

In Chapter 4 the pn^{2}-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 pn^{2}-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.

*Problem statement 3:*Is it possible to give a solution for the GHI problem for best-first search?

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.

- The discovery of a new replacement scheme (
*TwoBig*), based on a two-level transposition table and number of nodes of the subtree investigated. - Solving the game of domineering.
- The pn
^{2}-search algorithm. - The BTA algorithm (implemented for pn search), solving the GHI problem.

Back to my thesis page.