EGTB and draws

[hgm]

My interest in DTZ is mostly related to the 50-move rule,

Well, the most useful, for real games, is DTM50 and it's easy to see that DTZ isn't helping for that goal.
A friend wrote a program for the KNNKP DTM50, and it was not an easy task...

For real games DTZ50 is most useful, right? It will never bungle away any points. As the remark above shows, there DTM50 in the usual meaning does not exist, and you would need to make the 50-move counter part of the game state, making it prohibitively large. There really is not much to say in favor of DTM. It goes for the fastest mate, but who wants that? It leads to very unnatural play.

[wgarvin]

For real games DTZ50 is most useful, right? It will never bungle away any points. As the remark above shows, there DTM50 in the usual meaning does not exist, and you would need to make the 50-move counter part of the game state, making it prohibitively large. There really is not much to say in favor of DTM. It goes for the fastest mate, but who wants that? It leads to very unnatural play.

DTZ50 has lots of useful properties, but if you immediately play the move that leads to the "best" DTZ50 value, the engine might play obnoxiously in endings with pawns. e.g. it would feel compelled to push all of its pawns whenever it can, even if that means promoting 3 queens before going after the enemy with them.

One way to use it might be to continue doing searches, but immediately reject moves that cause you to lose, and also reject any move that would take you to a position that, when you take into account both your current halfmove counter and the DTZ50 value of the position, would take you too long to get to the next zeroing move (in other words: reject any move that would allow the opponent to delay your next zeroing move past 100 halfmoves). In that way, the engine would continue to do whatever "looked good" to its eval, but it would avoid losing, and it would always be forced to make enough progress to win any ending which was actually winnable under the 50-move rule.

Actually, I guess you can use whatever strategy you want to choose the successor moves as long as you avoid 3 things:
(1) don't repeat positions,
(2) don't play any moves that give up your won GTV, and
(3) don't play into any position where it will take you too long to get to the next zeroing move.

[Sven]

There really is not much to say in favor of DTM. It goes for the fastest mate, but who wants that? It leads to very unnatural play.

But for two different winning moves you need to know which one is better, and that is the one with the fastest mate, in the absence of any better rule. If you do not consistently play the move leading to fastest mate then you may end up in never mating at all, or mating only when it is too late due to the 50 moves rule.

What is "unnatural" with playing the perfect moves? It is not how humans play in most cases, but humans make errors. Why not learn the better way?

If mate in 1 is better than mate in 2, and mate in 4 is better than mate in 7, why shouldn't we say that mate in 38 is better than mate in 46?

Addressing the 50 moves problem should therefore be based on DTM. When playing a game, you may encounter the case that your search probes at a node P where the fifty moves counter has the value F. You can get the normal DTM value of P (e.g. mate in N) but if F+N>100 then you need a "DTM50" information telling you the DTM value for fifty=F and considering the 50 moves rule. DTZ does not help to find the best move since the "optimal" move according to DTZ could lead to a position where mating takes much longer than necessary.

For most positions I think that "DTM50" will not have many different values depending on F. DTM50 values could be assigned to ranges of F. Example:

Given a position N, the DTM value when not considering the 50 moves rule is V = +91 (i.e., mate in 91 plies or 46 moves). That means that for F in [0..9] DTM50 is +91. Let's also say that for F > 83 DTM50 is 0 since there is no winning path that zeroes the counter within (100-F) plies, so the position is a draw. For F in [10..83] you need to know whether there is a (possibly longer) path to mate that zeroes the fifty move counter in at most (100-F) plies, and that does also allow to continue with a mating sequence beyond the zeroing move that is still within the (now freshly initialized) 50 moves bounds, a condition which will be met very frequently. So a path that zeroes the counter early but converts into a position with DTM50 > 100 does not help at all, while another path that zeroes later may be preferred if it converts into a position with DTM50 <= 100.

I do not say that it is easy to design such a database, though. Certainly one way would be to enhance the game state by the 50 moves counter (F), as you mentioned. But hopefully there are better ways, since that one might have enormous costs.

Sven

[hgm]

But for two different winning moves you need to know which one is better, and that is the one with the fastest mate, in the absence of any better rule.

