7-men EGTB Bounty

[guyhaw]

I think we are now agreed that a push to create 7-man EGTs and the generation of DTR, i.e. (DTR, DTZR) EGTs - however coded - are diferent initiatives.
So, if KK wants all talk of DTR focussed in another thread, that's your call. However, I would suggest that talk of DTR here has been useful:

- it is a relatively complex subject, and a good test of whether interested parties can discuss technical subtleties effectively in this medium: so far, so good;
- the DTR metric is necessary and sufficient to achieve a win reachable under a k-move rule - and is therefore THE benchmark for the utility of other metrics;
- some good, and near-miss, ideas have been aired and discussed. Some of these should encourage reflection about generating other DTx EGTs.

The DTR metric is a two-number 'depth' (dtr, dtzr): dtr, as previously stated, can 'stick' (because it is controlled by a later phase as in KBBKNN) - which is why decreasing DTZR is a necessary pointer to the goal. So, yes, dtr alone is not enough - but we are talking of (dtr, dtzr) is 'the metric' now for clarity.


To clarify, DTZR IS the length of the shortest path to phase-change, given that (FIRST priority!) the two sides are minimaxing DTR, i.e. the attacker wants to win under a (k=) DTR-move rule AND the defender is maximising DTR. But this IS NOT the same as DTZk in all circumstances. This may seem a counter-intuitive fact, but it is the case - because the loser's FIRST objective under DTZ(k) is to draw or postpone the end of the current phase, not to maximise DTR.

Someone thought that the 'DTR' EGT (dtr, dtzr) was as easy to implement as DTZ(k) - but I never thought that, and I think it is clear that it is not. I have a better algorithm in mind that was described in either my paper which first defined DTR, or in the correcting note later. However this algorithm relies, for best efficiency, on the fact that WDL and DTZ EGTs already exist.

So my ambitions at the moment extend no further than DTR EGTs for 5-man endgames (although the 6-man DTZ EGTs also exist).

Metrics are not 'strong influenced by history of position': they are intrinsic to the position, regardless of how it was reached. What should affect the USE of any table - DTC/M/R/Z(50) - is how many moves are available in the current phase ... hence such move-restricting strategies as SZo, see above. 'Moves available' is a small part of 'history', and one does not need more, unless one is finessing a win against a fallible opponent and willing to increase DTZR but without visiting a position three times (or even twice).

Finally, good to see the 'risk of complexity' being considered by KK. I would expect any candidate 7-man code to reproduce the existing 3- to 6-man results, and be verified as having done so. Without these checkes, confidence cannot be maximised. When MB/JT generated the DTC and DTZ EGTs, JT checked that values aligned with DTM values and that the number of wins/draws/losses was the same [which turned up an error in one Nalimov DTM 5-man stats table, see elsewhere on this board].

g

[syzygy]

However, I still question the claim that DTZR = DTZk for the smallest 'k' for which the position is decisive.

And rightly so. For example, you might have a position with DTR=30 that is one move away from a position with DTR = DTZR = 29 (i.e. current phase is longest phase) and 10 moves away from a conversion into a win with DTR=30. In this case DTZ_30 = 10, but DTZR = 30. Not an actual counterexample, but it shows that there is no reason why in general DTZR = DTZ_k for k = DTR.

However, (DTR, DTZ_k for k = DTR) does seem to be sufficient as a tie-breaker. The winning line first minimizes DTR, and among moves with equal DTR it picks the move with lowest DTZ_k. Along a line of play with constant DTR = k, DTZ_k is strictly decreasing and that is sufficient to avoid loops.

But now I realize that this may still not be enough. Avoiding loops is one thing, but you must also make sure not to waste non-zeroing moves. Although a DTZ_k table will guarantee a win under a k-move rule, following DTZ_30 as long as DTR = 30 stays constant, say for 2 moves, then switching to DTZ_29 once DTR decreases, you could conceivably end up in a line that has 2+29 = 31 moves before a zeroing move occurs. (I don't know if this can actually occur, but I don't immediately see why not and in tablebases what can go wrong does go wrong. It might be possible to find an example for small DTR.)

So DTZR in (DTR, DTZR) seems to be more than just a tie-breaker. However, I'm now afraid that kronsteen is right that DTZR is not sufficient either (see my next post).

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.

Good point.

[syzygy]

The DTR metric is a two-number 'depth' (dtr, dtzr): dtr, as previously stated, can 'stick' (because it is controlled by a later phase as in KBBKNN) - which is why decreasing DTZR is a necessary pointer to the goal. So, yes, dtr alone is not enough - but we are talking of (dtr, dtzr) is 'the metric' now for clarity.

I fully agree that dtr alone is not enough. However, I now question that dtzr is sufficient.

To clarify, DTZR IS the length of the shortest path to phase-change, given that (FIRST priority!) the two sides are minimaxing DTR, i.e. the attacker wants to win under a (k=) DTR-move rule AND the defender is maximising DTR.

Agreed. And I also agree that in general DTZR != DTZ_k.

Now the problem: suppose you start in a position that wins for white with (DTR, DTZR) = (50, 50) and that black has a line to a conversion after 50 moves into a position with again DTR=50. Of course black is lost under the 50-move rule. However, black has very good chances to draw if white is playing according to (DTR, DTZR).

What black should do is follow the line that keeps DTR at 50, until black has a "non-optimal" move into a position with DTR < 50 and DTZR > 50 - move-counter. Of course black is not certain to get this possibility, but the point is that there is no guarantee that black does not.

To see how this can occur, consider the case that 45 moves have been made, and black "gives up" DTR=50 for a position that has DTR=10. By definition this position can still be converted to a winning position within 5 moves. However, white will suddenly focus on preserving DTR=10 instead of making sure to convert within 5 moves. Winning while preserving DTR=10 might easily take 6 moves (i.e. (DTR, DTZR) = (10, 6)) which allows black to claim the draw...

