Difference between revisions of "Scout"

From Chessprogramming wiki
Jump to: navigation, search
(Created page with "'''Home * Search * Scout''' [[FILE:Phoenix Lander small.jpg|border|right|thumb|[https://en.wikipedia.org/wiki/Phoenix_%28spacecraft%29 Phoenix] ([https://en...")
 
 
(2 intermediate revisions by the same user not shown)
Line 3: Line 3:
 
[[FILE:Phoenix Lander small.jpg|border|right|thumb|[https://en.wikipedia.org/wiki/Phoenix_%28spacecraft%29 Phoenix] ([https://en.wikipedia.org/wiki/Mars_Scout_Program Mars Scout 1]) <ref>Artist's concept of the [https://en.wikipedia.org/wiki/Phoenix_%28spacecraft%29 Phoenix] Mars lander by [https://en.wikipedia.org/wiki/NASA NASA]/[https://en.wikipedia.org/wiki/Jet_Propulsion_Laboratory JPL]/[http://www.fourth-millennium.net/space-exploration/space-exploration.html Corby Waste], from [http://phoenix.lpl.arizona.edu/images.php?gID=66&cID=1 Phoenix Mars Mission - Gallery - Images], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [http://de.wikipedia.org/wiki/Mars-Scout-Programm Mars-Scout-Programm from Wikipedia.de]</ref> ]]
 
[[FILE:Phoenix Lander small.jpg|border|right|thumb|[https://en.wikipedia.org/wiki/Phoenix_%28spacecraft%29 Phoenix] ([https://en.wikipedia.org/wiki/Mars_Scout_Program Mars Scout 1]) <ref>Artist's concept of the [https://en.wikipedia.org/wiki/Phoenix_%28spacecraft%29 Phoenix] Mars lander by [https://en.wikipedia.org/wiki/NASA NASA]/[https://en.wikipedia.org/wiki/Jet_Propulsion_Laboratory JPL]/[http://www.fourth-millennium.net/space-exploration/space-exploration.html Corby Waste], from [http://phoenix.lpl.arizona.edu/images.php?gID=66&cID=1 Phoenix Mars Mission - Gallery - Images], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [http://de.wikipedia.org/wiki/Mars-Scout-Programm Mars-Scout-Programm from Wikipedia.de]</ref> ]]
  
−
'''Scout''',
+
'''Scout''',<br/>
 
an [[Alpha-Beta]] enhancement introduced by [[Judea Pearl]] in [[Timeline#1980|1980]] <ref>[[Judea Pearl]] ('''1980'''). ''Asymptotic Properties of Minimax Trees and Game-Searching Procedures.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 14, No. 2</ref> <ref>[[Judea Pearl]] ('''1980'''). ''Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties''. Proceedings of the First Annual National Conference on Artificial Intelligence. Stanford. [http://ftp.cs.ucla.edu/pub/stat_ser/scout.pdf pdf]</ref> . Scout was originally introduced by a [[Recursion|recursive]] function called EVAL, with <span style="background-color: #d6d6d6;">{MAX, MIN}</span>-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|null-window]] search, with the idea that the saved nodes of the TEST would outweigh re-searches in reasonable well-ordered [[Search Tree|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]] <ref>[[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</ref> .  
 
an [[Alpha-Beta]] enhancement introduced by [[Judea Pearl]] in [[Timeline#1980|1980]] <ref>[[Judea Pearl]] ('''1980'''). ''Asymptotic Properties of Minimax Trees and Game-Searching Procedures.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 14, No. 2</ref> <ref>[[Judea Pearl]] ('''1980'''). ''Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties''. Proceedings of the First Annual National Conference on Artificial Intelligence. Stanford. [http://ftp.cs.ucla.edu/pub/stat_ser/scout.pdf pdf]</ref> . Scout was originally introduced by a [[Recursion|recursive]] function called EVAL, with <span style="background-color: #d6d6d6;">{MAX, MIN}</span>-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|null-window]] search, with the idea that the saved nodes of the TEST would outweigh re-searches in reasonable well-ordered [[Search Tree|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]] <ref>[[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</ref> .  
  
Line 19: Line 19:
 
* [[Parallel Search]]
 
* [[Parallel Search]]
 
* [[Principal Variation Search]]
 
* [[Principal Variation Search]]
−
* [[PVS and aspiration]]
+
* [[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=
 
* [https://en.wikipedia.org/wiki/Scout Scout from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Scout Scout from Wikipedia]
−
* [[Videos#FlatEarthSociety|Flat Earth Society]]  - Psychoscout, [https://en.wikipedia.org/wiki/John_F._Kennedy_Center_for_the_Performing_Arts John F. Kennedy Center for the Performing Arts], [https://en.wikipedia.org/wiki/Washington,_D.C. Washington D.C.], 2011, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
+
* [[:Category:Flat Earth Society|Flat Earth Society]]  - Psychoscout, [https://en.wikipedia.org/wiki/John_F._Kennedy_Center_for_the_Performing_Arts John F. Kennedy Center for the Performing Arts], [https://en.wikipedia.org/wiki/Washington,_D.C. Washington D.C.], 2011, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 
: {{#evu:https://www.youtube.com/watch?v=xuG5SB_d9pY|alignment=left|valignment=top}}
 
: {{#evu:https://www.youtube.com/watch?v=xuG5SB_d9pY|alignment=left|valignment=top}}
  
Line 39: Line 40:
  
 
'''[[Search|Up one level]]'''
 
'''[[Search|Up one level]]'''
 +
[[Category:Flat Earth Society]]

Latest revision as of 15:09, 22 November 2018

Home * Search * Scout

Phoenix (Mars Scout 1) [1]

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

External Links

References

  1. ↑ 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
  2. ↑ Judea Pearl (1980). Asymptotic Properties of Minimax Trees and Game-Searching Procedures. Artificial Intelligence, Vol. 14, No. 2
  3. ↑ 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
  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
  5. ↑ Alexander Reinefeld (1983). An Improvement to the Scout Tree-Search Algorithm. ICCA Journal, Vol. 6, No. 4
  6. ↑ Tony Marsland, Murray Campbell (1982). Parallel Search of Strongly Ordered Game Trees. ACM Computing Surveys, Vol. 14, No. 4, pdf
  7. ↑ Raphael Finkel, 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

Up one level

Retrieved from "https://www.chessprogramming.org/index.php?title=Scout&oldid=8657"