A Bibliography on Minimax Trees^{∗}

Claude G. Diderich^{†} Swiss Federal Institute of Technology, Lausanne Department of Computer Science, Theoretical Computer Science Lab

April 2nd, 1993

This article lists all theoretical and practical papers, theses and reports known to the author on the subject of studying minimax trees and analyzing sequential and parallel minimax tree search algorithms.

The items of the bibliography are listed in alphabetical order in accordance with the first author’s name. Items not marked are in my collection or are available to me (if there are any hard-to-obtain items in this group, I would be happy to make copies of them available). Others, e.g. items marked with a star (^{∗}), are cited elsewhere as relevant, but are yet unavailable to me (I would appreciate receiving copies of these from anyone who has access to them).

This bibliography is available in computer readable BibTEX form by sending an e-mail request to the author or by anonymous ftp from valkyries.andrew.cmu.edu in directory /pub/chess/texts. The labels indicated are the keys used in the BibTEX version of the bibliography. Any corrections as well as new items to this bibliography are kindly requested and highly appreciated in advance. Finally the author wishes to thank all the people who have helped in building this bibliography.

References

[Abra88] Bruce Abramson and Richard E. Korf. A model of two-player evaluation functions. In Proceedings of the Sixth National Conference on Artificial Intelligence (AAAI-87), pages 90–94, Seattle, WA, July 1987.

[Abra89] Bruce Abramson. Control strategies for two-player games. ACM Computing Surveys, 21(2):137–161, June 1989.

[Akl79] Selim G. Akl, David T. Barnard, and Ralph J. Doran. Searching game trees in parallel. Technical report, Queen’s University, Department of Computing and Information Science, November 1979. ^{∗}.

[Akl80] Selim G. Akl, David T. Barnard, and Ralph J. Doran. Simulation and analysis in deriving time and storage requirements for a parallel alpha-beta algorithm. In International Conference on Parallel Processing, pages 231–234, 1980.

[Akl82] Selim G. Akl, David T. Barnard, and Ralph J. Doran. Design, analysis, and implementation of a parallel tree search algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-4(2):192–203, March 1982.

[Akl89] Selim G. Akl. The Design and Analysis of Parallel Algorithms, chapter 12 – Traversing Combinatorial Spaces, pages 310–340. Prentice Hall, Englewood Cliffs, NJ, 1989.

[Almq88] Kenneth Almquist, Neil McKenzie, and Kenneth Sloan. An inquiry into parallel algorithms for searching game trees. Technical Report 88-12-03, University of Washington, Department of Computer Science, Seattle, WA, December 1988.

∗A previous version of this paper has been published in the “Bulletin of the EATCS”, Number 49, February 1993.

†Author’s address: Claude G. Diderich, 30, Avenue S. Reymondin, CH-1009 Pully, Switzerland, e-mail:

diderich@dma.epfl.ch

[Alth88] Ingo Althöfer. A parallel game tree search algorithm with a linear speedup. Technical report, University of Bielefeld, Faculty for Mathematics, Bielefeld, Germany, December 1988. submitted to Journal of Algorithms, accepted 1992.

[Alth90] Ingo Althöfer. An incremental negamax algorithm. Artificial Intelligence, 43:57–65, 1990.

[Alth91] Ingo Althöfer and Bernhard Balkenhol. A game tree with distinct leaf values which is easy for the alpha-beta algorithm. Artificial Intelligence, 52:183–190, 1991.

[Amig91] Claude Amiguet. Contrôleurs Distribués pour la Programmation Heuristique. PhD thesis, Swiss Federal Institute of Technology, Department of Computer Science, Lausanne, Switzerland, 1991. In french.

[Bal86a] Henri E. Bal and Robbert van Renesse. Parallel alpha-beta search. In Proceedings NGI-SION Symposium Stimulerende Informatica, pages 379–385, Utrecht, Netherlands, April 1986.

[Ball83] Bruce W. Ballard. The *-minimax search procedure for trees containing chance nodes. Artificial Intelligence, 21:327–350, 1983.

