DTM50 5-men tablebases : generation has started

[kronsteen]

I’ve started generating 5-men DTM50 tablebases. I’ve almost no time to do it and progress is very slow, but I expect to generate all 3 vs 2 / 2 vs 3 with 0-1 pawns before the end of 2013. The remaining ones (2-3 pawns, 4 vs 1 / 1 vs 4) will need new code and I expect to have them generated next year. Currently all 3 vs 2 pawless are generated, and 3 vs 2 with 1 pawn is under way.

Among the 9 endings that are directly influenced by the 50-move rule (knnkp, kqpkq, kbbkn, kbnkn, krbkr, kqrkq, krpkq, kbbkq, knnkq), the first 6 ones are already generated and the results are the following :

knnkp : The 50-move rule begins to strike at depth=52 and beyond this depth it has a considerable effect on the play for almost any position. As a consequence the maximal DTM50 positions are totally different from the maximal DTM positions. At movecount = 0 the longest DTM50 win is 112 moves, one of the maximal positions is Ka3 Na4 Nf2 / Ka6 Ph7 (wtm – 223 plies). If the movecounter in the initial position can be > 0, the longest DTM50 win tops out at 128 moves, one example is Kc3 Nb1 Nf6 / Ka3 Pa5 mc=4 or 5 plies (btm – 256 plies)

kqpkq : The 50-move rule effect begins at depth=59. Beyond this depth, a lot of wins are delayed by a few moves owing to the necessity of the winning side to push his pawn every 50 moves. The longest win is a mate in 137 (I’ll post a position and its winning line soon), so the DTM record for 5-men (127 moves in kppkp) is beaten .There are 36 wtm / 30 btm kqpkq positions with DTM50=137, some of them have queens on 8th/1st rank so I expect to find some mates in ~140 in kppkp which ought to be the deepest 5-men DTM50 positions.

kbbkn : The 50-move rule begins its effects at depth=56 and the maximal DTM50 value is 66. It seems that between these values DTM50 play can differ from DTZ50 or DTM play before reaching the Kling & Horwitz pseudo-fortress, but I haven’t checked this yet.

kbnkn : The 50-move rule begins its effects at depth=65 where it influences a very small fraction of the positions (<1%). This situation (tiny percentage of positions affected) remains up to depth=80 where there is a brutal cutoff, 80 being the maximal DTM50 value and all positions with DTM>=81 being 50 move rule draws.

krbkr : This ending has the special property of having all its deepest positions merging into a single variant that is both DTM and DTZ50 optimal. The result is that the 50-move rule effect is a simple cutoff at DTM=56 : All positions with DTM<=56 are winning under 50-move rule with DTM50=DTM, and all positions with DTM>=57 are 50-move rule draws.

kqrkq : Positions with DTM<=54 are unaffected by the 50-move rule. At depth >=55, some positions remain winning with DTM50=DTM, some become 50-move rule draws and some are still winnable but with DTM50>DTM because Black is able to engage a variant in which he is able to force an exchange of queens in the last phase of the game instead of being forced to give up queen for rook (or being mated). One of the maximal positions is Ka1 Qa8 Ra2 / Kg7 Qa4 (btm), with DTM=56 and DTM50=61.

[syzygy]

Very interesting results. Funny that the DTM50 record beats the DTM record!

[kronsteen]

Yes, the 50-move rule hasn't always a sterilizing effect on very deep positions. It will certainly have one on pawnless endings, rubbing out all the records that have been found there (mate in 262 in krnknn, mate in 545 in kqnkrbn, winning nature of krbknn etc...) and limiting pawnless ending depths to 80 moves or so (capture in 50 moves and easy win afterwards). But it will have more interesting effects on positions with pawns, especially on deep endings where the winning side has a pawn that must be moved every 50 moves - typically the case for kqpkq. I'm curious to see - when 6-men DTM50 EGTs will exist - what will be the effect of the 50-move rule on endings such as krrpkq, kqppkq, kbbpkr. It seems already that the maximal kqppkq position (mate in 182) is winnable under the 50-move rule, perhaps in more than 200 moves. The unusual ending knnkpp will also be interesting.