Metrics are not 'strong influenced by history of position': they are intrinsic to the position, regardless of how it was reached.

DTZR is indeed independent of the history of a position, but what kronsteen means is a bit different. He is right, as I realized when trying to explain where he went wrong.

Unfortunately, I don't think this problem can be solved by tweaking the pair (DTR, DTZR).

What should affect the USE of any table - DTC/M/R/Z(50) - is how many moves are available in the current phase ... hence such move-restricting strategies as SZo, see above. 'Moves available' is a small part of 'history', and one does not need more, unless one is finessing a win against a fallible opponent and willing to increase DTZR but without visiting a position three times (or even twice).

With a DTZ-table available, it is possible to make sure the move-counter is reset in time. However, that means losing control of DTR which may then exceed 50. With a DTZ50-table available you can keep the move-counter under control while ensuring that DTR <= 50. So DTR can be used to choose between moves, but it cannot replace DTZ50.

More generally, if you want perfect play under any k-move rule, you need the full DTZ_k table for any k. (I agree with kronsteen that all this information put together can probably be compressed reasonably well, but it is still an enormous amount of information. Far more than (DTR, DTZR) would have taken.)

The good news is that you can as well leave out DTZR and store only DTR.

[kronsteen]

Good point to see that trying to minimize DTR as first priority can cause losing control of length of current phase. IMO, this points towards the same point I raised before : history of position (i.e number of non-zeroing moves previously played, let’s call it x) does have influence on DTR, and in a non-trivial manner.
Let’s go back to the previous kqbnk position suggested by g. Full position assessment is, assuming game is played under a k-move rule and x non-zeroing moves have been previously played :

- If k<=29 and x<k, Kxa2 draws, Kc1 loses (DTR=1)
- If k>=30 and x=k, Kxa2 loses (DTR=29), Kc1 draws
- If k>=30 and x<k both Kxa2 (DTR=29) and Kc1 (DTR=1) lose, but Kxa2 lasts longer and therefore should be chosen by some “second rank decision rule”.

More complex positions might lead to even more complex “full DTR position assessement” with x as a variable. That’s what I mean by “DTR is strongly influenced by history of position”. If a DTZR metric can, in a single number, fully solve this complexity, that would be replacing a function by a number, that would be great simplification, and I would be amazed. I don’t believe (but maybe g can convince me otherwise) this is currently the case with g’s DTZR as, as you correctly realized, a strategy trying to minimize DTR(0) as first priority can theoretically lead to loss of control of length of current phase.

Strategy I suggested on my previous post with DTR(x) resists this loss-of-control problem. It needs this heavy database containing DTR for every position and every number of non zeroing moves previously played (x). But as soon as you have it, this strategy is described as follows : From current position, consider every possible move. If it is a zeroing move, read the number DTR(0) of resulting position. If it is a non-zeroing move, read the number DTR(x+1) of resulting position. Then try to minimize this number if you are attacking side (getting to 0 means achieving mate), try to maximize it if you are defending side (getting to inf means achieving draw). Note also that a very similar scheme might be required in order to compute DTMx or DTCx metrics (by replacing DTR(x) by DTM(x) or DTC(x) in position evaluation), should these metrics be wanted too.

[guyhaw]

[ szy, kr and I are probably pulling the focus to DTR rather than 7-man, but not much else seems to be going on in this thread. ]

It's getting late here, so I will just say that, yes, there is a danger of chasing ever-lower, but ever further-away, targets of DTR (as was recognised in my ICGA_J paper on strategies for endgame play). ]

For this reason, note (above) that my recommended move-filtering strategy is not SV+R-ZR- but SV+ZoZRoR-ZR- ...
[ ... Zo and ZRo guard choice of moves against 'moves available'; don't allow DTZ to get too great, don't chase a DTR if DTZR is too great ]

... or even better SV+BZoZRoR-ZR+
[ 'SB' bans moves that allow the defender to repeat a previous position if the attacker wants to win; ZR+ maximises DTZR over the moves left. ]

There seem to be some hypothetical scenarios being described above: best is to come up with specific positions that demonstrate the point if possible.
g

[syzygy]

Good point to see that trying to minimize DTR as first priority can cause losing control of length of current phase. IMO, this points towards the same point I raised before : history of position (i.e number of non-zeroing moves previously played, let’s call it x) does have influence on DTR, and in a non-trivial manner.

Yes, it is the same point although we might approach it from somewhat different directions. (But it was your point that made me realize it.)

As I understand it, one of your concerns is that you would like a table to give proper information in the case a table is entered at a winning position that is drawn under the 50-move rule, and the 'losing' side make non-optimal moves. Is the information from the table sufficient to determine if the position is already won under the 50-move rule?

At first sight this doesn't seem very important (at least to me). If you enter a table into a 50-move rule draw, then the winning side can only do its best and hope that the losing side messes up. Why would you need to know exactly when you can declare a win... just follow the table and see what happens.

However, this overlooks the fact that a table that does not provide the information you want, also does not provide sufficient information to be able to play optimally. And being able to play out a winning line is very important to me.

You already mentioned that DTM50 lacks the property of being history independent. This is true in the following sense: if you know that a particular position is a mate in 80 if move-counter = 0, you do not know if that same position is still a mate in 80 if move-counter = 1. And for the same reason, what can happen is this: position p is legally won in 80, e.g. 40 moves to a capture and another 40 moves to mate. After one ply from each side, the position may have become legally won in 60, with 50 moves to a capture and another 10 moves to mate. Now the winning side will choose the "faster' mate, which however leads to an unnecessary draw.