[Ball86b] Henri E. Bal and Robbert van Renesse. A summary of parallel alpha-beta search results. ICCA Journal, 9(3):146–149, September 1986. ^{∗}.

[Baud78a] Gérard M. Baudet. On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence, 10:173–199, 1978.

[Baud78b] Gérard M. Baudet. The Design and Analysis of Algorithms for Asynchronous Multiprocessors. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, 1978.

[Beal80] D. F. Beal. Advances in Computer Chess 2, chapter An Analysis of Minimax, pages 103–109. Edinburgh University Press., 1980. Editor: M. R. B. Clarke.

[Berl75] Hans Jack Berliner. Chess as Problem Solving. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, 1975.

[Berl89] Hans Jack Berliner and Carl Eberling. Pattern knowledge and search: The SUPREME architecture. Artificial Intelligence, 38(2):161–198, 1989.

[Berl90] Hans Jack Berliner, Gordon Goetsch, Murray S. Campbell, and Carl Ebeling. Measuring the performance potential of chess programs. Artificial Intelligence, 43(1):7–21, April 1990.

[Bohm89] Max Böhm and Ewald Speckenmeyer. A dynamic processor tree for solving game trees in parallel. Technical report, University of Dortmund, Fachbereich Informatik, Dortmund, Germany, 1989.

[Bord90] Andrei Z. Broder, Anna R. Karlin, Prabhakar Raghavan, and Eli Upfal. On the parallel complexity of evaluating game-trees. Technical Report RR RJ 7729, IBM Research Division, October 1990. ^{∗}.

[Brat82] I. Bratko and M. Gams. Advances in Computer Chess 3, chapter Error Analysis of the Minimax Principle, pages 1–15. Pergamon Press, 1982. Editor: M. R. B. Clarke.

[Camp83] Murray S. Campbell and T. A. Marsland. A comparison of minimax tree search algorithms. Artificial Intelligence, 20:347–367, 1983.

[Chak92] P. P. Chakrabarti and S. Ghose. A general best first search algorithm in and/or graphs. Journal of Algorithms, 13(2):177–187, June 1992.

[Cung91] Van-Dat Cung and Catherine Roucairol. Parallel minimax tree searching. RR 1549, INRIA, November 1991. In French, will appear in English.

[Darw83] Nevin M. Darwish. A quantitative analysis of the alpha-beta pruning algorithm. Artificial Intelligence, 21:405–433, 1983.

[Dide92] Claude G. Diderich. Evaluation des performances de l’algorithme SSS* avec phases de synchronisation sur une machine parallèle à mémoires distribuées. Technical report, Swiss Federal Institute of Technology, Department of Computer Science, Laboratory for Theoretical Computer Science, Lausanne, Switzerland, June 1992. In french.

[Feld87] Rainer Feldmann and Peter Mysliwietz. Parallele Spielbaumsuche. Master’s thesis, University of Paderborn, Paderborn, Germany, December 1987. Diplomarbeit, In german.

[Feld89] Rainer Feldmann, Burkhard Monien, Peter Mysliwietz, and Oliver Vornberger. Distributed game tree search. ICCA Journal, 12(2):65–73, 1989. ^{∗}.

[Feld90a] Rainer Feldmann, Burkhard Monien, Peter Mysliwietz, and Oliver Vornberger. Distributed game tree search. In Laveen N. Kanal Vipin Kumar, P. S. Gopalakrishnan, editor, Parallel Algorithms for Machine Intelligence and Vision, pages 66–101. Springer-Verlag, 1990.

[Feld90b] Rainer Feldmann, Peter Mysliwietz, and Burkhard Monien. Advances in Computer Chess 6, chapter 1 — A Fully Distributed Chess Program, pages 1–27. Ellis Horwood, 1990. Editor: D. Beal.

[Feld90c] Burkhard Monien Rainer Feldmann, Peter Mysliwietz. Spielbaumsuche auf einem Transputernetzwerk. In Parallel - Algorithmen und -Rechnerstrukturen (PARS), Workshop Sprachen und Systeme zur Parallelverarbeitung. Gesellschaft für Informatik, January 1990. In german.

