First of all, don't worry, it is possible. But you should not try to pass the bonus to the tip nodes. That would indeed give hash problems. The solution is to not change anything in your Search() procedure. That already solves all potential hash problems. You just add the bonus AFTER Search() has returned a value for a particular root move. So that would be done in your SearchRoot(). What you basically do there is change every occurrence of

value = -Search(-beta, -alpha,...)

in

value = bonus[n] - Search(bonus[n]-beta, bonus[n]-alpha,...)

where bonus[n] is the development bonus value for the move you are currently searching. It is all very natural when you think about it. You should consider Search() as a black box. You give it some numbers alpha and beta, and Search() gives you a number x, with the properties that, relative to the real value v of this move,

If v <= alpha, then x <= alpha,

If v >= beta, then x >= beta,

If alpha < v < beta, then x = v.

If you search a move, you want to know if its real value + bonus[n] is bigger than alpha. So you want to know if its real value is bigger than alpha-bonus[n]. So you give Search() the bounds alpha-bonus[n] and beta-bonus[n], and add bonus[n] to the result. And you do this in SearchRoot().

So no fudging with hash table scores whatsoever!

Of course this trick gives all kinds of possibilities. Not only can you stimulate development, or add in some randomization. It is also easy to solve the 'underpromotion' problem: to prevent the program from under-promoting to a rook (in situations where the piece will probably be captured the next move anyway), you give underpromotion moves a penalty. Or in trivially drawn endgames like KRKR you give captures a bonus. Or in not-so-trivially drawn endgames for which tablebases give draw values you give moves that give away a piece (but do not change the outcome) a penalty, hoping that the opponent will make a fatal mistake further on in the game :-)

Ronald de Man

Bloom Filter

Ronald de Man revealed the trick to speed up repetition detection with a Bloom filter, implemented as a small hash table indexed by some lower bits of the hash-key, to increment a counter while entering and decrement the counter while leaving a node ^{[11]}^{[12]} .

Syzygy Bases

In April 2013, Ronald de Man published his Syzygy Bases^{[13]} , a compact endgame tablebase of up to six pieces. It consist of two sets of files, WDL files storing win/draw/loss information considering the fifty-move rule, for access during search, and DTZ files with distance-to-zero information for access at the root^{[14]}^{[15]} .

## Table of Contents

Home * People * Ronald de ManRonald de Man, alias Syzygy,a Dutch mathematician, computer scientist and IP lawyer, in the 90s researcher at Eindhoven University of Technology, competitor at the International Mathematical Olympiad 1990, winning the Silver medal

^{[1]}, and the ACM International Collegiate Programming Contest 1995, to win Bronze within theARoMAteam from Delft University of Technology^{[2]}^{[3]}. He is co-developer of the Linux desktop environment and graphical user interface GNOME^{[4]}, and as chess programmer author of the chess and Antichess^{[5]}playing program Sjaak, which plays at FICS under the handleTrojanKnight^{[6]}^{[7]}^{[8]}. He further ported Stockfish to plain C, dubbed CFish.## Scoring Root Moves

Ronald de Man proposed a method to apply randomness^{[9]}and/or bonuses, i.e. developing bonus, or penalties suggested by an oracle, in scoring moves at the root without any changes in alpha-beta search or leaf evaluation, and without any problems with the transposition table^{[10]}:First of all, don't worry, it is possible. But you should not try to pass the bonus to the tip nodes. That would indeed give hash problems. The solution is to not change anything in your Search() procedure. That already solves all potential hash problems. You just add the bonus AFTER Search() has returned a value for a particular root move. So that would be done in your SearchRoot(). What you basically do there is change every occurrence ofwhere bonus[n] is the development bonus value for the move you are currently searching. It is all very natural when you think about it. You should consider Search() as a black box. You give it some numbers alpha and beta, and Search() gives you a number x, with the properties that, relative to the real value v of this move,If you search a move, you want to know if its real value + bonus[n] is bigger than alpha. So you want to know if its real value is bigger than alpha-bonus[n]. So you give Search() the bounds alpha-bonus[n] and beta-bonus[n], and add bonus[n] to the result. And you do this in SearchRoot().So no fudging with hash table scores whatsoever!Of course this trick gives all kinds of possibilities. Not only can you stimulate development, or add in some randomization. It is also easy to solve the 'underpromotion' problem: to prevent the program from under-promoting to a rook (in situations where the piece will probably be captured the next move anyway), you give underpromotion moves a penalty. Or in trivially drawn endgames like KRKR you give captures a bonus. Or in not-so-trivially drawn endgames for which tablebases give draw values you give moves that give away a piece (but do not change the outcome) a penalty, hoping that the opponent will make a fatal mistake further on in the game :-)Ronald de Man## Bloom Filter

Ronald de Man revealed the trick to speed up repetition detection with a Bloom filter, implemented as a small hash table indexed by some lower bits of the hash-key, to increment a counter while entering and decrement the counter while leaving a node^{[11]}^{[12]}.## Syzygy Bases

In April 2013, Ronald de Man published his Syzygy Bases^{[13]}, a compact endgame tablebase of up to six pieces. It consist of two sets of files,WDLfiles storing win/draw/loss information considering the fifty-move rule, for access during search, andDTZfiles with distance-to-zero information for access at the root^{[14]}^{[15]}.## Selected Publications

^{[16]}1995).On Composants of Solenoids. Fundamenta Mathematicae 147, pdf^{[17]}1999).The Generating Function for the Number of Roots of a Coxeter Group. Journal of Symbolic Computation, Vol. 27, No.6^{[18]}2003)Managing service-level agreements in metro ethernet networks using backpressure. Bell Labs Technical Journal, Vol. 8, No. 2^{[19]}.## Forum Posts

^{[20]}^{[21]}## External Links

Syzygy (mathematics) from Wikipedia

## References

2002).The design and implementation of the Rookie 2.0 Chess Playing Program. Masters Thesis, pdf2016).Compression of underdetermined data in a 7-piece chess table. Moscow University Computational Mathematics and Cybernetics, Vol. 40, No. 1## What links here?

Up one level