7-men EGTB Bounty

[jshriver]

I am faaaar from rich, but have a few pennies I'd be willing to donate to such a "fund" and more importantly willing to donate bandwidth to the cause.

I'm greatful for Nalimov, but w/o an open source or "non requiring author for authorization license" egtb generation/probing is at a stand still right now.

Anxious to see the results.
-Josh

[Kirill Kryukov]

My doubtz about syzygy's format are:
1. How much his tables will be larger than WDL50?
2. How much the access will be slower than WDL50?
If the answer is "tiny difference" for both questions, then I don't see any problem. If the answer is something like "10% different" or more (for any of the questions), then I would prefer a simple WDL50 for players + additional WDL(>50) for those who need it. Note that the difference should be probably measured not on the whole 7-men set, but on the most useful tables, which will be accessed more often.

In my estimation DTZ50+ tables should not be more than 1% larger. In any case I don't see how it could be close to 10%. The most useful tables will be tables with several pawns. Those will normally have quite low distance to zero values and should hardly be affected, if at all. (Note that DTZ50+ compared to DTZ50 does not affect positions that are won under the 50-move rule, but that would convert to "cursed positions" when using the DTZ-metric. DTZ50+ should be more efficient than taking a DTZ-table and storing in addition the delta with DTZ50, or the other way around.)

Btw, I wouldn't call it a "format". The precise file format is to a large extent independent of the metric used. Choices made in picking a file format will have a huge impact on table size and access times (much more than the choice between DTZ50, DTZ50+ or DTZ).

If the difference is just 1% in both space and access time, for both DTZ50+ and WDL50+, then I don't have any problems with DTZ50+ and WDL50+. Note that it is WDL50 (or WDL50+) that needs fastest possible access, not DTZ50+.

[kronsteen]

If the difference is just 1% in both space and access time, for both DTZ50+ and WDL50+, then I don't have any problems with DTZ50+ and WDL50+. Note that it is WDL50 (or WDL50+) that needs fastest possible access, not DTZ50+.

Note that going for WDL50+ instead of WDL50 will need capability to store 5 different states (win, draw, loss, cursed win, blessed loss) instead of 3. True, endings containing lots of CW/BL (of the krbknn type) will be few, but they will be far more than 6-men. Also, the majority of endings will contain CW/BL positions even if such positions are very few. Take for example kqqbbkn, the material is heavily unbalanced, but one can find blessed losses in bn takes a wq with check, forking the 2nd wq in the process, and after taking it reaches a blessed loss in kbbkn. So, adding CW/BL possibilities will in many WDL50 tables result in spreading a thin powder of « 4 » and « 5 » in an ocean of « 1 », « 2 » and « 3 ». syz, do you have a compression scheme capable of shrinking such tables almost as hard as same tables without these few « 4 » and « 5 » and allowing access almost as fast for probing code ? If not, one might be afraid that adding these states could hurt final size of compressed files (or access speed) far more than theory says.

[Kirill Kryukov]

If the difference is just 1% in both space and access time, for both DTZ50+ and WDL50+, then I don't have any problems with DTZ50+ and WDL50+. Note that it is WDL50 (or WDL50+) that needs fastest possible access, not DTZ50+.

Note that going for WDL50+ instead of WDL50 will need capability to store 5 different states (win, draw, loss, cursed win, blessed loss) instead of 3. True, endings containing lots of CW/BL (of the krbknn type) will be few, but they will be far more than 6-men. Also, the majority of endings will contain CW/BL positions even if such positions are very few. Take for example kqqbbkn, the material is heavily unbalanced, but one can find blessed losses in bn takes a wq with check, forking the 2nd wq in the process, and after taking it reaches a blessed loss in kbbkn. So, adding CW/BL possibilities will in many WDL50 tables result in spreading a thin powder of « 4 » and « 5 » in an ocean of « 1 », « 2 » and « 3 ». syz, do you have a compression scheme capable of shrinking such tables almost as hard as same tables without these few « 4 » and « 5 » and allowing access almost as fast for probing code ? If not, one might be afraid that adding these states could hurt final size of compressed files (or access speed) far more than theory says.

I'm wondering the same thing, but syzygy is promising 1% difference. In both probing time and file sizes. If it is possible then there is no problem. I mean possible for WDL50+ vs WDL50. I too strongly suspect that the WDL50+ probing will be much slower then WDL50. The question is how much slower. Another question is why bother at all, if you can create a compact and fast WDL50 and compliment it with WDL(>50) for those few who need WDL.

[syzygy]

The difference between WDL50 and WDL50+ in compressed size will indeed be bigger than between DTZ50 and DTZ50+. I would still be surprised if the impact is anywhere close to significant for the more important tables (i.e. those with a few pawns), but of course I could be wrong.

