Download the full-sized PDF of Heuristic Search in One and Two Player GamesDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Computing Science, Department of


This file is in the following collections:

Technical Reports (Computing Science)

Heuristic Search in One and Two Player Games Open Access


Author or creator
Marsland, Tony
Reinefeld, Alexander
Additional contributors
computer gaming
Type of item
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.\"
Date created
License information
Creative Commons Attribution 3.0 Unported

Citation for previous publication

Link to related item

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1027334
Last modified: 2015:10:12 17:03:47-06:00
Filename: TR93-02.pdf
Original checksum: a35d3e8b2dc0b2dcf0287e3d72f753c0
Well formed: true
Valid: true
Page count: 50
Activity of users you follow
User Activity Date