Here is one of the maximal kqpkq positions and a DTM50 optimal line :

4Q3/8/8/8/2K5/4P3/k7/7q b - - 0 1


... Qc1+ 1. Kd4 Qb2+ 2. Ke4 Qe2 3. Kf4 Qf2+ 4. Kg5 Qg1+ 5. Kh6 Qh2+ 6. Kg7 Qb2+ 7. Kh7 Qb7+ 8. Kh6 Qb6+ 9. Kg5 Kb3 10. Kf5 Qc5+ 11. Kf6 Kc2 12. Qe4+ Kc1 13. Kf7 Qh5+ 14. Ke7 Qc5+ 15. Kd7 Qa7+ 16. Ke8 Qb8+ 17. Kf7 Qc7+ 18. Qe7 Qc4+ 19. Qe6 Qc7+ 20. Kf6 Qc3+ 21. Qe5 Qc6+ 22. Ke7 Qb7+ 23. Kd8 Qa8+ 24. Kd7 Qa4+ 25. Ke7 Qb4+ 26. Ke6 Qc4+ 27. Qd5 Qc8+ 28. Ke7 Qc7+ 29. Kf6 Qc3+ 30. Qd4 Qc8 31. Kf7 Qb7+ 32. Kg6 Qc6+ 33. Kf5 Qb5+ 34. Kf4 Qf1+ 35. Ke4 Qg2+ 36. Ke5 Qg5+ 37. Ke6 Qg8+ 38. Kd7 Qf7+ 39. Kc6 Qe8+ 40. Kc7 Qf7+ 41. Kb6 Qb3+ 42. Kc6 Qe6+ 43. Kc5 Qc8+ 44. Kb4 Qb7+ 45. Kc4! Qc6+ 46. Qc5 Qe4+ 47. Kb5+! Kd2 48. Qd4 Qd3+ 49. Kc5 Ke2 50. e4 Qa3+51. Kc6 Qa8+ 52. Kc7 Qa5+ 53. Kd7 Qb5+ 54. Ke7 Qb7+ 55. Kf6 Qc6+ 56. Kg5 Qc1+ 57. Kh5 Qf4 58. Kg6 Qg3+ 59. Kf6 Qh4+ 60. Ke6 Qg4+ 61. Kd6 Qf4+ 62. Kc6 Kf3 63.Qd3+ Kg4 64. Qd1+ Kh4 65. Qd5 Qf6+ 66. Kd7 Qg7+ 67. Ke8 Qh8+ 68. Ke7 Qh7+ 69. Kd6 Qh8 70. Qe6 Qd4+ 71. Ke7 Qg7+ 72. Ke8 Qh8+ 73. Kf7 Qh7+ 74. Kf6 Qh6+ 75. Ke5 Qg5+ 76. Kd6 Qd8+ 77. Kc6 Qd4 78. Qh6+ Kg4 79. Qg6+ Kh4 80. Qh7+ Kg3 81. Qf5 Qa4+! 82. Kd6 Qd4+ 83. Ke6 Qb6+ 84. Kf7 Qc7+ 85. Kg6 Qc6+! 86. Kg5 Qc1+ 87. Kh5! Qf4 88. Qg5+ Kf3 89. e5 Qf7+ 90. Qg6 Qd5 91. Qf5+ Ke3 92. Kg5 Qg8+ 93. Qg6 Qd5 94. Qf6 Qg2+ 95. Kh6 Qh1+ 96. Kg6 Qb1+ 97. Qf5 Qb8 98. Kh5 Qb2 99. Kh4 Qb8 100. Kg4 Qb4+ 101. Kg5 Qb7 102. Qf4+ Kd3 103. Kg4 Qe7 104. Qf5+ Kc3 105. e6 Kb2 106. Qf7 Qb4+ 107. Kg5 Qd2+ 108. Qf4 Qg2+ 109. Kf6 Qc6 110. Qf5 Ka2 111. Kf7 Qc4 112. Qe5 Kb1 113. Kf8 Qf1+ 114. Ke8 Qc4 115. e7 Qc6+ 116. Kf7 Qc4+ 117. Qe6 Qf4+ 118. Qf6 Qc7 119. Kg6 Qg3+ 120. Qg5 Qb8 121. Qg1+ Kc2 122. Qg2+ Kd1 123. Qd5+ Kc1 124. Qc6+ Kd1 125.Qa4+ Kc1 126. e8=Q Qg3+ 127. Kh5 Qf3+ 128. Qg4 Qd5+ 129. Qg5+ Qxg5 130. Kxg5 Kd1 131. Kf5 Kd2 132. Ke4 Kc3 133. Qa4 Kd2 134. Qb4+ Kc2 135. Ke3 Kc1 136. Kd3 Kd1 137. Qb1#