My conclusion is that even though DTM50 can be computed in the sense that its value for each position can be determined for the case move-counter = 0, such a table is useless for practical play. The same holds for DTR, for DTC50, etc.

Luckily, DTZ50 is free of this problem. The reason that DTZ50 works fine is that any "tail" of a DTZ-minimizing path is again a DTZ-minimizing path (i.e. if you reset the move-counter in the middle of a path, the remainder of that path stays the same). Also DTZ50+ should be fine. The reason is that if you enter a DTZ50+ table in the DTZ50-part, DTZ50 is all you'll see. And if you enter the table at a cursed position, no "k-move rule"-guarantee is given which further down the line could be spoiled by the history-problem.

Also DTM and DTC (and DTZ) don't have any problems, because they don't give any "k-move rule"-guarantee either.

My DTZ_(k_1 < k_2 < k_3 < ...) notation can be scrapped, as it doesn't define useful tables with the exception of DTZ_k and DTZ_(k < inf) (= "DTZ_k+").

If a DTZR metric can, in a single number, fully solve this complexity, that would be replacing a function by a number, that would be great simplification, and I would be amazed.

I am pretty much convinced that this cannot be solved by adding a single number to DTR.

Strategy I suggested on my previous post with DTR(x) resists this loss-of-control problem. It needs this heavy database containing DTR for every position and every number of non zeroing moves previously played (x).

I believe this is equivalent to having the full DTZ_k information for all k (maybe in a somewhat different format, but still the same huge amount of information).

[syzygy]

It's getting late here, so I will just say that, yes, there is a danger of chasing ever-lower, but ever further-away, targets of DTR (as was recognised in my ICGA_J paper on strategies for endgame play).

I don't have your ICGA_J paper at hand, but I am afraid that there is an inaccuracy in par 5.2 of "Chess endgames: 6-man data and strategy".

The paper states that SR-ZR- is a necessary and sufficient strategy to achieve any win available against best play given a k-move rule. If I understand correctly, SR-ZR- is the strategy that first selects the moves that minimize DTR, and that among moves with equal DTR picks a move that minimizes DTZR. Unfortunately, this is incorrect. See my previous post for a theoretical strategy that should sometimes work for the losing side (given that everything than can go wrong, will go wrong in tablebases).

I suspect that the oversight occurred through assuming that it is sufficient to consider "optimal play" by the losing side. SR-ZR- indeed works fine if black is so kind to use SR+ZR+ (or just SR+). However, a strategy is only winning if it wins against all possible strategies that the losing side could use.

For this reason, note (above) that my recommended move-filtering strategy is not SV+R-ZR- but SV+ZoZRoR-ZR- ...
[ ... Zo and ZRo guard choice of moves against 'moves available'; don't allow DTZ to get too great, don't chase a DTR if DTZR is too great ]

I don't know the definition of V+. If a k-move rule is used and Zo employs DTZ_k to throw out all moves that require more moves than 'moves available', then any strategy starting with SZo preserves wins (disregarding draw by rep), but wouldn't that be SZko and not SZo? Any strategy that could potentially start by throwing out the only move that according to DTZ_k and "moves available" preserves the win, will fail.

There seem to be some hypothetical scenarios being described above: best is to come up with specific positions that demonstrate the point if possible.

I think it shouldn't be hard to find a position on which e.g. SR-ZR- fails to preserve a win under the k-move rule for a low value of k. I'll try to find one later, but in any case the 'existence' of a hypothetical scenario makes it extremely unlikely that no such positions exist in the whole of chess.

I don't think this position is what I'm looking for but it's a start: White: Ka6, Rd4, Black: Pa7 Kc8. black to move, 1 "available move", and a k-move rule with k sufficiently high to win KRK. If black applies SR+ZR+, it will play Kc7. Then Kxa7 and white wins. Black can draw by playing Kb8, but SR+ZR+ will discard this move since it lowers DTR too much. So SR+ZR+ may lose positions that are drawn.

[guyhaw]

sz: If I said somewhere that SR-ZR- was the necessary and sufficient strategy to win a win that was winnable under a k-move rule, that was a slip: thank you for pointing that out. Particularly clumsy of me, as I knew that right at the beginning when I defined DTR and DTZR.

'Winnable' implies that DTZR is =< 'moves available'. All that is needed is to keep the lid on DTR, obviously reduce DTZR by 1 at each stage, and reduce DTR by 1 at the same time if possible. Strategies SZo and SZRo needs to 'guard' the length of the current phase to prevent the attacker chasing a DTR that is 'out of reach'. After all, DTR =< k so there's no need to drive it down further. The idea is to win under a k-move rule, not to minimise DTR before ending the current phase.

"Position P is a 'mate in 80' with move-counter 0 but not with move-counter 1" suggests some confusion between the concept of DTM and the concept of winnable-win. DTM is independent of the move-counter: what is dependant on the move-counter is whether a DTM-minimaxing line risks a k-move-rule draw-claim.

SV+ simply filters the move-choice to those that maximise the theoretical value of the position, i.e. do not reduce it. So if you have a win, you should only choose moves that retain the win - obvious really.

g

[syzygy]

'Winnable' implies that DTZR is =< 'moves available'. All that is needed is to keep the lid on DTR, obviously reduce DTZR by 1 at each stage, and reduce DTR by 1 at the same time if possible.

But this is not "all that is needed" to win any position that is won under the 50-move rule. Keeping the lid on DTR is too much to ask. Potentially there is only one winning line under the 50-move rule, and along this line DTR need not be monotonically decreasing (e.g. it might go from 50 to 10 to 15 to 1). When selecting moves by keeping the lid on DTR, reducing DTZR by 1, you can only get a line of play along which DTR never increases, which means you potentially miss that single winning line.

