Search_with_Random_Leaf_Values - peregrineshahin/ChessProgrammingWiki GitHub Wiki
title: Search with Random Leaf Values
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.
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
- Conspiracy Numbers
- Depth
- Diminishing Returns
- Evaluation
- Leaf Node
- Match Statistics
- Mobility
- Playing Strength
- Pseudorandom Number Generator
- Score Granularity
- Scoring Root Moves
- Search Instability
- Search Pathology
- Search versus Knowledge
- Temporal Difference Learning
Publications
1985 ...
- Bruce Abramson (1985). A Cure for Pathological Behavior in Games that Use Minimax. Uncertainty in Artificial Intelligence 1, arXiv:1304.3444
- Bruce Abramson, Richard Korf (1987). A Model of Two-Player Evaluation Functions. AAAI-87. pdf
1990 ...
- Bruce Abramson (1990). Expected-Outcome: A General Model of Static Evaluation. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12, No. 2
- Don Beal, Martin C. Smith (1994). Random Evaluations in Chess. ICCA Journal, Vol. 17, No. 1
- Don Beal, Martin C. Smith (1994). Random Evaluations in Chess. Advances in Computer Chess 7
- Mark Levene, Trevor Fenner (1995). A Partial Analysis of Minimaxing Game Trees with Random Leaf Values. ICCA Journal, Vol. 18, No. 1
- Andreas Junghanns, Jonathan Schaeffer (1997). Search versus knowledge in game-playing programs revisited. IJCAI-97, Vol 1, pdf » Search versus Knowledge in Practice
2000 ...
- Mark Levene, Trevor Fenner (2001). The Effect of Mobility on Minimaxing of Game Trees with Random Leaf Values. Artificial Intelligence, Vol. 130, No. 1, Review in ICGA Journal, Vol. 24, No. 4, pdf
- Ulf Lorenz, Burkhard Monien (2002). The Secret of Selective Game Tree Search, When Using Random-Error Evaluations. Proceedings of 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pdf
- Ingo Althöfer, Susanne Heuser (2005). Randomised Evaluations in Single-Agent Search. ICGA Journal, Vol. 28, No. 1, preprint as pdf
- Brandon Wilson, Austin Parker, Dana S. Nau (2009). Error Minimizing Minimax: Avoiding Search Pathology in Game Trees. pdf
Forum Posts
1990 ...
- Re: Weakest Chess Program needed by Kenneth S A Oksanen, rgc, November 12, 1991
- Re: Human VS computer by Don Beal, rgc, July 11, 1994
1995 ...
- Primitive Chess Program by David Ewart, rgc, June 09, 1995
- Re: Incoporating chess knowledge in chess programs by Bruce Moreland, rgcc, June 28, 1996 » Mobility
- random play by Robert Hyatt, rgcc, November 25, 1996 » Scoring Root Moves
- Randomness in move selection by Robert Hyatt, rgcc, December 01, 1996
- Re: Interesting random chess question - What is probability to win? by Jari Huikari, CCC, October 03, 1998 » Nero
- Random chess statistics, part two by Jari Huikari, CCC, October 14, 1998
- Re: Heinz, Hyatt and Newborn next best move paradox by Robert Hyatt, rgcc, March 19, 1999
- Freeware program with RANDOM eval by Georg von Zimmermann, CCC, November 20, 1999
2000 ...
- Simple Learning Technique and Random Play by Miguel A. Ballicora, CCC, January 18, 2001 » Persistent Hash Table
- Random factor in static evaluation! by Tiago Ribeiro, CCC, June 15, 2001
- Random play by Russell Reagan, CCC, April 08, 2003
- A question about random numbers by Antonio Senatore, CCC, July 22, 2004
2005 ...
- What is "randomness" for a CM9k personality? by Wilma, rgcc, June 12, 2005 » Chessmaster
- Random number mobility scores by Guest, rgcc, September 20, 2008
2010 ...
- Re: To kick off some technical discussions by Robert Hyatt, OpenChess Forum, June 20, 2010
Re: To kick off some technical discussions by Robert Hyatt, OpenChess Forum, June 20, 2010
- Pathology on Game trees by Gerd Isenberg, CCC, July 22, 2010
- Re: Depth vs playing strength by John Merlino, CCC, January 10, 2012 » The King
- Implications of Lazy eval on Don Beal effect in Fail Soft by Henk van den Belt, CCC, November 19, 2014
2015 ...
- How to dumb down/weaken/humanize an engine algorithmically? by Dominik Klein, CCC, January 18, 2015
- "random mover" chess programs by Norbert Raimund Leisner, CCC, June 24, 2016
- Strategies for weaker play levels by Evert Glebbeek, CCC, June 28, 2016
- Adding a random small number to the evaluation function by Uri Blass, CCC, September 03, 2016
- random evaluation perturbation factor by Stuart Cracraft, CCC, April 24, 2017
- Randomizing an evaluation and retiring opening books by Ivan Ivec, FishCooking, November 18, 2017
- Near-random movers by Robert Pope, CCC, February 14, 2018
- Why does stockfish randomise draw evaluations? by Vincent Tang, CCC, September 01, 2019 » Stockfish, Draw Evaluation, Draw Score
2020 ...
- Controlled randomness of evaluation function by nescitus, ProDeo Forum, December 06, 2020
External Links
- Randomization from Wikipedia
- Randomized algorithm from Wikipedia
- Randomness from Wikipedia
- Random tree from Wikipedia
- Random walk from Wikipedia
- Cannonball Adderley - Autumn Leaves (Somethin' Else 1958), YouTube Video
feat. Miles Davis, Hank Jones, Sam Jones and Art Blakey
References
- ↑ Acer palmatum subsp. matsumurae (Koidz) Ogata, image by 松岡明芳, November 22, 2006, CC BY 3.0, Wikimedia Commons, Autumn leaf color from Wikipedia
- ↑ 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
- ↑ Don Beal, Martin C. Smith (1994). Random Evaluations in Chess. Advances in Computer Chess 7
- ↑ Mark Levene, Trevor Fenner (1995). A Partial Analysis of Minimaxing Game Trees with Random Leaf Values. ICCA Journal, Vol. 18, No. 1
- ↑ Mark Levene, Trevor Fenner (2001). The Effect of Mobility on Minimaxing of Game Trees with Random Leaf Values. Artificial Intelligence, Vol. 130, No. 1
- ↑ Re: "random mover" chess programs by Harm Geert Muller, CCC, June 24, 2016
- ↑ Don Beal, Martin C. Smith (1994). Random Evaluations in Chess. ICCA Journal, Vol. 17, No. 1