Notation :
Normal text = moves that are DTM optimal and DTZ50 optimal (+ exclamation mark if the choice among DTM+DTZ50 optimal moves is restricted - see move 81)
Bold = a move that is DTM optimal but not DTZ50 optimal
Underlined + exclamation mark = a move that is DTZ50 optimal but not DTM optimal
Bold + underlined + 2 exclamation marks = a move that is neither DTM optimal nor DTZ50 optimal (no such moves here)

In the first phase White must be able to play e4 within 50 moves. In order to do so he must play two DTM non-optimal moves, 45. Kc4 which costs 1 move, and 47. Kb5+ which costs 13 moves. White finally plays e4 at move 50, at this point DTZ50 is 44 but White is still not out of the woods and must concede further depth if he wants to play e5 before move 101. At move 85 Black plays Qc6+ which costs 1 move but forces White to give back 4 moves with 87. Kh5. In the end the win has been delayed by 1+13-1+4=17 moves, the initial position has DTM=120 and therefore DTM50=137.

This position has mc=0 (max DTM50 positions in kqpkq have mc=0 but this is not always the case for other endings) and can be reached in 4 moves from the kppkp position Kc4 Pe4 Pe3 / Ka2 Ph5 which ought to be a mate in 141 and may well be the absolute DTM50 record for 5-men.

[kronsteen]

I've corrected the pgn above, there was an error at move 81 (81... Qc3+ shortens the mate by 3 moves by allowing 82. Qc5, the correct move is 81... Qa4+). Thanks to ernest who identified the error. The result is validated by two independantly written DTM50 generators and can now be considered as a certainty.

[galen]

Hi! Having built my own generator and tables, as noted in another thread, I have come to compare my results to yours. To all appearances, everything matches up, which I think is good confirmation for both of us. Here are my notes:

knnkp: To be super-precise, I find it begins to strike at depth "51.5"; e.g., there are positions where Black is mated in 51 DTM but more in DTM50 (e.g., Ka4 Nc3 Nh3 / Ka8 Nc4, Black mated in 55). Other than that, same results.

kqpkq: Same results, although the 36/30 counts are presumably after removing the one symmetry, so the full total would be 72/60.

kbbkn: Same results.

kbnkn: Same results I think; the deepest is mated in 80 (160 plies).

krbkr: Same results. In fact, all lines would merge if it were only a 33.5-move rule, with a cutoff at mate in 40.

kqrkq: Same results.

I didn't check all your moves, but I got the same depth for the kqpkq position you posted.

I have also built full tables for knnkq and kbbkq, and indeed for kbbbkq and half of knnnkq. I just added summaries of the latter two to my draft. I've been slouching though when it comes to pawns, and I don't have krpkq or even krpkr. I tried to do something fancy to make pawns (and particularly promotions) more efficient and less cumbersome, but it hasn't really come together.

[syzygy]

I'd like to see the DTM50-line for
8/8/8/4k2p/7N/2N2K2/8/8 b - - 0 5

[galen]

I'd like to see the DTM50-line for
8/8/8/4k2p/7N/2N2K2/8/8 b - - 0 5

