Page 109 of Jesper Torp Kristensen's Master's thesis (Generation and compression of endgame tables in chess with fast random access using OBDDs) refers to a program from the 2003-2004 era called EgmProbe that apparently used decision trees (but using some sort of exception table!) to model chess endgame win/draw/loss results.
In the reference section, this information is given:
[23] Johan Melin: EgmProbe 2.0
http://www3.tripnet.se/∼owemelin/johan/ ... eamer.html
Web searching reveals that Knight Dreamer was a chess engine written by Johan Melin. Unfortunately, archive.org doesn't seem to have anything stored for it, but the web page https://web.archive.org/web/20050207051 ... ~owemelin/ suggests that johan@melin.com at least used to be a functional email address for the program's author.
If anyone has any additional written information about this endgame table implementation or is still in contact with Johan Melin, I would be interested to know about it.
decision-tree based EGTs? Knight Dreamer by Johan Melin
Moderator: Ras
-
Dave Gomboc
- Posts: 29
- Joined: Sun Aug 15, 2021 12:22 am
- Full name: Dave Gomboc
-
hgm
- Posts: 28505
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: decision-tree based EGTs? Knight Dreamer by Johan Melin
The problem with exception tables is that they have to specify the positions, while an EGT containing all positions just has to contain the DTx, the position implied by the indexing scheme. And encoding a position could take a lot of bits. So the rule-based predictions should really be very good befory you gain anything.
OTOH, run-length encoding of a generally drawn WDL EGT could be considered an incrementally encoded exception table, where the rule is that the game is drawn, and the other results are the exceptions. With a less simplistic rule than result=draw the exceptions would become more sparse, and the table even shorter.
If you want DTx rather than WDL things are more difficult. But this is mainly an academic exercise; for playing strength DTx is largely irrelevant, and any other method to guarantee progress in the non-draw sectors of a WDL EGT performs equally well. So it would be really useful (and presumably a lot easier) to have a decision tree that determines such a progress measure for a given position (and tabulate the exceptions to that).
OTOH, run-length encoding of a generally drawn WDL EGT could be considered an incrementally encoded exception table, where the rule is that the game is drawn, and the other results are the exceptions. With a less simplistic rule than result=draw the exceptions would become more sparse, and the table even shorter.
If you want DTx rather than WDL things are more difficult. But this is mainly an academic exercise; for playing strength DTx is largely irrelevant, and any other method to guarantee progress in the non-draw sectors of a WDL EGT performs equally well. So it would be really useful (and presumably a lot easier) to have a decision tree that determines such a progress measure for a given position (and tabulate the exceptions to that).