[Feld91a] Rainer Feldmann, Peter Mysliwietz, and Burkhard Monien. Distributed game tree search on a massively parallel system. In Th. Ottmann B. Monien, editor, Data structures and efficient algorithms: Final report on the DFG special joint initiative, volume LNCS 594, pages 270–288. Springer-Verlag, September 1991.

[Feld91b] Rainer Feldmann, Peter Mysliwietz, and Burkhard Monien. Experiments with a fully distributed chess program. In V. Allis J. van den Herik, editor, Heuristic Programming in Artificial Intelligence 3, pages 72–87, 1991. Also in: Tech.Report, University Paderborn, Paderborn, Germany.

[Felt88] E. W. Felten and S. W. Otto. Chess on a hypercube. In Geoffrey Fox, editor, The Third Conference on Hypercube Concurrent Computers and Applications, volume II-Applications, pages 1329–1341, Passadena, CA, 1988.

[Ferg88] C. Ferguson and Richard E. Korf. Distributed tree search and its application to alpha-beta pruning. In Proceedings of the Seventh National Conference Artificial Intelligence (AAAI-88), pages 128–132, Minneapolis, MN, August 1988.

[Fink80] Raphael A. Finkel and John P. Fishburn. Parallel alpha-beta search on arachne. In IEEE International Conference on Parallel Processing, pages 235–243, 1980. ^{∗}.

[Fink82] Raphael A. Finkel and John P. Fishburn. Parallelism in alpha-beta search. Artificial Intelligence, 19:89–106, 1982.

[Fink83] Raphael A. Finkel and John P. Fishburn. Improved speedup bounds for parallel alpha-beta search. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-5(1):89–92, 1983.

[Fish84] John P. Fishburn. Analysis of Speedup in Distributed Algorithms, volume 14 of Computer Science: Distributed Database Systems, chapter 4 – Parallel Alpha-Beta Search, pages 11–54. UMI Research Press, 1984. Revision of thesis (PhD) – University of Wisconsin, Madison, 1981.

[Full73] S. H. Fuller, J. G. Gaschnig, and J. J. Gillogly. An analysis of the alpha-beta pruning algorithm. Technical report, Carnegie-Mellon University, Department of Computer Science, Pittsburgh, July 1973. ^{∗}.

[Hewe92] R. Hewett and K. Ganesan. Consistent linear speedup in parallel alpha-beta search. In ICCI’92, Computing and Information, pages 237–240. IEEE Computer Society Press, 1992. ∗.

[Hiro87] Usui Hiromoto, Yamashita Masafumi, Imai Masaharu, and Toshihide Ibaraki. Parallel searches of game trees. Systems and Computers in Japan, 18(8):97–109, 1987.

[Hora90] Helmut Horacek. Reasonning with uncertainty in computer chess. Artificial Intelligence, 43:37–56, 1990.

[Hsu89] Feng-Hsiung Hsu, T. S. Anantharaman, Murray S. Campbell, and A. Nowatzyk. Computers, Chess, and Cognition, chapter 5 Deep Thought, pages 55–78. Springer Verlag, 1990.

[Hsu90] Feng-Hsiung Hsu. Large Scale Parallelization of Alpha-Beta Search: An Algorithmic and Architectural Study with Computer Chess. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, February 1990.

[Hunt88] Matthew M. Huntbach and F. Warren Burton. Alpha-beta search on virtual tree machines. Information Sciences, 44:3–17, 1988. ^{∗}.

[Hyat89] R. M. Hyatt and B. W. Suter. A parallel alpha/beta tree searching algorithm. Parallel Computing, 10:299–308, 1989.

[Ibar86] Toshihide Ibaraki. Generalization of alpha-beta and SSS* search procedures. Artificial Intelligence, 29:73–117, 1986.

[Ibar87] Toshihide Ibaraki. Game solving procedure H* is unsurpassed. In D. S. Johnson and al., editors, Discrete Algorithms and Complexity, pages 185–200. Academic Press, Inc., 1987.