I have this position as mated in 85, 87, 91, 95, 98, 101, 103, or 118, or draw, depending on the initial count. When it's zero, here is a mate in 85 line (not unique):

1. ... Kd4 2. Nd1 Kd3 3. Ne3 Kd4 4. Kf4 Kd3 5. Nef5 Kc4[1] 6. Ke5 Kc5 7. Ng7 Kc4 8. Ne6 Kd3 9. Kf4 Kc3 10. Ke3 Kc4 11. Ke4 Kc3 12. Kd5 Kb4 13. Kd4 Kb5 14. Nd8 Kb4 15. Nc6+ Kb5 16. Kd5 Ka6 17. Nd4 Kb6[2] 18. Kd6 Ka5 19. Kc5 Ka4 20. Nc6[3] Kb3 21. Kd4 Kc2 22. Na5[4] Kd2 23. Nb3+ Ke2 24. Ke4 Kf2 25. Nd4 Kg3 26. Ndf5+ Kg4 27. Nf3 h4 28. Ne3+ Kg3 29. Nf1+ Kf2 30. N3h2 Ke2 31. Kd4 Kd1 32. Kc3 Ke2 33. Kc2 Ke1 34. Kd3 Kd1 35. Ne3+ Kc1 36. Kc3 Kb1 37. Nf3 Kc1 38. Nd5 Kd1 39. Nf4 h3

... and White mates in 47, which is less than 50, so follow any DTM line.

Notes:

[1] E.g., Kc3 is better if you started with PC > 13.

[2] The first DTM-suboptimal move (vs. Kb7, which is better for a lot of values of PC).

[3] The last DTM-suboptimal move.

[4] Despite the previous note, we're not out of the 50-move woods: Although DTM says Nf3 is just as good here, 22. ... h3! would draw the game!

Edit: Added note 4, fixed typo.

[syzygy]

Thanks!
The original position (from the Rybka forum, I think) was:
8/8/8/6kp/2p5/2N2K2/8/3N4 w - - 0 1

Someone complained that my tables did not score this as a win, whereas the Nalimov tables did. Of course the position is a draw by the 50-move rule.

What is somewhat funny is that after 1.Ke3, the Nalimov tables suggest 1...Kg6 which results in a position that is lost.

See here and here.

Using DTZ50 (versus Nalimov) the mate is delivered at move 103. With DTM50 this could have been at move 90. I think the difference will usally be bigger for easier positions where there is more room for wasting moves.

[galen]

krpkq is complete. The deepest DTM50 (at zero count) is mate in 98, which is unique up to the horizontal flip symmetry:

8/8/1pk5/K7/8/8/1r6/4Q3 w


One move is lost relative to DTM to avoid a 50-move draw after the first pawn push.

However, if the counter is high enough (33-36), the record is mated in 107, which beats the DTM record.

[kronsteen]

knnkp: To be super-precise, I find it begins to strike at depth "51.5"; e.g., there are positions where Black is mated in 51 DTM but more in DTM50 (e.g., Ka4 Nc3 Nh3 / Ka8 Nc4, Black mated in 55). Other than that, same results.

Yes some positions lost in 51 (DTM) for Black are also 50-move rule draws : 4334 out of 262666

kqpkq: Same results, although the 36/30 counts are presumably after removing the one symmetry, so the full total would be 72/60.

Yes for pawnful endings I count only positions with wk on a-d files (positions with wk on e-h files are mirrored) and for pawnful endings I count only positions with wk in a1d1d4 triangle. This is what Nalimov does and allows direct comparison with Nalimov tbs files.

kbnkn: Same results I think; the deepest is mated in 80 (160 plies).

Same results - max positions = 159 plies wtm (mate in 80), 160 plies btm (lost in 80).

[kronsteen]

