DTM50 : A new (and ultimate ?) metric for EGTs

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..

DTM50 : A new (and ultimate ?) metric for EGTs

Postby kronsteen » Fri Sep 14, 2012 7:47 am

I’m currently looking at DTM50 (distance to mate metric, playing with 50-move rule). I’ve built a generator capable of building raw (uncompressed) DTM50 tables for all 3-men, pawnless 4-men , pawnful 4-men (soon), and 5-men later (I need to upgrade my hardware to handle them, I’m waiting for Haswell for that, but the generator is almost ready). 6-men will require a different coding architecture (my generator works with built-in RAM EGTBs and is limited to 5-men for this reason) but I’ll be able to furnish the general algorithm if needed.

Preliminary results are extremely interesting.

Looking at the first tables built, I can say with good confidence that :

- Optimal DTM50 lines are often the same as DTM (when the 50-move rule plays no role), or the same as DTZ50 (when the 50-move limit forces the winning side to play or force a zeroing move as fast as possible) ;

- But DTM50 lines can also be in-between, and only DTM50 tables are capable of showing these “in-between” lines, displaying optimal play taking care of both mate speedup and 50-move rule restrictions – a play that could be considered as “perfect play, ultimate knowledge” for those playing with the 50 move rule. This is the real added value of DTM50 tables. It can be expected that DTM50 tables will raise a lot of new interesting knowledge about some endings such as kqpkq, knnkp, and many 6-men of course

- DTM50 will take very reasonable space storage, this is very good news and this was unexpected. More precisely, DTM50 will probably be a not-so-big add-on to a set already composed of DTM + DTZ50 EGTs. I’ll try to post later technical explanations showing that the supplementary information carried by DTM50 over DTM+DTZ50 seems to follow a few basic patterns and will therefore be very highly compressible with a well designed compression scheme.


DTM50 is a “movecount (MC) dependant metric”, meaning that it can take several different values for the same position, depending on the current move counter. DTM50 grows with MC (a higher move count is always favourable for the defender), and when MC gets higher than 100 - DTZ50 (in plies), the position is drawn as the defender becomes able to force a 50-move rule draw.

I can give a taste with the following position. It is the only kpk position with DTM50 taking 4 different values depending on the current value of MC :

Kd2, Pc2 / Ka3 (white to move)

For MC < 92, DTM50 = 17
For MC = 92 or 93, DTM50 = 18
For MC = 94 or 95, DTM50 = 21
For MC = 96 to 99, DTM50 = 22

We can see why by following the unconstrained DTM line and spotting the moments when the 50-move limit forces white to follow a different and slower winning path :

1. Kc3 (1) Ka4
2. Kc4 Ka5
3. Kc5 (2) Ka6
4. Kc6 (3) Ka7
5. c4 (4)


(1) This move will force a sequence of 4 reversible moves (Kc3, bk plays, wk plays, bk plays) and will therefore walk into a 50-move rule draw if the initial MC is > 95. In that case, White must play 1. c3 immediately, delaying mate by 5 moves
(2) If the initial position was with MC=94 or 95, MC is now 98 or 99 and White must play 3. c3 instead, which delays mate by 4 moves
(3) If the initial position was with MC=92 or 93, White must play 4. c4 instead. This delays mate by one move
(4) Now and not before pushing the pawn becomes DTM optimal.

Understanding DTM50 is relatively straightforward in this example, but it is far from being always the case. I’ve also built the kqkr DTM50 table and after having a first look I can say that this table contains “in-between” lines that are pretty mysterious, influenced by both distance to mate and distance to capture of the rook.

I’ll keep posting as I get new results. I’ll also try to post some explanatory text (technical and non-technical) about DTM50 because this metric is a little harder to understand than the more popular DTM.

k
kronsteen
 
Posts: 88
Joined: Fri Aug 01, 2008 11:20 am
Location: France

Unlocking the secrets of DTM50 (more…)

Postby kronsteen » Tue Sep 18, 2012 5:25 pm

Look at this krkp position : Ka8, Rf5 / Kg8, Ph7 (white to move)

The DTM50 EGT shows the following results :

If MC<82, DTM50=19
If MC = 82 or 83, DTM50 = 20
If MC = 84 or 85, DTM50 = 28
If MC>85, draw