[Ibar91a] Toshihide Ibaraki. Search algorithms for minimax game trees. In Comference: Twenty Years NP-Completeness, Sicily, Italy, June 1991. ^{∗}.

[Ibar91b] Toshihide Ibaraki and Yoshiroh Katoh. Searching minimax game trees under memory space constraint. Annals of Mathematics and Artificial Intelligence, 1:141–153, 1990.

[Kain91] Hermann Kaindl, Reza Shams, and Helmut Horacek. Minimax search algorithms with and without aspiration windows. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-13(12):1225–1235, December 1991.

[Karp89] Richard M. Karp and Yanjun Zhang. On parallel evaluation of game trees. In First ACM Annual symposium on parallel algorithms and architectures (SPAA’89), pages 409–420, New York, NY, 1989. ACM.

[Kato88] Y. Katoh and Toshihide Ibaraki. Game solving procedure SSS* is unsurpassed. Systems and computers in Japan, 19(7):93–103, 1988.

[Klei90] Theo Klein Paste and Patrick van der Laag. An analysis of the SSS* algorithm. Master’s thesis, Erasmus University Rotterdam, Rotterdam, NL, 1990. ^{∗}.

[Knut75] Donald E. Knuth and Ronald W. Moore. An analysis of alpha-beta pruning. Artificial Intelligence, 6(4):293–326, 1975.

[Korf85] Richard E. Korf. Iterative deepening: An optimal admissible tree search. Artificial Intelligence, 27:97–109, 1985.

[Korf89] Richard E. Korf. Generalized game trees. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-89), pages 328–333, Detroit, MI, August 1989.

[Korf90] Richard E. Korf. Depth-limited search for real-time problem solving. The Journal of Real-Time Systems, pages 7–24, 1990.

[Korf91] Richard E. Korf. Multi-player alpha-beta pruning. Artificial Intelligence, 48(1):99–111, February 1991.

[Kraa90] H.-J. Kraas. Zur Parallelisierung des SSS*-Algorithmus. PhD thesis, University of Braunschweig, Braunschweig, Germany, 1990. In german, ^{∗}.

[Kuma83] Vipin Kumar and Laveen N. Kanal. A general branch and bound formulation for understanding and synthesizing and/or tree search procedures. Artificial Intelligence, 21:179–198, 1983.

[Kuma84] Vipin Kumar and Laveen N. Kanal. Parallel branch-and-bound formulations for AND/OR tree search. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6(6):768–778, November 1984.

[Kuma88] Vipin Kumar and Laveen N. Kanal. A general branch and bound formulation for and/or graph and game tree search. In Search in Artificial Intelligence. Springer Verlag, 1988.

[Leif85] Daniel B. Leifker and Laveen N. Kanal. A hybrid SSS*/alpha-beta algorithm for parallel search of game trees. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-85), pages 1044–1046, 1985.

[Leve92] Willem G. Levelt, M. Frans Kaashoek, Henri E. Bal, and Andrew S. Tanenbaum. A comparison of two paradigms for distributed shared memory. Software: Practice and Experience, 22(11):985–1010, November 1992.

[Li90] Liwu Li and T. A. Marsland. Probability-based game tree pruning. Journal of Algorithms, 11(1):27–43, March 1990.

[Lind83] Gary Lindstrom. The key node method: A highly-parallel alpha-beta algorithm. Technical Report UUCS 83-101, University of Utah, Department of Computer Science, Salt Lake City, March 1983. ^{∗}.

[Low91] Chin-Chau Low. Parallel game tree searching with lower and upper bounds. Master’s thesis, University of Illinois at Urbana Campaign, IL, 1991.

[Mars82] T. A. Marsland and Murray S. Campbell. Parallel search of strongly ordered game trees. ACM Computing Surveys, 14(4):533–551, December 1982.

[Mars83a] T. A. Marsland. Relative efficiency of alpha-beta implementations. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-83), pages 763–766, Karlsruhe, Germany, August 1983. ^{∗}.

