Changes

Jump to: navigation, search

Ronald de Man

11,132 bytes added, 16:19, 31 May 2018
Created page with "'''Home * People * Ronald de Man''' '''Ronald de Man''', [https://en.wikipedia.org/wiki/Alias alias] [https://en.wikipedia.org/wiki/Syzygy Syzygy],<br/> a D..."
'''[[Main Page|Home]] * [[People]] * Ronald de Man'''

'''Ronald de Man''', [https://en.wikipedia.org/wiki/Alias alias] [https://en.wikipedia.org/wiki/Syzygy Syzygy],<br/>
a Dutch mathematician, computer scientist and IP lawyer, in the 90s researcher at [https://en.wikipedia.org/wiki/Eindhoven_University_of_Technology Eindhoven University of Technology], competitor at the [https://en.wikipedia.org/wiki/International_Mathematical_Olympiad International Mathematical Olympiad] 1990, winning the Silver medal <ref>[http://www.imo-official.org/participant_r.aspx?id=2462 International Mathematical Olympiad - Ronald de Man]</ref> , and the [https://en.wikipedia.org/wiki/ACM_International_Collegiate_Programming_Contest ACM International Collegiate Programming Contest] 1995, to win Bronze within the ''ARoMA'' team from [[Delft University of Technology]] <ref>[http://www.delta.tudelft.nl/artikel/-programmeren-hoef-je-niet-te-kunnen/10155 'Programmeren hoef je niet te kunnen' - TU Delta - Weekblad van de Technische Universiteit Delft], March 16, 1995 (Dutch)</ref> <ref>[http://icpc.baylor.edu/past/ ACM Programming Contest World Finals]</ref> . He is co-developer of the [[Linux]] [https://en.wikipedia.org/wiki/Desktop_environment desktop environment] and [https://en.wikipedia.org/wiki/Graphical_user_interface graphical user interface] [https://en.wikipedia.org/wiki/GNOME GNOME] <ref>[http://rpmfind.net/linux/RPM/opensuse/11.1/x86_64/gnome-libs-32bit-1.4.2-11.1.x86_64.html gnome-libs-32bit-1.4.2-11.1.x86_64 RPM]</ref> , and as chess programmer author of the chess and [[Losing Chess|Antichess]] <ref>[http://ilk.uvt.nl/icga/games/losingchess/ ICGA: Losing Chess] by [[Guy Haworth]]</ref> playing program [[Sjaak]], which plays at [[FICS]] under the handle ''TrojanKnight'' <ref>[http://www.nicklong.net/chess/atomic/mewis/trojanknight.txt Statistics for TrojanKnight(C)]</ref> <ref>[http://groups.google.com/group/rec.games.chess.computer/msg/6bb58a0605f7e2f1 Re: AEGON 97/ 1st round: HIARCS lost] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], April 25 1997</ref> <ref>[http://poincare.matf.bg.ac.rs/~andrew/suicide/fics/en0404C.htm FICS Statistics - April 2004, Best Ratings - Computer List]</ref>. He further ported [[Stockfish]] to plain [[C]], dubbed [[CFish]].
<span id="ScoringRootMoves"></span>
=Scoring Root Moves=
[[Ronald de Man]] proposed a method to apply [[Search with Random Leaf Values|randomness]] <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/AI3xadkLEIk/UUqnp9J3BaMJ Re: random play] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], November 28, 1996</ref> and/or bonuses, i.e. developing bonus, or penalties suggested by an [[Oracle|oracle]], in [[Score|scoring]] [[Moves|moves]] at the [[Root|root]] without any changes in [[Alpha-Beta|alpha-beta search]] or [[Evaluation|leaf evaluation]], and without any problems with the [[Transposition Table|transposition table]] <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/me7GkjsEgds/iC_ZJm5UwswJ Re: computer chess "oracle" ideas...] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], April 7, 1997, see also [https://www.stmintz.com/ccc/index.php?id=390268 Re: mate threat extension/null move] by [[Don Beal]], [[CCC]], October 04, 2004 » [[Mate Threat Extensions]], [[Null Move Pruning|Null Move]] and [[Win at Chess|WAC]] booster</ref>:
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 [[Repetitions|repetition detection]] with a [https://en.wikipedia.org/wiki/Bloom_filter Bloom filter], implemented as a small [[Hash Table|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 <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/c431ac1739de871b/d8f8d6ee1b252b86 Re: triple repetition] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], October 27, 1997</ref> <ref>[[Marcel van Kervinck]] ('''2002'''). ''The design and implementation of the Rookie 2.0 Chess Playing Program''. Masters Thesis, [http://alexandria.tue.nl/extra2/afstversl/wsk-i/kervinck2002.pdf pdf]</ref> .

=Syzygy Bases=
In April 2013, Ronald de Man published his [[Syzygy Bases]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47681&start=45 Re: New 6-piece tablebases] by [[Ronald de Man]], [[CCC]], April 10, 2013</ref> , a compact [[Endgame Tablebases|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|fifty-move rule]], for access during search, and '''DTZ''' files with [[Endgame Tablebases#DTZ|distance-to-zero]] information for access at the [[Root|root]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47681 New 6-piece tablebases] by [[Ronald de Man]], [[CCC]], April 01, 2013</ref> <ref>[https://github.com/syzygy1/tb syzygy1/tb · GitHub] by [[Ronald de Man]]</ref> .

=Selected Publications=
<ref>[http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/m/Man:Ronald_de.html DBLP: Ronald de Man]</ref>
* [[Ronald de Man]] ('''1995'''). ''[http://www.ams.org/journals/era/1995-01-02/S1079-6762-95-02005-1/home.html On Composants of Solenoids]''. [https://en.wikipedia.org/wiki/Fundamenta_Mathematicae Fundamenta Mathematicae] 147, [http://matwbn.icm.edu.pl/ksiazki/fm/fm147/fm14726.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Solenoidal_vector_field Solenoidal vector field from Wikipedia]</ref>
* [[Ronald de Man]] ('''1999'''). ''[http://dl.acm.org/citation.cfm?id=312392 The Generating Function for the Number of Roots of a Coxeter Group]''. [http://www.informatik.uni-trier.de/~ley/db/journals/jsc/jsc27.html#Man99 Journal of Symbolic Computation, Vol. 27, No.6] <ref>[https://en.wikipedia.org/wiki/Coxeter_group Coxeter group from Wikipedia]</ref>
* [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/m/Malhotra:Richa.html Richa Malhotra], [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/h/Haalen:Ronald_van.html Ronald van Haalen], [[Ronald de Man]], [http://nl.linkedin.com/in/michielvaneverdingen Michiel van Everdingen] ('''2003''') ''[http://onlinelibrary.wiley.com/doi/10.1002/bltj.10065/abstract Managing service-level agreements in metro ethernet networks using backpressure]''. [http://www.informatik.uni-trier.de/~ley/db/journals/bell/bell8.html#MalhotraHME03 Bell Labs Technical Journal, Vol. 8, No. 2] <ref>[https://en.wikipedia.org/wiki/Metro_Ethernet Metro Ethernet from Wikipedia]</ref> .

=Forum Posts=
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/msg/a30577d2a7a74a51 Re: random play] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], November 28, 1996 <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/ba5f8759ec0ce454 Randomness in move selection] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], December 01, 1996</ref>
* [http://groups.google.com/group/rec.games.chess.computer/msg/9b240379394bc968 Re: Hash functions for use with a transition table] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], March 7, 1997 » [[BCH Hashing]]
* [http://groups.google.com/group/rec.games.chess.computer/msg/0df39371422a600c Re: computer chess "oracle" ideas...] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], April 3, 1997 » [[Oracle]]
* [http://groups.google.com/group/rec.games.chess.computer/msg/ccc2546e26d92f88 Re: computer chess "oracle" ideas...] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], April 7, 1997
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/c431ac1739de871b/d8f8d6ee1b252b86 Re: triple repetition] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], October 27, 1997
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=47681 New 6-piece tablebases] by [[Ronald de Man]], [[CCC]], April 01, 2013 » [[Syzygy Bases]]
* [http://www.talkchess.com/forum/viewtopic.php?t=49702 tablebase caching / mmap() / page cache] by [[Ronald de Man]], [[CCC]], October 13, 2013 » [[Memory]], [[Endgame Tablebases]], [[Syzygy Bases]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59947 Question to syzygy author] by [[Marco Costalba]], [[CCC]], April 24, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60222 tablebase compression / academic integrity] by [[Ronald de Man]], [[CCC]], May 19, 2016 <ref>[[Victor Zakharov]], [[Michael G. Malkovsky]], [[Vladislav Y. Shchukin]] ('''2016'''). ''[http://link.springer.com/article/10.3103%2FS0278641916010076 Compression of underdetermined data in a 7-piece chess table]''. [http://www.springer.com/mathematics/journal/11968 Moscow University Computational Mathematics and Cybernetics], Vol. 40, No. 1</ref>

=External Links=
* [https://github.com/syzygy1/tb syzygy1/tb · GitHub] by [[Ronald de Man]] » [[Syzygy Bases]]
* [https://en.wikipedia.org/wiki/Syzygy Syzygy from Wikipedia]
: [https://en.wikipedia.org/wiki/Syzygy_%28mathematics%29 Syzygy (mathematics) from Wikipedia]
* [hhttp://icga.leidenuniv.nl/icga/games/losingchess/ ICGA: Losing Chess] by [[Guy Haworth]]

=References=
<references />

'''[[People|Up one level]]'''

Navigation menu