In any case, it would be relatively easy to later convert WDL50+-tables to WDL50-tables in order to optimise for access speed during search. During a search, it's probably not too important to know that a position is not a normal draw but a 50-move rule draw.

Another question is why bother at all, if you can create a compact and fast WDL50 and compliment it with WDL(>50) for those few who need WDL.

It would be double the work, but ok, it all depends on what turns out to be possible.

DTZ50+ is certainly a bit of bother (as 7-piece tables are in general), but if it so happens that it can be implemented without too much trouble, then at least it should be given a try on e.g. some 6-piece tables to get a feeling for the impact.

If the design of the 7-piece generator does not allow for it, then so be it.

[syzygy]

Take for example kqqbbkn, the material is heavily unbalanced, but one can find blessed losses in bn takes a wq with check, forking the 2nd wq in the process, and after taking it reaches a blessed loss in kbbkn.

Nice example

So, adding CW/BL possibilities will in many WDL50 tables result in spreading a thin powder of « 4 » and « 5 » in an ocean of « 1 », « 2 » and « 3 ».

Indeed, and my assumption is that this is the case for most tables.

syz, do you have a compression scheme capable of shrinking such tables almost as hard as same tables without these few « 4 » and « 5 » and allowing access almost as fast for probing code ?

For sure such a compression scheme is required! The one I'm using for my 5-piece tables would be able to handle it. It works basically like this:
1. start with a sequence of symbols, e.g. W/D/L symbols, or W/D/L/C/B symbols. This is the uncompressed table.
2. look for the pair of consecutive symbols that occurs with highest frequency.
3. replace this pair throughout the table by a new symbol.
4. go back to 2, until you reach a predetermined number of symbols, or until there are no consecutive pairs anymore that occur with high frequency.
5. now apply Huffman coding on the resulting sequence.

With this scheme, a "thin layer" will have almost no impact. Probably the thinly spread '4' and '5' symbols will not even be replaced in your example. Their Huffman codes will be quite long, but since they are so rare they will not add noticeably to final size.

To allow for random access, some kind of index must be added to the table so you know where to start decompressing (this is also needed for e.g. datacomp.exe). The nice thing about my coding scheme is that you don't have to decompress whole blocks: you can just parse Huffman symbols starting from the beginning of a block (which can be done really fast), look up how many original symbols are represented by each parsed symbol, and skip symbols until you reach the Huffman symbol that contains the original symbol you need. Then you do a kind of binary search on the 'pairing tree' to get the value you need.

Another nice thing is that it gives an easy way to deal with "don't care values" (for broken positions): replace them by symbols that pair well with their neighbours.

Inspiration for the scheme comes from the RE-PAIR compression scheme by Larsson and Moffat, see here.

[guyhaw]

I've been away on holiday for a week, hence my lack of comment about what has been posted here recently.

EGTs without 'e.p. positions' would be 'regression': Nalimov's include 'e.p. positions'. Positions with castling rights can be added later without affecting the values/depths of positions without castling rights. This is not so re adding 'e.p. positions' later.

Lots of posts from 'sz', and I must confess that I have not had time to get my mind around the complex ideas and notation proposed there. I caution against a "DTZ(k)" notation as (a) the 'k' is a subscript and (b) as jk points out 'DTZ' is a function DTZ:position-->value-depth, and one might want to talk about DTZ(p).

KK noted somewhere that 'we will only note when the 50-move rule makes a difference for positions with DTZ > 50'. If I read that correctly, it is a big error. Please note that KBBKNN has maxDTZ < 50, and yet - because of KBBKN - a major % of the theoretical wins are subject to draw-claims under the 50-move rule.

'DOS' or 'DUS' has been suggested. Apart from KK's lack of enthusiasm with which I agree, it is about the 50-move rule but does not include '50' in its name. 'Blessed' and 'cursed' wins - seems to be a judgemental, emotive and ad hoc notation, not 'mathematical' in the sense that it is not generalisable, so I do not recommend that.

jkominek correctly asks the basic question (as paraphrased here) "How is this community going to manage itself". I suggest it follows the W3C open approach: 'Requests for Comment', 'Requests for Technology' etc. It works.

I also agree with jk's point about sticking with existing metrics. This community has a 'new challenge' in that it has never been shown that a community approach will reliably deliver 'product' that can be trusted as having integrity. It has to meet the requirement of 'performing reliably' and producing something that is self-evidently correct first - which probably means producing something that adds no new knowledge but can be checked against something that exists already.