Strategies SZo and SZRo needs to 'guard' the length of the current phase to prevent the attacker chasing a DTR that is 'out of reach'. After all, DTR =< k so there's no need to drive it down further. The idea is to win under a k-move rule, not to minimise DTR before ending the current phase.

The problem is that a (DTR, DTZR)-table will try to minimize DTR, since each position stores the DTR assuming move-counter = 0.

"Position P is a 'mate in 80' with move-counter 0 but not with move-counter 1" suggests some confusion between the concept of DTM and the concept of winnable-win. DTM is independent of the move-counter: what is dependant on the move-counter is whether a DTM-minimaxing line risks a k-move-rule draw-claim.

I did not refer to the concept of DTM, but to the concept of DTM50. DTM is indeed independent of the move-counter, DTM50 is not.

A DTM50-table can be defined and computed (for each position the DTM50-value assuming move-counter = 0), but such a table is not useful.

SV+ simply filters the move-choice to those that maximise the theoretical value of the position, i.e. do not reduce it. So if you have a win, you should only choose moves that retain the win - obvious really.

When talking about k-move rules, this is not so obvious. Does SV+ preserve wins under the 50-move rule while taking into account move-counter? Or is SV+ intended to work "for any k-move rule"?

[guyhaw]

I attach here, zipped (as .pdf is unacceptable!), the original ICGA-published papers introducing DTR/DTZR and correcting, in the DTR Note, the minimax-rule for calculating DTR and DTZR. The presentation of the algorithms for calculating DTR and DTZR is not now the best available, as I've done better in this thread, but they are the only ones formally published. I hope the papers are useful in indicating where I was 'coming from' in creating DTR and DTZR.

sz's admirable probing on DTR/DTZR has however given pause for thought. I think sz is correctly pointing out that, while the attacker can minimise DTR (and then after that DTZR) and the defender cannot increase DTR, the defender may be able to increase DTZR by conceding in DTR terms. I had recognised this in the first paper, but not the possible consequence (which I cannot currently exclude) that this puts a k-move 'winnable' win out of reach.

Certainly, in the current concept of the (DTR, DTZR) EGT, Black is assumed to be maximising DTR and then DTZR, so moves to a lesser DTR but greater DTZR are not considered in the retrograde step.

SV+ filters-down the legal moves to just the moves to positions with the same theoretical value in whatever EGTs are available - DTC/M/Z (or DTZ50 if you prefer).

For some time now, I have been suggesting move-choice strategies other than SR-ZR- (for the reasons above), and I have mentioned:
SV+BZoZRoR-(ZR- or ZR+) where:

SV+ retains the win, ignoring any k-move-draw constraints
SB bans any move that allows the defender to force the attacker back to a position previously visited (twice, or once if you wish)
SZo filters out any moves making DTZ > 'moves available', or picks moves minimising DTZ if there would be no moves available
SZRo filters out any moves chasing a DTR or which DTZR > 'moves available', or minimises DTZR if there would be no moves available
SR- minimises DTR
SZR- minimises DTZR ... or (if preferred)
SZR+ maximises DTZR (without the risk of repeating position becuase of precursor SB) in order to allow the fallible opponent to err more.

However, I am still left wondering now whether 'winnable wins against best play under a k-move draw-rule' are all won by this strategy.
I now suspect not, which is progress of a sort, but counterexamples (especially without DTR EGTs) will be difficult to find.

DTR_ICGA_J_v3.zip

Original paper defining DTR and DTZR

(20.45 KiB) Downloaded 569 times

Strategies_ICGA.zip

Correction to first paper

(328.25 KiB) Downloaded 554 times

Thanks - g

[guyhaw]

Realising the further consequences of the defender not playing a SR+ZR+ strategy but at some stage playing a SZR+... strategy instead ...

When entering the phase, let us assume the win is winnable under a k-move rule (k currently 50). Nothing changes until the defender concedes in DTR terms in order to increase DTZR. This may result in DTZR being =< 'moves available' or not. There seems to be more point in doing it when DTZR is made > 'moves available'. DTR >= DTZR makes this a decreasing opportunity within phase: we would have DTR1 > DTR2 > DTR3 >= DTZR3 etc.

Of course, some example positions would be helpful, for which we do need the (DTR, DTZR) EGT as currently defined.

Maybe I have to rethink what is meant by 'win achievable under the k-move rule': I think that IS precisely the set of wins identified in a DTZk EGT, and it is not now clear to me that that is the same as the set of positions with DTR = k.

Maybe I should rethink how DTZR is backed up: it should perhaps be max(DTZRs available to defender for DTRs =< current DTR) rather than max(DTZRs available for the current DTR). But is it then helpful in pointing the way to the end of phase?

Further thought needed.
g

[syzygy]

I think there are (at least) two ways in which SR-ZR- can go wrong, although the two might on a closer look be manifestations of the same problem.

One is when the losing side concedes DTR to increase DTZR. That this can happen can be seen by consideren positions for which the first phase is not the longest phase. That means DTR stays constant, giving room for black near the end of the first phase to find a "suboptimal" move that increases DTZR above "moves available". (I agree though that this does not prove that this scenario can occur in chess. However...)

The other way is when black does apply SR+ZR+, but DTR along the winning line does not behave as you might expect. What I mean is the following. Fix a position P and look up (DTR, DTZR). This pair is the result of backing up values along a minimax-optimal line starting from a subtable and ending in P. During generation, values are backed up one move per iteration. It is very well possible that this line is crossed (and overwritten) somewhere, let's say in position Q, by a "later" minimax-optimal line. E.g. Q on the line leading to P might have been set to (DTR, DTZR) = (20, 10), while on the "later" line it is set to (DTR, DTZR) = (15, 15). This later line will follow and overwrite the earlier line, setting (20, 11) to (16, 16), (20, 12) to (17, 17), (20, 13) to (18, 18), (20, 14) to (19, 19) and stop at R = (20, 15). Now if P has (50, 50), playing according to SR-ZR- and SR+ZR+ will lead from P to R with 15 moves left. From that point on play will follow the later line (the first 5 moves up to Q coinciding with the earlier line), requiring 20 moves to a zeroing move and thus resulting in a draw. So even if black does apply SR+ZR+, white is not guaranteed to win all positions won under the 50-move rule.

