Search with Random Leaf Values

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * with Random Leaf Values

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 ...

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