As I see it, two sets of people who have the latest ideas are not proposing to contribute to this community (which is handicapped by their absence):
- 'SHREDDER' Stefan M-K and Eiko Bleicher have produced 5-man WDL EGTs as product. No 'nod' to k-move rules here.
... their 5-man EGTs are 157MB compared to Nalimov's 7,500MB. There was talk of 6-man WDL EGTs but I see no mention of them at the moment.
- YK has a new, unpublished index-scheme, apparently based on FEG ideas and better than Nalimov's index scheme in some respects
- MB/YK have the experience of producing 7-man EGTs on a more than trivial scale.
... although 'keen' to move to DTZ, even they have not yet gone to the DTZ metric for 7-man P-ful EGTs afaik. It takes thought, skill and time.
... MB generalised 'tbgen' to be his 'gtbgen' - covering M*N boards, fairy pieces and both DTZ and DTZk (and specifically DTZ50) metrics.
All have their reasons which I appreciate. SMK/EB see their WDL EGTs as commercially valuable and their own intellectual property.

In talk of indexing-schemes and EGT values, I think it is being forgotten that a value is needed for 'broken' index-positions, i.e. [and the word 'broken' is not ideal] index-positions for which there is no corresponding legal chess-position. So the 4th value of the WDL EGT is already being used.

Those interested in compositions are not necessarily 'composers', just as those interested in games are not necessarily 'players'.

The comment about the 'DTR' metric (DTR, DTZR) shedding light on KQPKQ is absolutely correct. To that, I add that a DTZ50 EGT 'EZ50' would only provide knowledge which is 50-specific. Any non-DTR metric will recommend moves which, in some position, will walk into an avoidable k-move draw. Therefore, these metrics are all compromising optimal-play in one way or another. Nevertheless, I consider the DTR metric to be at least 'one bridge too far' for this proposed initiative.

g

[kronsteen]

KK noted somewhere that 'we will only note when the 50-move rule makes a difference for positions with DTZ > 50'. If I read that correctly, it is a big error. Please note that KBBKNN has maxDTZ < 50, and yet - because of KBBKN - a major % of the theoretical wins are subject to draw-claims under the 50-move rule.

I found some original text as « (WDL+DTZ) is computed for only those position where Z is more than 50’ ». I think one should read “Z50” instead of “Z”. It is clear that positions with Z>50 are not the same as positions with Z50>50, and we’re interested in the last ones only. It is also clear that positions with Z50>50 can have DTZ less than 50, but in that case the corresponding line of play mathematically leads after the zeroing move to a winning position which is unwinnable under 50-move rule.

It also means that, should DTZ(>50) and DTZ50 tables be joined together, for winning positions unwinnable under 50-move rule one should store, not DTZ, but DTZ+50, in order to avoid any ambiguity. I think this is syz’s original idea. The value contained in the table then allows immediate interpretation : if it is <=50, position is a win under 50-move rule, and value is DTZ50. If it is >50, position is a win but unwinnable under 50-move rule, and position has DTZ = value-50.

Turning to an example, full table could provide info such as “this kbbknn position is winning, but only off 50-move rule. If you shut off 50-move rule, you can win a knight (or force mate instead) in 20 moves and win the resulting kbbkn position, but this resulting position is still unwinnable under 50-move rule”.

[syzygy]

EGTs without 'e.p. positions' would be 'regression': Nalimov's include 'e.p. positions'. Positions with castling rights can be added later without affecting the values/depths of positions without castling rights. This is not so re adding 'e.p. positions' later.

As long as e.p. is taken into account when calculating all other positions, it is not a regression.

... their 5-man EGTs are 157MB compared to Nalimov's 7,500MB.

Nalimov's can be quite a bit improved upon (especially by going to DTZ), but 157MB means they are replacing a lot of information by table searches. That might be worth it, of course. (For sure all 61 tables can be replaced by a 0-bit table and a search function. Same for most 52 tables. 43 tables with low maxDTZ can be replaced by WDL tables (smallest of each wtm, btm-pair). For 43 tables with high maxDTZ you could maybe store (dtz + 4) / 5, instead of dtz and of course only the smallest of wtm, btm. Positions with a winning zeroing move can be set to don't care.)

Hmm, my 5-piece WDL tables are around 700MB I believe, so only keeping the smallest of each (wtm, btm)-pair would leave me at around 300MB, still not close to 157MB... I don't expect setting winning captures to don't care to bridge that gap.

- YK has a new, unpublished index-scheme, apparently based on FEG ideas and better than Nalimov's index scheme in some respects

Interesting. An indexing scheme designed for fast generation, or an indexing scheme designed for excluding as many broken and symmetric positions as possible?

In talk of indexing-schemes and EGT values, I think it is being forgotten that a value is needed for 'broken' index-positions, i.e. [and the word 'broken' is not ideal] index-positions for which there is no corresponding legal chess-position. So the 4th value of the WDL EGT is already being used.

Why not treat them as don't cares for much improved compression?