Why should the mate be delayed by as much as 9 moves for some particular values of MC ? Let’s follow the main DTM line and see what happens :

1. Kb7 Kg7
2. Kc6 Kg6
3. Rf1 Kg5
4. Kd5 Kg4
5. Rf7 h5… and mate in 14 more moves

But if MC=84 or 85 initially, Black plays 4. Kg6 instead of 4. Kg4. And now White must abandon the DTM optimal line at once by playing 5. Ke6 which is the only remaining winning move. The game proceeds as follows :

5. Ke6 Kg5
6. Kf7 Kg4
7. Kg7 (or Rh1) h5


So here’s what happened : with the MC so close to the 50-move limit, both sides turned towards the DTZ50 optimal strategy (i.e trying to force – for White - or avoid – for black - the play of a zeroing move, namely the black pawn being moved or captured). This forced White to go for a direct attack with his king of the black pawn on his original square in order to force him to move. White succeeded just in time, but after 7.h5 the whole process has caused a considerable degradation of his position, with his king shouldered away by the Black king and Black nearly in position to force a draw. But White is still able to recover and force a mate 22 moves later.

Amazing stuff… and these “DTM50 new effects” are already visible with only 4 men on board.
kronsteen
 
Posts: 88
Joined: Fri Aug 01, 2008 11:20 am
Location: France

Re: Unlocking the secrets of DTM50 (more…)

Postby syzygy » Tue Sep 18, 2012 11:09 pm

kronsteen wrote:Amazing stuff… and these “DTM50 new effects” are already visible with only 4 men on board.

Except that best play will not lead to MC >= 82 in such positions :wink:

My DTZ50 line for this position is:
1. Kb7 Kg7
2. Rf1 Kg6
3. Rh1 Kg7
4. Kc6 Kg6
5. Kd6 Kg7
6. Ke7 Kg6
7. Kf8 Kf5
8. Rxh7
I guess this is one of the drawing lines you get with MC=86?
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

Re: Unlocking the secrets of DTM50 (more…)

Postby kronsteen » Wed Sep 19, 2012 8:51 am

Syz, good to see you again. This forum is so quiet nowadays…

syzygy wrote:Except that best play will not lead to MC >= 82 in such positions


Of course. Clearly these first DTM50 curiosities are academic and will never happen in real games, but this won’t hold true when endings such as knnkp or kqpkq will be probed. In the case of kqpkq, particularly if inaccurate play is allowed before reaching a position to be analyzed, MC can easily take any value and can take “unnecessary high” values if previous inaccuracies from the attacker have resulted in going in loops or long checking sequences by the defending queen.

I’ve spotted a small flaw in your line. My tables show that after 3. Rh1 Black is able to last one ply longer and therefore force a draw if the initial MC was 85 :

3. Rh1 Kg7
4. Kc6 Kg6
5. Kd6 Kg7
6. Ke7 Kg8 !
7. Kf6 Kh8 !
8. Kf7 h5

In this variant, Black uses a different strategy, allowing himself to have his king stalemated in the h8 corner and being forced to move the pawn afterwards. This strategy lasts one ply longer.

This effect may be due to the fact that existing DTZ50 tables are stored in full moves and not in plies as they should. I believe that DTZ50 tables in full moves cannot spot the difference between a zeroing move played by white (capture of the black pawn) and a zeroing move played by Black (moving the black pawn) one ply later. I currently use online access to DTZ50 tables at www.chess.jaet.org and actually these tables consider both 6… Kg6 and 6…Kg8 as DTZ50 optimal, when in fact 6. Kg8 lasts one ply longer.

Only DTM (or DTM50) tables should be allowed to be stored in full moves as it is automatically known which side plays the move reaching the goal of the table (i.e mate), this is not true for DTC/DTZ/DTC50/DTZ50 tables. This is also the reason why I build DTM50 tables with MC in plies and not in full moves.
kronsteen
 
Posts: 88
Joined: Fri Aug 01, 2008 11:20 am
Location: France

Re: Unlocking the secrets of DTM50 (more…)

Postby syzygy » Wed Sep 19, 2012 7:31 pm

kronsteen wrote:Syz, good to see you again. This forum is so quiet nowadays…

I've not been sitting still, though :). Just finished generating the 6-piece WDL50+ and DTZ50+ tables for regular chess, and I will now generate them for atomic chess.

I’ve spotted a small flaw in your line. (...)

This effect may be due to the fact that existing DTZ50 tables are stored in full moves and not in plies as they should. I believe that DTZ50 tables in full moves cannot spot the difference between a zeroing move played by white (capture of the black pawn) and a zeroing move played by Black (moving the black pawn) one ply later. I currently use online access to DTZ50 tables at http://www.chess.jaet.org and actually these tables consider both 6… Kg6 and 6…Kg8 as DTZ50 optimal, when in fact 6. Kg8 lasts one ply longer.

Correct, my DTZ50+ table for KRvKP stores dtz in full moves. Tables such as KNNvKP store dtz in plies, though. So if a position can be won while respecting the 50-move rule, my tables will provide a solution, but the resulting "optimal" line can be off by 1 ply. (And if a position is a "cursed" win, my tables will also show how to make progress.)
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

Re: DTM50 : A new (and ultimate ?) metric for EGTs

Postby kronsteen » Fri Sep 21, 2012 12:50 pm

kronsteen wrote:I've not been sitting still, though . Just finished generating the 6-piece WDL50+ and DTZ50+ tables for regular chess


Nice. My own vision is that the obvious path for developing new EGTs for regular chess – more men on board – is going to require fast growing computing resources that already exceed what can be personally owned by the EGT enthusiasts we are. Recent developments on 7-men just show that. But we’re still able to do something useful by ourselves, namely developing multimetrics : WDL, DTZ, DTC, DTM with and without 50 move rule (8 at all) for all 3-6 men, and perhaps later something more exotic like DTR or distance to various events that could bring more knowledge and help understanding the underlying logic of some complex endings. Your DTZ50 for 3-6 men should be a big step towards that. The purpose of my current work on DTM50 is to demonstrate for 3-5 men (a good experimental territory) that this unknown metric can be made perfectly suitable, understood and widely used just like DTM currently is. Distributing DTZ50 first should definitely be helpful for that as DTM50 includes DTZ50 information (see my previous post). The final goal I’m thinking about is distribution of all 8 metrics listed above organized in expansion sets so that everybody could download the sets he wants according to his needs.

kronsteen wrote:and I will now generate them for atomic chess

Fantasy variants can also be enjoyable. Direct online query interfaces such as ones made by kk for 3x3 and 3x4 chess are especially handy.


DTM50 tables generated so far : All 3-men and all 2 vs 2 except for kpkp (requires en passant, not implemented yet). Now I’ll take some time to check the tables against anything possible and make absolutely sure that they’re correct before going on. Next steps : 3 vs 1, kpkp, and a generator ready to run for 5-men. If I find some interesting positions regarding DTM50 I’ll post them.


kronsteen wrote:Correct, my DTZ50+ table for KRvKP stores dtz in full moves. Tables such as KNNvKP store dtz in plies, though. So if a position can be won while respecting the 50-move rule, my tables will provide a solution, but the resulting "optimal" line can be off by 1 ply. (And if a position is a "cursed" win, my tables will also show how to make progress.)


DTZ50 tables stored in full moves can provide a solution for endings on which the 50 move rule is known to have no effect, assuming the initial positions are analyzed at MC=0. But DTZ50 in plies is required whenever the 50-move rule can modify the outcome (draw instead of win), either because the initial position is impacted (“cursed win” in our previous familiar terms), or because an initial MC>0 is considered, just like DTM50 does.
kronsteen
 
Posts: 88
Joined: Fri Aug 01, 2008 11:20 am
Location: France

Re: DTM50 : A new (and ultimate ?) metric for EGTs

Postby syzygy » Fri Sep 21, 2012 9:25 pm

kronsteen wrote:
kronsteen wrote:I've not been sitting still, though . Just finished generating the 6-piece WDL50+ and DTZ50+ tables for regular chess

Nice. My own vision is that the obvious path for developing new EGTs for regular chess – more men on board – is going to require fast growing computing resources that already exceed what can be personally owned by the EGT enthusiasts we are.

With current hardware computing 6-piece tables has become very manageable. I generated (and compressed) the full 6-piece set in under 5 days (with I think at least half the time spent on compression). The result is 68.3GB of WDL50+ data (so win/draw/loss including cursed wins and losses) and 81.9GB of DTZ50+ data. So they can really be used for game play (the WDL data almost fitting completely in RAM on a machine with 64 GB).

For the full set of 7-piece tables on a PC it seems better to wait a few more years. But I might give generating 7-piece tables for endgames with opposing white and black pawns a try. They are only 2.5 times bigger than 6-piece tables with a pawn and have basically the same RAM requirements during generation.

The purpose of my current work on DTM50 is to demonstrate for 3-5 men (a good experimental territory) that this unknown metric can be made perfectly suitable, understood and widely used just like DTM currently is. Distributing DTZ50 first should definitely be helpful for that as DTM50 includes DTZ50 information (see my previous post).

If you make tables that only include DTM50 information for combinations (position, MC) reachable with optimal play by the winning side (assuming the winning side starts using the table at MC=0), those tables will probably hardly be bigger than the regular DTM tables. (And some tricks can reduce the tables much further, e.g. if WDL is available you can store draw values as don't cares and don't have to distinguish between winning and losing. And half a table of DTM is sufficient if you have WDL anyway for use during a search.)

I understand that you are interested in the complete information, but providing smaller tables as an option might make more people use them.

kronsteen wrote:and I will now generate them for atomic chess

Fantasy variants can also be enjoyable. Direct online query interfaces such as ones made by kk for 3x3 and 3x4 chess are especially handy.

That is a possibility. I made one a long time ago for 4-piece suicide chess, but it's not online anymore.

DTM50 tables generated so far : All 3-men and all 2 vs 2 except for kpkp (requires en passant, not implemented yet). Now I’ll take some time to check the tables against anything possible and make absolutely sure that they’re correct before going on. Next steps : 3 vs 1, kpkp, and a generator ready to run for 5-men. If I find some interesting positions regarding DTM50 I’ll post them.

I can provide numbers for number of cursed wins etc., but we probably only count them in the same way for tables with a single pawn.
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

DTM50 : All 3 and 4-men created

Postby kronsteen » Sun Oct 07, 2012 2:43 pm

All 3-men and 4-men DTM50 tables are created (also kpkp with en-passant rule). Tables are in raw format with no compression and there are still many redundancies to be eventually discarded, but they already shrink to less than 300 MB using winzip. I expect that with specific compression and no redundancies they will be close to twice the size of DTM Nalimov tables (3-4 men Nalimovs are 30 MB).

As no 3 or 4-men ending has depth>50, the 50-move rule plays no role for positions analyzed at movecount (MC) = 0. But if we allow movecounts>0, many new interesting features arise. Certainly such features won't happen in real games because the players won't fool around playing dozens of useless non-zeroing moves before reaching a critical MC value and suddenly wise up. But these will also appear the same way in 5+men endings and will have a big influence on the play even at MC=0 for endings that go deeper than 50 moves.

I've given below the maximal DTM50 positions for all 3-4 men. If DTM=DTM50, every DTM maximal position is also DTM50 maximal at MC=0, and the winning lines are the same (examples of such positions can be found at http://kirill-kryukov.com/chess/longest ... ates.shtml). If DTM50>DTM, I show below one DTM50 maximal position and the minimal critical value of MC. Sometimes it can be found a DTM50 maximal position that is also a DTM maximal at MC=0, sometimes not (Whenever possible, the DTM50 maximal position example given is also DTM maximal at MC=0). When DTM50>DTM, DTM50 and DTM optimal lines differ at some point and I've given a short explanation of what can be observed. Some "DTM50 max themes" already observed for White are :

- play immediately a "weak" zeroing move (ex : underpromotion)
- play a variant that diverges immediately or quickly from the DTM line and aims at forcing Black to quickly capture one white piece (kqxk, krxk) or push his pawn (krkp)
- begin the play the same way as DTM but at some point late in the process be forced to play a variant that allows better defence by Black in order to speed up MC reset (kqkp especially has a nice black knight promotion in the end)

Info given are :
1) max DTM of the ending
2) max DTM50 of the ending
3) Is the given DTM50 maximal position also a DTM maximal at MC=0 (Yes/No)
4) FEN of one DTM50 maximal position with the proper value of MC (the next to last figure)
5) Short description of the DTM50 optimal line and how it differs from the DTM line