I have this position as mated in 85, 87, 91, 95, 98, 101, 103, or 118, or draw, depending on the initial count. When it's zero, here is a mate in 85 line (not unique):1. ... Kd4 2. Nd1 Kd3 3. Ne3 Kd4 4. Kf4 Kd3 5. Nef5 Kc4[1] 6. Ke5 Kc5 7. Ng7 Kc4 8. Ne6 Kd3 9. Kf4 Kc3 10. Ke3 Kc4 11. Ke4 Kc3 12. Kd5 Kb4 13. Kd4 Kb5 14. Nd8 Kb4 15. Nc6+ Kb5 16. Kd5 Ka6 17. Nd4 Kb6[2] 18. Kd6 Ka5 19. Kc5 Ka4 20. Nc6[3] Kb3 21. Kd4 Kc2 22. Na5[4] Kd2 23. Nb3+ Ke2 24. Ke4 Kf2 25. Nd4 Kg3 26. Ndf5+ Kg4 27. Nf3 h4 28. Ne3+ Kg3 29. Nf1+ Kf2 30. N3h2 Ke2 31. Kd4 Kd1 32. Kc3 Ke2 33. Kc2 Ke1 34. Kd3 Kd1 35. Ne3+ Kc1 36. Kc3 Kb1 37. Nf3 Kc1 38. Nd5 Kd1 39. Nf4 h3

Same results with my knnkp DTM50 TB (mating distances and pgn)

krpkq is complete. The deepest DTM50 (at zero count) is mate in 98, which is unique up to the horizontal flip symmetry. One move is lost relative to DTM to avoid a 50-move draw after the first pawn push. However, if the counter is high enough (33-36), the record is mated in 107, which beats the DTM record.

Same results with my kqkrp DTM50 TB.

[galen]

Among the 9 endings that are directly influenced by the 50-move rule (knnkp, kqpkq, kbbkn, kbnkn, krbkr, kqrkq, krpkq, kbbkq, knnkq), the first 6 ones are already generated and the results are the following :

For endings with direct (rather than inherited) 50-move rule influence, this list should also include krpkb. There are a few cases where, even with DTZ play, a pawn gets stuck at d5 (or e5) for more than 50 moves, resulting in a draw. It's also possible for a win to be delayed; e.g., in this position—

8/1K6/3k4/R2P4/8/8/7b/8 w - - 0 1


—DTM=61 but DTM50=62.

[galen]

This position has mc=0 (max DTM50 positions in kqpkq have mc=0 but this is not always the case for other endings) and can be reached in 4 moves from the kppkp position Kc4 Pe4 Pe3 / Ka2 Ph5 which ought to be a mate in 141 and may well be the absolute DTM50 record for 5-men.

I have now built complete kppkp tables, and this is verified. Or, to be clear, this position (Kc4 Pe3 Pe4 / Ka2 Ph5) with Black to move is mated in 141 (282 plies), which is the deepest 5-man mate.

There are (up to lateral symmetry) four distinct positions which are mated in 141; all are minor variants of this one. The White king can be on c5 instead of c4, and the Black pawn can be on g5 if the White king is instead on c5 or c6. In all four cases, initial play is rather prosaic, with no variation: both players must unhesitatingly rush their pawns to promotion. Once both have queens, it is Black's turn and mated in 137.

