Proceedings

Best-First Fixed-Depth Game-Tree Search in Practice

Download BibTeX Cite

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.

  1. [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.
  2. [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.
  3. T. Ibaraki. Generalization of alpha-beta and SSS* search procedures. Artificial Int elligence, 29:73-117, 1986.
  4. [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.
  5. [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.
  6. [Marsland et al., 1987] T.A. Marsland , A. Reinefeld , and J. Schaeffer. Low overhead alternatives to SSS* . Artificial Intelligence, 31:185-199, 1987.
  7. [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.
  8. [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.
  9. [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.
  10. [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.
  11. [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.
  12. [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.
  13. [Reinefeld and Ridinger , 1994] A. Reinefeld and P. Ridinger. Time-efficient state space search. Ar- tificial Intelligence, 71(2):397-408, 1994.
  14. [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.
  15. [Schaeffer, 1989] J. Schaeffer. The history heuristic and alpha-beta search enhancements in practice. IEEE PAM!, 11(1) :1203-1212, 1989.
  16. [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.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards