Endgame Metrics

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..
Post Reply
User avatar
jshriver
Posts: 298
Joined: Tue Jan 31, 2006 5:59 am
Sign-up code: 0
Location: Toledo, OH, USA
Contact:

Endgame Metrics

Post by jshriver »

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
Dhanish
Posts: 47
Joined: Fri Sep 14, 2007 5:25 am
Sign-up code: 0
Contact:

Re: Endgame Metrics

Post by Dhanish »

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
guyhaw
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Sign-up code: 10159
Location: Reading, UK
Contact:

Re: Endgame Metrics

Post by guyhaw »

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
h.g.muller
Posts: 223
Joined: Mon Feb 19, 2007 8:24 am
Sign-up code: 0
Location: Amsterdam
Contact:

Re: Endgame Metrics

Post by h.g.muller »

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".
Codeman
Posts: 85
Joined: Fri Oct 19, 2007 7:50 pm

Re: Endgame Metrics

Post by Codeman »

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
could one of you please outline the difference between DTZ and DTZ to me?

Edmund
h.g.muller
Posts: 223
Joined: Mon Feb 19, 2007 8:24 am
Sign-up code: 0
Location: Amsterdam
Contact:

Re: Endgame Metrics

Post by h.g.muller »

Is that a typo?
Codeman
Posts: 85
Joined: Fri Oct 19, 2007 7:50 pm

Re: Endgame Metrics

Post by Codeman »

h.g.muller wrote:Is that a typo?
sorry, DTZ and DTR
Dhanish
Posts: 47
Joined: Fri Sep 14, 2007 5:25 am
Sign-up code: 0
Contact:

Re: Endgame Metrics

Post by Dhanish »

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.
guyhaw
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Sign-up code: 10159
Location: Reading, UK
Contact:

"Constrained Optimisation ..."

Post by guyhaw »

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.
jkominek
Posts: 150
Joined: Mon Dec 04, 2006 9:02 am
Sign-up code: 0
Location: Pittsburgh, PA

Re: Endgame Metrics

Post by jkominek »

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?
Metrics that have been used:
  • 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
As I understand it (corrections and additions welcome):
  • 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
My efforts are towards DTM tablebases with derivative WLD bitbases.
Also is there a good online description which gives a decent amount of material describing each of these.
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.

john
jkominek
Posts: 150
Joined: Mon Dec 04, 2006 9:02 am
Sign-up code: 0
Location: Pittsburgh, PA

getting past the attachment filter

Post by jkominek »

guyhaw wrote:I seem not to be able to attach .pdf or .doc files here, so will ponder what to do next.
Zip your document file before uploading. The extensions .zip and .gz make it through.

john
h.g.muller
Posts: 223
Joined: Mon Feb 19, 2007 8:24 am
Sign-up code: 0
Location: Amsterdam
Contact:

Re: Endgame Metrics

Post by h.g.muller »

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.
jkominek
Posts: 150
Joined: Mon Dec 04, 2006 9:02 am
Sign-up code: 0
Location: Pittsburgh, PA

Re: Endgame Metrics

Post by jkominek »

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.
Nice point! This makes use of the "extra" 4th bit-value and provides another bitbase variant. I like it.
  • 00 - normal draw
    01 - win
    10 - rule-forced draw
    11 - loss
An alternative representation is
  • 00 = 0 - rule-forced draw
    01 = 1 - win
    10 = -2 - loss
    11 = -1 - normal draw
such that in 2's complement interpretation: loss < normal draw < rule-forced draw < win. Presumably this would be easier to integrate into a forward search.

john
jkominek
Posts: 150
Joined: Mon Dec 04, 2006 9:02 am
Sign-up code: 0
Location: Pittsburgh, PA

Re: Endgame Metrics

Post by jkominek »

An updated list, adding Muller's other forms and going back in history. Again: additions are welcome; possible mistakes to be corrected.
  • 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 (?)
While conducting this historical search I found a wonderful quote due to van den Herik.
"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.
Delightful. We can now curse the obnoxious 50-move rule with scientific authority.

john
guyhaw
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Sign-up code: 10159
Location: Reading, UK
Contact:

50-move rule ...

Post by guyhaw »

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
guyhaw
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Sign-up code: 10159
Location: Reading, UK
Contact:

Re: Endgame Metrics

Post by guyhaw »

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
jkominek
Posts: 150
Joined: Mon Dec 04, 2006 9:02 am
Sign-up code: 0
Location: Pittsburgh, PA

Re: Endgame Metrics

Post by jkominek »

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 (?)
john
Post Reply