The comment about the 'DTR' metric (DTR, DTZR) shedding light on KQPKQ is absolutely correct. To that, I add that a DTZ50 EGT 'EZ50' would only provide knowledge which is 50-specific. Any non-DTR metric will recommend moves which, in some position, will walk into an avoidable k-move draw. Therefore, these metrics are all compromising optimal-play in one way or another. Nevertheless, I consider the DTR metric to be at least 'one bridge too far' for this proposed initiative.

Agreed. However, *if* my DTZ50+ proposal can be made to work, it should be possible to adapt the generator to DTR as well. Maybe not the most efficient one, but it should be a nice start for 5-men.

The idea is basically to build a DTZ-generator. Use it for 50 iterations and you have a DTZ50-generator. Use it for 50 iterations, merge in conversions to 50-move rule draws, iterate to the end, and you have a DTZ50+-generator. Do 1 iteration, merge in conversions to 1-move rule draws, do a 2nd iteration, merge in conversions to 2-move rule draws, do a 3rd iteration, etc., and you get DTR.

[syzygy]

It also means that, should DTZ(>50) and DTZ50 tables be joined together, for winning positions unwinnable under 50-move rule one should store, not DTZ, but DTZ+50, in order to avoid any ambiguity. I think this is syz’s original idea. The value contained in the table then allows immediate interpretation : if it is <=50, position is a win under 50-move rule, and value is DTZ50. If it is >50, position is a win but unwinnable under 50-move rule, and position has DTZ = value-50.

