Ronald de Man

From Chessprogramming wiki
Jump to: navigation, search

Home * People * Ronald de Man

Ronald 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 the ARoMA team 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 handle TrojanKnight [6] [7] [8]. He ported Stockfish to plain C, dubbed CFish, and to Rust as Rustfish.

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 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,
1. If v <= alpha, then x <= alpha,
2. If v >= beta, then x >= beta,
3. 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] .

Selected Publications

[16]

Forum Posts

1995 ...

2010 ...

External Links

Syzygy (mathematics) from Wikipedia

References

  1. International Mathematical Olympiad - Ronald de Man
  2. 'Programmeren hoef je niet te kunnen' - TU Delta - Weekblad van de Technische Universiteit Delft, March 16, 1995 (Dutch)
  3. ACM Programming Contest World Finals
  4. gnome-libs-32bit-1.4.2-11.1.x86_64 RPM
  5. ICGA: Losing Chess by Guy Haworth
  6. Statistics for TrojanKnight(C)
  7. Re: AEGON 97/ 1st round: HIARCS lost by Ronald de Man, rgcc, April 25 1997
  8. FICS Statistics - April 2004, Best Ratings - Computer List
  9. Re: random play by Ronald de Man, rgcc, November 28, 1996
  10. Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 7, 1997, see also Re: mate threat extension/null move by Don Beal, CCC, October 04, 2004 » Mate Threat Extensions, Null Move and WAC booster
  11. Re: triple repetition by Ronald de Man, rgcc, October 27, 1997
  12. Marcel van Kervinck (2002). The design and implementation of the Rookie 2.0 Chess Playing Program. Masters Thesis, pdf
  13. Re: New 6-piece tablebases by Ronald de Man, CCC, April 10, 2013
  14. New 6-piece tablebases by Ronald de Man, CCC, April 01, 2013
  15. syzygy1/tb · GitHub by Ronald de Man
  16. DBLP: Ronald de Man
  17. Solenoidal vector field from Wikipedia
  18. Coxeter group from Wikipedia
  19. Metro Ethernet from Wikipedia
  20. Randomness in move selection by Robert Hyatt, rgcc, December 01, 1996
  21. Victor Zakharov, Michael G. Malkovsky, Vladislav Y. Shchukin (2016). Compression of underdetermined data in a 7-piece chess table. Moscow University Computational Mathematics and Cybernetics, Vol. 40, No. 1

Up one level