Control strategies for two-player games
Author:
Open Access
- 1 June 1989
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 21 (2) , 137-161
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.Keywords
This publication has 43 references indexed in Scilit:
- Generalization of alpha-beta and SSS∗ search proceduresArtificial Intelligence, 1986
- On the nature of pathology in game searchingArtificial Intelligence, 1983
- A comparison of minimax tree search algorithmsArtificial Intelligence, 1983
- Parallel Search of Strongly Ordered Game TreesACM Computing Surveys, 1982
- A world-championship-level Othello programArtificial Intelligence, 1982
- An investigation of the causes of pathology in gamesArtificial Intelligence, 1982
- The B∗ tree search algorithm—New resultsArtificial Intelligence, 1982
- The solution for the branching factor of the alpha-beta pruning algorithm and its optimalityCommunications of the ACM, 1982
- An advice program for a complex chess programming taskThe Computer Journal, 1980
- Experiments with the M & N tree-searching programCommunications of the ACM, 1970