Heuristic Search in One and Two Player Games

• Author(s) / Creator(s)

  • Reinefeld, Alexander
  • Marsland, Tony

• Technical report TR93-02. With the continuing price-performance improvement of small computers there is growing interest in looking again at some of the heuristic techniques developed for problem-solving and planning programs, to see if they can be enhanced or replaced by more algorithmic methods. The application of raw computing power, while and anathema to some, often provides better answers than is possible by reasoning or analogy. Thus brute force techniques form a good basis against which to compare more sophisticated methods designed to mirror the human deductive process. One source of extra computing power comes through the use of parallel processing on a multicomputer, an so this aspect is also covered here. Here we review the development of heuristic algorithms for application in single-agent and adversary games. We provide a detailed study of iterative deepening A* and its many variants, and show how effective various enhancements, including the use of refutation lines and a transposition table, can be. For adversary games a full review of improved versions of the alpha-beta algorithm (e.g. Principal Variation Search) is provided and various comparisons made to SSS*, Aspiration Search and Scout. The importance of memory functions is also brought out. The second half of the paper deals exclusively with parallel methods not only for single-agent search, but also with a variety of parallelizations for adversary games. In the latter case there is an emphasis on the problems that pruning poses in unbalancing the work load, and so the paper covers some of the dynamic tree-splitting methods that have evolved. This survey will be of interest to those concerned with fundamental issues in computing, but should be especially appealing to experimentalists who want to explore the limitations of theoretical models and to extend their utility. Hopefully this will lead to the development of new theories for dealing with the search of \"average trees.\" | TRID-ID TR93-02

• Date created

  1993

• Subjects / Keywords

  • Computer gaming
  • Heuristics

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3B853M8S

• License

  Attribution 3.0 International