Best-First Fixed-Depth Game-Tree Search in Practice
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 273-280.
© 1995 International Joint Conferences on Artificial Intelligence
Abstract
We present a new paradigm for minimax search algorithms: MT, a memory-enhanced version of Pearl's Test procedure. By changing the way MT is called, a number of practical best-first search algorithms can be simply constructed. Reformulating SSS* as an instance of MT eliminates all its perceived implementation drawbacks. Most assessments of minimax search performance are based on simulations that do not address two key ingredients of high performance game-playing programs: iterative deepening and memory usage. Instead, we use experimental data gathered from tournament checkers, Othello and chess programs. The use of iterative deepening and memory makes our results differ significantly from the literature. One new instance of our framework, MTD(f), out-performs our best Alpha-Beta searcher on lea f nodes, total nodes and execution time. To our knowledge, these are the first reported results that compare both depth-first and bestfirst algorithms given the same amount of memory.
- [De Bruin et al., 1994] A. de Bruin, W . Pijls, and A. Plaat . Solution trees as a basis for game-tree search. ICCA Journal, 17(4): 207-219, December 1994.
- [Campbell and Marsland, 1983] M. Campbell and T.A. Marsland. A comparison of minimax tree search algo- rithms. Artificial Intelligence, 20:34 7-367, 1983.
- T. Ibaraki. Generalization of alpha-beta and SSS* search procedures. Artificial Int elligence, 29:73-117, 1986.
- [Kaindl et al., 1991] H. Kaindl, R. Shams, and H. Ho- racek. Minimax search algorithms with and without aspiration windows. IEEE PAM!, 13(12) :1225-1235, 1991.
- [Knuth and Moore, 1975] D.E. Knuth and R.W. Moore. An analysis of alpha-beta pruning. Artificial Intelli- gence, 6(4):293-326, 1975.
- [Marsland et al., 1987] T.A. Marsland , A. Reinefeld , and J. Schaeffer. Low overhead alternatives to SSS* . Artificial Intelligence, 31:185-199, 1987.
- [Muszycka and Shinghal , 1985] A. Muszycka and R. Shinghal. An empirical comparison of pruning strate- gies in game trees. IEEE SMC, 15(3) :389-399 , 1985.
- [Pearl, 1982] J. Pearl. The solution for the branching factor of the alpha-beta pruning algorithm and its op- timality. CACM, 25(8):559-564, 1982.
- [Pijls and De Bruin, 1990] W. Pijls and A. de Bruin . Another view on the SSS* algorithm . In T. Asano, editor, Algorithms, SIGAL '90, Tokyo , volume 450 of LNCS, pages 211-220 . Springer-Verlag , August 1990.
- [Plaat et al., 1994a] A. Plaat, J. Schaeffer, W. Pijls, and A. de Bruin. Nearly optimal minimax tree search? Technical Report CS-94-19, Dept. of Computing Sci- ence, Univ. of Alberta, 1994.
- [Plaat et al., 1994b] A. Plaat, J . Schaeffer, W. Pijls, and A. de Bruin. A new paradigm for minimax search . Technical Report CS-94-18, Dept. of Computing Sci- ence, Univ. of Alberta, 1994.
- [Plaat et al., 1994c] A. Plaat , J . Schaeffer , W . Pijls, and A. de Bruin. SSS* = a/3 + TT. Technical Report CS- 94-17, Dept . of Computing Science, Univ. of Alberta, 1994.
- [Reinefeld and Ridinger , 1994] A. Reinefeld and P. Ridinger. Time-efficient state space search. Ar- tificial Intelligence, 71(2):397-408, 1994.
- [Roizen and Pearl, 1983] I. Roizen and J. P earl. A min- imax algorithm better than alpha-beta? Yes and no. Artificial Intelligence, 21 :199-230, 1983.
- [Schaeffer, 1989] J. Schaeffer. The history heuristic and alpha-beta search enhancements in practice. IEEE PAM!, 11(1) :1203-1212, 1989.
- [Stockman, 1979] G.C . Stockman. A minimax algo- rithm better than alpha-beta? Artificial Intelligence, 12(2):179-196, 1979.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
For over 30 years, Alpha-Beta has been the algorithm of choice for searching game trees. Using a simple left-to right depth-first traversal, it is able to efficiently search trees [Knuth and Moore, 1975; Pearl, 1982]. Several im portant enhancements were added to the basic Alpha Beta framework, including iterative deepening, transpo sition tables, the history heuristic, and minimal search windows [Schaeffer, 1989]. The resulting algorithm is so efficient that other promising fixed-depth algorithms were largely ignored. In particular, although best-first search strategies seemed promising both analytically and in simulations, they are not used in practice.
This paper presents a number of contributions to our understanding of depth-first and best-first minimax search:
- MT, a memory enhanced version of Pearl's Test pro cedure, is introduced. MT yields a binary-valued decision. We present a simple framework of MT
2 University of Alberta, Dept. of Computing Science, 615 General Services Building, Edmonton, AB, Canada T6G 2H1
drivers (MTD) that make repeated calls to MT to home in on the minimax value. Surprisingly, MTD can be used to construct a variety of best-first search algorithms (such as SSS* [Stockman, 1979]) using depth-first search.
- SSS* (and its dual DUAL* [Marsland et al. , 1987]) has not been used in practice because of several per ceived drawbacks [Campbell and Marsland, 1983; Kaindl et al., 1991; Marsland et al., 1987; Roizen and Pearl, 1983] . When expressed in the MTD framework, these problems disappear. Furthermore, SSS* becomes easy to implement and integrate into a conventional Alpha-Beta game-playing program.
- Simulations of minimax search algorithms in the literature are misleading because they make sim plifying assumptions (such as assuming no depen dencies between leaf values, or excluding iterative deepening and transposition tables). Our approach was to gather experimental data from three real game-playing programs (chess, Othello and check ers), covering the range from high to low branch ing factors. Our results contradict published sim ulation results on the relative merit of a variety of minimax search algorithms [Kaindl et al., 1991; Marsland et al., 1987; Reinefeld and Ridinger, 1994] .
- In previous work, depth-first and best-first mini max search algorithms were compared using differ ent amounts of memory. These are the first exper iments that compare them using identical storage requirements.
- With dynamic move reordering, SSS* is no longer guaranteed to expand fewer leaf nodes than Alpha Beta (Stockman's proof [Stockman, 1979] does not hold in practice) . In our experiments, SSS* per forms as fast as any of our Alpha-Beta implemen tations, but visits too many interior nodes to be practical.
- A new instance of our framework, MTD(f), out per forms our best Alpha-Beta searcher on leaf nodes, total nodes and execution time.
2 Memory-enhanced Test
Pearl introduced the concept of a proof procedure for game trees in his Scout algorithm [Pearl, 1982] (also known as Null- Window Search). Scout called Test, a proof procedure that takes a search assertion (for ex ample, the minimax value of the tree is :::: w) and re turns a binary value (assertion is true or false). It turns out that Scout-based algorithms will never consider more unique leaf nodes than would Alpha-Beta. For the spe cial case of a perfectly ordered tree both Alpha-Beta and the Scout-variants search the so-called minimal search tree [Knuth and Moore, 1975]. Simulations have shown that, on average, Scout-variants (such as NegaScout) sig nificantly out-perform Alpha-Beta [Kaindl et al., 1991; Marsland et al., 1987] . However, when used in prac tice with iterative deepening, aspiration searching and transposition tables, the performance of all algorithms greatly increases. As a result, the relative advantage of NegaScout significantly decreases [Schaeffer, 1989].
Test does an optimal job of answering a binary-valued question by maximizing the number of cutoffs. However, game-tree searches are usually over a range of values. We would like to use the efficiency of Test to find the minimax value of a search tree. Repeated calls to Test will be inefficient, unless Test is modified to reuse the results of previous searches. Enhancing Test with mem ory yields a new algorithm which we call MT (short for Memory-enhanced Test) . The storage can be organized as a familiar transposition table [Campbell and Mars land, 1983]. Before a node is expanded in a search, a check is made to see if the value of the node is available in memory, the result of a previous search. Later on we will see that adding storage has some other benefits that are crucial for the algorithm's efficiency: it makes it possible to have the algorithm select nodes in a best-first order.
We would like our formulation of Test to be as clear and concise as possible. In figure 1 MT is shown as a procedure that takes a node n and a single value 1 to test on. For MT to function correctly, 1 must be un equal to any possible leaf value, since we have deleted the "=" part of the cutoff test [Plaat et al., 1994a]. We can set 1 = w + E:, where E: is a value smaller than the difference between any two leaf node evaluations. An alternative would be to formulate MT as a null-window Alpha-Beta search (a = lf J, ,8 = h l) with a transpo sition table. We prefer our one-bound version because it focuses attention on the value to be tested, although the null window search version may be better suited for implementation in existing game playing programs.
There are three differences between MT and Test. One is that MT is called with w - E: instead of w, so that there is no need for the "=" part in the cutoff test, ob viating extra tests in the code of MT. The second is that MT returns a bound on the minimax value, and not just a Boolean result. The third (and more fun damental) difference is that MT uses storage to pass on search results from one pass to the next , making efficient multi-pass searches possible. [Ibaraki, 1986; De Bruin et al., 1994] provide a theoretical background.
Figure 1 shows the pseudo-code for MT using Nega max. The routine assumes an evaluate routine that as signs a value to a node. Determining when to call evalu ate is application-dependent and is hidden in the defini-
function MT(n, 1) --+ 9;
{ precondition: 1 f. any leaf-evaluation; MT must be called with ')' = w - t: to prove 9 < w or 9 2: w } if retrieve(n) = found then if n.f- > 1 then return n.f-; if n. t+ < 1 then return n. t+; if n = leaf then n.f+ := n.f- := 9 := evaluate(n); else 9 := -oo; c := firstchild(n) ; while 9 < 1 and c # .L do 9 := max(9, -MT(c, - ')')); c := nextbrother(c); if 9 < 1 then n.f+ := 9 else n.f- := 9; store(n); return 9; Figure 1: MT function MTD(+oo)--+ f; 9 := +oo; n :=root; repeat bound:= 9; 9 := MT(n, bound- t:); until 9 = bound; return 9; Figure 2: MTD( +oo)
tion of the condition n = leaf. For a depth d fixed-depth search, a leaf is any node that is d moves from the root of the tree. The search returns an upper or lower bound on the search value at each node, denoted by j+ and f- respectively. Before searching a node, the transpo sition table information is retrieved and, if it has been previously searched deep enough, the search is cutoff. At the completion of a node, the bound on the value is stored in the table. The bounds stored with each node are denoted using Pascal's dot notation.
In answering the binary-valued question, MT returns a bound on the minimax value. If MT's return-value g > 1 then it is a lower bound, while if g < 1, it is an upper bound. Usually we want to know more than just a bound. Using repeated calls to MT, the search can home in on the minimax value f . To achieve this, MT must be called from a driver routine. One idea for such a driver would be to start at an upper bound for the search value, j+ = +oo. Subsequent calls to MT can lower this bound until the minimax value is reached. Figure 2 shows the pseudo-code for such a driver , called MTD(+oo) . The variable g is at all times an upper bound j+ on the minimax value of the root of the game tree [Plaat et al., 1994c]. Surprisingly, MTD( +oo) expands the same leaf nodes in the same order as SSS*, provided that the transposition table is big enough and no information is lost through table collisions (see section 3).
Storage is critical to the performance of a multi-pass MT algorithm. Without it, the program would revisit interior nodes without the benefit of information gained from the previous search and expand them. Instead, MT can retrieve an upper and/or lower bound for a node, using a relatively cheap table lookup. The storage table provides two benefits: (1) preventing unnecessary node re-expansion, and (2) facilitating best-first node selec tion (see sections 3 and 4). Both are necessary for the efficiency of the algorithm.
One could ask the question whether a simple one-pass Alpha-Beta search with a wide search window would not be as efficient. Various papers point out that a tighter Alpha-Beta window causes more cutoffs than a wider window, all other things being equal (for example, [Campbell and Marsland, 1983; Marsland et al., 1987; Plaat et al., 1994c]). Since MT does not re-expand nodes from a previous pass, it cannot have fewer cutoffs than wide-windowed Alpha-Beta for new nodes. (Nodes expanded in a previous pass are not re-expanded but looked-up in memory.) This implies that any sequence of MT calls will be more efficient (it will never evaluate more leaf nodes and usually significantly less) than a call to Alpha-Beta with window ( -oo, +oo ), for non-iterative deepening searches.
3 Four Misconceptions concerning SSS*
MTD( +oo) causes MT to expand the same leaf nodes in the same order as SSS* (see [Plaat et al., 1994c] for a substantiation of this claim). The surprising result that a depth-first search procedure can be used to examine nodes in a best-first manner can be explained as follows. The value of g- c (where g = j+) causes MT to explore only nodes that can lower the upper bound at the root; this is the best-first expansion order of SSS*. Only chil dren that can influence the value of a node are traversed: the highest-valued child of a max node, and the lowest of a min node. Expanding brothers of these so-called criti cal children gives a best-first expansion. It is instructive to mentally execute the MTD( +oo) algorithm of figure 1 on an example tree such as the one in [Stockman, 1979], as is done in [Plaat et al., 1994b].
An important issue concerning the efficiency of MT based algorithms is memory usage. SSS* can be regarded as manipulating one max solution tree in place. A max solution tree has only one successor at each min node and all successors at max nodes, while the converse is true for min solution trees [Pijls and De Bruin, 1990; Stockman, 1979]. Whenever the upper bound is lowered, a new (better) subtree has been expanded. MTD(+oo) has to keep only this best max solution tree in memory. Given a branching factor of w and a tree of depth d, the space complexity of a driver causing MT to construct and refine one max solution tree is therefore of the order O(wrd/ 2 1 ), and a driver manipulating one min solution tree is of order O(wld/ 2 J) (as required for DUAL*). A simple calculation and empirical evidence show this to be realistic storage requirements. (Due to lack of space we refer to [Plaat et al., 1994c] for an in-depth treatment of these issues.)
A transposition table provides a flexible way of stor ing solution trees. While at any time entries from old (inferior) solution trees may be resident, they will be overwritten by newer entries when their space is needed. There is no need · for a time-consuming SSS* purge op eration. As long as the table is big enough to store the min and/or max solution trees that are essential for the efficient operation of the algorithm, it provides for fast access and efficient storage.
The literature cites four issues concerning SSS* [Kaindl et al., 1991; Roizen and Pearl, 1983]. The first is the complicated algorithm. Comparing the code for Alpha-Beta [Knuth and Moore, 1975] and SSS* [Stock man, 1979], one cannot help getting the feeling of being overwhelmed by its complexity. Looking at the code in figure 2 we think this is solved. The second is SSS*'s exponential storage demands. A counter-argument is that Alpha-Beta in game-playing programs also has ex ponential storage needs to achieve good performance; the transposition table must be large enough to store the move ordering information of the previous iteration. In other words, both Alpha-Beta and SSS* perform best with a minimum of storage of the order of the size of min/max solution tree(s). The third is that SSS* uses expensive operations on the sorted OPEN list. In our MT reformulation, no such operations are used. There is no explicit OPEN list, only an implicit search tree stored in a transposition table. The store and retrieve operations are just as fast for Alpha-Beta as for SSS*. In summary, the arguments against SSS* are eliminated using an MT representation. SSS* is no longer an im practical algorithm [Plaat et al., 1994c].
The fourth issue in the literature is that SSS* will provably never expand more leaf nodes than Alpha-Beta [Stockman, 1979]. However, our experiments used itera tive deepening and move reordering, which violates the implied preconditions of the proof. In expanding more nodes than SSS* in a previous iteration, Alpha-Beta re orders more nodes. Consequently, in a subsequent itera tion SSS* may have to consider a node for which it has no move ordering information whereas Alpha-Beta does. Thus, Alpha-Beta's inefficiency in a previous iteration can actually benefit it later in the search. With iterative deepening, it is now possible for Alpha-Beta to expand fewer leaf nodes than SSS * (a short example proving this can be found in [Plaat et al., 1994c]).
MTD( +oo) shows up poorly if all nodes visited in the search is used as the performance metric. MTD( +oo) re traverses internal nodes to find the best node to expand next, whereas Alpha-Beta does not.
We conclude that our reformulation together with the results of section 5 contradict the literature on all four points.
4 Drivers for MT
Having seen one driver for MT, the ideas can be en compassed in a generalized driver routine. The driver can be regarded as providing a series of calls to MT to successively refine bounds on the minimax value. By parameterizing the driver code, a variety of algorithms can be constructed. The parameter needed is the first starting bound for MT. Using this parameter, an algo rithm using our MT driver, MTD, can be expressed as MTD(first) (see figure 3). (In [Plaat et al., 1994b] a more general version of MTD is presented, facilitating the con struction of more algorithms.) A number of interesting algorithms can easily be constructed using MTD. Some interesting MTD formulations include:

SSS*. SSS* can be described as MTD(+oo).
DUAL*. In the dual version of SSS* minimization is replaced by maximization, the OPEN list is kept in reverse order, and the starting value is -oo. This algo rithm becomes MTD( -oo) . The advantage of DUAL* over SSS* lies in the search of odd-depth search trees [Marsland et al. , 1987] .
MTD(f). Rather than using +oo or -oo as a first bound, we can start at a value which might be closer to f. Given that iterative deepening is used in many appli cation domains, the obvious approximation for the mini max value is the result of the previous iteration. In MTD terms this algorithm becomes MTD(heuristic-guess). If the initial guess is below the minimax value, MTD(f) can be viewed as a version of DUAL* that started closer to j , otherwise it becomes a version of SSS* that started closer to f .
Other MTD variations possible are: bisecting the in terval [!+, f-] in each pass, using larger step sizes, and searching for the best move (not the best value) [Plaat et al., 1994b] .
Formulating a seemingly diverse collection of algo rithms into one unifying framework focuses attention on the fundamental differences. For example, the frame work allows the reader to see just how similar SSS* and DUAL* really are, and that these are just special cases of calling Pearl's Test (or rather MT). The drivers con cisely capture the algorithm differences. MTD offers us a high-level paradigm that facilitates the reasoning about important issues like algorithm efficiency and memory usage, without the need for low-level details.
By using MT, all MTD algorithms benefit from the maximum number of cutoffs a single bound can gener ate. Each MTD makes a different choice for this bound, which influences the number of cutoffs. Tests show that on average, there is a relationship between the starting bound and the size of the search trees generated: a se quence of MT searches to find the game value benefits from a start value close to the game value. Starting bounds such as +oo or -oo are in a sense the worst possible choices.
Figure 4 validates the choice of a starting bound close to the game value. The figure shows the percentage of unique leaf evaluations of MTD(f) , for Othello; similar results were obtained using chess and checkers. The data points are given as a percentage of the size of the search tree built by our best Alpha-Beta searcher (Aspiration NegaScout). (Since iterative deepening algorithms are used, the cumulative leaf count over all previous depths is shown for depth 8 and 9.) Given an initial guess of h and the minimax value of j, the graph plots the search effort expended for different values of h - f . For each depth the first guess is distorted by the same amount . To the left of the graph, MTD(f) is closer to DUAL*, to the right it is closer to SSS*. A first guess close to f makes MTD(f) perform better than the 100% Aspi· ration NegaScout baseline. The guess must be close to f for the effect to become significant (between -15 and +10 off for Othello, given that values lie in the range [-64, +64]). Thus, if MTD(f) is to be effective, th~ f obtained from the previous iteration must be a good In dicator of the next iteration's value.

5 Experiments
There are three ways to evaluate a new algorithm: anal ysis, simulation or empirical testing. The emphasis in the literature has been on analysis and simulation. This is surprising given the large number of game-playing pro grams in existence.
The mathematical analyses of minimax search algo rithms do a good job of increasing our understanding of the algorithms, but fail to give reliable predictions of their performance. The problem is that the game trees are analyzed using simplifying assumptions; the trees dif fer from those generated by real game-playing programs. To overcome this deficiency, a number of authors have conducted simulations (for example, [Kaindl et al. , 1991; Marsland et al., 1987; Muszycka and Shinghal, 1985]). In our opinion, the simulations did not capture the be havior of realistic search algorithms as they are used in game-playing programs. Instead, we decided to conduct experiments in a setting that was to be as realistic as possible. Our experiments attempt to address the con cerns we have with the parameters chosen in many of the simulations:
- High degree of ordering: most simulations have the quality of their move ordering below what is seen in real game-playing programs.
- Dynamic move re-ordering: simulations use fixed depth searching. Game-playing programs use itera tive deepening to seed memory (transposition table)
with best moves to improve the move ordering. This adds overhead to the search, which is more than off set by the improved move ordering. Also, transposi tions and the history heuristic dynamically re-order the game tree during the search. Proofs that SSS* does not expand more leaf nodes than Alpha-Beta do not hold for the iterative deepened versions of these algorithms.
- Memory: simulations assume either no storage of previously computed results, or unfairly bias their experiments by not giving all the algorithms the same storage. For iterative deepening to be effec tive, best move information from previous iterations must be saved in memory. In game-playing pro grams a transposition table is used. Simulations often use an inconsistent standard for counting leaf nodes . In conventional simulations (for example, [Marsland et al., 1987]) each visit to a leaf node is counted for depth-first algorithms like NegaScout, whereas the leaf is counted only once for best-first algorithms like SSS* (because it was stored in mem ory, no re-expansion occurs).
- Value dependence: some simulations generate the value of a child independent of the value of the par ent. However, there is usually a high correlation between the values of these two nodes in real games.
The net result is that iterative deepening and mem ory improve the move ordering beyond what has been used in most simulations. Besides move ordering the other three differences between artificial and real trees can cause problems in simulations. Just increasing the move ordering to 98% is not sufficient to yield realis tic simulations. As well, simulations are concerned with tree size, but practitioners are concerned with execution time. Simulation results do not necessarily correlate well with execution time. For example, there are many pa pers showing SSS* expands fewer leaf nodes than Alpha Beta. However, SSS* implementations using Stockman's original formulation have too much execution overhead to be competitive with Alpha-Beta [Roizen and Pearl, 1983].
5.1 Experiment Design
To assess the feasibility of the proposed algorithms, a series of experiments was performed to compare Alpha-Beta, NegaScout, SSS* (MTD(+oo)), DUAL* (MTD(-oo)), MTD(J) (and other variants, see [Plaat et al. , 1994b]).
Rather than use simulations, our data has been gathered from three game-playing programs: Chinook (checkers), Keyano (Othello), and Phoenix (chess). All three programs are well-known in their respective do main. For our experiments, we used the program au thor's search algorithm which, presumably, has been highly tuned to the application. The only change we made was to disable search extensions and forward prun ing. All programs used iterative deepening. The MTD algorithms would be repeatedly called with successively deeper search depths. All three programs used a stan dard transposition table with 2 21 entries. For our experiments we used the program author's original transposi tion table data structures and table manipulation code.
Conventional test sets in the literature proved to be poor predictors of performance. Test set positions are selected, usually, to test a particular characteristic or property of the game and are not indicative of typical game conditions. By using a sequences of moves from real games as the test positions, we are attempting to create a test set that is representative of real game search properties.
All three programs were run on 20 balanced test posi tions, searching to a depth so that all searched roughly the same amount of time. (A number of test runs was performed on a bigger test set and to a higher search depth to check that the 20 positions did not cause anomalies.) In checkers, the average branching factor is approximately 3 (1.2 moves in a capture position; 8 in a non-capture position), in Othello it is 10 and in chess it is 36. The branching factor determined the maximum search depth for our experiments: 17 ply for Chinook, 10 ply for Keyano, and 8 ply for Phoenix.
Many papers in the literature use Alpha-Beta as the base line for comparing the performance of other algo rithms (for example, [Campbell and Marsland, 1983]). The implication is that this is the standard data point which everyone is trying to beat . However, game-playing programs have evolved beyond simple Alpha-Beta algo rithms. Therefore, we have chosen to use the current al gorithm of choice as our base line: aspiration window en hanced NegaScout [Campbell and Marsland, 1983]. The graphs in figure 4 show the cumulative number of nodes over all previous iterations for a certain depth (which is realistic since iterative deepening is used) , relative to Aspiration NegaScout.
To our knowledge this is the first comparison of algo rithms like Alpha-Beta, NegaScout, SSS* and DUAL* where all algorithms are given the exact same resources.
5.2 Experiment Results
Figure 5 shows the performance of Phoenix for (unique) leaf evaluations (NBP or number of bottom positions), and Figure 6 shows the total node count (leaf, interior, and transposition nodes). The total node count includes all revisits to previously searched nodes. Although most simulations only report NBP, we find that the total node count has a higher correlation with execution time for some algorithms. Detailed results for all the games can be found in [Plaat et al., 1994b].
Over all three games, the best results are from MTD(J). Its leaf node counts are consistently better than Aspiration NegaScout, averaging at least a 5% improvement . More surprisingly is that MTD(J) out performs Aspiration NegaScout on the total node mea sure as well. Since each iteration requires repeated calls to MT (at least two and possibly many more) , one might expect MTD(J) to perform badly by this measure be cause of the repeated traversals of the tree. This sug gests that MTD(J), on average, is calling MT close to the minimum number of times. For all three programs, MT gets called between 3 and 4 times on average. In con trast, the SSS* and DUAL* results are poor compared to NegaScout when all nodes in the search tree are con sidered. Each of these algorithms performs dozens and sometimes even hundreds of MT searches, depending on how wide the range of leaf values is.


Implementing SSS* as an instance of MTD yields re sults that run counter to the literature. SSS* is now as easy to implement as Aspiration NegaScout, uses as much storage and has no additional execution overhead, but performs generally worse when viewed in the context of iterative deepening and transposition tables. DUAL* is more efficient than SSS* but still comes out poorly in all the graphs measuring total node count. Sometimes SSS* expands more leaf nodes than Alpha-Beta (as dis cussed in section 3), contradicting both the analytic and simulation results for fixed-depth SSS* and Alpha-Beta. An interesting observation is that the effectiveness of SSS* appears to be a function of the branching factor; the larger the branching factor, the better it performs.
Given these results, some of the algorithmic differences can be explained. If we know the value of the search tree is j, then two searches are required: MT(f -c-), which fails high establishing a lower bound on f, and MT(f + c-), which fails low and establishes an upper bound on f- The closer the approximation to f, the less the work that has to be done (according to figure 4). As that figure indicated, the performance of MTD(f) is dependent on the quality of the score that is used as the first-guess. For programs with a pronounced odd/even oscillation in their score, results are better if not the score of the previous iterative deepening pass is used, but the one from 2 passes ago. Considering this, it is not a surprise that both DUAL* and SSS* come out poorly. Their initial bounds for the minimax value are poor, meaning that the many calls to MT result in sig nificantly more interior as well as leaf nodes. NegaScout used a wide window for the principal variation (PV) and all re-searches. The wide-window search of the PV gives a good first approximation to the minimax value. That approximation is then used to search the rest of the tree with minimal window searches-which are equiv alent to MT calls. If these refutation searches are suc cessful (no re-search is needed), then NegaScout deviates from MTD(f) only in the way it searches the PV for a value, the wider window causing less cutoffs. MTD(f) uses MT for searching all nodes, including the PV.

The bottom line for practitioners is execution time. Since we did not have the resources to run all our ex periments on identical and otherwise idle machines , we only show execution time graphs for MTD(f) in fig ure 7. Comparing results for the same machines we found that MTD(f) is on average consistently the fastest algo rithm. In our experiments we found that for Chinook and Keyano MTD(f) was about 5% faster in execution time than Aspiration NegaScout, for Phoenix we found MTD(f) 9-13% faster. For other programs and other machines these results will obviously differ, depending in part on the quality of the score of the previous iteration, and on the test positions used. Also, since the tested algorithms perform relatively close together, the relative differences are quite sensitive to variations in input pa rameters. In generalizing these results, one should keep this sensitivity in mind. Using these numbers as absolute predictors for other situations would not do justice to the complexities of real-life game trees. We refer to [Plaat et al., 1994b) for the remainder of our experimental data and explanations.
Basing one's conclusions only on simulations can be hazardous. For example, the general view is that SSS* is (1) difficult to understand, (2) has unreasonable mem ory requirements, (3) is slow, ( 4) provably dominates Alpha-Beta in expanded leaves, and (5) that it expands significantly fewer leaf nodes than Alpha-Beta. A re cent paper used simulations to show that point 2 and 3 could be wrong [Reinefeld and Ridinger, 1994], paint ing an altogether favorable picture for SSS*. Using real programs, we showed that all five points are wrong, mak ing it clear that , although SSS* is practical, in realistic programs it has no substantial advantage over Alpha Beta-variants like Aspiration NegaScout . We think that only real programs provide a valid basis for conclusions.
6 Conclusions
Over thirty years of research have been devoted to im proving the efficiency of Alpha-Beta searching. The MT family of algorithms are comparatively new, without the benefit of intense investigations. Yet, MTD(f) is already out-performing our best Alpha-Beta based implementa tions in real game-playing programs. MT is a simple and elegant paradigm for high performance game-tree search algorithms. It eliminates all the perceived drawbacks of SSS* in practice.
The purpose of a simulation is to reliably model an algorithm to gain insight into its performance. Simu lations are usually performed when it is too difficult or too expensive to construct the proper experimental en vironment. For game-tree searching, the case for simu lations is weak. There is no need to do simulations when there are quality game-playing programs available for ob taining actual data. Further, as this paper has demon strated, simulation parameters can be incorrect, result ing in large errors in the results that lead to misleading conclusions . In particular, the failure to include iterative deepening, transposition tables, and almost perfectly or dered trees in many simulations are serious omissions.
Although a 10% improvement for Chess may not seem much, it comes at no extra algorithmic complexity: just a standard Alpha-Beta-based Chess program plus one while loop. Binary-valued searches enhanced with it erative deepening, transposition tables and the history heuristic is an efficient search method that uses no ex plicit knowledge of the application domain. It is remark able that one can search almost perfectly without explic itly using application-dependent knowledge other than the evaluation function.
Acknowledgements
This work has benefited from discussions with Mark Brockington (author of Keyano) , Yngvi Bjornsson and Andreas Junghanns. The financial support of the Dutch Organization for Scientific Research (NWO), the Natural Sciences and· Engineering Research Council of Canada (grant OGP-5183) and the University of Alberta Cen tral Research Fund are gratefully acknowledged.
@inproceedings{ijcai1995p36,
title = {Best-First Fixed-Depth Game-Tree Search in Practice},
author = {Plaat, Aske and Schaeffer, Jonathan and Pijls, Wim and de Bruin, Arie},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {273--280},
year = {1995},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1995/36},
}
TY - CPAPER TI - Best-First Fixed-Depth Game-Tree Search in Practice AU - Plaat, Aske AU - Schaeffer, Jonathan AU - Pijls, Wim AU - de Bruin, Arie T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 273 EP - 280 UR - https://ijcai.org/proceedings/1995/36 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: