Relative Efficiency of Alpha-Beta Implementations

ABSTRACT

Most of the data on the relative efficiency of different implementations of the alpha-beta al­ gorithm is neither readily available nor in a form suitable for easy comparisons. In the present study four enhancements to the alpha-beta algorithm--iterative deepening, aspiration search, memory tables and principal variation search--are compared separately and in various combinations to determine the most effective alpha-beta implemen­ tation. The rationale for this work is to ensure that new parallel algorithms incorporate the best sequential techniques. Rather than relying on si­ mulation or searches of specially constructed trees, a simple chess program was used to provide a uniform basis for comparisons.

I INTRODUCTION

Perhaps the most complete description of the alpha-beta algorithm is the paper by Knuth and Moore, in which a negamax implementation is des­ cribed [1]. That paper also makes a clear distinction between those nodes in the game tree where cutoffs may occur, and those which must be fully explored, and so are .logical candidates for the application of multiple processors during parallel searches. One field where the alpha-beta algorithm is universally applied is that of compu­ ter chess. Here the problems are so large that a tree of the whole game cannot be built and so an approximate solution is sought, one which involves a succession of searches on fixed depth trees. At a terminal node (a leaf ) an evaluation function is invoked to estimate the value of the subtrees dis­ carded. In chess, non-quiescent moves at the terminal nodes are explored more fully, with spe­ cial subse.t searches involving, for example, only moves which check or capture (or their forced responses) .

The alpha-beta algorithm owes its efficiency to the employment of two bounds which form a window. Typically, a call to the alpha-beta func­

tion is of the form:

V := AB(p, alpha, beta, depth ) ; where p is a pointer to a structure which repre­ sents a position, alpha and beta are the lower and upper bounds on the window, and depth is the spe­ cified length of search. The number returned by the function is called the minimax value of the tree, and measures the potential success of the next player to move. A skeleton for the alph~beta function appears in a recent survey paper [2],

RELATIVE EFFICIENCY OF ALPHA-BETA IMPLEMENTATIONS

T.A. Marsland

Computing Science Department University of Alberta EDMONTON T6G 2Hl Canada

where more details about certain alpha-beta re­ finements appear. Previous studies of alpha-beta efficiency have not considered these refinements, or have not been done on a basis which allows for simple comparisons. To provide more consistency, this new quantitative study presents results from a simple working chess program', and may be com­ pared with those from searches of specially constructed trees [3].

II ALPHA-BETA REFINEMENTS

An iterative deepening mode, in which a se­ quence of successively deeper and deeper searches is carried out until some time limit is exceeded, is a simple way of extending the alpha-beta al­ gorithm. A search of depth D PlY (moves) is used to dynamically reorder (sort) the choices and thus prepare the way for a faster search to D+l ply than would be possible directly. My aim is to de­ termine exactly how much a shallow search may improve a deeper one, and to compare the results with those for a direct full window search. The methods considered are: -- ----

1. Simple iteration, in which the move list at the root node of the tree is sorted after each iteration. By this means the candidate bes t move is tried first during the next iteration.
2. Aspiration search, in which the score re­ turned by the best move found so far is used as the centre of a narrow window within which the score for the next iteration is expected to fall. If the value returned is outside the window, the search has failed high or low and must be repeated with a window which spans the new range of pos­ sible values [2].
3. Minimal window search employs a full window only on the candidate principal variation. All the alternate variations are searched with a zero window, under the assumption that they will fail-low in any case. Should one of the moves not fail this way then it becomes the start of a new principal variation and the search is repeated for this move with a window which covers the correct range of possible values. The PVS (principal variation search) implementation of this algorithm is based on Calphabeta [4], which in turn is simi-

1: Tinkerbelle [K. Thompson], a chess program which participated at the US Computer Chess Championship, San Diego, November, 1974.

lar to Scout [5]. The algorithm is presented in Figure 1, through a Pascal like language extended with a retur n statement. Undefined in the program are functions evaluate ( to assess the value of a leaf ) , and generat e ( to list the moves for the current position) . For simplicity, additional fun­ ctions make ( to actually play the move considered) and undo ( to retract the current move ) are not included . Note that PVS preserves the property of Falphabeta [4], in that for failing searches the bound returned may be better than the alpha limit. Thi s means that the re-search of a new principal variation normally proceeds with a narrower win­ dow. More importantly, PVS may be easily extended to draw on the idea that the correct score for a candidate principal variation is not needed until a potential rival arises. This extension to alpha­ beta searching is based on a technique employed by K. Thompson at the first level of the tree search in Belle' . Note also that zero window searches normally cut off quite quickly. If this is not the case, then a profitable heuristic is to curtail the search and repeat immediately with the appro­ priate window.

Haturally, all of these methods may be im­ proved by the inclusion of transposition and refutation memory tables.

III MEMORY TABLES