kpk 28 30 Yes 8/8/8/1k6/8/8/K5P1/8 w - - 78 1 White must push his pawn earlier in the main line, delaying mate by 2 moves
knk - -
kbk - -
kr 16 16
kq 10 10
kppk 32 32
knnk 1 1
knpk 27 33 No 8/1P6/8/8/k1N5/8/8/K7 w - - 98 1 Bishop underpromotion forced at move one
kbpk 31 33 No K7/1P6/k7/8/1B6/8/8/8 w - - 98 1 Knight underpromotion forced at move one
kbnk 33 33
kbbk 19 19
krpk 16 26 No 8/8/8/1R6/k7/8/5P2/K7 w - - 98 1 White must play 1.Ka2 or 1.Kb2 to force Black to take the rook at once
krnk 16 24 No 2R5/3k4/8/8/8/8/K4N2/8 w - - 80 1 If MC=80 exactly white can't follow DTM line (mate in 21 plies) and must force Black to take the knight one ply earlier
krbk 16 20 No 8/8/2k5/8/8/8/RB6/K7 w - - 80 1 Same as krnk (see above)
krrk 7 20 No 8/8/3k4/8/8/R7/R7/K7 w - - 91 1 Same as krnk (see above)
kqpk 10 28 No k7/8/8/8/8/6Q1/6P1/K7 w - - 98 1 White must sacrifice his queen at once (1.Qb8+)
kqnk 9 15 No 1N6/8/8/8/6k1/Q7/8/K7 w - - 88 1 Same as krnk (see above) 1
kqbk 8 14 No 8/4B3/8/Q7/4k3/8/8/K7 w - - 90 1 Same as krnk (see above)
kqrk 6 18 No 8/3k4/8/8/8/1R6/Q7/K7 w - - 96 1 Same as krnk (see above)
kqqk 4 11 No 8/8/8/5k2/8/Q7/Q7/K7 w - - 96 1 Same as krnk (see above)

kpkp 33 33
kpkn 29 29
kpkb 29 29
kpkr 43 43
kpkq 29 29

knkp 7 7
knkn 1 1
knkb 1 1
knkr 1 1
knkq - -

kbkp 1 1
kbkn 1 1
kbkb 1 1
kbkr - -
kbkq - -

krkp 26 32 No 1K6/R7/6p1/8/5k2/8/8/8 w - - 78 1 If MC=78 or 79 the white king must attack the pawn from behind in order to force him to move quickly, and is badly placed after that. White still can recover, but loses 8 moves in the process (at MC=0 the position is DTM50=DTM=24).
krkn 40 40
krkb 29 29
krkr 19 19
krkq 19 19

kqkp 28 34 Yes 3Q4/3K4/8/8/8/3k4/3p4/8 w - - 48 1 if MC=48 exactly White must speed up conversion by 1 ply and in the end he must play a variant that allows Black to promote to Knight with check, delaying mate by 6 moves
kqkn 21 24 No 8/8/1n6/2k5/K7/1Q6/8/8 w - - 64 1 if White must take the black knight as fast as he can he loses 3 moves in the final phase
kqkb 17 19 Yes 7Q/8/8/4b3/3k4/8/8/K7 w - - 76 1 Same as kqkn (see above) - 2 moves lost
kqkr 35 37 Yes 8/1r6/8/3k4/8/8/8/1KQ5 w - - 40 1 Same as kqkn (see above) - 2 moves lost
kqkq 13 13

I can already answer to any DTM50 3-men and 4-men query (As I explained before, DTM and DTZ50 access are available online but are not sufficient to probe DTM50 optimal lines). 5-men will come later - with a bunch of discoveries awaiting.

k
kronsteen
 
Posts: 88
Joined: Fri Aug 01, 2008 11:20 am
Location: France

The maximal DTM50 position for kqkp

Postby kronsteen » Mon Oct 08, 2012 5:57 pm

3Q4/3K4/8/8/8/3k4/3p4/8 w - - 48 1
3Q4/3K4/8/8/8/3k4/3p4/8 w - - 48 1

