Publications, Reports, and Preprints on Minimax Search Algorithms

Selected Publications

• Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin:
  Best-First Fixed-Depth Minimax Algorithms,
  In: Artificial Intelligence, Volume 87(1-2), November 1996, page 255-293.
  In publications on minimax algorithms, SSS* is usually praised for building small search trees, and chided for its excessive memory usage (as well as its complicated formulation). We present a new formulation which turns this view upside down: the formulation is very simple, tests in practice show that its memory requirements are perfectly acceptable, and, most importantly, that it does not out-perform depth-first Alpha-Beta variants. In fact, SSS* itself is formulated as a special case of Alpha-Beta. Furthermore, a new best-first algorithm called MTD(f) is presented, which does out-perform the algorithms that are currently used in practice. 40 pages. Abstract
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin:
  Exploiting Graph Properties of Game Trees
  Proceedings of the 13th National Conference on Artificial Intelligence (AAAI'96), August 4-8, 1996, Portland, Oregon. AAAI/MIT Press, Volume 1, page 234-239.
  Traditionally, game tree researchers have thought of the game graph as a tree. The paper shows that this focus has obscured some important properties of actual game graphs, which can be exploited to create a smaller minimal graph, showing that in practice there is more room for improvement of minimax algorithms than previously assumed. Two improvements for on-line algorithms such as Alpha-Beta that exploit this room are presented. 6 pages.
• Aske Plaat
  Research Re: search & Re-search,
  PhD Thesis, Tinbergen Institute and Department of Computer Science, Erasmus University Rotterdam, Thesis Publishers, Amsterdam, The Netherlands, June 20, 1996.
  In-depth treatment of the topics of the AIJ and AAAI96 papers: After giving an overview of current minimax search algorithms such as Alpha-Beta and SSS*, a reformulation of SSS*'s best-first expansion strategy facilitates the formulation of new, more efficient, algorithms. The reformulation sheds new light on the memory requirements of SSS*-like algorithms, showing that these algorithms are actually feasible in practice. Furthermore, an investigation into the structure of the minimal tree in practice identifies an area where further improvements can be found. 180 pages. Abstract
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin:
  Best-First Fixed-Depth Game-Tree Search in Practice,
  In Fourteenth International Joint Conference on Artificial Intelligence, IJCAI'95, Montreal, Canada, volume 1, pages 273-279, August 1995, Postscript, 179KB.
  A short overview on SSS* and MTD(f), based on early results which led to the AIJ article. 7 pages.

Other Work