You say it: "In absence of a better rule". But the point is of course that better rules are not absent, and perhaps even abundant. Like DTC, DTZ...

If you do not consistently play the move leading to fastest mate then you may end up in never mating at all, or mating only when it is too late due to the 50 moves rule.

This is simply not true. Any progress measure does guarantee you make progress towards mate, and can be used to build tablebases. It is exactly playing for the fastest mate without paying attention to the 50-move rule that leads to 50-move draws from won positions.

What is "unnatural" with playing the perfect moves?

I guess that depends on how you define perfect. If that definition includes moves that suck, I would consider it unnatural to play them. Because I would rather not play moves that suck, even when they are 'perfect'...

It is not how humans play in most cases, but humans make errors. Why not learn the better way?

If mate in 1 is better than mate in 2, and mate in 4 is better than mate in 7, why shouldn't we say that mate in 38 is better than mate in 46?

I had this discussion many times with fellow club members when I was still playing Chess myself, in my student days. They always criticised my moves in the late end-game. "Why do you try to stop his passer with your King? Your passer would have been there earlier. Now it takes much longer to win, because he can step in the square, and then you have to go all the way to his passer to gobble it up, and then move to the other side to drive away his King from before your protected by zugzwang, and keep it protected al the way while you move to promotion...". Next move the opponent resigned, of course, because I had left him no hope. And hope was much more effective metric than DTM.

Addressing the 50 moves problem should therefore be based on DTM. When playing a game, you may encounter the case that your search probes at a node P where the fifty moves counter has the value F. You can get the normal DTM value of P (e.g. mate in N) but if F+N>100 then you need a "DTM50" information telling you the DTM value for fifty=F and considering the 50 moves rule. DTZ does not help to find the best move since the "optimal" move according to DTZ could lead to a position where mating takes much longer than necessary.

For most positions I think that "DTM50" will not have many different values depending on F. DTM50 values could be assigned to ranges of F. Example:

Given a position N, the DTM value when not considering the 50 moves rule is V = +91 (i.e., mate in 91 plies or 46 moves). That means that for F in [0..9] DTM50 is +91. Let's also say that for F > 83 DTM50 is 0 since there is no winning path that zeroes the counter within (100-F) plies, so the position is a draw. For F in [10..83] you need to know whether there is a (possibly longer) path to mate that zeroes the fifty move counter in at most (100-F) plies, and that does also allow to continue with a mating sequence beyond the zeroing move that is still within the (now freshly initialized) 50 moves bounds, a condition which will be met very frequently. So a path that zeroes the counter early but converts into a position with DTM50 > 100 does not help at all, while another path that zeroes later may be preferred if it converts into a position with DTM50 <= 100.

I do not say that it is easy to design such a database, though. Certainly one way would be to enhance the game state by the 50 moves counter (F), as you mentioned. But hopefully there are better ways, since that one might have enormous costs.

Sven

[Sven]

But for two different winning moves you need to know which one is better, and that is the one with the fastest mate, in the absence of any better rule.

You say it: "In absence of a better rule". But the point is of course that better rules are not absent, and perhaps even abundant. Like DTC, DTZ...

You say there are better rules, I say probably there aren't, but we both have not proven either view, so let's keep this point open ...

If you do not consistently play the move leading to fastest mate then you may end up in never mating at all, or mating only when it is too late due to the 50 moves rule.

This is simply not true. Any progress measure does guarantee you make progress towards mate, and can be used to build tablebases. It is exactly playing for the fastest mate without paying attention to the 50-move rule that leads to 50-move draws from won positions.

You misunderstood. I did not intend to say "without paying attention to the 50-move rule", and in fact I stated exactly the opposite further down in my post when writing about "DTM50". See below where you just quoted the most important part of my post without commenting it

Furthermore, just making progress and "zeroing" early enough can be insufficient if you convert to a position with DTM50 > 100 so you can't win anymore.

At this point I believe that we are actually very close in our positions but maybe you did not realize yet. A major difference seems to be that you prefer something like "DTZ50" while I prefer "DTM50".

What is "unnatural" with playing the perfect moves?

