Endgame Metrics
- jshriver
- Posts: 298
- Joined: Tue Jan 31, 2006 5:59 am
- Sign-up code: 0
- Location: Toledo, OH, USA
- Contact:
Endgame Metrics
Over the past couple years I know this has been asked either here or on talkchess, but I have yet to find the question or answer again, so perhaps some ladies or gentlemen here can enlighten me.
What are the different metrics used in egtb's, and second among the known egtb tablebases (nalimov, chessmaster, etc) what do they use as a metric? Also is there a good online description which gives a decent amount of material describing each of these.
Thanks!
-Josh
What are the different metrics used in egtb's, and second among the known egtb tablebases (nalimov, chessmaster, etc) what do they use as a metric? Also is there a good online description which gives a decent amount of material describing each of these.
Thanks!
-Josh
Re: Endgame Metrics
Aaron Tay's FAQ has been the basic reference for quite a few years. http://www.horizonchess.com/FAQ/Winboard/egtb.html .
It appears to have been updated significantly from the last time I've seen it.
Wikipedia also has a good discussion: http://en.wikipedia.org/wiki/Endgame_tablebase .
The help file for Wilhelm also has some explanation of the metrics: http://home.tiscalinet.ch/kruandr/Wilhe ... 20(En).pdf
It appears to have been updated significantly from the last time I've seen it.
Wikipedia also has a good discussion: http://en.wikipedia.org/wiki/Endgame_tablebase .
The help file for Wilhelm also has some explanation of the metrics: http://home.tiscalinet.ch/kruandr/Wilhe ... 20(En).pdf
-
- Posts: 489
- Joined: Sat Jan 21, 2006 10:43 am
- Sign-up code: 10159
- Location: Reading, UK
- Contact:
Re: Endgame Metrics
Aaron Tay's focus on EGTs is good news, but arguably ripe for a review and makeover. Two examples:
1) DTZ EGTs are not 'just theory' but have been generated for 3- to 5-man EGTs, and (obviously) for 6-man P-less endgames where DTZ == DTC.
2) [ DTR EGTs are however still just a theoretical concept. ]
3) Bitbases need more than one bit per position: there are 'draws' and 'broken positions' as in Nalimov DTM EGTs ... so 2 bits is the ration rather than 1.
g
1) DTZ EGTs are not 'just theory' but have been generated for 3- to 5-man EGTs, and (obviously) for 6-man P-less endgames where DTZ == DTC.
2) [ DTR EGTs are however still just a theoretical concept. ]
3) Bitbases need more than one bit per position: there are 'draws' and 'broken positions' as in Nalimov DTM EGTs ... so 2 bits is the ration rather than 1.
g
-
- Posts: 223
- Joined: Mon Feb 19, 2007 8:24 am
- Sign-up code: 0
- Location: Amsterdam
- Contact:
Re: Endgame Metrics
Well, it depends a little bit on how you organize them. I always generate one-sided end-game tables, not distinguishing the positions that are not won for white. So you would need two files to completely describe the end-game as win / draw / loss.
In that case, you can use a single bit per position for bitbases. There is no need to treat broken positions special; they will never be probed, and thus are "don't cares".
In that case, you can use a single bit per position for bitbases. There is no need to treat broken positions special; they will never be probed, and thus are "don't cares".
Re: Endgame Metrics
could one of you please outline the difference between DTZ and DTZ to me?guyhaw wrote:Aaron Tay's focus on EGTs is good news, but arguably ripe for a review and makeover. Two examples:
1) DTZ EGTs are not 'just theory' but have been generated for 3- to 5-man EGTs, and (obviously) for 6-man P-less endgames where DTZ == DTC.
2) [ DTR EGTs are however still just a theoretical concept. ]
3) Bitbases need more than one bit per position: there are 'draws' and 'broken positions' as in Nalimov DTM EGTs ... so 2 bits is the ration rather than 1.
g
Edmund
-
- Posts: 223
- Joined: Mon Feb 19, 2007 8:24 am
- Sign-up code: 0
- Location: Amsterdam
- Contact:
Re: Endgame Metrics
Is that a typo?
Re: Endgame Metrics
sorry, DTZ and DTRh.g.muller wrote:Is that a typo?
Re: Endgame Metrics
Where are the terms DTZ and DTR defined?
Wikipedia says: Haworth has discussed two other metrics, namely "depth to zeroing-move" (DTZ) and "depth by the rule" (DTR). These metrics correct for the fifty move rule, but few tablebases with these metrics have been released to the public Reference: G. McC. Haworth (March 2000). "Strategies for Constrained Optimisation" (PDF). ICGA Journal. Retrieved on 2007-04-01 is given , but I was not able to retrieve the paper from the link http://www.is.reading.ac.uk/common/publ ... /02124.pdf though I tried several times the last few days.
Aaron Tay's FAQ gives: In addition, Distance to zeroing (DTZ) and the superior Distance to rule (DTR)tablebases have being proposed to overcome the fact that DTM and DTC do not recognise the fifty move rule. Only in theory so far.
Wilhelm-Readme gives:
DTZ = Distance to Zeroing Move, this means the distance (measured in moves too) to the move which causes the restart of the move counter until a draw by the 50-move rule would occur or until the mate. In pawnless endgames, the draw due to the 50-move rule can only be avoided by capturing a piece, therefore DTC =DTZ for pawnless endgames.
DTC50 and DTZ50 are in principle the same as DTC and DTZ, but with respect to the 50-move rule. This means that all positions which would be drawn according to the 50-move rule are effectively marked a draw. But note that with DTC50, pawn moves which do not fulfil a DTC criterion are not considered as moves resetting the 50-move counter. DTC(n) and DTZ(n) are the generalisations of DTC50 and DTZ50 for a more general n-move rule.
Wikipedia says: Haworth has discussed two other metrics, namely "depth to zeroing-move" (DTZ) and "depth by the rule" (DTR). These metrics correct for the fifty move rule, but few tablebases with these metrics have been released to the public Reference: G. McC. Haworth (March 2000). "Strategies for Constrained Optimisation" (PDF). ICGA Journal. Retrieved on 2007-04-01 is given , but I was not able to retrieve the paper from the link http://www.is.reading.ac.uk/common/publ ... /02124.pdf though I tried several times the last few days.
Aaron Tay's FAQ gives: In addition, Distance to zeroing (DTZ) and the superior Distance to rule (DTR)tablebases have being proposed to overcome the fact that DTM and DTC do not recognise the fifty move rule. Only in theory so far.
Wilhelm-Readme gives:
DTZ = Distance to Zeroing Move, this means the distance (measured in moves too) to the move which causes the restart of the move counter until a draw by the 50-move rule would occur or until the mate. In pawnless endgames, the draw due to the 50-move rule can only be avoided by capturing a piece, therefore DTC =DTZ for pawnless endgames.
DTC50 and DTZ50 are in principle the same as DTC and DTZ, but with respect to the 50-move rule. This means that all positions which would be drawn according to the 50-move rule are effectively marked a draw. But note that with DTC50, pawn moves which do not fulfil a DTC criterion are not considered as moves resetting the 50-move counter. DTC(n) and DTZ(n) are the generalisations of DTC50 and DTZ50 for a more general n-move rule.
-
- Posts: 489
- Joined: Sat Jan 21, 2006 10:43 am
- Sign-up code: 10159
- Location: Reading, UK
- Contact:
"Constrained Optimisation ..."
The Univ of Reading changed the management of its website, using a Content Management System. As part of this 'move forward', it ditched all my colleagues' web-pages that had their publications attached. Dh's inability to get anything from referenced URLs is part of the fall-out. I seem not to be able to attach .pdf or .doc files here, so will ponder what to do next.
Re: Endgame Metrics
Metrics that have been used:jshriver wrote: What are the different metrics used in egtb's, and second among the known egtb tablebases (nalimov, chessmaster, etc) what do they use as a metric?
- DTM - distance to mate
DTC - distance to conversion
DTZ - distance to zeroing move
DTZ50 - above, considering 50 move rule
WLD - win/loss/draw bitbases
W~W - win / non-win bitbases
- Thompson - DTC
Wirth - DTC
Edwards - DTM
Heinz - DTM
Moreland - ?
Nalimov - DTM
Antonelli - DTM
DeKoning - DTM
Muller - DTM
Shawul - WLD
Melin - WLD (represented as decision trees)
Meyer-Kahlen - W~W (?)
Konoval - DTC/DTZ/DTZ50
Is there any in the above list you'd say has a "decent" amount of material? They're all under-documented. Nalimov's and Heinz's work has the advantage of being described in the literature, but that's targeted at a different audience.Also is there a good online description which gives a decent amount of material describing each of these.
john
getting past the attachment filter
Zip your document file before uploading. The extensions .zip and .gz make it through.guyhaw wrote:I seem not to be able to attach .pdf or .doc files here, so will ponder what to do next.
john
-
- Posts: 223
- Joined: Mon Feb 19, 2007 8:24 am
- Sign-up code: 0
- Location: Amsterdam
- Contact:
Re: Endgame Metrics
Note that I also have versions of my EGTB generator around (now that I revived my laptop with the semi-crashed hard disk) that do DTC in stead of DTM (not posted on my website, though, but it is a small adaptation). When I do DTC50, I actually do not mark positions that take longet than 50 reversible moves to win in this or any later phase as draws, but as won positions with DTC > 50. (So that anyone probing them can see that they are draws, but nevertheless can play them optimally and exploit any fallibility on the opponent's part.
Re: Endgame Metrics
Nice point! This makes use of the "extra" 4th bit-value and provides another bitbase variant. I like it.h.g.muller wrote: When I do DTC50, I actually do not mark positions that take longet than 50 reversible moves to win in this or any later phase as draws, but as won positions with DTC > 50. (So that anyone probing them can see that they are draws, but nevertheless can play them optimally and exploit any fallibility on the opponent's part.
- 00 - normal draw
01 - win
10 - rule-forced draw
11 - loss
- 00 = 0 - rule-forced draw
01 = 1 - win
10 = -2 - loss
11 = -1 - normal draw
john
Re: Endgame Metrics
An updated list, adding Muller's other forms and going back in history. Again: additions are welcome; possible mistakes to be corrected.
john
- Strohlein (1970) - ?
Komissarchik, Arlazarov, Futer (1973) - ?
Clarke (1977) - DTC
Arlazarov, Futer (1978) - ?
Thompson (1975-96) - DTC
van den Herik, Herschbert (1985) - DTM
Nefkens (1985) - DTM
Zellner (1989) - DTC
Stiller (1989-95) - DTC
Edwards (1994) - DTM
DeKoning, Kuijf (1995-2003) - DTM
Heinz (1999) - DTM
Moreland (1999) - ?
Wirth (1999) - DTC
Nalimov (1999-2005) - DTM
Konoval, Bourzutschky (2005-07) - DTC/DTZ/DTZ50
Melin (2006) - WLD (represented as decision trees)
Antonelli (2007) - DTM
Muller (2007+) - DTM, DTC, DTC50
Shawul (2007) - WLD
Meyer-Kahlen (2007) - W~W (?)
Delightful. We can now curse the obnoxious 50-move rule with scientific authority."Since such a line of play would violate the obnoxious 50-move rule, it follows that in this worst case and many others, Black could claim a draw in what is essentially a lost position, had it not been for the sad artifice of this rule." ICCA, vol. 9, no. 1, March 1986, pp. 46.
john
-
- Posts: 489
- Joined: Sat Jan 21, 2006 10:43 am
- Sign-up code: 10159
- Location: Reading, UK
- Contact:
50-move rule ...
The k-move rule does irritate the purist, but not particularly the Studies Community to whom it does not apply.
One can even find P-less 6-man positions in which Black is forced to capture to loss, but can claim a 50-move draw before moving.
g
One can even find P-less 6-man positions in which Black is forced to capture to loss, but can claim a 50-move draw before moving.
g
-
- Posts: 489
- Joined: Sat Jan 21, 2006 10:43 am
- Sign-up code: 10159
- Location: Reading, UK
- Contact:
Re: Endgame Metrics
Ken Thompson did KRPKR and KQPKQ to the DTZ metric. He also did KRNKNN to the DTM metric.
Tamplin generated EGTs to the DTC metric, and then used Bourzutschky's code to work to the DTC, DTZ and DTZ50 metrics on 6-man P-less endgames.
I don't think Konoval has had anything to do with the DTZ and DTZ50 metrics - except when DTZ == DTC because there are no Pawns.
The Konoval-Bourzutschky partnership is exclusively DTC so far, though there were or are plans to go to DTZ.
The Meyer-Kahlen work, in which E.Bleicher has been involved I think, is WLD.
g
Tamplin generated EGTs to the DTC metric, and then used Bourzutschky's code to work to the DTC, DTZ and DTZ50 metrics on 6-man P-less endgames.
I don't think Konoval has had anything to do with the DTZ and DTZ50 metrics - except when DTZ == DTC because there are no Pawns.
The Konoval-Bourzutschky partnership is exclusively DTC so far, though there were or are plans to go to DTZ.
The Meyer-Kahlen work, in which E.Bleicher has been involved I think, is WLD.
g
Re: Endgame Metrics
Updated. More precise dates are appreciated.
- Strohlein (1970) - ?
Komissarchik, Arlazarov, Futer (1973) - ?
Clarke (1977) - DTC
Arlazarov, Futer (1978) - ?
Thompson (1975-96) - DTC (some DTM, DTZ)
van den Herik, Herschbert (1985) - DTM
Nefkens (1985) - DTM
Zellner (1989) - DTC
Stiller (1989-95) - DTC
Edwards (1994) - DTM
DeKoning, Kuijf (1995-2003) - DTM
Heinz (1999) - DTM
Moreland (1999) - ?
Wirth (1999) - DTC
Nalimov (1999-2005) - DTM
Tamplin (?) - DTC
Bourzutschky, Tamplin (?) - DTC, DTZ, DTZ50
Konoval, Bourzutschky (2005-07) - DTC
Melin (2006) - WLD (represented as decision trees)
Antonelli (2007) - DTM
Muller (2007+) - DTM, DTC, DTC50
Shawul (2007) - WLD
Meyer-Kahlen, Bleicher (2007) - WLD (?)