Exactly. One clarification: In the case >50, value-50 is the number of moves to either a conversion, or to a position that would be won under the 50-move rule (but once you reach it you won't have enough moves left, at least with optimal play from both sides).

Turning to an example, full table could provide info such as “this kbbknn position is winning, but only off 50-move rule. If you shut off 50-move rule, you can win a knight (or force mate instead) in 20 moves and win the resulting kbbkn position, but this resulting position is still unwinnable under 50-move rule”.

Except that forcing a mate in 20 moves would mean a win . But yeah, if the value=70, one "optimal" line of play could convert into a "cursed" KBBKN position (in 20 moves), another optimal line of play could lead to a mate in 70. Or 70 moves to convert into a position won under the 50-move rule. In the last two cases it is 20 moves to convert into a win under 50-move rule.

Engines don't even need to know this, although it might be nice to teach them that values>50 are not really won.

[guyhaw]

sz's idea that one calculates a DTZ50 EGT, then relaxes the k-move rule by one to add the new 'DTZ51' wins and so on ... and that this gives DTR is quite wrong - on two counts.

First, one generates a DTZ50 EGT from the DTZ50 EGTs of possibly-succeeding endgame. So, in creating more wins (under a 51-move rule) in succeeding endgames, the depths of positions in the target endgame may be less under a 51-move rule than under a 50-move rule. Thus, the 'new wins' are not just one move away from the old 50-move rule wins.

Secondly, under DTZ, the loser never makes a capture unless it is their only move. With the DTR metric, the loser may well capture to get into a longer succeeding phase. [This is why my assumption of years ago that DTZ50 >= DTZ is wrong.] 'KBN5/8/8/8/8/8/Q7/1k6 b' is a case in point: under DTR, Black takes then Queen.'

Nesting up' a set of DTZk EGTs is not only wrong but will not produce such voluntary captures to loss.

g

[Kirill Kryukov]

I realized that a DTZ50 + DTZ(>50) combination won't provide a DTZ, because DTZ50 table does not contain DTZ. So I no longer propose an dual metric of DTZ50 + DTZ(>50). Something like syzygy's idea should be used, or alternatively two totally different tables for DTZ50 and DTZ.

WDL50 + WDL(>50) however should still provide a perfectly fine WDL.

I updated the requirement draft in the first post. I think DTZ50, DTZ, WDL50 and WDL should be all in the requirement. The details of the implementation (combined vs separate files, etc) will be up to the implementator. The review board (not assembled yet) will have to consider the compactness and performance of each submitted solution.

It's OK to not store the EP positions in the tables as long as the tables are EP-correct and the probing code performs the necessary search automatically.

Suggestions and comments are welcome.

[Kirill Kryukov]

KK noted somewhere that 'we will only note when the 50-move rule makes a difference for positions with DTZ > 50'. If I read that correctly, it is a big error. Please note that KBBKNN has maxDTZ < 50, and yet - because of KBBKN - a major % of the theoretical wins are subject to draw-claims under the 50-move rule.

Yes, I understand now that DTZ can't be realized by a DTZ50 + DTZ(>50).

- 'SHREDDER' Stefan M-K and Eiko Bleicher have produced 5-man WDL EGTs as product. No 'nod' to k-move rules here.
... their 5-man EGTs are 157MB compared to Nalimov's 7,500MB. There was talk of 6-man WDL EGTs but I see no mention of them at the moment.

They can't be directly compared to each other as Shredder bases are WDL, not a DT*. Though this is a good example why a WDL50 is so important - a successful compression may make the whole 7-men WDL50 tables practical to have on current day hardware. A complete 7-men DTZ50 will be not practical for a some years.

In talk of indexing-schemes and EGT values, I think it is being forgotten that a value is needed for 'broken' index-positions, i.e. [and the word 'broken' is not ideal] index-positions for which there is no corresponding legal chess-position. So the 4th value of the WDL EGT is already being used.

This can be done in the probing code? Though in such case it should be optional. Eg. a probing code will have a way to enable or disable the check for broken positions. If an engine never probes broken positions, then the probing code should not waste time checking if a position is broken or not.

[kronsteen]

sz's idea that one calculates a DTZ50 EGT, then relaxes the k-move rule by one to add the new 'DTZ51' wins and so on ... and that this gives DTR is quite wrong - on two counts.

A suggestion : if I’m right, there is a straightforward and readily available path to DTR, provided a DTZk generator already exists : compute DTZk tables for every k (starting with k=1, then k=2, etc... stop when WDLk table is identical to WDLinf. When computing a DTZk table, have WDLk (or DTZk) tables of every daughter ending available first, and refer to these tables and nothing else). When all tables are generated, DTR is k for which position is reported as won in DTZk table and drawn in DTZk-1 table, and DTZR = DTZk. This is inelegant, CPU time consuming, but it saves all efforts needed to build a new generator specifically designed for DTR and for which verifying tests would also be required. As long as we’re talking of 3-men, 4-men, and a few 5-men endings, this might be the best route to quick results.

Exactly. One clarification: In the case >50, value-50 is the number of moves to either a conversion, or to a position that would be won under the 50-move rule (but once you reach it you won't have enough moves left, at least with optimal play from both sides).

May be I miss something, but I don’t see the point in including won positions under 50-move rule as “targets from cursed positions”. When you want to study a winning position which is drawn under 50-move rule, you must make a case for 50-move rule : if you want to neglect it, what you’re interested in is “true” DTZ (or DTC, DTM…). If you want to take it into account, what you’re interested in is a “hopeful” line of play, i.e. which gives you best opportunities to exploit you opponent’s inaccuracies. But even in the latter case, it seems it doesn’t make much sense to head for a won position within 50-move rule which will be in fact unwinnable because of the non-zeroing moves played in order to reach it, and whose optimal line of play must be broken (sometimes very quickly) in order to reset 50-move rule clock. If purpose is to show “hopeful” lines of play in cursed positions, possibilities are :

- DTR : probably best theoretical choice, but out of reach for 7-men, of course
- DTZ : a good practical choice, as it doesn’t specify the phase which will require more than 50 moves (and will therefore need mistakes from opponent), and allows zeroing moves leading to cursed positions, which can be purposeful in many cases
- DTZ50 (note : I define DTZ50 as min number of moves required to force either mate or a zeroing move leading to a winning position under 50-move rule : this definition allows possible DTZ50 values greater than 50) : this choice aims at making every effort to exploit opponent’s inaccuracies in current phase, and precludes delayed strategies (i.e make voluntarily a zeroing move leading to a cursed position, hoping to win it later) which are allowed by DTZ.

My opinion is DTZ is best overall choice for “cursed positions metric”.

[syzygy]

My one-liner for DTR was indeed too optimistic. My method for getting DTZ50+ using a modified DTZ-generator should still work though.

It seems it will be hard to "re-use" a dedicated DTZ-generator for generating DTR.

Exactly. One clarification: In the case >50, value-50 is the number of moves to either a conversion, or to a position that would be won under the 50-move rule (but once you reach it you won't have enough moves left, at least with optimal play from both sides).

May be I miss something, but I don’t see the point in including won positions under 50-move rule as “targets from cursed positions”.

I see now what you mean.

What we agree on is that positions winnable under the 50-move rule and only those should get values <= 50. What is left are the 'winning' positions that are drawn under the 50-move rule.

A position that is drawn under the 50-move rule can be 'winning' when ignoring the 50-move rule for three reasons (or a combination):
1. it is at distance >50 from mate.
2. it is at distance >50 from a conversion to a position that is won under the 50-move rule.
3. it is at distance >0 from a conversion to a position that is 'winning' but drawn under the 50-move rule.

My proposed encoding for these cases is:
1. value = distance.
2. value = distance.
3. value = 50 + distance.
If the position is a combination (e.g. there are case 2 lines of play and there are case 3 lines of play), the value will be the minimum.

In each case the value is > 50, so they don't interfere with the DTZ50-part of the table (all positions winnable under the 50-move rule).

Another sensible encoding is "50 + distance" for all three cases. This will effectively store for each 'cursed win' the value it would have in a full DTZ table (but increased by 50 to avoid interference with the DTZ50-part). So this is exactly your "true" DTZ.

My proposed encoding seems to give a smaller range of values, and should for that reason compress better. However, that needs experimental verification.

For practical gameplay your encoding will prefer a short line of play to a conversion to a cursed win with 6-pieces over a (too) long line of play to a conversion to a real win with 6-pieces. It would be my guess that having the long phase of play with more pieces gives more practical chances.

Theoretically your encoding is probably nicer though. And DTZ50+ with your encoding is easy to generate: generate a DTZ50 table and a DTZ table, then merge the tables while adding 50 to all DTZ values.

it seems it doesn’t make much sense to head for a won position within 50-move rule which will be in fact unwinnable because of the non-zeroing moves played in order to reach it, and whose optimal line of play must be broken (sometimes very quickly) in order to reset 50-move rule clock.

You don't have to break it "quickly". You do have to break it within 50 moves. The opponent must make 50 accurate moves (with 7 pieces on the board), or he might still lose it.

Anyway, I like your encoding about as much as my encoding. I'd like to know if the difference in compression ratio is noticeable. (Taken over all tables it is probably not.)

[guyhaw]

kronsteen's idea - for generating the DTR EGT 'ER' = {(dtr, dtzr)} - by creating a succesion of 'EZk' DTZk EGTs: it's a nice try but it does not work.

The reason is that, as stated previously, in DTZk EGts, the loser does not voluntarily capture to loss. In DTR EGTs, they often do.
Example: KN6/8/8/8/B7/8/Q7/1k6 b. DTZ = DTC = 2 plies (1m) after 1...Kc1 {forced by metric} 2.Qc2#. But DTZR = 1 ply, 1...Kxa2 and DTR = 59 plies (30m).
Exercise: consider how this position is treated when generating a succession of DTZk EGTs: Black always selects Kc1.

I'm not sure that, even if it had worked, it would have been the best way to go - because the prior knowledge available focuses the DTR EGT generation:
- let us suppose we are identifying the wins for 'White'
- the drawn, lost (for White) and broken positions can be marked as 'dealt with', even if the depth of the lost positions is not known
- if maxDTZ(E) > maxDTZ(E's successor endgames) = 'mmxDTZ(E)', then for DTZ > mmxDTZ, we have DTR = DTZR = DTZ
- (DTM >= DTR), DTR >= DTZ, DTR >= DTZR, and indeed maxDTR =< maxDTZ (of endgame 'E' and all its successors)
- so, if DTZ(p) > the current DTR for which positions are being given depths, we need not attempt to give that position a (DTR, DTZR) depth.

Agreed: WDLk EGTs can stand in well, and with great efficiency, for sub-endgames' DTZk EGTs ... and this is now in KK's requirements that they should.
g

[syzygy]

kronsteen's idea - for generating the DTR EGT 'ER' = {(dtr, dtzr)} - by creating a succesion of 'EZk' DTZk EGTs: it's a nice try but it does not work.

Of course it does work.

The reason is that, as stated previously, in DTZk EGts, the loser does not voluntarily capture to loss. In DTR EGTs, they often do.
Example: KN6/8/8/8/B7/8/Q7/1k6 b. DTZ = DTC = 2 plies (1m) after 1...Kc1 {forced by metric} 2.Qc2#. But DTZR = 1 ply, 1...Kxa2 and DTR = 59 plies (30m).
Exercise: consider how this position is treated when generating a succession of DTZk EGTs: Black always selects Kc1.

This position is a draw under the 29-move rule, so by its very definition DTZ_k will mark it as a draw for k < 30 (while advising Qxa2). DTZ_k will mark it as a loss for white for k >= 30.

[syzygy]

A suggestion : if I’m right, there is a straightforward and readily available path to DTR, provided a DTZk generator already exists : compute DTZk tables for every k (starting with k=1, then k=2, etc... stop when WDLk table is identical to WDLinf. When computing a DTZk table, have WDLk (or DTZk) tables of every daughter ending available first, and refer to these tables and nothing else).

This can be somewhat optimized by already merging the N-piece DTZ_k tables into N-piece DTR tables before proceeding to N+1-piece tables. DTR as a daughter table has all you need to generate DTZ_k for each k.

[guyhaw]

Re the kronsteen idea (for generating DTR EGTs from {DTZk} EGTs} which sz is supporting ...

I agree that a succession of DTZk EGTs will pick up the first 'k' for which some position is decisive, and so will determine DTR.

My concern is that we also need DTZR and the correct move, and I don't see where that comes from as, for the position KN6/8/8/8/B7/8/Q7/1k6 b, no DTZk EGT will give DTZR = 1 ply and feature Kxa2 as the move to make.

g

[guyhaw]

As DTR >= DTZ and DTR >= DTZR, I proposed encoding the DTR EGT {(DTR, DTZR)} in the form {(DTR-DTZ, DTR-DTZR)} on the assumption that DTZ EGTs would always be to hand.

I then asked what the 'first' positions would be with entries other than (0, 0) for (DTR-DTZ, DTR-DTZR), and sz helpfully pointed to KQKQ and KRKR.

maxDTZ(KQKQ) = maxDTZ(KQK) = 10 (wtm) but maxDTZ(KRKR) = 4 while maxDTZ(KRK) = 16 (wtm) so even the maxDTZ wtm KRKR win illustrates the point.
8/8/8/R7/8/8/8/rk1K4 w: 1.Rb5+!! Ka2 2.Kc2!! Ka3' 3.Ra5+!! Kb4 4.Rxa1!! with DTC/M/Z = 12m, so ...
... originally DTZ = DTZR = 4m, DTR = 12m and DTR-entries are (8, in moves.

An 'earlier' position will probably exist in KPK where White has to push the Pawn and then manoeuvre the K.
g

[syzygy]

My concern is that we also need DTZR and the correct move, and I don't see where that comes from as, for the position KN6/8/8/8/B7/8/Q7/1k6 b, no DTZk EGT will give DTZR = 1 ply and feature Kxa2 as the move to make.

I think kronsteen is right that dtzr of a position is equal to the position's value in DTZ_k for k = dtr. (It would be good to write down a proof, though.)

In your example, Kxa2 will be a loss for the first time in DTZ_30. In DTZ_30, the position has dtz=1. This leads to (30, 1) in DTR. In DTR, Kxa2 leads to a loss with dtr=30, and Kc1 leads to a loss with dtr=1, so Kxa2 will be picked. (But this is a case where you don't need dtzr to distinguish between positions with equal dtr.)

I don't think it's the most efficient way to generate DTR, but it allows you to base the generation on a DTZ-generator.

[guyhaw]

Two apologies. First, I missed kronsteen's (Aug 13, 6.08pm) proposal that DTZR = DTZk where the 'k' is the smallest 'k' for which the position is decisive.

Also, in my example position KN6/8/8/8/B7/8/Q7/1k6 b, I missed the fact that Black will play 1...Kxa2 when 'k' is small enough for White's KBNK win to be beyond a k-move draw claim.

However, I still question the claim that DTZR = DTZk for the smallest 'k' for which the position is decisive. Maybe the point I am making could be clearer with a different position to discuss. Maybe DTZR = DTZk when the winner makes the move into the next phase [and maybe that is provable, though I don't have a clear mindset on even that yet.]

However, if it is the loser that should be voluntarily making the move into the next phase to minimise DTR, this is not something that the loser does under the DTZk metric (or DTCk), so I think there must be cases where the loser heads off in another direction and DTZR =/= DTZk.

Let us say that depth is measured in plies (as it is most accurately measured, but not as it is commonly measured) and 'k' >= 59 so the above position is a win for White whatever Black does. Black will now not choose 1...Kxa2 as this loses just as 1...Kc1 does. So it will play 1...Kc1 to make DTZk = 2 plies rather than equal to 1 ply. This does not maximise DTR. So DTZk = 2 plies whereas DTZR = 1 ply.

A variant of the above is perhaps clearer. KNB5/8/8/8/8/8/R7/1k6 b: DTZ=3m, DTM=6m, DTZR = 0m/1p with 1...Kxa2 after which DTZ=DTM=30m/59p provided the 'k' of the k-move rule >= 30.

The scenario of Black being forced to capture (under DTC(k) or DTZ(k) metrics) is very rare, and there are occasions when Black would force-capture on the 101st ply of a phase, but would claim the draw first. [This, incidentally, does raise questions about whether a player should be allowed to refuse to play a forced move in order to claim a 50-move draw.] As a result, this scenario has 'caught out' some creators of EGTs, including Nicklaus Wirth whose DTC EGTs had depth in plies (but were one ply out in forced-capture situations).

With the DTR metric, the loser changes phase more often, as they also should do so voluntarily as above. I have not worked out yet what the impact of this is on the EGT-generating algorithm. I think it means that there are two sets of positions being retro'd back 'in parallel', the set where the Winner changes phase and the set where the loser changes phase. This should I think also happen with the DTC(k) and DTZ(k) metrics.

This is all tricky stuff, and my intuition and conjectures on it have often proved wrong.
g

[kronsteen]

***sorry g, I post this only a few minutes later than your previous post, and I haven't had time to take it into account. I hope this will be helpful, though.***

Syz, thanks for your support, but I also understand g’s arguments. Seems some misunderstanding comes from the definition of DTZR.
If DTZR = shortest path to force a zeroing move leading to a win under a k-move rule (k being the DTR of current position), assuming winning/losing side try to min/max its length, then DTZR = DTZk with k=DTR. But it seems that’s not what g wants. In previous example this metric leads to Kc1, not Kxa2
If DTZR = shortest path to force a zeroing move when winning/losing side tries to minimize/maximize DTR, it might be different from DTZk. But this metric falls into a category of metrics which may be more awkward to compute : I call these “metrics strongly influenced by history of position” (let’s call them MSIHP). In case of metrics taking a k-move rule into account, history of position is represented by number of non-zeroing moves previously played in order to reach it. Trouble with MSIHP is that current position on the board is not the only entry required to give full position assessment, information on history of the position is also required. And this can inflate size of TBs a lot.

Some examples :

DTM, DTC, DTZ are not MSIHP : they depend only on current position on the board.

DTZk is not MSIHP : DTZk position status depends on history, but in a very simple way. Let’s call x the number of non-zeroing moves previously played. If x+DTZk<=k, position is a win, DTZk(x) = DTZk(0), and winning line is the same. If x+DTZk>k, position becomes a draw (DTZk(x) becomes = inf).

DTM50, DTC50 are MSIHP. A previous thread wanted to know “shortest legal mate” from a given knnkp position, which was in effect DTM50, i.e not allowing lines falling under 50-move rule draw claim. As DTM50 is MSIHP, this may be difficult to compute, and DTM50 depends on number of moves previously played. Keeping calling x this number, it is perfectly possible that DTM50(x) = 60 for 0<=x<=10, DTM50(x) = 70 for 11<=x<=25, DTM50(x) = 80 for x=26, and DTM50(x)=inf (i.e position becomes a draw) for x>27. And with totally different lines for each case.

DTR is MSIHP. Note it also means that computing a metric designed to show winning lines such as DTZR assumes x=0 in initial position, and there might be no easy way to deduct DTZR(x) from DTZR(0), and positions reached in winning line require DTZR(x), not DTZR(0), evaluation.

My opinions a this stage are :

- DTZR(0) (which is g's DTZR) might be seen as incomplete
- computing DTZR(0) may require, not only DTZk for every k, but also DTZk(x) for every k and every x
- having DTR(x) for every x is heavier, but more complete information than DTR(0) and DTZR(0). In addition, DTR(x) can show practical winning lines : white tries to minimize DTR with each of his moves (black does the opposite), (for reached position he reads DTR(0) if he makes a zeroing move and DTR(x+1) if he doesn't), and even if he can only keep DTR at its current value, a move doing this really makes progress toward victory as it either 1) is a zeroing move or 2) increments x by 1 and then forces quicker apparition of a zeroing move or a move that lowers DTR in subsequent play.
- DTR(x) can be extracted very easily from all DTZk(0) tables, as we can say that :
- for every x, DTZk(x) is x+DTZk(0) if it is <=k, inf instead.
- for every x, DTR(x) is k for which DTZk-1(x) is inf and DTZk(x) is not.
- DTZk(x) and DTR(x) tables are very heavy, but will certainly allow very hard compression as value is often the same for a lot of different 'x'
- From DTR(x), computing DTZR(0) might be easy (but I haven't checked this)

Tricky stuff. I hope this helps towards a goal of future DTR tables. Sorry if you find mistakes, I try to think and write fast, and I've not g's experience on this subject.

[Kirill Kryukov]

Sorry if I am missing something, but I thought we concluded that DTR is not suitable for 7-men EGTB? The reasons:

1. DTR does not always allow to find the best move. So it will have to be supplimented with some additional information.

2. DTR is a non-trivial concept, never tested in practical tables. As I posted somewhere above, even DTM and WDL implementations have numerous bugs. Even if the tables and the probing library are correct, this still does not ensure bug-free user code (engines, etc). And the more complex the metric is (like DTR), the less bug-free implementations we will see. Not to mention the increased risk of bugs in the generator, and increased difficulty of verifying the tables.

3. DTR does not allow easy interchange with WDL, like DTZ does. You can compute the whole set in WDL and only kpppkpp in DTZ, and still get a correct DTZ, same for WDL50 and DTZ50. To compute a DTR table for kpppkpp you need all other tables in DTR first.

While being a theoretically interesting concept, I don't see how DTR can come even close to competing with simpler metrics in practical usefulness. Could someone comment if I am missing something?

[kronsteen]

No, you're correct, current discussion about DTR aims at better understanding of this new concept, helping g (or syz) to program a DTR generator for simple endings (3-5 men perhaps) and trying to raise new knowledge with it on some interesting “target” endings such as kqpkq. This has nothing to do with 7-men, of course. As DTR discussion is somewhat off-topic now, maybe opening a new thread to pursue it would be good idea. Or perhaps we should concentrate on 7-men for now.