MC=48 plies for the initial position. This position is also maximal for DTM, but DTM=28 whereas DTM50=34 if MC=48 precisely (if MC<48 DTM50=DTM=28 and the winning lines are the same, and if MC>48 the position is drawn).

The 23 first moves are the same for DTM and DTM50 :

1. Kc8+ Kc2
2. Qc7+ Kc1
3. Qb6+ Kb1
4. Qc5+ Kb1
5. Qb4+ Kc2
6. Qc4+ Kb2
7. Qd3 Kc1
8. Qc3+ Kd1
9. Kd7 Ke2
10. Qc4+ Ke1
11. Qe4+ Kf2
12. Qd3 Ke1
13. Qe3+ Kd1
14. Kd6 Kc2
15. Qe4+ Kc1
16. Qc4+ Kb2
17. Qd3 Kc1
18. Qc3+ Kd1
19. Kd5 Ke2
20. Qc4+ Ke1
21. Qe4+ Kf2
22. Qd3 Ke1
23. Qe3+ Kd1

reaching this position :
8/8/8/3K4/8/4Q3/3p4/3k4 w - - 94 1
8/8/8/3K4/8/4Q3/3p4/3k4 w - - 94 1

Then the paths diverge. The DTM optimal line continues as :

24. Kd4 Kc2
25. Qc3+ Kd1
26. Ke3 Ke1
27. Qxd2+ Kf1
28. Qf2#

Unfortunately, playing with 50-move rule after 26… Ke1 the move counter reaches 100 plies and Black claims a 50-move rule draw. But the initial position is still winnable under 50-move rule and the DTM50 line is :

24. Kc4! Kc2
25. Qb3+! Kc1
26. Kc3! d1=N+
27. Kd3 Nf2+
28. Kd4 Nd1
29. Qa2 Nb2
30. Kc3 Nd1+
31. Kb3 Nb2
32. Qxb2+ Kd1
33. Qf2 Kc1
34. Qe1#

After 26.Kc3 White has immobilized the Black king and forced Black to promote his pawn at MC=99, one ply before the 50-move limit. If Black chooses a queen White mates immediately with 27. Qb2#, but Black promotes to a knight instead, and pushes the mate back at move 34.
kronsteen
 
Posts: 88
Joined: Fri Aug 01, 2008 11:20 am
Location: France

DTM50 data structure and compression

Postby kronsteen » Fri Oct 12, 2012 1:51 pm

A post discussing first ideas about DTM50 compression strategy – I’ve very little experience in this area and about what to do exactly in order to achieve good compression rates and access time for future probing engines. Help welcome :) !

DTM50 is a movecount (MC) dependant metric. This means that for a given position there is not only one DTM50 value, but 100 DTM50 values, each one corresponding to a different value of MC in the [0,99] interval. Fortunately, many of these values are identical : for all 3-men endings, the maximal number of different DTM50 values for a single position is 4, and for 4-men endings this maximal number is 8. DTM50 values are growing with MC, eventually reaching the value inf when the position becomes drawn under 50-move rule.

The observed structure of currently built DTM50 tables (3-4 men) shows that DTM50 tables basically contain 3 chunks of information :

- the DTM50 value at MC=0 (D0);
- the highest MC value (MCmax) for which the position is winnable
- the DTM50 values other than D0, and their corresponding MC value in the [1,MCmax] interval.

D0 is very often equal to DTM, and when it is not, it is also very frequent that the position is simply drawn under 50-move rule (D0 = inf). Apart from very special endings such as knnkp there will be very few positions winnable under 50-move rule but having D0 > DTM (note also that D0 is always greater or equal to DTM)
That means that D0 information can be stored as a small add-on table (that will very often be empty, as explained above) to a standard DTM table that everyone interested in DTM50 is supposed to own, with these symbols : E : D0 = DTM, D : D0 = inf (position is drawn because of 50-move rule, a “cursed win”), x : D0 = DTM+x.

MCmax info is nothing else than the DTZ50 table, as MCmax = 100-DTZ50 (in plies). This is why everyone wanting complete DTM50 tables must have DTZ50 first. Together with the remarks about D0 this is also why DTM50 should definitely be envisaged as an expansion set to DTM & DTZ50 tables.