For each initial move in the game tree, the alpha-beta algorithm determines a sequence of moves which is sufficient to cut off the search. These sequences may be stored in a refutation table. After a search to depth D on a tree of con­ stant width W this table will contain W*D entries. Thus upon the next iteration there exists a set of move sequences of length D-ply that are to be tried first. The next ply is then added and the search continues. The candidate principal varia­ tion is fully searched, but for the alternate variations the moves in the refutation table may again be sufficient to cut off the search, and thus save the move generation that would normally occur at each node. The storage overhead is very small, although a small triangular table is also

needed to identify the refutations [6].

A transposition table holds not only refuta­ tions and the main subvariations, but also has the capacity for including more information. In parti­ cular, once a subtree has been searched its transposition table entry will contain not only the length of the search tree and the value of the subtree, but also whether that value represents the true score or an upper / lower bound on the score [2] . A typical transposition table might contain 100,000 entries, each of 10 bytes, for a million-byte total storage overhead. In our imple­ mentation, the (position encoding) hash key was 48 bits long, of which 12 bits were used to index into an 8192-entry table. Various choices for ac­ cessing the transposition table are discussed in a recent report [7]. For this study only a single

probe of the table was made for each position.

2: BELLE, the current world champion chess pro­ gram, developed by K. Thompson, Bell Laboratories.

IV RESULTS

Minimax tree searches generally involve signi­ ficantly more calculation at a leaf than at an interior node. For example, chess programs carry out a check and capture analysis in the form of an extended tree search. Therefore the following re­ sults are based on the number of terminal nodes examined . It is reasonable to assume that the various heuristics in the evaluation function are · equally effective across all alpha-beta refine­ ments, and so we have a machine-independent measure for future comparisons.

The algorithms were tested on a data set which was used to assess the performance of computer chess programs and human players [8). That data set contains 24 chess positions (labelled A .. X in Table 1) , but A was deleted from our study since it involved a simple sequence of forcing checks. All the remaining positions were searched with 3, 4 and 5-ply trees, using a combination of alpha­ beta refinements, and a 6-ply search was done with the best method. The raw results have been con­ densed into Figure 2, which shows the ratio of the number of terminal nodes searched relative to a direct search. In order to see how much improve­ ment is possible in the alpha-beta algorithm, the formula

bounds on x, is plotted in Figure 2 as the minimum tree size [9]. Here the value for W is estimated as the average width of the nodes in the trees being studied. The zig-zag appearance of Figure 2 is normal for alpha-beta searches [10 ] , and,occurs because for an even-ply search a larger fraction of the terminal nodes must be fully evaluated.

From Table 1 we see that one of the positions influences the final results strongly. For example, in the case of board W a change occurred in the principal variation, thus the 4-ply search was not a good predictor of the 5-ply result . Just how serious this can be is clear from Table 1, which shows that for board W all the iterative searches are more expensive than a direct search. This is reinforced in the 6-ply results when, for the case PVS with transposition table, 28% of the effort was expended on board W [7]. Some effective heuristics for partial re-ordering of the move list between iterations can be developed to cor­ rect this problem. Even so, iterative searches may be at a disadvantage whenever the principal varia­ tion changes. For problems' of this type we are designing parallel versions of PVS.

V ASSESSMENT OF SEQUENTIAL METHODS

These results confirm that iterative deepening is an effective enhancement to the alpha-beta al­ gorithm, provided it is used in conjunction with some form of aspiration or memory table search. For relatively shallow trees (depth ~ 5) there is not much to choose between refutation and transpo­ sition memory tables. By its very nature, a

transposition table is continually being filled with new positions, some of which may destroy en­ tries that have not yet been reused. Thus it is not possible to guarantee that all the primary refutations will be retained. This problem can be overcome through the inclusion of a small and easy to maintain refutation table. To support this com­ bination, we observed that for the 5-ply PVS case an average 2 percentage point improvement oc­ curred, while in the 6-ply case a more dramatic 31 percentage point improvement was seen, Figure 2. From this second result we conclude that a trans­ position table of 8192 entries is too small for 6ply searches of complex positions, since it be­ comes seriously overcommitted and cannot perform as well as the simpler refutation table. On the other hand, the true power of a transposition table was not brought out by our data set, since there were only two endgames, boards F and H (Table 1) .

VI CONCLUSIONS

Of the two principal refinements, narrow window aspiration search and use of memory tables, it was found that preservation and use of the re­ futations from a previous iteration was more important than aspiration searching. This point is clearly illustrated in Table 1, where a full window search with refutation table support is superior to a narrow window aspiration search wi­ thout a memory table.

Based on our experiments, as summarized by results presented in Figure 2, it is clear that PVS is potentially superior to narrow window as­ piration searching, since it avoids the need to determine an acceptable window. Note that these results reverse an earlier conclusion for the game of checkers, where Calphabeta was described as being "disappointing" and "probably not to be recommended" [4]. Thus for two different games contradictory results appear, illustrating not only how game-dependent these methods may be, but also the influence of strong move ordering [2] on the efficiency of tree search algorithms.