Bruce Abramson
Skip Abstract Section
Abstract
Computer games have been around for almost as long as computers. Most of these games, however, have been designed in a rather ad hoc manner because many of their basic components have never been adequately defined. In this paper some deficiencies in the standard model of computer games, the minimax model, are pointed out and the issues that a general theory must address are outlined. Most of the discussion is done in the context of control strategies, or sets of criteria for move selection. A survey of control strategies brings together results from two fields: implementations of real games and theoretical predictions derived on simplified game-trees. The interplay between these results suggests a series of open problems that have arisen during the course of both analytic experimentation and practical experience as the basis for a formal theory.
- ABRAMSON, B. 1986. An explanation of and cure for minimax pathology. In Uncertainty in Artificial Intelligence, L. Kanal and J. Lemmer, Eds. North-Holland, Amsterdam, pp. 495-504.Google Scholar
- ABRAMSON, B. 1987. The expected-outcome model of two-player games. Ph.D. thesis, Department of Computer Science, Columbia University, New York, 1987. Google Scholar
- ABRAMSON, B. 1988. Learning expected-outcome evaluators in chess. In Proceedings of the AAA! 1988 Spring Symposium Series: Computer Game Playing (Palo Alto, Calf., Mar.). AAAI, Menlo Park, Calif., pp. 26-28.Google Scholar
- ABRAMSON, B., AND KORF, R. 1987. A model of twoplayer evaluation functions. In Proceedings of the 6th National Conference on Artificial Intelligence. Morgan Kaufmann, Los Altos, Calif., pp. 90-94.Google Scholar
- ADELSON-VELSKIY, G. M., ARLAZAROV, V. L., AND DONSKOY, M. V. 1975. Some methods of controlling the tree search in chess programs. Artif. InteU. 6, 361-371.Google Scholar
- ANANTHARAMAN, T., CAMPBELL, M., AND HSIU, F. 1988. Singular extensions: Adding selectivity to brute force searching. In Proceedings of the AAAI 1988 Spring Symposium Series: Computer Game Playing. AAAI, Menlo Park, Calif., pp. 8-13.Google Scholar
- BALLARD, B. W. 1983. The *-minimax procedure for trees containing chance nodes. Artif. lnteU. 21, 327-350.Google Scholar
- BAUDET, G. M. 1978. On the branching factor of the alpha-beta pruning algorithm. Artif. Intelt. 10 (2), 173-199.Google Scholar
- BEAL, D. F. 1980. An analysis of minimax. In Advances in Computer Chess 2, M. R. B. Clarke, Ed. Edinburgh, Univ. Press, Edinburgh, Scotland, pp. 17-24.Google Scholar
- BEAL, D. F. 1982. Benefits of minimax search. In Advances in Computer Chess 3, M. R. B. Clarke, Ed. Pergamon Press, Elmsford, N.Y., pp. 103-109. Google Scholar
- BE^L, D. F. 1987. Experiments with the null move. In Advances in Computer Chess 5. North-Holland, Amsterdam.Google Scholar
- BERLEKAMP, E., CONWAY, J. H., AND GUY, R. K. 1982. Winning Ways. Academic Press, Orlando, Fla. (in two volumes.)Google Scholar
- BERLINER, H. J. 1973. Some necessary conditions for a master chess program. In Proceedings of the 3rd International Joint Conference on Artificial Intelligence (Stanford, Calif., Aug. 20-23). Morgan Kaufmann, Los Altos, Calif., pp. 77-85.Google Scholar
- BERLINER, H. J. 1977a. A representation and some mechanisms for a problem-solving chess program. In Advances in Computer Chess, M. R. B. Clarke, Ed. Edinburgh Univ. Press, Edinburgh, Scotland, pp. 7-29.Google Scholar
- BERLINER, H. J. 1977b. The use of domain-dependent descriptions in tree searching. In Perspectives on Computer Science. Academic Press, Orlando, Fla., pp. 39-62.Google Scholar
- BERLINER, H. J. 1978. A chronology of computer chess and its literature. Artif InteK 10, 201-214.Google Scholar
- BERLINER, H. J. 1979. The b* tree search algorithm: A best-first proof procedure. Arti{. InteU. 21, 23-40.Google Scholar
- BERLINER, $. J. 1980. Backgammon computer program beats world champion. Artif. inteU. 14, 205-220.Google Scholar
- BERLINER, H. J. 1981. An examination of brute force intelligence. In Proceedings o{ the 7th International Joint Conference on Artificial Intelligence (Vancouver, B.C., Canada, Aug. 24-28). Morgan Kaufmann, Los Altos, Calif., pp. 581-587.Google Scholar
- BERLINER, H. Z. 1988. New Hitech computer chess success. AI Mag. 2, 133. Google Scholar
- BERLINER, H. J., AND EBELING, C. 1986. The supreme architecture: A new intelligent paradigm. Artif. Intell. 28, 3-8. Google Scholar
- BHATTACHARYA, S., AND BAGCHI, A., 1986. Making best use of available memory when searching game-trees. In Proceedings of the 5th National Conference on Artificial Intelligence (Philadelphia, Pa., Aug. 11-15), pp. 163-167.Google Scholar
- BIRMINGHAM, J. A., AND KENT, P. 1977. Tree searching and tree pruning techniques. In Advances in Computer Chess, M. R. B. Clarke, Ed. Edinburgh Univ. Press, Edinburgh, Scotland, pp. 89-96.Google Scholar
- BOTVINNIK, U. M. 1970. Computers, Chess, and Long Range Planning (A. Brown, transl.). Springer-Verlag, New York. Google Scholar
- Botvinnik M.M. 2982. Decision making ~n~l computers. In Advances in Computer Chess 3, M. R. B. Clarke, Ed. Pergamon Press, Elmsford, N.Y., pp. 169-180.Google Scholar
- BOTVINNIK, M. M. 1984. Computers in Chess' Solving Inexact Search Problems (A. Brown, transl.). Springer-Verlag, New York. Google Scholar
- BRAMER, M. A. 1980. An optimal algorithm for king and pawn against king using pattern knowledge. In Advances in Computer Chess 2, M. R. B. (~.l~rlr.~ l~.rl ~rllnh,,v~h TTnlv Pro~ ~e}inh,,r~h. Scotland.Google Scholar
- BRAMER, M. A. Ed. 1983. Computer Game Playing: Theo~ and Practice. Ellis Horwood Ltd. 1, Chichester, W. Sussex, England Google Scholar
- BRATKO, I., AND GAMS, M. 1982. Error analysis of the minimax principle. In Advances in Computer Chess 3, M. R. B. Clarke, Pergamon Press, Elmsford, N.Y., pp. 1-16.Google Scholar
- BRATKO, I., AND MICHm, D. 1980. An advice program for a complex chess programnnng tas~. Comput. J. 23, 353-359.Google Scholar
- BRUDNO, A. L. 1963. Bounds and valuations for nhviclvin~ t.ho ~n~reh nf o gtimat~g In Prnhlern.~ ~---tv ................... of Cybernetics. Pergamon Press, Elmsford, N.Y., pp. 225-241.Google Scholar
- CAMPBELL, M. 1981. Algorithms for the parallel search of game-trees. M.S. thesis, Computer Science Dept., University of Alberta, Alberta, Canada, Aug.Google Scholar
- CAMPBELL, M. S., AND MARSLAND, T. A. 1983. A comparison of minimax tree search algorithms. Artif. InteU. 20, 347-367.Google Scholar
- Chi, P. C. the ikolni iugbiu kjhbj kjhbj performance of minimax and product in gametree searching. In Proceedings of the 2nd Workshop of Uncertainty in Artificial Intelligence (Philadelphia, Pa., Aug.), pp. 49-55.Google Scholar
- CHI, P.-C., AND NAU, D. S. 1987. Comparing minimax and product in a variety of games. In Proceedings o/me" 6th National~.un/erence on Artificial Intelligence (Seattle, Wash., July 13- 17), pp. 100-104.Google Scholar
- CONDON, J. H., AND THOMPSON, l<. 191q2. Relic chess hardware. In Advances in Computer Chess 3, M. R. B. Clarke, Ed. Pergamon Press, Elmsford, N.Y., pp. 45-54.Google Scholar
- CONDON, J. H., AND THOMPSON, K. 1983. Belle. In Chess Skill in Man and Machine, P. W. Frey, Ed. Springer-Verlag, New York, pp. 201-210.Google Scholar
- EDWARDS, D., AND HART, T. i963. The alpha-beta heuristic. Tech. Rep. 30, MIT AI Memo, Computer Science Dept., Massachusetts Institute of Technolo~, Cambridge, Mass., Oct. Originally published as the Tree Prune Algorithm, Dec. 1961. Google Scholar
- FULLER, S., GASCHNIG, J., AND GILLOGLY, J. 1973. Analysis of the alpha-beta pruning algorithm. Tech. Rep., Computer Science Dept., Carnegie- Mellon ........... unlverslLy, t-lCLSourgn, Pa.Google Scholar
- GOETSCH, G., AND CAMPBELL, M. 1988. Experiments with the null move heuristic in chess. In Pr .. dings of the A A A l !988 Spring Symposium Series' Computer Game Playing. AAAI, Menlo Park, Calif., pp. 14-18.Google Scholar
- GREENBLATT, R. D., EASTLAKE, III, D. E., AND CROCKER, S. D. 1967. The Greenblatt chess program. In Proceedings of the 1967 Fall Joint Computer Conference (Washington, D.C.), pp. ~UI-/51U.Google Scholar
- GRIFFITH, A. K. 1974. A comparison and evaluation of three machine learning procedures as applied +, ,hog .. e oh~o~o~o Artif. !nteU. 5, 137-148.Google Scholar
- HARRIS, L. R. 1974. The heuristic search under conditions of error. Artif. InteU. 5, 217-234.Google Scholar
- HARTMANN r~ 10~'/,~ LI .. +n ,~v+~or.+ ,,.~} ... + knowledge from grandmaster games, Part 1. Int. Comput. Chess Assoc. J. I0 (1), 14-36.Google Scholar
- HARTMANN~ D. 1987b. How to extract relevant knowledge from grandmaster games, Part 2. int. Comput. Chess Assoc. J. 10 (2), 78-90.Google Scholar
- IBARAK{, T. 1986. Generalization of alpha-beta and SSS* search procedures. Artif. InteU. 29 (1), 73-118. Google Scholar
- KAINDL, H. 1983a. Quiescence search in computer chess, in Computer Game Playing' Theory and Practice, M. A. Bramer, Ed. Ellis Horwood Ltd., Chichester, W. Sussex, England, pp. 39-52.Google Scholar
- KAINDL, H. 1983b. hguigid yugfcug ygdfyt computer chess. In Proceedings of the 8th International Conference on Artificial Intelligence (Karlsruhe, West Germany, Aug. 8-12). Morgan Kaufmann, Los Altos, Calif., pp. 760-762.Google Scholar
- KARMAKAR, N. 1984. A new polynomial time algorithm for linear programming. In Proceedings of the i6th Annual A CM Symposium on the Theory of Computing (Washington, D.C., Apr. 30-May 2). ACM, New York, pp. 302-311. Google Scholar
- KNUTH, D. E., ~ND MOORE, R W ~,~n of alpha-beta pruning. Arti{. /n~;~. 6, 293-326.Google Scholar
- KOPEC, D. 1985. Chess computers. Abacus, 2, 10-28. An optimal admissible tree search. Artif. Intell. 27, 97-109. Google Scholar
- LEVY, D. 1976. Chess and Computers. Computer Science Press, Potomac, Md. Google Scholar
- MAGGS, P. B. 1979. Programming strategies in the game of Reversi. BYTE, 4, 66-79.Google Scholar
- MARSLAND, T. A. 1983. Relative efficiency of alphabeta implementations. In Proceedings of the 8th International Conference on Artificial Intelligence Kaufmann, Los Altos, Calif. pp. 763-766.Google Scholar
- MARSLAND, T. A. 1986. A review of game-tree pruning. Int. Comput. Chess Assoc. J. 9 (1), 3-19.Google Scholar
- MARSLAND, T. A., AND CAMPBELL, M. 1982. Parallel search of strongly ordered game trees. A CM Comput. Surv. 14 (4, Dec.), 533-551. Google Scholar
- MARSLAND, T. A., AND POPOWICH, F. 1985. Parallel game-tree search. IEEE Trans. Pattern Anal. Mach. Intell. 7 (4, July), 442-452.Google Scholar
- MARSLAND, W. A., REINEFELD, A., AND SCHAEFFER, J. 1987. Low overhead alternatives to SSS*. Artif Intell. 31 (2), 185-199. Google Scholar
- MCALLESTER, D. A. 1985. A new procedure for growing Bin-max trees. Tech. rep., MIT Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Mass., July.Google Scholar
- MICmE, D. 1977. King and rook against king: Historical background and a problem on the infinite board. In Advances in Computer Chess, M. R. B. Clarke, Ed. Edinburgh Univ. Press, Edinburgh, Scotland.Google Scholar
- MICHON, G. P. 1983. Recursive random games: A probabilistic model for perfect information games. Ph.D. thesis, Computer Science Dept., University of California at Los Angeles, 1983. Google Scholar
- NAU, D. S. 1982a. An investigation of the causes of pathology in games. Artif InteU. 19, 257-278.Google Scholar
- NAY, D. S. 1982b. The last player theorem. Artif Intell. 18, 53-65.Google Scholar
- NAU, D. S. 1983a. Decision quality as a function of search depth on game trees. J. ACM 30, 4 (oct.) 687-708. Google Scholar
- NAU, D. S. 1983b. Pathology on game trees revisited, and an alternative to minimax. Artif InteU. 21, 221-244.Google Scholar
- NAU, D. S., PURDOM, P., AND TZENG, C.-H. 1983. Experiments on alternatives to minimax. Tech. rep., Computer Science Dept., Univ. of Maryland, College Park, Md., Oct.Google Scholar
- NEWBORN, M. M. 1975. Computer Chess. Academic Press, Orlando, Fla. Google Scholar
- NEWBORN, M. M. 1977. The efficiency of the alphabeta search on trees with branch-dependent terminal node scores. Artif InteU. 8 (2), 137-153.Google Scholar
- NEWBORN, M. M. 1985. A parallel search chess program. In ACM '85--The Range of Computing: Mid-80's Perspective (Denver, Colo., Oct. 14-16). ACM, New York, pp. 272-277. Google Scholar
- NEWELL, A., SHAW, J. C., AND SIMON, H. A. 1963. Chess playing programs and the problem of com~ plexity. In Computers and Thought, E. Feigenbaum and J. Feldman, Eds. McGraw-Hill, New York, pp. 39-70. Google Scholar
- NILSSON, N. J. 1980. Principles of Artificial InteUigence. Tioga Publ., Palo Alto, Calif. Google Scholar
- PALAY, A. J. 1982. The b* tree search algorithmnew results. Artif Intell. 19, 145-163.Google Scholar
- PALAY, A. J. 1985. Searching With Probabilities. Pitman, London. Google Scholar
- PEARL, J. 1980. Asymptotic properties of minimax trees and game-searching procedures. Artif. Intell. 14, 113-138.Google Scholar
- PEARL, J. 1981. Heuristic search theory: A survey of recent results. In Proceedings of the 7th International Joint Conference on Artificial Intelligence. Morgan Kaufmann, Los Altos, Calif., pp. 24-28.Google Scholar
- PEARL, J. 1982. The solution for the branching factor of the alpha-beta pruning algorithm and its optimality. Commun. ACM, 25, 8 (Aug.) 559-564. Google Scholar
- PEARL, J. 1983. On the nature of pathology in game searching. Artif intell. 20, 427-453.Google Scholar
- PEARL, J. 1984. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison Wesley, Reading, Mass. Google Scholar
- PiTRAT, J. 1977. A chess combination program which uses plans. Artif InteU. 21,275-321.Google Scholar
- PITRAT, J. 1980. The behaviour of a chess combination program using plans. In Advances in Computer Chess2, M. R. B. Clarke, Ed. Edinburgh Univ. Press, Edinburgh, Scotland.Google Scholar
- REIBMAN, A. L., AND BALLARD, B. W. 1983. Nonminimax search strategies for use against fallible opponents. In Proceedings of the 8th International Joint Conference on Artificial Intelligence (Karlsruhe, West Germany, Aug. 8-12). Morgan Kaufmann, Los Altos, Calif., pp. 338-342.Google Scholar
- REINEFELO, A. 1983. An improvement of the scout tree-search algorithm, int. Comput. Chess Assoc. J. 6 (4), 4-14.Google Scholar
- RICH, E. 1983. Artificial Intelligence. McGraw-Hill, New York. Google Scholar
- RIVEST, R. 1987. Game tree searching by min/max approximation. Artif. Intell. 34 (1), 77-96. Google Scholar
- ROIZEN, I., AND PEARL, J. 1983. A minimax algorithm better than alpha-beta? Yes and no. Artif. Intell. 21, 199-220.Google Scholar
- ROSENBLOOM, P. S. 1982. A world-championshiplevel Othello program. Artif. intell. 19, 279-320.Google Scholar
- SAMUEL, A. L. 1959. Some studies in machine learning using the game of checkers. IBM J. 3, 211-229.Google Scholar
- SAMUEL, A. r. 1967. Some studies in machine learning using the game of Checkers iI--recent progress. IBM J. 11,601-617.Google Scholar
- SCHAEFFER, J. 1986. Improved parallel alpha-beta search. In A CM/IEEE Fall Joint Computer Conference Proceedings (Dallas, Tex., Nov. 2-6), pp. 519-527. Google Scholar
- SCHAErFER, J. 1987. Speculative computing. Int. Comput. Chess Assoc. J. 10 (3), 118-124.Google Scholar
- SHANNON, C. E. 1950. Programming a computer for playing chess. Philos. Mag. 41,256-275.Google Scholar
- SLAGLE, J. R., AND DIXON, J. K. 1969. Experiments with some programs that search trees, j. ACM, 2 (Apr.) 16, 189-207. Google Scholar
- SLAGLE, J. R., AND DIXON, J. K. 1970. Experiments with the M & N tree-searching procedure. Commun. ACM 13, 3 (Mar.) 147-154. Google Scholar
- SLATE, D. J., AND ATKIN, r. R. 1977. Chess 4.5-- the Northwestern University chess program. In Chess Skill in Man and Machine, P. W. Frey, Ed. Springer-Verlag, New York, pp. 82-118.Google Scholar
- STOCKMAN, G. C. 1979. A minimax algorithm better than alpha-beta? Artif Intell. 12, 179-196.Google Scholar
- THOMPSON, K. 1982. Computer chess strength, in Advances in Computer Chess 3, M. R. B. Clarke, Ed. Pergamon Press, Elmsford, N.Y., pp. 55-56.Google Scholar
- TRUSCOTT, W. 1979. Minimum variance tree searching. in Proceedings of the 1st International Symposium on Policy Analysis and Information Systems (Durham, N.C.) pp. 203-209.Google Scholar
- TZENG, C.-H., AND PURDOM, P. W. 1983. A theory of game trees. In Proceedings of the 8th International Joint Conference on Artificial Intelligence (Karlsrahe, West Germany, Aug. 8-12) Morgan Kaufmann, Los Altos, Calif., pp. 416-419.Google Scholar
- VON NEUMANN, J., AND MORGENSTERN, O. 1944. Theory of Games and Economic Behavior. Princeton Univ. Press, Princeton, N.J.Google Scholar
- WILKINS, D. 1977. Using chess knowledge to reduce search. In Chess Skill in Man and Machine, P. W. Frey, Ed. Springer-Verlag, New York.Google Scholar
- WILKINS, D. 1980. Using patterns and plans in chess. Artif. Intell. 14, 165-203.Google Scholar
- WILKINS, D. 1982. Using knowledge to control tree searching. Artif. inteU. 18, 1-51.Google Scholar
- WINSTON, P. H. 1977. Artificial Intelligence. Addison-Wesley, Reading, Mass. Google Scholar
Recommendations
Player modeling, search algorithms and strategies in multi-player games
ACG'05: Proceedings of the 11th international conference on Advances in Computer GamesFor a long period of time, two person zero-sum games have been in the focus of researchers of various communities. The efforts were mainly driven by the fascination of special competitions such as Deep Blue vs. Kasparov, and of the beauty of parlor ...
Analyzing n-player impartial games
AbstractCombinatorial game theory is the study of two player perfect information games. While work has been done in the past on expanding this field to include n-player games we present a unique method which guarantees a single winner. Specifically our ...
Reviews
John Thomas Ritschdorff
Abramson considers computer games and the various control strategies, proposed and implemented, for playing them. He introduces the major approaches for describing and analyzing game search trees, including the minimax, alpha-beta pruning, iterative deepening, SSS*, and SCOUT methods. He makes a distinction between game programming and heuristic programming and stresses that the interplay between the two has been minimal. The paper surveys game programming using Shannon's classification of strategies as either type-A or type-B. Type-A strategies involve full-width minimax searches, and type-B strategies involve selective searches. Abramson briefly describes numerous examples of both strategy types and contrasts their advantages and disadvantages. The author demonstrates how previous assumptions about the central role of the minimax technique are being challenged. The complexity of mathematical models for control strategies had inhibited complete analyses. Recent theoretical investigations have yielded surprising and interesting results regarding the conventional wisdom on minimax. The paper presents some alternatives to the minimax procedure and concludes with an enumeration of areas for further exploration. The author's purpose is to survey work in control strategies and point out open questions. He achieves this purpose throughout the paper. The survey and background sections are excellent. This paper would be an ideal primer for someone wishing to become familiar with control strategies. The writing is clear and explicit. Well-chosen examples appear throughout, and the pointers to the literature are extensive. The consideration of open questions leaves the reader with an excellent grasp of what remains to be done and its relative importance. Abramson's paper is a valuable addition to the literature. Novices and experts alike will be able to use this work.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments