Publications, Reports, and Preprints on Minimax Search Algorithms

Other Work

• Charles E. Leiserson and Aske Plaat:
  Programming Parallel Applications in Cilk,
  Submitted for publication, 1997.
  An overview of the Cilk parallel programming system. 13 pages.
• Jonathan Schaeffer and Aske Plaat:
  New Advances in Alpha-Beta Searching,
  In Proceedings of the 24th ACM Computer Science Conference, February 16-18, 1996, pp. 124-130.
  A short discussion of three practical improvements of Alpha-Beta: 1) improved handling of fail lows, 2) making better use of transpositions, and 3) MTD(f). 7 pages.
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin:
  Best-First and Depth-First Minimax Search in Practice,
  In Proceedings of Computing Science in the Netherlands 1995, Utrecht, the Netherlands, November 27-28, 1995, pages 182-193, Postscript, 85KB.
  Discusses performance and memory usage of Alpha-Beta and SSS*. 12 pages.
  A slightly longer version with a more technical flavor has been presented as:
  An Algorithm Faster than NegaScout and SSS* in Practice,
  at the Computer Strategy Game Programming Workshop at the World Computer Chess Campionship, May 26, 1995, Hong Kong, Postscript, 109KB.
• Arie de Bruin, Wim Pijls, and Aske Plaat:
  Solution Trees as a Basis for Game Tree Search,
  ICCA Journal, volume 17, number 4, december 1994, pages 207-218. Postscript, 170KB.
  Theoretical issues in the relation of Alpha-Beta and SSS* are discussed. 17 pages.
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin:
  A Minimax Algorithm Better than Alpha-Beta? No and Yes,
  Technical Report 95-15, Department of Computing Science, University of Alberta, June 1995. Postscript, 426KB. Compressed, 161KB.
  An extended version of the AIJ article. 46 pages.
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin:
  SSS* = Alpha-Beta + TT,
  Technical Report 94-17, Department of Computing Science, University of Alberta, December 1994. Postscript, 256KB.
  Discusses the relation between Alpha-Beta and SSS*. Analyzes memory use and performance using three tournament game playing programs. 32 pages.
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin:
  A New Paradigm for Minimax Search,
  Technical Report 94-18, Department of Computing Science, University of Alberta, December 1994. Postscript, 261KB.
  Tests with three tournament programs of Alpha-Beta, NegaScout, SSS*, and a new algorithm, MTD(f). As you probably guessed, the new one wins. 24 pages.
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin:
  Nearly Optimal Minimax Tree Search?,
  Technical Report 94-19, Department of Computing Science, University of Alberta, December 1994. Postscript, 160KB.
  Most people use Alpha-Beta's best case as the minimal tree that proves the minimax value. This report shows that in practice a graph that is substantially smaller can be constructed, showing that there is more room for improving full-width minimax algorithms than was previously assumed. 17 pages.
• Arie de Bruin, Wim Pijls, and Aske Plaat:
  Solution Trees as a Basis for Game Tree Search,
  Technical Report EUR-CS-94-04, Erasmus University Rotterdam, May 1994. Postscript, 155KB.
  Some theory on the relation between Alpha-Beta and SSS*, based on solution trees, and simulations of a number of algorithms on artificial trees. 19 pages.
• Aske Plaat:
  Vereenvoudiging van gedistribueerde applicatie ontwikkeling,
  Master's thesis (in Dutch), June 1992, Erasmus University Rotterdam. 185 pages.