[Mars83b] T. A. Marsland and Fred Popowich. Multiprocessor tree searching system design. Technical Report TR 83-06, University of Alberta, Department of Computer Science, Edmonton, Canada, July 1983.

[Mars85] T. A. Marsland and Fred Popowich. Parallel game-tree search. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-7(4):442–452, July 1985.

[Mars87] T. A. Marsland, Alexander Reinefeld, and Jonathan Schaeffer. Low overhead alternatives to SSS*. Artificial Intelligence, 31:185–199, 1987.

[Mars88] T.A. Marsland, M. Olafsson, and Jonathan Schaeffer. Multiprocessor Tree-Search Experiments, pages 37–51. Pergamon Press, 1986. D.F. Beal (Editor).

[McAl88] David Allen McAllester. Conspiracy numbers for min-max searching. Artificial Intelligence, 35:287–310, 1988.

[Meul90] M. van der Meulen. Conspiracy number search. ICCA Journal, 13(1):3–14, March 1990. ∗.

[Mich83] Gerard P. Michon. Recursive Random Games: A Probabilistic Model for Perfect Information Games. PhD thesis, University of California at Los Angeles, Computer Science Department, Los Angeles, CA, 1983.

[Moni87] Burkhard Monien and Oliver Vornberger. Parallel processing of combinatorial search trees. In Proceedings International Workshop on Parallel Algorithms and Architectures, Math. Research Nr. 38, Akademie - Verlag Berlin, pages 60–69, 1987. ^{∗}.

[Nau82] Danna S. Nau. The last player theorem. Artificial Intelligence, 18:53–65, 1982.

[Nau83] Danna S. Nau. Pathology on game trees revisited, and an alternative to minimaxing. Artificial Intelligence, 21:221–244, 1983.

[Newb77] Monroe M. Newborn. The efficiency of the alpha-beta search on trees with branchdependent terminal node scores. Artificial Intelligence, 8:137–153, 1977.

[Newb88] Monroe M. Newborn. Unsynchronized iteratively deepening parallel alpha-beta search. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-10(5):687–694, 1988.

[Nils80] Nils J. Nilsson. Principles of Artificial Intelligence. Tioga Publishing Company, Palo Alto, CA, 1980.

[Pear80] Judea Pearl. Asymptotical properties of minimax trees and game searching procedures. Artificial Intelligence, 14(2):113–138, 1980.

[Pear82] Judea Pearl. The solution for the branching factor of the alpha-beta pruning algorithm and its optimality. Communications of the ACM, 25(8):559–564, August 1982.

[Pear83] Judea Pearl. On the nature of pathology in game searching. Artificial Intelligence, 20:427–453, 1983.

[Pear84] Judea Pearl. Heuristics – Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishing Co., Reading, MA, 1984.

[Pijl91] Wim Pijls. Shortest Paths and Game Trees. PhD thesis, Erasmus University Rotterdam, Rotterdam, NL, November 1991.

[Pijl92a] Wim Pijls and Arie Bruin. Another view of the SSS* algorithm. Technical report, Erasmus University Rotterdam, Rotterdam, NL, January 1992. Also in: Algorithms, Proceedings of the International Symposium, SIGAL’90, Tokyo, Japan, Aug. 1990.

[Pijl92b] Wim Pijls and Arie Bruin. Searching informed game trees. Technical report, Erasmus University Rotterdam, Rotterdam, NL, 1992. Extended abstract. Also in: Proceedings CSN ’92 (Computer Science in the Netherlands), Mathematical Center, Amsterdam, 1992.

[Pijl92c] Wim Pijls and Arie Bruin. Searching informed game trees. Technical Report EUR-CS-92-02, Erasmus University Rotterdam, Rotterdam, NL, October 1992.

[Popo83] Fred Popowich and T. A. Marsland. Parabelle: Experiences with a parallel chess program. Technical Report TR 83-07, University of Alberta, Department of Computer Science, Edmonton, Canada, August 1983. ^{∗}.