The problem is closely related to the overwriting of values by older lines. That this overwriting of values may happen is acknowledged in your correction note:

In fact, the standard retrograde-analysis algorithm which has already produced EGTs for the DTC, DTZ and DTM metrics (Thompson, 1986) can be used to produce EGTs to the DTR metric. The most familiar DTC version sets dc in the first possible phase, and the same holds for the DTZ version and dz. For the DTM metric, dm may be set in the first possible phase and potentially reduced later, or more efficiently (Wu and Beal, 2001), all positions with DTM = dm can be given their depth correctly in phase dm.

Note that the "more efficient" version does not work for DTM50 since it can't keep track of the move-counter. I have to think a bit what it would mean for (DTR, DTZR), but I am sure it will not solve the problems.

In fact, the problem is not caused by the particular algorithm picked for the generation of the table, but by the fact that the DTR-value of a position with move-counter = x cannot be calculated from the DTR-value of a position with move-counter = 0, as Kronsteen observed.

This still does not give an actual position, which would indeed be nice to have, but for me the important thing is that there is no logically sound reason that such positions do not exist.

Maybe I have to rethink what is meant by 'win achievable under the k-move rule': I think that IS precisely the set of wins identified in a DTZk EGT, and it is not now clear to me that that is the same as the set of positions with DTR = k.

The set of positions with DTR <= k is the set of positions identified by DTZ_k. The set of positions with DTR = k is the set of positions identified by DTZ_k minus the set of positions identified by DTZ_(k-1).

[guyhaw]

... not in best position to study complex arguments too thoroughly as am at the Edinburgh Fest en vacance...

However, no problems arise from the way the (DTR, DTZR) EGT is created. It can be created correctly, both in principle and in practice - and without any over-writing of 'previous values'. The same potential overwriting problem occurs with DTM EGTs until you realise that you should hold onto DTM=m wins in the sub-endgame until cycle 'm' has happened (after which you have all the DTM=m wins).

All EGTs are created on the assumption, not only that the attacker plays, e.g., SM- but that the defender plays SM+.
So, take the EGT 'EM', minimaxing DTM. 'EM' is short for {DTM | SM-/SM+}. JvdH was good enough to point this out to me as we left an ICGA Conference some 7 year ago.
Similarly EGT 'ER', minimaxing (DTR, DTZR), is an abbreviation for {(DTR, DTZR) | SR-SZR-/SR+SZR+}.

An obvious point to make is that, given an initial DTR=k, the current phase itself should not be longer than 'k' if one wanted to limbo under a notional k-move rule. This is an academic objective, and different from minimising DTR at every opportunity given the moves available in the phase.

The defender's best (and maybe only) opportunity to subvert the SR-ZR- strategy is where a later phase controls DTR. SZoZRoR-ZR- introduces two pre-filters which (a) guard the length of the current phase (to the initial DTR if you are a purist), and (b) make sure that DTRs are not chased that are beyond 'moves available'. This is a tough strategy to beat, but it will no doubt be beatable by a defender who can decrease DTR in order to increase DTZR beyond 'moves available'.

When the ER = {(DTR, DTZR)} EGTs exist, we will be in a better position to search for an example of SR-ZR- being subverted. Obviously, the EZ50 = {DTZ50} EGT is necessary and sufficient to win any winnable endgame under a 50-move rule, but it is finessing against a fallible opponent that is interesting.

g


g

[syzygy]

However, no problems arise from the way the (DTR, DTZR) EGT is created. It can be created correctly, both in principle and in practice - and without any over-writing of 'previous values'. The same potential overwriting problem occurs with DTM EGTs until you realise that you should hold onto DTM=m wins in the sub-endgame until cycle 'm' has happened (after which you have all the DTM=m wins).

But that non-overwriting algorithm does not work for DTR (nor for DTM50). It does not work, because pairs like (19, 19) < (20, 15) back up to (20, 20) > (20, 16). The (19, 19)-cycle finds (19, 19). The (20, 15)-cycle will not overwrite (19, 19), because 19 < 20. But now the (20, 16)-cycle will miss positions backed up from potential (20, 15)-positions which (correctly) did not succeed in overwriting the (19, 19) pairs. These positions are picked up in the (20, 20)-cycle, but their values are now incorrect as they should be (20, 16) (since 16 < 20).

I believe the DTC-based algorithm does find the correct (DTR, DTZR)-value for each position (and move-counter = 0), but now winning paths will partially overlap, also causing trouble.