Here is a board with another of the positions (although boards on here aren't showing up for me at the moment):

8/8/2K5/6p1/4P3/4P3/k7/8 b - - 0 1


No deeper mates emerge from letting the counter get too high.

Although this result is not too surprising, I wouldn't mind confirmation. For one, I had to redo most of my en passant code to accommodate the two White pawns. I'm pretty sure it's right, but it was a bit tricky.

[galen]

Thanks!
The original position (from the Rybka forum, I think) was:
8/8/8/6kp/2p5/2N2K2/8/3N4 w - - 0 1

Someone complained that my tables did not score this as a win, whereas the Nalimov tables did. Of course the position is a draw by the 50-move rule.

What is somewhat funny is that after 1.Ke3, the Nalimov tables suggest 1...Kg6 which results in a position that is lost.

See here and here.

Using DTZ50 (versus Nalimov) the mate is delivered at move 103. With DTM50 this could have been at move 90. I think the difference will usally be bigger for easier positions where there is more room for wasting moves.

Hi syzygy, I am now able to evaluate the original knnkpp positions. My tables agree with yours (unsurprisingly) that the position shown is a draw, but after 1. Ne3 Kg6?, White can win, possibly. White might mate in 93, 94, or 98, depending on what moves went by before Black's fatal mistake; if PC>81, the game is drawn, and so Black's "error" is inconsequential.

Assuming White has 23 plies to work with, here is a winning line, where the mate (by your numbering) is on move 94:

1. Ne3 Kg6 2. Ng2 Kf5 3. Nh4 Kg5 4. Kg3 Kf6 5. Kf4 Ke6 6. Ne2 Kf6 7. Ng3 Ke6 8. Ke4 c3 9. Kd3 c2 10. Kxc2 Ke5 11. Kd3 Kd5 12. Ne2 Ke5 13. Kc4 Ke4 14. Kc5 Ke5 15. Nd4 Ke4 16. Ndf3 Kd3 17. Kb4 Ke3 18. Kc3 Ke4 19. Kc4 Ke3 20. Kd5 Kd3 21. Ne5+ Ke3 22. Neg6 Kd3 23. Nf4+ Kc3 24. Kc5 Kd2 25. Kd4 Kc2 26. Nd5 Kb3 27. Kd3 Ka4 28. Kc4 Ka5 29. Kc5 Ka4 30. Nc3+ Kb3 31. Ne4 Ka4 32. Nd2 Ka3 33. Kc4 Kb2 34. Ne4 Kc2 35. Nf3 Kb2 36. Nd4 h4 37. Nf3 Kc2 38. Nd6 Kb2 39. Nb5 Kc2 40. Na3+ Kb2 41. Kb4 Kc1 42. Kc3 Kd1 43. Kd3 Kc1 44. Nc4 Kd1 45. Nb2+ Kc1 46. Kc3 Kb1 47. Nd3 Ka2 48. Kb4 h3 ... and mate in 46 per any DTM line.

White's 17 is the last DTM-suboptimal move. However, for White's 21, 30, and 34 there are DTM-equivalent moves that are inferior in chess.

[h.g.muller]

What algorithm is used to generate DTM50? Is it sufficient to start from DTM50 successors, and start generating like you would for DTZ, except that you propagate DTM together with DTZ? And then, when a retro-move reaches a position that already was a DTZ win/loss (so you would normally ignore it), overwrite it, and continue propagation 'through' it when it gets a lower DTM?

[kronsteen]

My DTM50 generator works as follows :

1) identify illegal positions in order to exclude them from all subsequent searches
2) do all decaptures and depromotions from all possible subendings, and get this way an upper bound (if white to move) or lower bound (if black to move) of DTM50, for every plycount of the positions from which a capture or promotion is possible. In order to do this the information needed is the DTM50 value of all subending positions with the plycounter = 0 (equals DTM for a vast majority or positions, but a few positions winning without the 50 move rule are drawn under 50 move rule, and a (very) few positions are still winning but with the mate delayed (DTM50@PC=0 > DTM).
3) identify checkmate (lost in 0) and stalemate positions
4) do a backward step to identify all won in 1 positions (with the corresponding plycounter interval)
5) do a forward step to identify all lost in 1 positions (with the corresponding plycounter interval)
6) repeat steps 4 and 5 to identify won in n / lost in n positions, until no further progress is done and the max value from decaptures/depromotions is also exceeded. There is only one iteration per value of n, and there are no overwrites : on pass n, a (position,plycount) state with still unknown status which is discovered to have (wtm) one link to at least one (position,plycount) lost in <n (for b) , or (btm) all links to (position,plycount) won in <=n (for w), is a new proven win in n (wtm) or loss in n (btm).

[h.g.muller]

So do I understand correctly that you treat every (position, plycount) combination as a separate element of the EGT, multiplying its size by 100?

