EGTB and draws

[rjgibert]

I got into a discussion with some friends about GM draws and how to structure candidates tournaments, tournaments in general and tiebreaker games, etc. in a better way to produce more fighting chess. One of the things we got into was the scoring of draws e.g. win = 4pts, stalemate = 3 pts, other draws = 2 pts, getting stalemated = 1 and loss = 0 pts. The question arose of how often stalemates occur with one friend contending they were infrequent and me contending they were only infrequent, because how they are scored.

One thing I thought of to sort this out is generating an EGTB with both DTM and DTS (=Distance To Stalemate) information, where giving stalemate would be valued more highly than other draws, but still less than a win. I observed that such an EGTB would remain perfectly usable for ordinary chess and might even have advantages over ordinary EGTBs.

Imagine requiring an opponent to thread their way to a stalemate in 20 to avoid losing. The idea is more pressure would be placed on an opponent to defend accurately if getting stalemate were the only way they could salvage their position. As things are now, all draws are equally weighted in EGTBs even though they are really not.

Another idea is some other distinction between draws besides stalemate in an EGTB e.g. perhaps a computer opponent's use of null move in the endgame is exploitable to win a drawn position or draw a lost position via zugzwang.

So my question is, do these sort of ideas have any value?

[Kirill Kryukov]

One thing I thought of to sort this out is generating an EGTB with both DTM and DTS (=Distance To Stalemate) information, where giving stalemate would be valued more highly than other draws, but still less than a win. I observed that such an EGTB would remain perfectly usable for ordinary chess and might even have advantages over ordinary EGTBs.

I generated exactly this kind of EGTB for 3x3 chess in 2004. It was fun to watch the long stalemate lines, also to try solving "stalemate in N" problems.

I've no idea how useful this kind of EGTB would be for normal chess to improve the play against fallible opponents. I suspect that strength improvement may no be large enough to justify the extra bulk, at least compared to the alternatives.

Imagine requiring an opponent to thread their way to a stalemate in 20 to avoid losing. The idea is more pressure would be placed on an opponent to defend accurately if getting stalemate were the only way they could salvage their position. As things are now, all draws are equally weighted in EGTBs even though they are really not.

Another idea is some other distinction between draws besides stalemate in an EGTB e.g. perhaps a computer opponent's use of null move in the endgame is exploitable to win a drawn position or draw a lost position via zugzwang.

So my question is, do these sort of ideas have any value?

Yes, being able to model the opponent and set traps should be very valuable for improving the endgame strength. One of the articles discussing this issue: link.

[rjgibert]

One thing I thought of to sort this out is generating an EGTB with both DTM and DTS (=Distance To Stalemate) information, where giving stalemate would be valued more highly than other draws, but still less than a win. I observed that such an EGTB would remain perfectly usable for ordinary chess and might even have advantages over ordinary EGTBs.

I generated exactly this kind of EGTB for 3x3 chess in 2004. It was fun to watch the long stalemate lines, also to try solving "stalemate in N" problems.

I've no idea how useful this kind of EGTB would be for normal chess to improve the play against fallible opponents. I suspect that strength improvement may no be large enough to justify the extra bulk, at least compared to the alternatives.

Imagine requiring an opponent to thread their way to a stalemate in 20 to avoid losing. The idea is more pressure would be placed on an opponent to defend accurately if getting stalemate were the only way they could salvage their position. As things are now, all draws are equally weighted in EGTBs even though they are really not.

Another idea is some other distinction between draws besides stalemate in an EGTB e.g. perhaps a computer opponent's use of null move in the endgame is exploitable to win a drawn position or draw a lost position via zugzwang.

So my question is, do these sort of ideas have any value?

Yes, being able to model the opponent and set traps should be very valuable for improving the endgame strength. One of the articles discussing this issue: link.

Thank you for the link. Here is a stalemate in 9 problem for you to solve, that I quickly cooked up:
[D] 2k5/8/2K5/6N1/8/8/8/8 w - - 6 1

[wgarvin]

Its interesting.

On a slightly different topic.. I've recently been wondering about generating DTM and DTZ together in one database. DTZ only needs about 6 bits, so it would have ~9 bits for DTM information. With the DTZ values available, I think the engine would always be able to avoid making moves that allow the opponent to claim a draw under the 50-move rule, if starting from any database position still winnable under the 50-move rule.

It seems like that would be a lot simpler than all of the DTR/DTZR stuff that I read about over at the CCRL egtb forum... The engine would be able to play "typical" DTM-minimizing moves in most situations, but if would never play such a move if the current halfmove counter plus 2x DTZ value would reach or exceed 100 and allow opponent to claim a draw. If it ended up in a segment with a longish length, it would probably find that some of the DTM-minimizing moves would be ineligible (because they would lead to positions whose DTZ was too high according to the current halfmove counter) and it would be forced to choose a successor with a more reasonable DTZ instead.

