Home * Search * Scout
external image 750px-Phoenix_Lander_small.jpg

Scout is an Alpha-Beta enhancement introduced by Judea Pearl in 1980 [1] [2] . Scout was originally introduced by a recursive function called EVAL, with {MAX, MIN}-parameter. A boolean function called TEST was used to prove all siblings of the first brother were either below or equal to MAX so far, or above or equal to MIN. If a condition did not hold, a re-search was necessary to get the real new MAX or MIN value. This was essentially a null-window search, with the idea that the saved nodes of the TEST would outweigh re-searches in reasonable well-ordered search trees. Therefor Pearl expected Scout's superiority over Alpha-Beta in practical game trees, which was confirmed in 1985 by Rajjan Shinghal and Agata Muszycka-Jones [3] .
Phoenix (Mars Scout 1) [4]

Enhancements

In 1983 Alexander Reinefeld turned Scout and Negamax with some fail-soft refinements into NegaScout [5] . Already in 1982 Tony Marsland and Murray Campbell introduced PVS [6] , based on Finkel's and Fishburn's routine Palphabeta [7] , in Fishburn's 1981 Thesis [8] called Calphabeta, which in turn is similar to Judea Pearl's Scout.

See also


External Links


References

  1. ^ Judea Pearl (1980). Asymptotic Properties of Minimax Trees and Game-Searching Procedures. Artificial Intelligence, Vol. 14, No. 2, pp. 113-138. ISSN 0004-3702.
  2. ^ Judea Pearl (1980). Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties. Proceedings of the First Annual National Conference on Artificial Intelligence. Stanford. pdf
  3. ^ Agata Muszycka-Jones, Rajjan Shinghal (1985). An empirical comparison of pruning strategies in game trees. IEEE Transactions on Systems, Man, and Cybernetics, Vol. 15, No. 3
  4. ^ Mars-Scout-Programm from Wikipedia.de
  5. ^ Alexander Reinefeld (1983). An Improvement to the Scout Tree-Search Algorithm. ICCA Journal, Vol. 6, No. 4, pp. 4-14. pdf
  6. ^ Tony Marsland, Murray Campbell (1982). Parallel Search of Strongly Ordered Game Trees. ACM Computing Surveys, Vol. 14, No. 4, pdf
  7. ^ Raphael Finkel and John Philip Fishburn (1980). Parallel Alpha-Beta Search on Arachne. IEEE International Conference on Parallel Processing, pp. 235-243.
  8. ^ John Philip Fishburn (1981). Analysis of Speedup in Distributed Algorithms Ph.D. Thesis, University of Wisconsin-Madison, pdf, Calphabeta at page 167

What links here?


Up one level