The last chunk of information is the intermediate DTM50 values and their corresponding MC values. At first sight it looks very heavy, but fortunately the first tables built show that this part has low entropy as a few patterns are very common such as :
- DTM50 = D0 if MC=MCmax (no intermediate DTM50 values at all)
- DTM50 = D0+1 at 2-ply distance from 50-move rule draw (MC=MCmax-1 or MCmax). This is the case when DTM and DTZ50 lines are the same up to a point where the winning side must choose between a non-zeroing move mating in n and a zeroing move mating in n+1.
- DTM50=D0+2 at 2-ply distance from 50-move rule draw (MC=MCmax-1 or MCmax). Same as above, but the final zeroing move delays mate by 2 moves
- DTM50=D0+1 at 4-ply distance from 50-move rule draw (MCmax-3<=MC<=MCmax). Same as above, but the final zeroing move is played 1 move earlier and if a DTM-optimal non-zeroing move is played instead, it can’t be played at next move.
There are more complex patterns of course but they are far less common, and the number of positions having 2, 3, 4… different DTM50 values drops considerably when the number of different DTM50 values gets higher. That’s why applying Huffman coding on this chunk will certainly produce very good compression rates.

Seen onto an example :

Kc3, Pc2 / Ke8
MC < 94 : DTM50 = 18
MC = 94 or 95 : DTM50 = 19
MC = 96 or 97 : DTM50 = 21
MC > 97 : draw

The first chunk is : D0 = 18. Naturally DTM of this position is also 18 so there is no need to store any additional data if the DTM kpk table is already available
The second chunk is : DTZ50 = 3 plies (MCmax = 97).
The third chunk is :
- if MC>=MCmax - 3, DTM50>=D0 + 1
- if MC>=MCmax - 1, DTM50>=D0 + 3
which can be represented by the following entire word :
3 1 1 3

One can have a better overall idea by looking at the complete kpk DTM50 table in text format attached below. First value is DTM50 at MC=0 (254 = draw and 255 = illegal), 2nd value is first value of MC with a change in DTM50 value, 3rd value is new DTM50 value, 4th – 5th value are next value of MC – next DTM50 value, etc… . (This raw table also contains a lot of info to be thrown away).

kpk_txt.zip
(738.96 KiB) Downloaded 135 times



syzygy wrote:If you make tables that only include DTM50 information for combinations (position, MC) reachable with optimal play by the winning side (assuming the winning side starts using the table at MC=0), those tables will probably hardly be bigger than the regular DTM tables. (And some tricks can reduce the tables much further, e.g. if WDL is available you can store draw values as don't cares and don't have to distinguish between winning and losing. And half a table of DTM is sufficient if you have WDL anyway for use during a search.)

I understand that you are interested in the complete information, but providing smaller tables as an option might make more people use them.



It is an interesting idea but I’ll keep it for later, for several reasons :

- Building DTM50 tables originated only from MC=0 positions needs a forward propagating algorithm when full DTM50 tables are generated with a backward propagating algorithm. This will require a new code – to be written –, and this code won’t build tables by itself but will work on already built tables and change DTM50 values to “don’t cares” for what I call “alien territory” (positions+MC combinations that are unreachable from MC=0 positions with optimal DTM50 play by the winning side)
- It will lead to replace the DTZ50 value (which taken alone is a valuable information) by the MC frontier value to “alien territory” (which is of less value, obviously)
- For now I’ve no clue about how much it’ll cut down TB sizes. My feeling is that for those already owning DTM + DTZ50 tables the incomplete DTM50 tables will be of little interest compared with complete ones, and might even be bigger as they store an additional piece of information, the MC frontier value quoted above.
- Such incomplete DTM50 tables will preclude probing non-optimal DTM50 playing lines. If you want to know why a move is inferior to another and probe the resulting position the table will sometimes return the statement “don’t care, you’ve walked into alien territory, you shouldn’t be there”. This won’t bother users only wanting chess engines capable of making perfect DTM50 play from MC=0 positions, but it will be restrictive for other applications.

Such tables could exist, nevertheless, and should be considered as small extensions of DTM tables only for those who don’t care about DTZ50.
kronsteen
 
Posts: 88
Joined: Fri Aug 01, 2008 11:20 am
Location: France


Return to Endgame Tablebases

Who is online

Users browsing this forum: No registered users and 3 guests