I'm not sure what strategy it should apply when in a lost or drawn ending.

I guess to generate it, you'd have to use the WLD values determined by DTZ, and then calculate the DTM values after (so I guess they would technically need to be DTZ50 and DTM50 values, or the engine might be tempted to play towards "mates" that couldn't actually be reached under the 50-move rule. Thats probably why this is so much simpler than the proposed DTR formats--it would only correctly support the 50-move rule, not K-move for arbitrary K's).

[rjgibert]

[D] 2k5/8/2K5/6N1/8/8/8/8 w - - 6 1

Solution: 1.Nf7 Kb8 2.Nd6 Ka8 3.Kc5 Ka7 4.Kb5 Ka8 5.Ka6 Kb8 6.Kb6 Ka8 7.Nb5 Kb8 8.Na7 Ka8 9.Nc6 stalemate

Not much to it I'm afraid. What did you expect on short notice?

[Kirill Kryukov]

Sorry, I did not have time to try solving it. Also, with more pieces probably much longer stalemate lines can be found. (Although my guess is maxDTM will be still larger).

Here is one in 3x3 chess:



White to move and stalemate in 14.

In my case the idea to compute distance to stalemate originated from Shogi, where stalemate is a win. I did not think of it as having any utility for normal playing though.

[Kirill Kryukov]

Its interesting.

On a slightly different topic.. I've recently been wondering about generating DTM and DTZ together in one database. DTZ only needs about 6 bits, so it would have ~9 bits for DTM information. With the DTZ values available, I think the engine would always be able to avoid making moves that allow the opponent to claim a draw under the 50-move rule, if starting from any database position still winnable under the 50-move rule.

It seems like that would be a lot simpler than all of the DTR/DTZR stuff that I read about over at the CCRL egtb forum... The engine would be able to play "typical" DTM-minimizing moves in most situations, but if would never play such a move if the current halfmove counter plus 2x DTZ value would reach or exceed 100 and allow opponent to claim a draw. If it ended up in a segment with a longish length, it would probably find that some of the DTM-minimizing moves would be ineligible (because they would lead to positions whose DTZ was too high according to the current halfmove counter) and it would be forced to choose a successor with a more reasonable DTZ instead.

I'm not sure what strategy it should apply when in a lost or drawn ending.

I guess to generate it, you'd have to use the WLD values determined by DTZ, and then calculate the DTM values after (so I guess they would technically need to be DTZ50 and DTM50 values, or the engine might be tempted to play towards "mates" that couldn't actually be reached under the 50-move rule. Thats probably why this is so much simpler than the proposed DTR formats--it would only correctly support the 50-move rule, not K-move for arbitrary K's).

The big idea behind DTZ metric is to save space (as it compresses better) and generation time (as it needs less iterations, and as it can use WDL sub-tables). Both purposes are defeated if we still pack DTM together with it. Although I guess this combination would be still much simpler than DTR.

I'm not sure why DTM became so popular, as for practical game-playing or analysis purposes it is one of the least efficient metrics (second only to DTR). I guess because it was a more simple concept to grasp for most people, and because DTC or DTZ play may look unnatural. Perhaps this unnatural play can be helped by some clever search.

[wgarvin]

The big idea behind DTZ metric is to save space (as it compresses better) and generation time (as it needs less iterations, and as it can use WDL sub-tables). Both purposes are defeated if we still pack DTM together with it. Although I guess this combination would be still much simpler than DTR.

I'm not sure why DTM became so popular, as for practical game-playing or analysis purposes it is one of the least efficient metrics (second only to DTR). I guess because it was a more simple concept to grasp for most people, and because DTC or DTZ play may look unnatural. Perhaps this unnatural play can be helped by some clever search.

Hmm, good points. My interest in DTZ is mostly related to the 50-move rule, and I've been thinking mostly about 5-man endings, so the larger compressed size was not something I was worrying about. I guess as you go to 6-man, doubling (or more) the database size gets inconvenient.

[ernest]

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

[wgarvin]

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

I was under the impression that DTM50 suffers from practical problems that make it untrustworthy for actual play:
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.

[Edit: note that regular DTM does not suffer from this history-dependence problem, but it also doesn't respect the 50-move rule.]

In contrast, I think the combination of DTM50 + DTZ50 does always allow you to play out a winning line without falling victim to the 50-move rule, whenever that is possible.

(Personally what I really want is WLD50 combined with heuristics that can win all the won positions with minimal or no extra information... basically take what Heinz et al. did with Darkthought and scale it up to 5-piece endings, and generate proof-dbs to make sure it can win all the winnable positions with the chosen strategy without falling victim to the 50-move rule. And then find better ways to compress the bitbases so they can fit in RAM, support fast random access from the search, etc.)