25,161
edits
Changes
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..."
'''[[Main Page|Home]] * [[Search]] * Scout'''
[[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''',
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> .
=Enhancements=
In 1983 [[Alexander Reinefeld]] turned Scout and [[Negamax]] with some [[Fail-Soft|fail-soft]] refinements into [[NegaScout]] <ref>[[Alexander Reinefeld]] ('''1983'''). ''An Improvement to the Scout Tree-Search Algorithm.'' [[ICGA Journal#6_4|ICCA Journal, Vol. 6, No. 4]]</ref> . Already in 1982, [[Tony Marsland]] and [[Murray Campbell]] introduced [[Principal Variation Search|PVS]] <ref>[[Tony Marsland]], [[Murray Campbell]] ('''1982'''). ''Parallel Search of Strongly Ordered Game Trees.'' [[ACM#Surveys|ACM Computing Surveys]], Vol. 14, No. 4, [http://www.cs.ualberta.ca/%7Etony/OldPapers/strong.pdf pdf]</ref> , based on [[Raphael Finkel|Finkel's]] and [[John Philip Fishburn|Fishburn's]] routine '''Palphabeta''' <ref>[[Raphael Finkel]], [[John Philip Fishburn]] ('''1980'''). ''Parallel Alpha-Beta Search on Arachne.'' [[IEEE]] International Conference on Parallel Processing, pp. 235-243</ref> , in Fishburn's 1981 Thesis <ref>[[John Philip Fishburn]] ('''1981'''). ''Analysis of Speedup in Distributed Algorithms'' Ph.D. Thesis, [https://en.wikipedia.org/wiki/University_of_Wisconsin-Madison University of Wisconsin-Madison], [http://www.cs.wisc.edu/techreports/1981/TR431.pdf pdf], ''Calphabeta'' at page 167</ref> called '''Calphabeta''', which in turn is similar to Judea Pearl's Scout.
=See also=
* [[Alpha-Beta]]
* [[Iterative Deepening]]
* [[Jamboree]]
* [[Move Ordering]]
* [[MTD(f)]]
* [[NegaScout]]
* [[Null Window]]
* [[Parallel Search]]
* [[Principal Variation Search]]
* [[PVS and aspiration]]
=Publications=
* [[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
* [[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]
* [[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, [https://en.wikipedia.org/wiki/University_of_Wisconsin-Madison University of Wisconsin-Madison], [http://www.cs.wisc.edu/techreports/1981/TR431.pdf pdf]
* [[Tony Marsland]], [[Murray Campbell]] ('''1982'''). ''Parallel Search of Strongly Ordered Game Trees.'' [[ACM#Surveys|ACM Computing Surveys]], Vol. 14, No. 4, [http://www.cs.ualberta.ca/%7Etony/OldPapers/strong.pdf pdf]
* [[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
=External Links=
* [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
: {{#evu:https://www.youtube.com/watch?v=xuG5SB_d9pY|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one level]]'''
[[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''',
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> .
=Enhancements=
In 1983 [[Alexander Reinefeld]] turned Scout and [[Negamax]] with some [[Fail-Soft|fail-soft]] refinements into [[NegaScout]] <ref>[[Alexander Reinefeld]] ('''1983'''). ''An Improvement to the Scout Tree-Search Algorithm.'' [[ICGA Journal#6_4|ICCA Journal, Vol. 6, No. 4]]</ref> . Already in 1982, [[Tony Marsland]] and [[Murray Campbell]] introduced [[Principal Variation Search|PVS]] <ref>[[Tony Marsland]], [[Murray Campbell]] ('''1982'''). ''Parallel Search of Strongly Ordered Game Trees.'' [[ACM#Surveys|ACM Computing Surveys]], Vol. 14, No. 4, [http://www.cs.ualberta.ca/%7Etony/OldPapers/strong.pdf pdf]</ref> , based on [[Raphael Finkel|Finkel's]] and [[John Philip Fishburn|Fishburn's]] routine '''Palphabeta''' <ref>[[Raphael Finkel]], [[John Philip Fishburn]] ('''1980'''). ''Parallel Alpha-Beta Search on Arachne.'' [[IEEE]] International Conference on Parallel Processing, pp. 235-243</ref> , in Fishburn's 1981 Thesis <ref>[[John Philip Fishburn]] ('''1981'''). ''Analysis of Speedup in Distributed Algorithms'' Ph.D. Thesis, [https://en.wikipedia.org/wiki/University_of_Wisconsin-Madison University of Wisconsin-Madison], [http://www.cs.wisc.edu/techreports/1981/TR431.pdf pdf], ''Calphabeta'' at page 167</ref> called '''Calphabeta''', which in turn is similar to Judea Pearl's Scout.
=See also=
* [[Alpha-Beta]]
* [[Iterative Deepening]]
* [[Jamboree]]
* [[Move Ordering]]
* [[MTD(f)]]
* [[NegaScout]]
* [[Null Window]]
* [[Parallel Search]]
* [[Principal Variation Search]]
* [[PVS and aspiration]]
=Publications=
* [[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
* [[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]
* [[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, [https://en.wikipedia.org/wiki/University_of_Wisconsin-Madison University of Wisconsin-Madison], [http://www.cs.wisc.edu/techreports/1981/TR431.pdf pdf]
* [[Tony Marsland]], [[Murray Campbell]] ('''1982'''). ''Parallel Search of Strongly Ordered Game Trees.'' [[ACM#Surveys|ACM Computing Surveys]], Vol. 14, No. 4, [http://www.cs.ualberta.ca/%7Etony/OldPapers/strong.pdf pdf]
* [[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
=External Links=
* [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
: {{#evu:https://www.youtube.com/watch?v=xuG5SB_d9pY|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one level]]'''
