I am really confused by all this talk of DTR, DTZ, DTZ50, DTS- + etc
It seems to me like there is only one relevant metric under the fifty move rule: the minimum number of moves required to mate from a given position with a given move counter state.
Any one position is actually 100 positions. For example, it might be that a given position is mate in 82 with 50 moves to go on the counter, but a mate in 87 with 42 moves to go, because the winning side must force a conversion early, thus lengthening the eventual mate.
The position of the pieces and the state of the ply count together provide all the important information. The three repetition rule can safely be discarded because, assuming a history of optimal play, such a position would have been considered a draw already and avoided.
Unfortunately, this means that tablebases might potentially require up to 100 times the space required by tablebases that ignore the 50 move rule.
Am I right?
dtx
-
h.g.muller
- Posts: 223
- Joined: Mon Feb 19, 2007 8:24 am
- Sign-up code: 0
- Location: Amsterdam
- Contact:
Re: dtx
I don't think this is very relevant: you always enter a certain phase with the 50-move counter at zero. There is no reasn to wait until that counter has increased to 42, and only then start consulting the tablebase. If the tablebase contains the DTZ, generated from zeroing events that are won under the 50-move rule (I guess this is what DTZ50 means) and you start in a won position with a DTZ smaller than 50, you will never run into a 50-move problem when you keep playing according to the tablebase.
Of course you have a problemif you are in a draw position that could be a forced win if one of the later phases were allowed to use more than 50 moves. On could add these positions with a DTZ > 50, but a decision should be taken what has priority when two or more phases along the path (perhaps including the current one) would have to exceed 50 moves. Would it be better to distribute the pain evenly over all these phases (as DTR does), meaning your only winning chance is a number of smallest possible opponent mistake in each of these phases, or would you concentrate all the deficit in one phase (if possible), so that one big blunder is enough. And if you opt for the latter, in which phase is the opponent more likely to blunder?
In the practice of engine-engine games, the latter question amounts to: which phases is he most likely to have tablebases for, so that there is zero chance he will make even a tiny mistake there, so that requiring even 51 moves there means a certain draw. This is what I dislike about DTR (no matter how aestetically pleasing that concept is): I would prefer to concentrate all the deficit in the most complex phase (maximal number of men), because that gives the best chance of the opponent nor having the tablebase.
Of course you have a problemif you are in a draw position that could be a forced win if one of the later phases were allowed to use more than 50 moves. On could add these positions with a DTZ > 50, but a decision should be taken what has priority when two or more phases along the path (perhaps including the current one) would have to exceed 50 moves. Would it be better to distribute the pain evenly over all these phases (as DTR does), meaning your only winning chance is a number of smallest possible opponent mistake in each of these phases, or would you concentrate all the deficit in one phase (if possible), so that one big blunder is enough. And if you opt for the latter, in which phase is the opponent more likely to blunder?
In the practice of engine-engine games, the latter question amounts to: which phases is he most likely to have tablebases for, so that there is zero chance he will make even a tiny mistake there, so that requiring even 51 moves there means a certain draw. This is what I dislike about DTR (no matter how aestetically pleasing that concept is): I would prefer to concentrate all the deficit in the most complex phase (maximal number of men), because that gives the best chance of the opponent nor having the tablebase.
Re: dtx
Are you saying that you only need to store the value of each position when the move counter is at 50?
That would be sufficient to tell you whether a position was won, but it would not be sufficient to actually tell you what the winning moves are.
Consider three positions, A, B, and C
Position A is a win in 57 with 50 moves to go and a draw with 49 moves to go.
Position B is a win in 59 with 50 moves to go and a win in 64 with 49 moves to go.
In Position C, you can move into either of the above positions.
If you only stored the value with the move counter at 50, you would see (A: mate in 57, B: mate in 59, C: mate in 65)
Now you are in position C, trying to figure out which move to make. Since A has the shorter mate, you move to that, which lets the opponent get a draw.
That would be sufficient to tell you whether a position was won, but it would not be sufficient to actually tell you what the winning moves are.
Consider three positions, A, B, and C
Position A is a win in 57 with 50 moves to go and a draw with 49 moves to go.
Position B is a win in 59 with 50 moves to go and a win in 64 with 49 moves to go.
In Position C, you can move into either of the above positions.
If you only stored the value with the move counter at 50, you would see (A: mate in 57, B: mate in 59, C: mate in 65)
Now you are in position C, trying to figure out which move to make. Since A has the shorter mate, you move to that, which lets the opponent get a draw.
Re: dtx
If you store the DTZ50-value (as h.g.muller suggests), this is indeed sufficient.notnale wrote:Are you saying that you only need to store the value of each position when the move counter is at 50?
The DTZ50-value for a position is the number of moves to a zeroing move into a position that is won under the 50-move rule (with move-counter at 0), when the winning side is trying to minimize this number and the losing side is trying to maximize this number. (A zeroing move is a move that resets the move-counter, so either a capture or a pawn push.)
In a DTZ50-table you would see A: dtz50 = 50, B: dtz50 = 49, C: dtz50 = 50.Consider three positions, A, B, and C
Position A is a win in 57 with 50 moves to go and a draw with 49 moves to go.
Position B is a win in 59 with 50 moves to go and a win in 64 with 49 moves to go.
In Position C, you can move into either of the above positions.
If you only stored the value with the move counter at 50, you would see (A: mate in 57, B: mate in 59, C: mate in 65)
(To be more precise, you might see B: dtz50 = b for some value b <= 49, C: dtz = b+1. This is because B might also be a win in 80 with b moves to go.)
You are making a very good point though: a DTM50-table is not sufficient to actually win legally won positions. A DTR-table is not sufficient to actually win legally won positions either. Not even a (DTR, DTZR)-table (with DTZR as tie-breaker) is sufficient to actually win legally won positions.
Only DTZ50 has the required properties. All other tables try to do something "extra", but the 50-move rule in chess does in general not leave room for doing anything extra. Without a DTZ50-table, mistakes will be made. In the discussion in the other thread, I was for some time not aware of this. (The problem with this stuff is that once you realize that DTZ50 'works', it is very tempting to think that DTM50 and other tables will work too.)
I agree, and in fact I don't find DTR aesthetically pleasing anymore now that I've come to realize that DTR may give you a "k-move rule"-promise, but is then unable to deliver on that promise.h.g.muller wrote:In the practice of engine-engine games, the latter question amounts to: which phases is he most likely to have tablebases for, so that there is zero chance he will make even a tiny mistake there, so that requiring even 51 moves there means a certain draw. This is what I dislike about DTR (no matter how aestetically pleasing that concept is): I would prefer to concentrate all the deficit in the most complex phase (maximal number of men), because that gives the best chance of the opponent nor having the tablebase.
Even if DTR is only used for positions that cannot be won under the 50-move rule, I am for the moment not convinced by its utility. What you really want is a table that tells you if a position is won under the 50-move rule after N potentially non-optimal moves. DTZ50 provides this information: the position is legally won if and only if dtz50 + N <= 50. DTR does not provide this information. So the only thing DTR could possibly provide is a strategy with good chances to "trick" a fallible opponent into making fatal mistakes. But is there any evidence going beyond mere intuition that DTR is good for that?
Re: dtx
I guess it all comes down to what you want to use the tablebase for.
In an engine game, a mate is a mate no matter how long; all you are about is whether you can force mate or not. In this case, all you need is a single bit per position and movecounter, which is equivalent to the DTZ50 mentioned above.
However, while using the DTZ50 will always win a won position and never lose a drawn one, it will not necessarily get the shortest mate or the longest possible defence. If this is what you want, then I beleive it is necessary to use the 100 seperate numbers method
In an engine game, a mate is a mate no matter how long; all you are about is whether you can force mate or not. In this case, all you need is a single bit per position and movecounter, which is equivalent to the DTZ50 mentioned above.
However, while using the DTZ50 will always win a won position and never lose a drawn one, it will not necessarily get the shortest mate or the longest possible defence. If this is what you want, then I beleive it is necessary to use the 100 seperate numbers method
Re: dtx
I agree, and that doesn't seem worth it (to me) given that DTZ50 gives a very practical way of correctly taking into account the 50-move rule.notnale wrote:If this is what you want, then I beleive it is necessary to use the 100 seperate numbers method
To avoid unnatural DTZ50-optimizing winning lines (queen sacs and pawn pushes just for the sake of resetting the move counter), an engine could perform a regular search to see if a mate can be found. If a direct mate cannot be found, the engine can use the DTZ50-table to find a safe winning move.
If you really really want the fastest legal mate, a DTM50-table which stores the length of the shortest legal mate for each position might still be of help. What you do is perform a depth-first search from the position at which you enter the table, while using the DTM50 information to guide you. For the root position and for each position reached by a zeroing move you know the exact distance to mate. For the other positions you have a lower bound. This can be used to cut a lot of branches. A DTZ50-table should probably be added to cut even more branches (a position that cannot be won anymore given the current value of move-counter will certainly not lead to the shortest legal mate). I wouldn't be too surprised if this can be made to work reasonably well, but optionally you could also throw in a DTM50-table that assumes move-counter=25 (i.e. first phase is at most 50-25=25 moves), which limits the max search depth to 25 moves. That's still 50 ply, but the branching factor should be low (I hope...).
Re: dtx
Generating a DTM50-table that includes the information required to find the winning line may perhaps be somewhat doable.
First consider how DTZ50 is generated. Oversimplifying, you first generate all DTZ50-subtables and then perform 50 iterations of retrograde analysis. What is important here is that the Nth iteration finds all positions with dtz50 = N. Therefore the 30th iteration will not overwrite the value of positions found in the 20th iteration.
Now consider DTM50. First, you generate all DTM50-subtables. Then you perform 50 iterations of retrograde analysis. Now, the value of a position found in the Nth iteration will be dtm50 = N + k, where k is the dtm50-value of a position in a subtable that can be reached after N moves. It is possible that the 30th iteration finds an improved dtm50-value (e.g. 30 + 10 = 40) for a position that was already assigned a dtm50-value during the 20th iteration (e.g. 20 + 25 = 45).
This overwriting of values is why a "single-valued" DTM50-table fails to find back winning lines: a 49+30=79 dtm50-value for position A found in the 49th iteration might have been overwritten by a 50+20=70 dtm50-value in the 50th iteration. The line that led in the 49th iteration to the value of 79 may have led in the 50th generation to a position B with dtm50 = 80 (=50+30). The winning line for position B has now been replaced at A by a quicker mate, but this quicker mate needs 50 moves in the first phase, while starting from B only 49 moves are left.
If you really want to solve this problem, you should therefore not overwrite values found in earlier iterations, but somehow store them all together, including the number of the iteration at which they were found. This is more or less the same as your "100 separate numbers" (I guess 50 should be sufficient, one for each iteration, since you can map 2 plies to 1 move without messing up the 50-move rule if I'm not mistaken), but also shows that the algorithm for the generator is straightforward. The difficulty lies mainly in finding an efficient way of storing this type of data.
First consider how DTZ50 is generated. Oversimplifying, you first generate all DTZ50-subtables and then perform 50 iterations of retrograde analysis. What is important here is that the Nth iteration finds all positions with dtz50 = N. Therefore the 30th iteration will not overwrite the value of positions found in the 20th iteration.
Now consider DTM50. First, you generate all DTM50-subtables. Then you perform 50 iterations of retrograde analysis. Now, the value of a position found in the Nth iteration will be dtm50 = N + k, where k is the dtm50-value of a position in a subtable that can be reached after N moves. It is possible that the 30th iteration finds an improved dtm50-value (e.g. 30 + 10 = 40) for a position that was already assigned a dtm50-value during the 20th iteration (e.g. 20 + 25 = 45).
This overwriting of values is why a "single-valued" DTM50-table fails to find back winning lines: a 49+30=79 dtm50-value for position A found in the 49th iteration might have been overwritten by a 50+20=70 dtm50-value in the 50th iteration. The line that led in the 49th iteration to the value of 79 may have led in the 50th generation to a position B with dtm50 = 80 (=50+30). The winning line for position B has now been replaced at A by a quicker mate, but this quicker mate needs 50 moves in the first phase, while starting from B only 49 moves are left.
If you really want to solve this problem, you should therefore not overwrite values found in earlier iterations, but somehow store them all together, including the number of the iteration at which they were found. This is more or less the same as your "100 separate numbers" (I guess 50 should be sufficient, one for each iteration, since you can map 2 plies to 1 move without messing up the 50-move rule if I'm not mistaken), but also shows that the algorithm for the generator is straightforward. The difficulty lies mainly in finding an efficient way of storing this type of data.
Re: dtx
The main reason that I said 100 instead of 50 numbers was because in most complicated endgames, there are at least a few positions where either side could mate.
Now that I think about it however, you could actually do with just 50 numbers as you said, all you would need is an extra bit to show who was winning
Now that I think about it however, you could actually do with just 50 numbers as you said, all you would need is an extra bit to show who was winning
Re: dtx
notnale:
For DTZ50 you need to store distance to win in half moves as it sometimes makes a difference. This means that there are over 100 possible values per position, even if you only care about wins by one side. With wins by either side there are over 200 possible values.
For DTZ50 you need to store distance to win in half moves as it sometimes makes a difference. This means that there are over 100 possible values per position, even if you only care about wins by one side. With wins by either side there are over 200 possible values.
Re: dtx
Which still comes to a max of only 7.66 bits per position (for practical purposes, you'd use a byte)
Thats why DTZ50 is so useful: you only need a byte per position no matter how complicated a position it is, and it is still sufficient to win a won position or draw a drawn position. The only reason you would use more is if you actually cared about how long the mate took (see previous posts)
By the way, I'm not convinced about the need for half moves under DTZ50. I think 6.68 bits (one of 102 possible values, not 202) would suffice, not that it matters
Especially since the actually entropy of the tablebases is probably quite a bit lower then the theoretical maximum
Thats why DTZ50 is so useful: you only need a byte per position no matter how complicated a position it is, and it is still sufficient to win a won position or draw a drawn position. The only reason you would use more is if you actually cared about how long the mate took (see previous posts)
By the way, I'm not convinced about the need for half moves under DTZ50. I think 6.68 bits (one of 102 possible values, not 202) would suffice, not that it matters
Especially since the actually entropy of the tablebases is probably quite a bit lower then the theoretical maximum
Re: dtx
To have the complete DTM50 information you would need to store per position W/D/L, and if not D, then one distance-value per iteration that (over)writes the value. Where I wrote 50 iterations you could maybe also read 100 half-iterations, but in any case the value for a wtm-position can be written at most 50 times (and probably much less often) and same fot dtm-positions. The distance-values themselves will be 1-100 ply. So a rough estimation would be 2 + 50 * 7 = 352 bits per position, but proper compression would reduce that to very much less (but still a lot).
A lot of this information wil not actually be required. Many DTM50-tables will be "completed" within 50 iterations (i.e. a 51st iteration would not change values already set) and for those only the last value for each position is needed. I believe that also for DTM50-tables that are not "completed" within 50 iterations many of the intermediate values can be discarded. I think a kind of verification run could do this, but I'm not completely sure (hmm, you might again need 50 iterations). It might be fun to work this all out some time.
A lot of this information wil not actually be required. Many DTM50-tables will be "completed" within 50 iterations (i.e. a 51st iteration would not change values already set) and for those only the last value for each position is needed. I believe that also for DTM50-tables that are not "completed" within 50 iterations many of the intermediate values can be discarded. I think a kind of verification run could do this, but I'm not completely sure (hmm, you might again need 50 iterations). It might be fun to work this all out some time.
Is it really not possible to map plies to moves after generation without messing up the 50-move rule in border cases? You could be right, but until I've verified this for myself I hope you're wrong. It would mean that compressed DTZ50-tables are significantly larger than compressed DTZ-tables. (Well, I guess one could still store distance-values in moves for DTZ50-tables with maxDTZ < 50 moves.)koistinen wrote:For DTZ50 you need to store distance to win in half moves as it sometimes makes a difference. This means that there are over 100 possible values per position, even if you only care about wins by one side. With wins by either side there are over 200 possible values.
Re: dtx
I thought we decided that DTM50 was pretty much useless?
Also, is there a name for the tables which store the actual distance to mate considering the 50 move rule for every position and move counter state? If not, maybe we need to come up with a name
I think koistinen is wrong as well. Since in a mated position, it will always be the losing side's turn, the superior side will always be moving on odd numbered plies and the losing side on even numbered plies. As long as you make sure the GUI is programmed properly, it should be able to translate the full move numbers to plies without any problems.syzygy wrote: Is it really not possible to map plies to moves after generation without messing up the 50-move rule in border cases? You could be right, but until I've verified this for myself I hope you're wrong.
Also, is there a name for the tables which store the actual distance to mate considering the 50 move rule for every position and move counter state? If not, maybe we need to come up with a name
Re: dtx
I don't think so, because it is true only in final phase. If a zeroing move has to come before going to mate, this zeroing move can be either a (voluntary) move by winning side or a (forced) move by losing side.notnale wrote:I think koistinen is wrong as well. Since in a mated position, it will always be the losing side's turn, the superior side will always be moving on odd numbered plies and the losing side on even numbered plies. As long as you make sure the GUI is programmed properly, it should be able to translate the full move numbers to plies without any problems.
To my mind, such a table is nothing else than DTM50. What I insist on in some of my posts is this (but it's only my honest opinion) : some metrics must definitely be seen as functions of two variables, p (position on the board) and x (move-counter) and not p alone. DTM50 (or DTMk) is such a two-variable function. DTC50 (or DTCk) and DTR are two-variable functions also. DTM, DTC and DTZ are only one-variable functions (of p). DTZ50 (or DTZk) is intrinsically a two-variable function, but in this very particular case we fortunately have a very simple relationship usable to deduct DTZk(p,x) from DTZk(p,0) : DTZk(p,x)=DTZk(p,0) if DTZk(p,0)+x <=k , and is infinite instead. I don't know any such easy relationship to deduct DTMk(p,x) from DTMk(p,0), same for DTCk, same for DTR. And I the more I think of it, the more I believe there is simply none. I really think that sticking to an objective of a table of DTX(p,0) only when DTX is a very two variable (p,x) metric is wrong, as it will lead to unexploitable results in general.notnale wrote:Also, is there a name for the tables which store the actual distance to mate considering the 50 move rule for every position and move counter state? If not, maybe we need to come up with a name
My opinion is also that in general there won't be many different values of DTM50(p,x) for different values of x, and building a full table of DTM50(p,x) for 3-4-5 men of reasonable size (compressed) is certainly achievable. Same for DTR (and other two-variable metrics such as DTC50, DTMk, DTCk... if wanted also). Unless some easy relationship (such as for DTZk) simplifying matters is discovered, I think developing tables for "two-variable metrics" should be aimed at a full (p,x) table, count on great expected compression efficiency to reduce tables to an acceptable final size, and limit short-medium term ambitions to 5-men.
Re: dtx
Correct. But original question was : is it possible to map a DTZ50 table using only full-moves ? I don’t think so. True, distance to mate in plies is always odd (if winning side is to move) or even (if losing side is to move), but distance to next zeroing move is not.
Let’s see an example : Ka8, Qc7, Pa7, a5 / Kg8. White may :
1) play a zeroing move immediately : a5-a6.
2) force a zeroing move from Black at its next move : Qg7+, forcing Kxg7
3) head for a mate in two (Kb7 then a8=Q#)
Under 50-move rule, if 97 (or less) consecutive non-zeroing (CNZ) plies have been played, every line is winning, and line 3 may be seen as best as it is shortest route to mate.
If 98 CNZ-plies have been played, line 3 leads to a 50-move rule draw after Black’s move of Kh8 (or Kf8). Lines 1 and 2 are the only ones to win. Without the a5 pawn, line 2 is the only one to win.
If 99 CNZ-plies have been played, line 1 is the only one to win. Without the a5 pawn, draw is unavoidable.
I don’t think it is possible to map out all this information using only full moves in DTZ50 tables, the fact that distance to mate is always odd (line 1 = 5 plies, line 2 = 19 plies, line 3 = 3 plies) being not relevant in this case (although it would be if we were talking of DTM50).
Let’s see an example : Ka8, Qc7, Pa7, a5 / Kg8. White may :
1) play a zeroing move immediately : a5-a6.
2) force a zeroing move from Black at its next move : Qg7+, forcing Kxg7
3) head for a mate in two (Kb7 then a8=Q#)
Under 50-move rule, if 97 (or less) consecutive non-zeroing (CNZ) plies have been played, every line is winning, and line 3 may be seen as best as it is shortest route to mate.
If 98 CNZ-plies have been played, line 3 leads to a 50-move rule draw after Black’s move of Kh8 (or Kf8). Lines 1 and 2 are the only ones to win. Without the a5 pawn, line 2 is the only one to win.
If 99 CNZ-plies have been played, line 1 is the only one to win. Without the a5 pawn, draw is unavoidable.
I don’t think it is possible to map out all this information using only full moves in DTZ50 tables, the fact that distance to mate is always odd (line 1 = 5 plies, line 2 = 19 plies, line 3 = 3 plies) being not relevant in this case (although it would be if we were talking of DTM50).
Re: dtx
Counting in full moves in DTZ50 should be sufficient to find out whether a position can be won or not with ply-counter = even. By far the most important is the case ply-counter = 0, i.e. the first probe after entering the table (assuming both the wtm- and the btm-table are present).
Counting in full moves with not always allow you to determine with certainty whether a position can still be won with ply-counter = odd, but even if that is considered a problem it can easily be overcome by doing 1 ply and probing the other wtm/btm-table (now with even ply-counter).
My conclusion is therefore: if we are prepared to store both wtm and btm-tables, then DTZ50-values should be counted in full moves. If not, DTZ50-values should be counted in plies.
In the latter case, instead of counting in plies it would also be possible to count in full moves but keep values 99 and 100 separate. That would allow a precise determination of win/draw on entering a table, even with only one of each (wtm, btm)-pair available. Even that is not needed if WDL50-tables are available for both wtm and btm.
WDL50-tables must be stored for both wtm and btm, or a separate symbol is assigned to positions that are won with ply-counter = 0 but drawn with ply-counter = 1.
Counting in full moves with not always allow you to determine with certainty whether a position can still be won with ply-counter = odd, but even if that is considered a problem it can easily be overcome by doing 1 ply and probing the other wtm/btm-table (now with even ply-counter).
My conclusion is therefore: if we are prepared to store both wtm and btm-tables, then DTZ50-values should be counted in full moves. If not, DTZ50-values should be counted in plies.
In the latter case, instead of counting in plies it would also be possible to count in full moves but keep values 99 and 100 separate. That would allow a precise determination of win/draw on entering a table, even with only one of each (wtm, btm)-pair available. Even that is not needed if WDL50-tables are available for both wtm and btm.
WDL50-tables must be stored for both wtm and btm, or a separate symbol is assigned to positions that are won with ply-counter = 0 but drawn with ply-counter = 1.
Re: dtx
Because there is no way to tell whether a position occurs in a fourth or eigth ply.notnale wrote:Why not go farther and only store every fourth or every eigth ply?
It is very easy to tell whether a position has white-to-move (wtm) or black-to-move (btm). That is why it is possible to store only values for positions with white-to-move. In fact, most tablebase formats store wtm and btm tables in separate files.
Re: dtx
I was talking about the whole only store every other ply thing
If you only store every second ply, the computer will have to search an extra ply deep at runtime.
Bside, if you were going to do that, it would be more efficient to just store all of the WTM and omit the BTM tables
If you only store every second ply, the computer will have to search an extra ply deep at runtime.
Bside, if you were going to do that, it would be more efficient to just store all of the WTM and omit the BTM tables
Re: dtx
In any line of play, all odd plies will be played by the same side and all even plies will be played by the other side. That is why it is possible to separate odd-ply positions from even-ply positions.notnale wrote:I was talking about the whole only store every other ply thing
If you only store every second ply, the computer will have to search an extra ply deep at runtime.
But that is exactly what I was talking about.Bside, if you were going to do that, it would be more efficient to just store all of the WTM and omit the BTM tables
Maybe what confused you is "counting in moves" vs. "counting in plies". By counting in moves I don't mean only storing a value for every other ply, but storing values that count the distance to a zeroing move in number of full moves instead of half moves. So storing values 1-50 instead of 1-100. In my post I analyze the consequences of this choice.
Re: dtx
To go back once more to your earlier question:
Storing values as multiples of 4 or 8 plies (thus saving 2 or 3 bits per position, before compression) is certainly a possibility. It is similar to a suggestion I did in this post, where I suggested to store values as a multiple of 5 moves (10 plies). The precision lost can to a large extent be compensated for by performing a fixed depth search (which is only needed when probing at the root of the tree, so not at leaf nodes). However, it might become impossible to achieve optimal play with respect to the 50-move rule. (If you're playing at the limit of the 50-move rule, you can't afford to lose a ply.)
If it is k, then either d-1 = 2k or d-1 = 2k-1, so either d = 2k+1 or d = 2k. Since we already knew that either d = 2k or d = 2k-1, the only possibility is that d = 2k.
If it is k-1, then either d-1 = 2k-2 or d-1 = 2k-3, so either d = 2k-1 or d = 2k-2. Since we already knew that either d = 2k or d = 2k-1, the only possibility is that d = 2k-1.
So when storing dtz in number of moves, dtz in number of plies can be reconstructed provided both the wtm- and the btm-table are available. Therefore it is always possible to determine whether a position can be won within the number of available plies.
I realize now that to play optimally with respect to the 50-move rule, when choosing moves it is necessary to be able to distinguish between positions with d = 2k and positions with d = 2k-1 for all k (and not only for k = 50, as I originally thought). The reason is that if you enter the table at 100 or 101 plies from a winning zeroing move, any inaccuracy in the line of play that follows might swing the result from win to draw or from draw to win. So when storing dtz in full moves, both wtm and btm have to be available for tables with maxdtz50 = 50 (and some probing is needed in border cases, which however should be rare). When storing dtz in plies, having the smallest of wtm and btm available would be sufficient (but a lot more probing is needed).
One conclusion is that the requirement of "perfect 50-move play" places restrictions on the use of tricks to reduce compressed size. DTZ50-tables will therefore require more storage space than DTZ-tables. (However, most tables will probably have maxDTZ50 < 50 and for those tables tricks to reduce compressed size will not endanger 50-move rule accurate play.)
Maybe you meant: why not store each value as a multiple of four or eight plies? (Storing values as a number of full moves is the same as storing values as a multiple of two plies, i.e. somehow round up/down to a multiple of 2 and then divide by 2.)notnale wrote:Why not go farther and only store every fourth or every eigth ply?
Storing values as multiples of 4 or 8 plies (thus saving 2 or 3 bits per position, before compression) is certainly a possibility. It is similar to a suggestion I did in this post, where I suggested to store values as a multiple of 5 moves (10 plies). The precision lost can to a large extent be compensated for by performing a fixed depth search (which is only needed when probing at the root of the tree, so not at leaf nodes). However, it might become impossible to achieve optimal play with respect to the 50-move rule. (If you're playing at the limit of the 50-move rule, you can't afford to lose a ply.)
I"m not sure which system is my system, but let's assume both wtm and btm tables are available and that distance values are stored as a number of full moves. Suppose you are at position P in the table and the table gives dtz = k (in moves). Let d = dtz in plies. Then either d = 2k or d = 2k-1. Perform 1 ply and probe the table again. By definition, the position after 1 ply is d-1 plies from a zeroing move. The value returned by the table for that position is either k or k-1.So how would your system handle the positions posted by kronsteen?
If it is k, then either d-1 = 2k or d-1 = 2k-1, so either d = 2k+1 or d = 2k. Since we already knew that either d = 2k or d = 2k-1, the only possibility is that d = 2k.
If it is k-1, then either d-1 = 2k-2 or d-1 = 2k-3, so either d = 2k-1 or d = 2k-2. Since we already knew that either d = 2k or d = 2k-1, the only possibility is that d = 2k-1.
So when storing dtz in number of moves, dtz in number of plies can be reconstructed provided both the wtm- and the btm-table are available. Therefore it is always possible to determine whether a position can be won within the number of available plies.
I realize now that to play optimally with respect to the 50-move rule, when choosing moves it is necessary to be able to distinguish between positions with d = 2k and positions with d = 2k-1 for all k (and not only for k = 50, as I originally thought). The reason is that if you enter the table at 100 or 101 plies from a winning zeroing move, any inaccuracy in the line of play that follows might swing the result from win to draw or from draw to win. So when storing dtz in full moves, both wtm and btm have to be available for tables with maxdtz50 = 50 (and some probing is needed in border cases, which however should be rare). When storing dtz in plies, having the smallest of wtm and btm available would be sufficient (but a lot more probing is needed).
One conclusion is that the requirement of "perfect 50-move play" places restrictions on the use of tricks to reduce compressed size. DTZ50-tables will therefore require more storage space than DTZ-tables. (However, most tables will probably have maxDTZ50 < 50 and for those tables tricks to reduce compressed size will not endanger 50-move rule accurate play.)