I guess that depends on how you define perfect. If that definition includes moves that suck, I would consider it unnatural to play them. Because I would rather not play moves that suck, even when they are 'perfect'...

You qualify moves as "they suck" based on how you learned chess as a human. But tablebases are designed mostly for computers which don't have these feelings. There is no such concept of a "natural" move for a computer.

It is not how humans play in most cases, but humans make errors. Why not learn the better way?

If mate in 1 is better than mate in 2, and mate in 4 is better than mate in 7, why shouldn't we say that mate in 38 is better than mate in 46?

I had this discussion many times with fellow club members when I was still playing Chess myself, in my student days. They always criticised my moves in the late end-game. "Why do you try to stop his passer with your King? Your passer would have been there earlier. Now it takes much longer to win, because he can step in the square, and then you have to go all the way to his passer to gobble it up, and then move to the other side to drive away his King from before your protected by zugzwang, and keep it protected al the way while you move to promotion...". Next move the opponent resigned, of course, because I had left him no hope. And hope was much more effective metric than DTM.

Computers also do not decide based on "hope" And if your opponent resigned based on a "hopeless" position then he probably did not know how to offer maximal resistance.

Would you resign with rook vs. queen? Or would you think that your opponent has to show that he knows how to win? I guess the latter is true. And in that case it would be helpful for you to know how to offer maximal resistance in order to push the inevitable mate as far away as your opponent allows. (This part is not about "DTM50", of course, it is only about the relative importance of the "DTM" way of thinking in general.)

Sven

[wgarvin]

There really is not much to say in favor of DTM. It goes for the fastest mate, but who wants that? It leads to very unnatural play.

I'm not much of a chess player, and I was just assuming that DTM50 + DTZ50 would be a useful combination for playing out endings. At this point I think I would rather just have DTZ50 and come up with heuristics for each ending to try and play "natural looking" moves (but rely on the DTZ50 to make sure it makes enough progress).

The more I think about it, DTZ50 seems like the only useful metric for making sure you actually win positions that are supposed to be won. DTM doesn't solve this problem, nor does DTC, and neither DTM50 nor DTC50 by itself will solve it either. Haworth's DTR/DTZR might be able to do it, but there are still some unsolved consistency issues with that metric (and it is much more complex to reason about than something like DTZ50).

Addressing the 50 moves problem should therefore be based on DTM. When playing a game, you may encounter the case that your search probes at a node P where the fifty moves counter has the value F. You can get the normal DTM value of P (e.g. mate in N) but if F+N>100 then you need a "DTM50" information telling you the DTM value for fifty=F and considering the 50 moves rule. DTZ does not help to find the best move since the "optimal" move according to DTZ could lead to a position where mating takes much longer than necessary.

Disagree about DTM. I agree that DTZ50 might not give the "best move", but one nice thing about DTZ50 is that you can use it to guarantee that you make enough progress to always win a won position before the 50-move rule kicks in and lets your opponent claim a draw. As far as I'm aware, it is the only metric that guarantees this. DTM50 certainly doesn't. While DTM50 databases can certainly be built, they appear to be basically useless for actual play, unless you also have DTZ50 to provide 50-move-rule safety. [Edit: it might take an annoyingly long time to actually win, using DTZ50 to choose the moves. Thats why I suggest to use something else and only use the DTZ50 to prevent unnecessary draws due to the 50-move rule.]

Furthermore, just making progress and "zeroing" early enough can be insufficient if you convert to a position with DTM50 > 100 so you can't win anymore.

