Difference between revisions of "Scout"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
(One intermediate revision by the same user not shown) | |||
Line 19: | Line 19: | ||
* [[Parallel Search]] | * [[Parallel Search]] | ||
* [[Principal Variation Search]] | * [[Principal Variation Search]] | ||
− | * [[PVS and | + | * [[PVS and Aspiration]] |
=Publications= | =Publications= | ||
Line 29: | Line 29: | ||
* [[Alexander Reinefeld]] ('''1983'''). ''An Improvement to the Scout Tree-Search Algorithm.'' [[ICGA Journal#6_4|ICCA Journal, Vol. 6, No. 4]] | * [[Alexander Reinefeld]] ('''1983'''). ''An Improvement to the Scout Tree-Search Algorithm.'' [[ICGA Journal#6_4|ICCA Journal, Vol. 6, No. 4]] | ||
* [[Agata Muszycka-Jones]], [[Rajjan Shinghal]] ('''1985'''). ''An empirical comparison of pruning strategies in game trees''. [[IEEE#SMC|IEEE Transactions on Systems, Man, and Cybernetics]], Vol. 15, No. 3 | * [[Agata Muszycka-Jones]], [[Rajjan Shinghal]] ('''1985'''). ''An empirical comparison of pruning strategies in game trees''. [[IEEE#SMC|IEEE Transactions on Systems, Man, and Cybernetics]], Vol. 15, No. 3 | ||
+ | * [[Yanjun Zhang]] ('''1998'''). ''[https://www.sciencedirect.com/science/article/pii/S0196677498909282 The Variance of Two Game Tree Algorithms]''. [https://www.sciencedirect.com/journal/journal-of-algorithms Journal of Algorithms], Vol. 28, No. 1 | ||
=External Links= | =External Links= |
Latest revision as of 15:09, 22 November 2018
Scout,
an Alpha-Beta enhancement introduced by Judea Pearl in 1980 [2] [3] . 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 [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
Publications
- Judea Pearl (1980). Asymptotic Properties of Minimax Trees and Game-Searching Procedures. Artificial Intelligence, Vol. 14, No. 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
- Raphael Finkel, John Philip Fishburn (1980). Parallel Alpha-Beta Search on Arachne. IEEE International Conference on Parallel Processing, pp. 235-243
- John Philip Fishburn (1981). Analysis of Speedup in Distributed Algorithms Ph.D. Thesis, University of Wisconsin-Madison, pdf
- Tony Marsland, Murray Campbell (1982). Parallel Search of Strongly Ordered Game Trees. ACM Computing Surveys, Vol. 14, No. 4, pdf
- Alexander Reinefeld (1983). An Improvement to the Scout Tree-Search Algorithm. ICCA Journal, Vol. 6, No. 4
- 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
- Yanjun Zhang (1998). The Variance of Two Game Tree Algorithms. Journal of Algorithms, Vol. 28, No. 1
External Links
- Scout from Wikipedia
- Flat Earth Society - Psychoscout, John F. Kennedy Center for the Performing Arts, Washington D.C., 2011, YouTube Video
References
- ↑ Artist's concept of the Phoenix Mars lander by NASA/JPL/Corby Waste, from Phoenix Mars Mission - Gallery - Images, Wikimedia Commons, Mars-Scout-Programm from Wikipedia.de
- ↑ Judea Pearl (1980). Asymptotic Properties of Minimax Trees and Game-Searching Procedures. Artificial Intelligence, Vol. 14, No. 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
- ↑ 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
- ↑ Alexander Reinefeld (1983). An Improvement to the Scout Tree-Search Algorithm. ICCA Journal, Vol. 6, No. 4
- ↑ Tony Marsland, Murray Campbell (1982). Parallel Search of Strongly Ordered Game Trees. ACM Computing Surveys, Vol. 14, No. 4, pdf
- ↑ Raphael Finkel, John Philip Fishburn (1980). Parallel Alpha-Beta Search on Arachne. IEEE International Conference on Parallel Processing, pp. 235-243
- ↑ John Philip Fishburn (1981). Analysis of Speedup in Distributed Algorithms Ph.D. Thesis, University of Wisconsin-Madison, pdf, Calphabeta at page 167