[Powl90] C. Powley, C. Ferguson, and Richard E. Korf. Parallel heuristic search: Two approaches, pages 42–65. Springer-Verlag, 1990. Edited by V. Kumar, P. S. Gopalakrishnan and L.N.

[Powl91] C. Powley and Richard E. Korf. Single agent parallel window search. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-13(5):466–477, May 1991.

[Prak88] Bettadapu Prakash and T. A. Marsland. Accuracy and savings in depth-limited capture search. International Journal of Man-Machine Studies, 29(6):497–502, 1988.

[Rein85] Alexander Reinefeld, Jonathan Schaeffer, and T. A. Marsland. Information acquisition in minimal window search. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-85), volume 2, pages 1040–1043, 1985.

[Rein89] Alexander Reinefeld. Spielbaum Suchverfahren, volume Informatik-Fachberichte 200. Springer Verlag, 1989.

[Reza92] Jaleh Rezaie and Raphael Finkel. A comparison of some parallel game-tree search algorithms. Technical report, University of Kentucky, Department of Computer Science, Lexington, USA, 1992.

[Rive87] Ronald L. Rivest. Game tree searching by min/max approximation. Artificial Intelligence, 34(1):77–96, 1987.

[Roiz81] Igor Roizen. On the average number of terminal nodes examined by alpha-beta. Technical Report UCLA-ENG-CSL-8108, University of California at Los Angeles, Cognitive Systems Laboratory, Los Angeles, CA, 1981. ^{∗}.

[Roiz83] Igor Roizen and Judea Pearl. A minimax algorithm better than alpha-beta? yes and no. Artificial Intelligence, 21:199–230, 1983.

[Scha83] Jonathan Schaeffer. The history heuristic. ICCA Journal, 6(3):16–19, 1983. ^{∗}.

[Scha89a] Jonathan Schaeffer. Distributed game-tree searching. Journal of Parallel and Distributed Computing, 6:90–114, 1989.

[Scha89b] Jonathan Schaeffer. The history heuristic and alpha-beta search enhancements in practice. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-11(1):1203– 1212, November 1989.

[Scha90] Jonathan Schaeffer. Conspiracy numbers. Artificial Intelligence, 43:67–84, 1990.

[Schr86] G. Schrüfer. Advances in Computer Chess 4, chapter Presence and Absence of Pathology on Game Trees, pages 101–112. Pergamon Press, 1986. Editor: D. F. Beal.

[Schr88] G. Schrüfer. Minimax-Suchen Kosten, Qualität und Algorithmen. PhD thesis, University of Braunschweig, Braunschweig, West Germany, 1988. In german, ^{∗}.

[Shan50] Claude E. Shannon. Programming a computer for playing chess. Philosophical Magazine, 41:256–275, 1950. ^{∗}.

[Shen85] Chien-Chung Shen and Wen-Hsiang Tsai. A graph matching approach to optimal task assignment in distributed computing systems using a minimax criterion. IEEE Transactions on Computers, C-34:197–203, March 1985.

[Shin91] Rajjan Shinghal and Sofia Shved. Proposed modifications to parallel state space search of game trees. International Journal of Pattern Recognition and Artificial Intelligence, 5(5):809–833, 1991.

[Slag69] James H. Slagle and John K. Dixon. Experiments with some programs that search game trees. Journal of the ACM, 16(2):189–207, April 1969.

[Stei90] Igor Steinberg and Marvin Solomon. Searching game trees in parallel. In International Conference on Parallel Processing, pages III–9 – III–17, 1990. ^{∗}.

[Stoc79] G. C. Stockman. A minimax algorithm better than alpha-beta? Artificial Intelligence, 12(2):179–196, 1979.

[Tars83] M. Tarsi. Optimal search on some game trees. Journal of the ACM, 30:389–396, July 1983. Also as Tech. Report UCLA-ENG-CSL-8108.

[Vorn87] Oliver Vornberger and Burkhard Monien. Parallel alpha-beta versus parallel SSS*. In IFIP Conference on Distributed Processing, pages 613–625, Amsterdam, NL, October 1987. North-Holland.