Difference between revisions of "Search with Random Leaf Values"

From Chessprogramming wiki
Jump to: navigation, search
 
(7 intermediate revisions by the same user not shown)
Line 35: Line 35:
 
=Publications=  
 
=Publications=  
 
==1985 ...==
 
==1985 ...==
−
* [[Bruce Abramson]] ('''1985'''). ''A Cure for Pathological Behavior in Games that Use Minimax.'' Workshop on Uncertainty in Artificial Intelligence, [https://arxiv.org/abs/1304.3444 arXiv:1304.3444]
+
* [[Bruce Abramson]] ('''1985'''). ''A Cure for Pathological Behavior in Games that Use Minimax.'' [[Laveen Kanal#Uncertainty AI 1|Uncertainty in Artificial Intelligence 1]], [https://arxiv.org/abs/1304.3444 arXiv:1304.3444]
 
* [[Bruce Abramson]], [[Richard Korf]] ('''1987'''). ''A Model of Two-Player Evaluation Functions.'' [http://www.aaai.org/Conferences/AAAI/aaai87.php AAAI-87]. [http://www.aaai.org/Papers/AAAI/1987/AAAI87-016.pdf pdf]
 
* [[Bruce Abramson]], [[Richard Korf]] ('''1987'''). ''A Model of Two-Player Evaluation Functions.'' [http://www.aaai.org/Conferences/AAAI/aaai87.php AAAI-87]. [http://www.aaai.org/Papers/AAAI/1987/AAAI87-016.pdf pdf]
 
==1990 ...==
 
==1990 ...==
−
* [[Bruce Abramson]] ('''1990'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=44404 Expected-Outcome: A General Model of Static Evaluation]''. [[TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 12, No. 2
+
* [[Bruce Abramson]] ('''1990'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=44404 Expected-Outcome: A General Model of Static Evaluation]''. [[IEEE #TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 12, No. 2
 
* [[Don Beal]], [[Martin C. Smith]] ('''1994'''). ''Random Evaluations in Chess''. [[ICGA Journal#17_1|ICCA Journal, Vol. 17, No. 1]]
 
* [[Don Beal]], [[Martin C. Smith]] ('''1994'''). ''Random Evaluations in Chess''. [[ICGA Journal#17_1|ICCA Journal, Vol. 17, No. 1]]
 
* [[Don Beal]], [[Martin C. Smith]] ('''1994'''). ''Random Evaluations in Chess''. [[Advances in Computer Chess 7]]
 
* [[Don Beal]], [[Martin C. Smith]] ('''1994'''). ''Random Evaluations in Chess''. [[Advances in Computer Chess 7]]
Line 47: Line 47:
 
* [[Ulf Lorenz]], [[Burkhard Monien]] ('''2002'''). ''[http://www.springerlink.com/content/f6b4wb6l63dpd0jv/ The Secret of Selective Game Tree Search, When Using Random-Error Evaluations]''. Proceedings of 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS), [http://www.top-5000.nl/ps/The%20secret%20of%20selective%20earch%20when%20using%20random.pdf pdf]
 
* [[Ulf Lorenz]], [[Burkhard Monien]] ('''2002'''). ''[http://www.springerlink.com/content/f6b4wb6l63dpd0jv/ The Secret of Selective Game Tree Search, When Using Random-Error Evaluations]''. Proceedings of 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS), [http://www.top-5000.nl/ps/The%20secret%20of%20selective%20earch%20when%20using%20random.pdf pdf]
 
* [[Ingo Althöfer]], [[Susanne Heuser]] ('''2005'''). ''Randomised Evaluations in Single-Agent Search''. [[ICGA Journal#28_1|ICGA Journal, Vol. 28, No. 1]], [https://www.minet.uni-jena.de/preprints/althoefer_05/altheuser.pdf preprint as pdf]
 
* [[Ingo Althöfer]], [[Susanne Heuser]] ('''2005'''). ''Randomised Evaluations in Single-Agent Search''. [[ICGA Journal#28_1|ICGA Journal, Vol. 28, No. 1]], [https://www.minet.uni-jena.de/preprints/althoefer_05/altheuser.pdf preprint as pdf]
−
* [[Brandon Wilson]], [[Austin Parker]], [[Dana Nau]] ('''2009'''). ''Error Minimizing Minimax: Avoiding Search Pathology in Game Trees''. [http://www.cs.umd.edu/~nau/papers/wilson2009error.pdf pdf]
+
* [[Brandon Wilson]], [[Austin Parker]], [[Dana S. Nau]] ('''2009'''). ''Error Minimizing Minimax: Avoiding Search Pathology in Game Trees''. [http://www.cs.umd.edu/~nau/papers/wilson2009error.pdf pdf]
  
 
=Forum Posts=
 
=Forum Posts=
Line 77: Line 77:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=54387 Implications of Lazy eval on Don Beal effect in Fail Soft] by [[Henk van den Belt]], [[CCC]], November 19, 2014
 
* [http://www.talkchess.com/forum/viewtopic.php?t=54387 Implications of Lazy eval on Don Beal effect in Fail Soft] by [[Henk van den Belt]], [[CCC]], November 19, 2014
 
==2015 ...==
 
==2015 ...==
−
* [http://www.talkchess.com/forum/viewtopic.php?t=55011 How to dumb down/weaken/humanize an engine algorithmically?] by Dominik Klein, [[CCC]], January 18, 2015
+
* [http://www.talkchess.com/forum/viewtopic.php?t=55011 How to dumb down/weaken/humanize an engine algorithmically?] by [[Dominik Klein]], [[CCC]], January 18, 2015
 
* [http://www.talkchess.com/forum/viewtopic.php?t=60582 "random mover" chess programs] by [[Norbert Raimund Leisner]], [[CCC]], June 24, 2016
 
* [http://www.talkchess.com/forum/viewtopic.php?t=60582 "random mover" chess programs] by [[Norbert Raimund Leisner]], [[CCC]], June 24, 2016
 
* [http://www.talkchess.com/forum/viewtopic.php?t=60635 Strategies for weaker play levels] by [[Evert Glebbeek]], [[CCC]], June 28, 2016
 
* [http://www.talkchess.com/forum/viewtopic.php?t=60635 Strategies for weaker play levels] by [[Evert Glebbeek]], [[CCC]], June 28, 2016
Line 83: Line 83:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=63803 random evaluation perturbation factor] by [[Stuart Cracraft]], [[CCC]], April 24, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=63803 random evaluation perturbation factor] by [[Stuart Cracraft]], [[CCC]], April 24, 2017
 
* [https://groups.google.com/forum/#!topic/fishcooking/SVkQcfGai8U Randomizing an evaluation and retiring opening books] by [[Ivan Ivec]], [[Computer Chess Forums|FishCooking]], November 18, 2017
 
* [https://groups.google.com/forum/#!topic/fishcooking/SVkQcfGai8U Randomizing an evaluation and retiring opening books] by [[Ivan Ivec]], [[Computer Chess Forums|FishCooking]], November 18, 2017
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=66596 Near-random movers] by [[Robert Pope]], [[CCC]], February 14, 2018
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=71707 Why does stockfish randomise draw evaluations?] by [[Vincent Tang]], [[CCC]], September 01, 2019 » [[Stockfish]], [[Draw Evaluation]], [[Score#DrawScore|Draw Score]]
 +
==2020 ...==
 +
* [https://prodeo.actieforum.com/t123-controlled-randomness-of-evaluation-function Controlled randomness of evaluation function] by [[Pawel Koziol|nescitus]], [[Computer Chess Forums|ProDeo Forum]], December 06, 2020
  
 
=External Links=
 
=External Links=
Line 91: Line 95:
 
* [https://en.wikipedia.org/wiki/Random_walk Random walk from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Random_walk Random walk from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Cannonball_Adderley Cannonball Adderley] - [https://en.wikipedia.org/wiki/Autumn_Leaves_(1945_song) Autumn Leaves] ([https://en.wikipedia.org/wiki/Somethin%27_Else_(Cannonball_Adderley_album) Somethin' Else] 1958), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 
* [https://en.wikipedia.org/wiki/Cannonball_Adderley Cannonball Adderley] - [https://en.wikipedia.org/wiki/Autumn_Leaves_(1945_song) Autumn Leaves] ([https://en.wikipedia.org/wiki/Somethin%27_Else_(Cannonball_Adderley_album) Somethin' Else] 1958), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
−
: feat. [[:Category:Miles Davis|Miles Davis]], [https://en.wikipedia.org/wiki/Hank_Jones Hank Jones], [https://en.wikipedia.org/wiki/Sam_Jones_(musician) Sam Jones] and [https://en.wikipedia.org/wiki/Art_Blakey Art Blakey]
+
: feat. [[:Category:Miles Davis|Miles Davis]], [https://en.wikipedia.org/wiki/Hank_Jones Hank Jones], [https://en.wikipedia.org/wiki/Sam_Jones_(musician) Sam Jones] and [[:Category:Art Blakey|Art Blakey]]
 
: {{#evu:https://www.youtube.com/watch?v=dsp5OASh7bg|alignment=left|valignment=top}}
 
: {{#evu:https://www.youtube.com/watch?v=dsp5OASh7bg|alignment=left|valignment=top}}
  
Line 99: Line 103:
 
'''[[Search|Up one Level]]'''
 
'''[[Search|Up one Level]]'''
 
[[Category:Miles Davis]]
 
[[Category:Miles Davis]]
 +
[[Category:Art Blakey]]

Latest revision as of 21:54, 8 March 2021

Home * Search * with Random Leaf Values

Japanese maple autumn leaves [1]

Search with Random Leaf Values is of interest concerning playing strength, match statistics and search pathology. Randomized evaluation by adding noise concerns evaluation accuracy and evaluation error analysis - it might be used in introducing and learning new evaluation terms for various games or general game playing programs, or simply in randomizing or weakening engine play.

The Beal Effect

Random evaluation was first examined for the game of chess by Don Beal [2] and Martin C. Smith at the Advances in Computer Chess 7 conference at University of Limburg, July 1993, published in the ICCA Journal and conference proceedings [3], and further analyzed by Mark Levene and Trevor Fenner in 1995 [4] and 2001 [5]. Although using random numbers as "evaluation" results in random play with a one ply search (root-random), it was found that the strength of play rises rapidly with increased depth (lookahead-random) using a full-width minimax search. While a natural assumption is that lookahead on random numbers would also result in a random choice at the root as well, random evaluation would create a statistical preference for positions with large mobilty, and thus likely strong material [6].

Setup

To demonstrate this so called Beal Effect it is neccessary to consider awareness of terminal nodes where mate scores would favour deeper lookahead. Therefor root-random is replaced by lookahead-zero, performing a lookahead with the same search depth as lookahead-random, but non terminal leaves evaluated as zero, only tie-breaking at the root by a random number. Still a very weak player, a five ply search was already sufficient to win all of 100 games versus a random player.

Beal and Smith used following setup to automatically play the games: Draws by stalemate and four cases of insufficient material were recognized (KK, KNK, KBK, KNNK), but 50-move rule or threefold repetition discarded. Therefor games were limited to 200 moves and then WDL adjudicated by +=- material balance (which happend rarely) [7].

Further Experiments

Beal and Smith further applied random evaluations to components rather than the whole evaluation. They used material balance as dominating term plus a random number below one pawn unit. While a five ply search with random component only gained 63% over zero component, quiescing the material balance by exploring a capture tree in order to obtain the chess specific part of the evaluation, the random component gained 97% within the same search depth of five plies.

See also

Publications

1985 ...

1990 ...

2000 ...

Forum Posts

1990 ...

1995 ...

2000 ...

2005 ...

2010 ...

Re: To kick off some technical discussions by Robert Hyatt, OpenChess Forum, June 20, 2010

2015 ...

2020 ...

External Links

feat. Miles Davis, Hank Jones, Sam Jones and Art Blakey

References

  1. ↑ Acer palmatum subsp. matsumurae (Koidz) Ogata, image by 松岡明芳, November 22, 2006, CC BY 3.0, Wikimedia Commons, Autumn leaf color from Wikipedia
  2. ↑ The term "Beal Effect" was coined by Robert Hyatt, see Re: To kick off some technical discussions by Robert Hyatt, OpenChess Forum, June 20, 2010
  3. ↑ Don Beal, Martin C. Smith (1994). Random Evaluations in Chess. Advances in Computer Chess 7
  4. ↑ Mark Levene, Trevor Fenner (1995). A Partial Analysis of Minimaxing Game Trees with Random Leaf Values. ICCA Journal, Vol. 18, No. 1
  5. ↑ Mark Levene, Trevor Fenner (2001). The Effect of Mobility on Minimaxing of Game Trees with Random Leaf Values. Artificial Intelligence, Vol. 130, No. 1
  6. ↑ Re: "random mover" chess programs by Harm Geert Muller, CCC, June 24, 2016
  7. ↑ Don Beal, Martin C. Smith (1994). Random Evaluations in Chess. ICCA Journal, Vol. 17, No. 1

Up one Level

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