This is true, but if your databases are DTZ50, then you will never convert to such a position because you would know it was drawn under the 50-move rule
(i.e. the DTZ50 converting moves are initialized using WLD50 or DTZ50... you can't build a DTZ50 database starting from WLD or DTZ).

[Sven]

It seems I have a problem of correctly understanding the terms DTM50 and DTZ50. Can someone point me, please, to the exact definitions? I only know this one, does that contain the "DTZ50" definition we are talking about here, resp. that is commonly agreed? And where can I find a "DTM50" definition? Up to now I thought to know what was meant but I am no longer sure about it.

Sven

[Sven]

I agree that DTZ50 might not give the "best move", but one nice thing about DTZ50 is that you can use it to guarantee that you make enough progress to always win a won position before the 50-move rule kicks in and lets your opponent claim a draw. As far as I'm aware, it is the only metric that guarantees this. DTM50 certainly doesn't. While DTM50 databases can certainly be built, they appear to be basically useless for actual play, unless you also have DTZ50 to provide 50-move-rule safety. [Edit: it might take an annoyingly long time to actually win, using DTZ50 to choose the moves. Thats why I suggest to use something else and only use the DTZ50 to prevent unnecessary draws due to the 50-move rule.]

Emphasis mine.
Up to now I thought that DTM50 is exactly the combination of DTM and DTZ50 that you are looking for, providing the optimal path to mate in "DTM thinking" while also taking care of the 50-moves rule. So what is your reason to state "DTM50 certainly doesn't [guarantee to always win a won position before the 50-move rule kicks in]"?

Sven

[wgarvin]

I agree that DTZ50 might not give the "best move", but one nice thing about DTZ50 is that you can use it to guarantee that you make enough progress to always win a won position before the 50-move rule kicks in and lets your opponent claim a draw. As far as I'm aware, it is the only metric that guarantees this. DTM50 certainly doesn't. While DTM50 databases can certainly be built, they appear to be basically useless for actual play, unless you also have DTZ50 to provide 50-move-rule safety. [Edit: it might take an annoyingly long time to actually win, using DTZ50 to choose the moves. Thats why I suggest to use something else and only use the DTZ50 to prevent unnecessary draws due to the 50-move rule.]

Emphasis mine.
Up to now I thought that DTM50 is exactly the combination of DTM and DTZ50 that you are looking for, providing the optimal path to mate in "DTM thinking" while also taking care of the 50-moves rule. So what is your reason to state "DTM50 certainly doesn't [guarantee to always win a won position before the 50-move rule kicks in]"?

Sven

In a CCRL thread from 2008, syzygy has described the problem with DTM50 more clearly than I can:

http://kirill-kryukov.com/chess/discuss ... 556#p37556

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.

DTZ50 does not suffer from the same problem, because you're always making moves that have the minimum impact on the halfmove counter. Thus: if you were able to reach your goal within 50 total moves, and you have already made N of them, and you make one more, then you will still be able to reach your goal within 50 total moves. But with DTM50 or DTC50, the path you followed to get to a position (and the resulting halfmove counter) affects what is the "optimal" thing you can do once you're in this position. If your halfmove count=12, then even if you can still win, you might have to choose a different path than the one implied by the DTM50 values which assume halfmove count=0.

[wgarvin]

The names like "DTZ50" seem to be the consensus names for these metrics over at CCRL forum. Everyone is familiar with DTM, DTC and I guess DTZ (Distance-to-Zeroing move). Here are some others:

WLD = "Win/Loss/Draw" which is basically the game-theoretic value (GTV) of the position, with no distance information attached. "Bitbases", basically. Like DTM, DTC and DTZ, WLD does not account for the 50-move.

WLD50 is like WLD, but it only says "win" if you could start from that position, with halfmove counter = 0, and force a win before the 50-move rule kicks in and lets opponent claim a draw. (In positions that can't be zeroed within 50 moves, this type of database reports "draw" instead.)

DTZ50 is just like DTZ, except that when initializing it you have to use WLD50 or DTZ50 information for the successor endgames, instead of WLD or DTZ or DTM or whatever. DTZ50 might include scores above 50, but when consulting the database, if it says something like "win in 53" the engine should treat that as a draw.

DTC50 is just like DTC, except that when initializing it you have to have the successor endgames in a 50-move-aware format like DTC50 or DTZ50 or WLD50 (instead of DTC or DTZ or WLD).

DTM50 is just like DTM, except that when initializing it you have to use DTM50 for the successor endgames, instead of DTM.

[Edit: I think that DTC50 and DTM50 are supposed to have the same GTV values as WLD50 or DTZ50 (with DTZ50 values above 50 treated as "draw"). The distance values will obviously different. You would stop the retrograde generation process after 50 passes, I guess.]