What I had in mind was to let the EGT (or at least the working space for generating it) only contain one element per position, but keep both the DTZ and the best-so-far DTM for it. By iterating (retrograde) over DTZ this would generate the conventional DTZ50, which tells you how low large the 50-move counter can be in order to still have a forcible win. Positions getting assigned a DTZ in this iteration would (retro-)inherit the DTM of the successor on which the DTZ transition was based. (If it was based on transition of multiple daughters of DTZ=n, it would get DTZ=n+1, and the DTM would become the minimum of these daughter's DTM on winning moves.)

On any iteration both the positions that got assigned a DTZ (which is always permanent) and the positions of which the DTM was lowered would be put in the 'new list', and in the next iterations their parents would be examined to see if the should now get a DTZ, and if their DTM should be lowered. Any time lowering of a DTM takes place, it means we found that an over-all faster way was found to win the position, provided we have more time in the current phase. The combination of (DTZ,DTM) for this position could then be flushed to permanent storage (where DTZ implies required ply count).

[Edit]
I guess it would not even be needed to store the DTZ, as if follows from the iteration number. All that is needed is to store DTM for wtm and btm for each position, and keep track of which positions are in the 'win front'. (This could be done by reserving one bit in the DTM counter, or in a separate list.) Winning retro-moves from a win-front position would set the DTM of all their ancestors to their own DTM+1, if it is not already lower or equal (where 'undecided' is represented by DTM = infinite), and add it to the new win-front when they do. Losing retro-moves would always lead to ancestors that had a larger DTM, but they would have be verified, and their new DTM would be the largest DTM of any of their daughters, + 1, which would only become part of the new win front when it is now lower than it was before.

[kronsteen]

So do I understand correctly that you treat every (position, plycount) combination as a separate element of the EGT, multiplying its size by 100?

You’re correct, but I don’t store as many as 100 values for every position, because a lot of values are identical. I represent DTM50 of a position as a series that grows (not strictly) with the move counter, and also during generation with the order mate in 0 < mate in 1 < … < mate in n < unknown < drawn. The most varied position ever found so far is a knnkp position with 26 different DTM50 values according to the move counter, and apart from knnkp, the most varied 5-men position has 16 different values : so DTM50 information can be generally compressed. Anyway, I intended my generator only as a proof of concept limited to 5-men, and I’ve 16 GB of RAM available so I’ve no problem storing in RAM full EGTs with up to 26 different values (I used 30 before knowing the real maximum figure).

What I had in mind was to let the EGT (or at least the working space for generating it) only contain one element per position, but keep both the DTZ and the best-so-far DTM for it. By iterating (retrograde) over DTZ this would generate the conventional DTZ50, which tells you how low large the 50-move counter can be in order to still have a forcible win. Positions getting assigned a DTZ in this iteration would (retro-)inherit the DTM of the successor on which the DTZ transition was based. (If it was based on transition of multiple daughters of DTZ=n, it would get DTZ=n+1, and the DTM would become the minimum of these daughter's DTM on winning moves.)

On any iteration both the positions that got assigned a DTZ (which is always permanent) and the positions of which the DTM was lowered would be put in the 'new list', and in the next iterations their parents would be examined to see if the should now get a DTZ, and if their DTM should be lowered. Any time lowering of a DTM takes place, it means we found that an over-all faster way was found to win the position, provided we have more time in the current phase. The combination of (DTZ,DTM) for this position could then be flushed to permanent storage (where DTZ implies required ply count).

I’m not sure I’ve got everything, but your proposition seems to have some similarities to the one I posted on this thread : viewtopic.php?f=6&t=7314 (see my next to last post). More on this discussion will be extremely helpful because it addresses the problem that I currently consider as the key issue for making 6-men DTM50 real : how to store lightweight information per position in RAM during DTM50 generation. Current DTM50 generators (mine and probably galen’s one) have not been built around this feature, but I think it is theoretically possible, and your proposition is one more hint for this. We still have to understand each other (and also with galen) but I'm hopeful.

[h.g.muller]

OK, I'll join the discussion in that thread, then. But please note I have added something to my previous post, which probably crossed yours (as you don't quote it).