No algorithm will fix this (unless you're prepared to store per position DTR(x) as a function of x = move-counter).

[guyhaw]

sz: I am not following why you think there is a problem with generating the (DTR, DTZR) EGT - though it's entirely reasonable that you find it difficult to see clearly how it is generated. I have only just worked out a simple-to-explain (?) method myself. Anyway, your example is not clear to me.

No (dtr2, dtzr) depths are given to positions until all positions that will get a depth (dtr1, dtzr) with dtr1 < dtr2 have been given those depths.
No (dtr2, dtzr2) depth is given to a position until all positions that will get a depth (dtr2, dtzr1) with dtzr1 < dtzr2 have been given those depths.
There is no question of a position being given a 'temporary' (dtr, dtzr) depth and then having that over-written with the depth it should have.
The 'no overwriting' requirement (of an algorithm) is very important, as otherwise, all sorts of ripple effects would have to be managed.


You are correct that (19, 19) < (20, 15), that (19, 19) backs up to (20, 20), that (20, 15) backs up to (20, 16), and that (20, 20) > (20, 16). Why do you see that as a problem?
I think (it is not clear) that you are proposing some progressions P1 --> P2 that are impossible in (DTR, DTZR) terms ... but maybe you can be clearer in stating your example.

g

[syzygy]

sz: I am not following why you think there is a problem with generating the (DTR, DTZR) EGT - though it's entirely reasonable that you find it difficult to see clearly how it is generated.

It is quite clear to me how the generation works, both with the "DTZ-method" and with the "DTM-method". With the DTZ-method you get (as far as I can tell) correct (DTR, DTZR)-values (for move-counter = 0) and the inherent problems caused by partially overlapping winning lines. With the DTM-method you do not get correct (DTR, DTZR)-values.

We are now considering the DTM-method, i.e. set values to 'm' only in cycle 'm':

No (dtr2, dtzr) depths are given to positions until all positions that will get a depth (dtr1, dtzr) with dtr1 < dtr2 have been given those depths.

And what's more, no (dtr2, dtzr2) depths are given to positions untill all positions that will get a depth (dtr1, dtzr1) with dtr1 < dtr2 have been given those depths. Since you agreed that (19, 19) < (20, 15), I believe you agree to this.

No (dtr2, dtzr2) depth is given to a position until all positions that will get a depth (dtr2, dtzr1) with dtzr1 < dtzr2 have been given those depths.

Agreed.
Thus, the (19, 19)-cycle precedes the (20, 15)-cycle.
In addition, a position that received (19, 19) will not be overwritten to (20, 15), even if there is a (20, 14)-position leading up to it. This is because (19. 19) precedes (20, 15) in the (DTR, DTZR)-metric. I'm sure we agree on this.

Now note that it is very well possible that a position P has (DTR, DTZR) = (19, 19), but also allows for a 15-move long conversion to a win with DTR=20. I will assume P is such a position.

There is no question of a position being given a 'temporary' (dtr, dtzr) depth and then having that over-written with the depth it should have.

Agreed.

The 'no overwriting' requirement (of an algorithm) is very important, as otherwise, all sorts of ripple effects would have to be managed.

The overwriting of the DTZ-method indeed causes ripple effects. But these effects are not caused by the particular way the (correct!) values are generated. The overwriting is not a sign of the resulting values not meeting the definition of (DTR, DTZR), but merely makes visible a problem inherent to the definition of (DTR, DTZR).

You are correct that (19, 19) < (20, 15), that (19, 19) backs up to (20, 20), that (20, 15) backs up to (20, 16), and that (20, 20) > (20, 16). Why do you see that as a problem?

The position P has value (19, 19) so backs up to position Q with value (20, 20).
However, since P allows for a conversion in 15 moves to a position with DTR=20, position Q allows for a conversion in 16 moves to a position with DTR=20. Thus Q should not get value (20, 20), but value (20, 16). The DTM-method does not see this and is therefore incorrect when applied to the (DTR, DTZR)-metric. (20, 20) simply does not meet the definition of (DTR, DTZR).

If this still does not make it clear:
1. Do you agree that the position Q backed up from P (having the stated properties) should be assigned value (20, 16)? After all, there is a 16-move line leading to a conversion into a position with DTR=20. (Of course there might be still other lines leading to an even lower value for Q, but that's not what we are concerned with now.)
2. Do you agree that, since P was assigned value (19, 19) (which in itself is correct), it is impossible that a value of (20, 16) is backed up from P? The only value that can be backed up from (19, 19) is (20, 20).

Note that position R backed up from Q gets value (21, 21) whereas it should get (20, 17), as there is a 17-move line to a conversion into a position with DTR=20. Thus whereas for Q only DTZR is incorrect, for R also DTR is incorrect.

(P, Q, R are all positions with the winning side to move. It is not automatic that P does back up to a position Q and that Q does back up to a position R, since it may be that the losing side has better moves, but it should be clear that the scenario I describe is very likely to occur in all tables with sufficiently many wins.)

[Kirill Kryukov]

Getting back on topic, can everyone involved in discussion please check the requirements in the first post in this thread, and post if you can suggest any improvement?

[kronsteen]

Some suggestions (these are not really new requirements, but details which might not be seen as self-evident when reading current requirement sheet).

- Generator and probing code must be capable of 3-6 men as well as 7-men (including 51 and 51p). 7-men generation will use 6 men TBs as entry data, and it is advisable that such entry data is generated by the same code used for 7-men. This is essentially a warning against some other possibilities for 3-6 men DTZ/WDL TBs generation, such as reuse of existing TBs, which may be seen as easier/faster but is also more prone to bugs or future interfacing problems. Using the same code for generating every table from 3 to 7-men will provide best consistency for the overall set. Existing TBs will nevertheless be very useful for verification purposes (for example checking WDL 3-6 men produced by generator against WDL tables extracted from Nalimov TBs).

- Code must be capable of generating WDL (or WDLk) tables without having to build DTZ (or DTZk) tables first. This will be the only sensible scheme for 7-men, but for 3-6 men one could think of another scheme for mass-production of WDL+DTZ tables in which only DTZ tables are computed and WDL tables are extracted from them. Even if the “WDL only” code is not used for mass production of WDL 3-6 men, 3-6 men may well be the only possibility to check integrity of tables produced by this code, which means it must be capable of 3-6 men also.


I also note that 61 are part of the requirements, but I’m not very enthusiastic for this, my opinion being that 61 are pretty useless, and being backed by the following arguments :

- there exists a simple, well known and general rule for 61 position WDL assessment (which is also valid for X1 in general, X>=4) : attacker always wins, except if it owns only (immediately or after short range tactic from initial position) same-coloured bishops and pawns stored on the rook-file whose queening square is controlled by enemy king but not by the bishops (in which case position is drawn. Ex : Kd5, Bd2, e1, Pa2, a3, a5 / Kb7) ;
- positions escaping this general rule exist but are very exceptional (white pieces bottled up and being unable to untangle themselves) and easily solvable. Ex : Kb8, Qa8, Na1, Pa7, b7, d7 / Kd8 (drawn if wtm, due to wrong parity), or Kb6, Qa6, Ba7, Nb7, b8 / Ka8 (unavoidable stalemate) ;
- there are probably no miniature chess problems of 61 form which require great depth analysis, therefore checking/solving these problems can rely on traditional analysis by chess engines ;
- 61 intended as prerequisite data for 62 is definitely too far thinking.

I suggest to consider 61 capability as optional, in the same way as castling for instance.

[syzygy]

- Code must be capable of generating WDL (or WDLk) tables without having to build DTZ (or DTZk) tables first.

Since DTZ (or DTZk) tables can be built off WDL (or WDLk) subtables, this requirement will always be fulfilled: a generator for DTZ/DTZk can be modified to generate WDL/WDLk in a trivial way.

If what you want instead is a generator specifically optimized for WDL/WDLk, then we're not talking about generator code that is able to generate DTZ/DTZk. "WDL only"-code will have to be completely rewritten to become DTZ-capable.

This will be the only sensible scheme for 7-men, but for 3-6 men one could think of another scheme for mass-production of WDL+DTZ tables in which only DTZ tables are computed and WDL tables are extracted from them. Even if the “WDL only” code is not used for mass production of WDL 3-6 men, 3-6 men may well be the only possibility to check integrity of tables produced by this code, which means it must be capable of 3-6 men also.

I wonder a little why you would want "WDL only"-code if the goal is to produce DTZ.

If you want DTZ/DTZk, the only sensible thing from an engineering point of view seems to be using a DTZ-generator to generate DTZ/DTZk (off WDL/WDLk-subtables) and from these (trivially) generate WDL/WDLk-tables. It seems terribly inefficient to me to first generate all WDL/WDLk-tables and later fully redo all these huge computations to generate DTZ/DTZk-tables. That is just a waste of computational power.

The only reason I can see for doing WDL/WDLk first, is that it is decided that generating DTZ/DTZk must wait for a new generation of hardware and that we want to have "something" now. If that is decided, the only sensible option is generating WDL (and not WDL50), because without DTZ50 it is simply impossible to play anywhere near optimally in the sense of the 50-move rule and so there would not be any practical difference between positions won under the 50-move rule and cursed wins.

[Kirill Kryukov]

Some suggestions (these are not really new requirements, but details which might not be seen as self-evident when reading current requirement sheet).

- Generator and probing code must be capable of 3-6 men as well as 7-men (including 51 and 51p). 7-men generation will use 6 men TBs as entry data, and it is advisable that such entry data is generated by the same code used for 7-men. This is essentially a warning against some other possibilities for 3-6 men DTZ/WDL TBs generation, such as reuse of existing TBs, which may be seen as easier/faster but is also more prone to bugs or future interfacing problems. Using the same code for generating every table from 3 to 7-men will provide best consistency for the overall set. Existing TBs will nevertheless be very useful for verification purposes (for example checking WDL 3-6 men produced by generator against WDL tables extracted from Nalimov TBs).

I thought it was assumed, but now I added explicit requirement for this.

- Code must be capable of generating WDL (or WDLk) tables without having to build DTZ (or DTZk) tables first. This will be the only sensible scheme for 7-men, but for 3-6 men one could think of another scheme for mass-production of WDL+DTZ tables in which only DTZ tables are computed and WDL tables are extracted from them. Even if the “WDL only” code is not used for mass production of WDL 3-6 men, 3-6 men may well be the only possibility to check integrity of tables produced by this code, which means it must be capable of 3-6 men also.

Added as an optional feature.

I also note that 61 are part of the requirements, but I’m not very enthusiastic for this, my opinion being that 61 are pretty useless, and being backed by the following arguments :

- there exists a simple, well known and general rule for 61 position WDL assessment (which is also valid for X1 in general, X>=4) : attacker always wins, except if it owns only (immediately or after short range tactic from initial position) same-coloured bishops and pawns stored on the rook-file whose queening square is controlled by enemy king but not by the bishops (in which case position is drawn. Ex : Kd5, Bd2, e1, Pa2, a3, a5 / Kb7) ;
- positions escaping this general rule exist but are very exceptional (white pieces bottled up and being unable to untangle themselves) and easily solvable. Ex : Kb8, Qa8, Na1, Pa7, b7, d7 / Kd8 (drawn if wtm, due to wrong parity), or Kb6, Qa6, Ba7, Nb7, b8 / Ka8 (unavoidable stalemate) ;
- there are probably no miniature chess problems of 61 form which require great depth analysis, therefore checking/solving these problems can rely on traditional analysis by chess engines ;
- 61 intended as prerequisite data for 62 is definitely too far thinking.

I suggest to consider 61 capability as optional, in the same way as castling for instance.

Agreed, 61 are moved to the optional features.

Although, the simplicity of 61 means that they will compress into almost nothing. So there is no much overhead in computing and having them, I think. (At least in WDL and WDL50 formats).

[Kirill Kryukov]

- Code must be capable of generating WDL (or WDLk) tables without having to build DTZ (or DTZk) tables first.

Since DTZ (or DTZk) tables can be built off WDL (or WDLk) subtables, this requirement will always be fulfilled: a generator for DTZ/DTZk can be modified to generate WDL/WDLk in a trivial way.

"Can be modified" is not good enough. It should be coded, tested, and supported by the author.

If what you want instead is a generator specifically optimized for WDL/WDLk, then we're not talking about generator code that is able to generate DTZ/DTZk. "WDL only"-code will have to be completely rewritten to become DTZ-capable.

Generation performance is now added as an optional feature. Optional features will be used to decide the winner in a tie situations, so a generator that has a special fast code for "WDL only" will have advantage.

This will be the only sensible scheme for 7-men, but for 3-6 men one could think of another scheme for mass-production of WDL+DTZ tables in which only DTZ tables are computed and WDL tables are extracted from them. Even if the “WDL only” code is not used for mass production of WDL 3-6 men, 3-6 men may well be the only possibility to check integrity of tables produced by this code, which means it must be capable of 3-6 men also.

I wonder a little why you would want "WDL only"-code if the goal is to produce DTZ.

If you want DTZ/DTZk, the only sensible thing from an engineering point of view seems to be using a DTZ-generator to generate DTZ/DTZk (off WDL/WDLk-subtables) and from these (trivially) generate WDL/WDLk-tables. It seems terribly inefficient to me to first generate all WDL/WDLk-tables and later fully redo all these huge computations to generate DTZ/DTZk-tables. That is just a waste of computational power.

Most of tables will be generated in WDL or WDL50 first. Then, some important tables will be generated in DTZ or DTZ50, by those who want them. Having a mix of DTZ and WDL is the unique and strong point of our approach.

WDL files are easy to exchange and store. We won't be able to afford massive DTZ for a long time. So it makes perfect sense to incorporate a very fast WDL-only generator, in addition to the logical path DTZ->WDL.

The only reason I can see for doing WDL/WDLk first, is that it is decided that generating DTZ/DTZk must wait for a new generation of hardware and that we want to have "something" now. If that is decided, the only sensible option is generating WDL (and not WDL50), because without DTZ50 it is simply impossible to play anywhere near optimally in the sense of the 50-move rule and so there would not be any practical difference between positions won under the 50-move rule and cursed wins.

Yes, but WDL50 will allow easy creation of DTZ50, for example for kpppkpp ending. So it makes sense to create WDL50.

[guyhaw]

Discussion of DTR/DTZR has been a dialogue between me and szyzygy for a while - so I suggest we go to email if sz is happy with that.
I can be found via Guy ... Haworth ... and the University of Reading.
sz deserves thanks in the Acknowledgements (under their real name) in my next publication mentioning DTR/DTZR for, correctly , questioning the utility of at least the DTZR side of the ER == {(DTR, DTZR)} EGT.
I believe that the concepts of DTR and DTZR are well-defined, and that the issue is whether the EGT ER is being produced in the right way, and maybe whether there can be an ER at all.
It is difficult to think that there can be no EGT 'ER' if DTR and DTZR are indeed well defined.
Anyway, sz et moi can come back in a separate thread after pondering the issues, seeing if they are real, and deciding what if anything can be done about them.
g

[Kirill Kryukov]

You can discuss here if you feel it is related to the topic. Also you are welcome to start a new thread, even if only two people are discussing. Open discussion is good because it adds to the public knowledge base.

I modified the requirements in the first post of this thread. If there are any comments or suggestions, now is a good time to post.

[guyhaw]

I think the key to the further generation of EGTs will be the definition of the index-scheme for positions. This might be something to be decided and made part of the requirement.
It's dangerous to think that anything is 'the last word' in this (or any) area. Nalimov's concept is excellent: I don't know if his code is fully generic or more 'ad hoc'. JdK's FEG took a different approach, which meant that generation was in some senses more efficient, but that random-access was less efficient.
MB has 'cracked' the FEG indexing system (which has not been published) which allowed him to convert FEG EGTs for 'the last 16' 6-man endgames to Nalimov format, just as EN was releasing those last 16 EGTs. The idea of indexing one way for generation, and then converting to a 'use format' for later use is a good one, though it brings Quality Assurance issues in its wake.
The YK/MB index scheme for 7-man is an evolution of the FEG approach but is not pubished. So we know there are better approaches than 'Nalimov' but not what they are. If anyone understands the FEG approach to indexing (and that's me 'out'), they are welcome to contribute on this board.
g

[Kirill Kryukov]

I think the key to the further generation of EGTs will be the definition of the index-scheme for positions. This might be something to be decided and made part of the requirement.
It's dangerous to think that anything is 'the last word' in this (or any) area. Nalimov's concept is excellent: I don't know if his code is fully generic or more 'ad hoc'. JdK's FEG took a different approach, which meant that generation was in some senses more efficient, but that random-access was less efficient.
MB has 'cracked' the FEG indexing system (which has not been published) which allowed him to convert FEG EGTs for 'the last 16' 6-man endgames to Nalimov format, just as EN was releasing those last 16 EGTs. The idea of indexing one way for generation, and then converting to a 'use format' for later use is a good one, though it brings Quality Assurance issues in its wake.
The YK/MB index scheme for 7-man is an evolution of the FEG approach but is not pubished. So we know there are better approaches than 'Nalimov' but not what they are. If anyone understands the FEG approach to indexing (and that's me 'out'), they are welcome to contribute on this board.
g

I think index scheme should be up to the author of the generator. We can't imagine every possible indexing scheme, and you yourself admit that some people have developed clever indexing, which we don't know in detail. So it's a perfectly fine area of research and competition between the solutions. Now the access performance and compactness are listed as a bonus features in the requirements, so a more faster and compact solution will win. How to balance the access speed versus the compactness is the question that the evaluation board will have to think about.