CCRL Discussion Board

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

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

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

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".

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

Is that a typo?

h.g.muller wrote:Is that a typo?

sorry, DTZ and DTR

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.

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.

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

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

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.

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

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

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

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

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