KRBNKQN EGT stats ?

[guyhaw]

Did Marc Bourzutschky ever publish any stats for the Konoval-MB KRBNKQN DTC EGT? If so, does anyone have them?
g

[mbourzut]

Attached are stats files for kqnkrbn and krbnkqn in quasi-Nalimov format. If one wanted, one could combine them into one .tbs like file, as all wtm lost positions in kqnkrbn are btm lost positions in krbnkqn. For example, since there are about 32 billion positions in kqnkrbn that are "not won", and about 13 billion positions in krbnkqn that are lost for black (=lost for white in kqnkrbn) the number of draws for wtm in kqnkrbn is about 19 billion.

-Marc

[guyhaw]

... thanks mb - good to see you online again - g

[ernest]

Attached are ...-Marc

Bonjour Marc,
A friend of mine (in France) has produced the Nalimov-like DTM50 files (giving legal mates by the 50-move rule) for knnkp (and knnkq).
Have you (or friend) produced something like that? We would be interested in comparing

[guyhaw]

ernest,

Marc had/has a gtbgen code which certainly could produce DTZk EGTs (and purportedly DTCk and DTMk EGTs though I don't know how it did that).
John Tamplin used it to produce DTZ50 EGTs for all 3- to 5-man and 6-man P-less endgames.
g

[syzygy]

Attached are ...-Marc

Bonjour Marc,
A friend of mine (in France) has produced the Nalimov-like DTM50 files (giving legal mates by the 50-move rule) for knnkp (and knnkq).
Have you (or friend) produced something like that? We would be interested in comparing

Note that in the general case a DTM50-table will be broken, unless the move-counter is made part of the index (not the case for Nalimov-like tables). For knnkp and knnkq it might work though, as the subtables are not affected by the 50-move rule.

[guyhaw]

I would like to understand more clearly what people have in mind when they say 'make the move-counter part of the index', just for the avoidance of misunderstanding. Do they mean, in effect 'extend the FEN to include the move-counter'? I suspect so. This would appear to multiply the number of positions by 50, given the current 50-move rule, and this is a somewhat daunting prospect. I take it that such tables would be specific to the 50-move rule and not generic to a k-move (as the DTR EGT 'ER' is).


I'm a bit puzzled about what the DTM50 (and DTC50) EGTs achieve, and maybe I should have thought about this years ago: maybe Marc can clarify?

The DTZ50 EGT is definitive about which positions are decisive under a 50-move rule and assumes that there are 50 moves available. It says how many are needed assuming this quantity is minimaxed as Priority #1 by the two sides. Creating the DTZ50 EGT is the definitive way to define the set of positions where a draw-claim can be avoided [leaving aside the boundary issue created by measuring depth in moves rather than in plies].

I assume the DTM50 (and DTC50) EGTs do not show a position as being decisive unless it is decisive in the DTZ50 EGT. This implies that DTZ50 is created before DT(C/M)50 is created. I also assume that the DT(C/M)50 is not the same as the DTZ50 EGT and therefore does not always point to the 'DTZ50 way' to close out the current phase, although it always points to a path involving only positions which are decisive in DTZ50.

I guess therefore that following the DT(C/M)50 recommendations might result in a 50-move draw-claim, despite the '50' in the title of the EGT, although this is less likely than with the DT(C/M) EGT. Examples would be useful to confirm this. This does not mean that the DTM50 EGT is 'broken' if it clearly does what it says on the tin. I think the issue is that 'what it says on the tin' is open to misinterpretation.

The strategy to win with the DTZ50 and DTM50 EGTs would be SV+Z50oM- ... preserving theoretical value, guarding DTZ50 and only then minimising DTM.


Actually, I think of KNNKP(h4) as a 'successor table' [not a 'subtable'] of KNNKP(h5), etc. Therefore, re KNNKP, there are successor-tables affected by the 50-move rule. I don't have the per-square maxDTZs for KNNKP.

g

[guyhaw]

Hope I haven't got any finger-trouble here ...

wtm lost 88,147,287,576 ... 38.53% of positions: maxDTC/Z = 517 (24 positions), average DTC/Z = 49.59 (!)
wtm drawn 49,153,557,962 ... 21.49%
wtm won 91,451,411,502 ... 39.98%: maxDTC/Z = 32 (1 position), average DTC/Z = 1.13

btm lost 12,758,649,652 ... 05.78%: maxDTC/Z = 31 (1 position), average DTC/Z = 1.08
btm drawn 19,008,683,296 ... 08.62%
btm won 188,846,686,132 ... 85.60%: maxDTC/Z = 517 (6 positions), average DTC/Z = 14.96

So with btm, KRBNKQN is overwhelmingly won by Black: with wtm, it is more like 50-50.

For KRBKQ, the corresponding %s are:
wtm lost (13.35%), drawn (47.95%), won (38.69%)
btm lost (03.21%), drawn (25.60%), won (71.19%)

g

[syzygy]

I would like to understand more clearly what people have in mind when they say 'make the move-counter part of the index', just for the avoidance of misunderstanding. Do they mean, in effect 'extend the FEN to include the move-counter'? I suspect so. This would appear to multiply the number of positions by 50, given the current 50-move rule, and this is a somewhat daunting prospect. I take it that such tables would be specific to the 50-move rule and not generic to a k-move (as the DTR EGT 'ER' is).

I would not call it FEN but game state. The index encodes game state. If you ignore the 50-move rule, then the game state is (position, side-to-move) and you essentially get the tablebases we are used to. If you take into account the 50-move rule, then the game state is (position, side-to-move, move-counter).

For DTR the game state is (position, side-to-move, move-counter) as well, so the same index will work for DTR-tables (or: will make DTR-tables work). (And it would be sufficient to only store DTR for each (position, side-to-move, move-counter)-tuple.)

(I know that I'm ignoring en passant, castling and draw-by-rep. The latter two are ignored by tablebases, so do not form part of the game state as far as tablebases are concerned. En passant is part of the game state, and can be handled in any of the known ways.)

Of course this extended game state or index will inflate table size by a factor of 50 (or even 100, when counting in plies). However, the sequence of values stored for (position, side-to-move, k) for k = 0, 1, ..., 50 should normally compress pretty well. It compresses extremely well for DTZ50, see below. See also the last three paragraphs of this post.

I'm a bit puzzled about what the DTM50 (and DTC50) EGTs achieve, and maybe I should have thought about this years ago: maybe Marc can clarify?

DTM50 will give the shortest mate for the winning side against arbitrary play by the losing side, taking into account the 50-move rule. The shortest legal mate.

The DTZ50 EGT is definitive about which positions are decisive under a 50-move rule and assumes that there are 50 moves available. It says how many are needed assuming this quantity is minimaxed as Priority #1 by the two sides. Creating the DTZ50 EGT is the definitive way to define the set of positions where a draw-claim can be avoided [leaving aside the boundary issue created by measuring depth in moves rather than in plies].

In principle, DTZ50 is also based on (position, side-to-move, move-counter) as game state. However, in the case of DTZ50 a small miracle applies: if dtz50 for (p, s, 0) = v, then (as observed by kronsteen):
dtz50 for (p, s, x) = v, if x + v <= 50
dtz50 for (p, s, x) = infinity (i.e. the position is a draw), if x + v > 50.
This means that the set of values dtz50 for (p, s, x) with 0 <= x < 50 can be compressed/reduced to a single value. Or from another point of view, it is sufficient to base the tablebase on (position, side-to-move) as game state. This is why DTZ50 based on (position, side-to-move) works and why DTM50, DTC50 and DTR based on (position, side-to-move) do not.

I assume the DTM50 (and DTC50) EGTs do not show a position as being decisive unless it is decisive in the DTZ50 EGT. This implies that DTZ50 is created before DT(C/M)50 is created. I also assume that the DT(C/M)50 is not the same as the DTZ50 EGT and therefore does not always point to the 'DTZ50 way' to close out the current phase, although it always points to a path involving only positions which are decisive in DTZ50.

DTM50 based on (position, side-to-move) is a broken concept, so generating it based on DTZ50 will not work either.

The strategy to win with the DTZ50 and DTM50 EGTs would be SV+Z50oM- ... preserving theoretical value, guarding DTZ50 and only then minimising DTM.

With a "DTM50"-table based on (position, side-to-move), this will not give the shortest legal mate (under the 50-move rule). (Well, it might work if none of the subtables / successor tables are affected by the 50-move rule, or it might work for a particular table by sheer coincidence.)

Actually, I think of KNNKP(h4) as a 'successor table' [not a 'subtable'] of KNNKP(h5), etc. Therefore, re KNNKP, there are successor-tables affected by the 50-move rule. I don't have the per-square maxDTZs for KNNKP.

Good point! I completely forgot about pawn slices. This means that DTM50 for KNNKP based on (position, side-to-move) (e.g. a 'Nalimov-type' table) is theoretically broken.

[guyhaw]

Yes, sz is right to talk about 'game state' rather than 'FEN' as the latter is merely one representation of the former. Nalimov's EGTs, btw, do take into account 'en passant capture' but not castling rights.

I think I have a different attitude about EGTs to some other contributors, and I had it before sz pointed out the 'hidden path' difficulties associated with the DTR EGT. I don't regard use of EGTs as being just 'look up the position in an EGT and you will find the answer'.

Instead, I regard the move-choice as the responsibility of the player who will, consciously or not, use some strategy - in the form of a succession of filters - for focussing down on the final move. Thus, if you just look up the DTM EGT 'EM' (strategy SV+M-) or the DTC EGT 'EC' (Strategy SV+C-), you will occasionally trip over the 50-move rule. But if you also have available the DTZ EGT 'EZ', you can employ more sophisticated strategies like SV+ZoM- which at least ensure that the 50-move rule claim does not avoidably occur in the current phase.

In particular, my approach has been that the player uses the information offered by the EGTs in the context of the move-count, and that the EGTs know nothing of move-count.

Given mb's track EGT-record which is impeccable, I would be very reluctant to say that anything associated with him is 'broken'. Admittedly, the DTM50 EGT 'EM50' is only a partial response to the 50-move rule, but that does not mean it is 'broken' if it does what it claims to do. On the one hand, it avoids positions which are draws under a 50-move rule (even given 50 moves in the current phase) but does not guarantee that blind observance will avoid a 50-move-rule draw-claim. Maybe that's a bit difficult for some to understand or sympathise with. I've never felt the need to generate DTM50 or DTC50 EGTs for this reason.

I will ponder the 'small miracle' of DTZ as that sounds like a new insight.

g

[syzygy]

Given mb's track EGT-record which is impeccable, I would be very reluctant to say that anything associated with him is 'broken'. Admittedly, the DTM50 EGT 'EM50' is only a partial response to the 50-move rule, but that does not mean it is 'broken' if it does what it claims to do.

First of all, I do not know if mb has generated a DTM50 tablebase or not. (Hmm, in "Chess endgames: 6-man data and strategy" DTM_k tables are mentioned, but only in passing.)

If he has, then I doubt that it does what its maker thought it would do. At least to me, DTM50 is supposed to give the shortest legal mate for the winning side against any play by the losing side. Just as DTM give the shortest mate for the winning side against any play by the losing side (but completely ignoring the 50-move rule). Since a "Nalimov-type" DTM50-table does not (and cannot) do that, the concept is broken. (Of course I cannot exclude that the maker was only interested in the statistics and not in finding winning lines. In that case DTM50 of Nalimov-type is perfectly fine.)

It is the same as for DTR: one can write down a definition of the data on paper, and one can generate this data (and I don't doubt that for DTM50 mb has done this correctly, if indeed he has generated such tables), but the data does not do what one would think it does. (It *might* work ok for the particular DTM50-tables generated, e.g. because of no successor-tables being affected by the 50-move rule, but I'm thinking of theoretically sound concepts.)

On the one hand, it avoids positions which are draws under a 50-move rule (even given 50 moves in the current phase) but does not guarantee that blind observance will avoid a 50-move-rule draw-claim.

Could you give a complete definition of what DTM50 does? DTM50 must have to do something with minimizing the distance to mate, right?

I will ponder the 'small miracle' of DTZ as that sounds like a new insight.

I think it's very helpful to think of the 50-move rule as extending the game state. Within the framework of "Nalimov-type" tables (with (position, side-to-move) game state) adding awareness of the 50-move rule is a hack (essentially in terms of "we stop at 50 iterations"). It happens to work for DTZ (giving DTZ50), but for other metrics it fails and it's not easy to see why.

Once you extend game state with the move-counter, the 50-move rule (or any k-move rule for that matter) can be treated in a natural way, without any hacks.

Note that the "move-counter"-dimension leads to "move-counter"-slices (comparable to pawn-slices), because each move either transitions into a successor-table or pawn-slice, or transitions from a move-counter=k slice to a move-counter=k+1 slice. So generation will start with move-counter=50 (in plies), then move-counter=49, move-counter=48, etc. and stop at move-counter=0. These slices correspond to the iterations that we already know, and we naturally arrive at the "we stop at 50 iterations"-hack, which is now not a hack anymore. What is clear is that the information in all "move-counter"-slices must be retained if you want to be able to play out winning lines.

Performing this generation with the DTZ-metric leads to "move-counter"-slices that can be collapsed into DTZ50-tables of Nalimov-type without loss of information. This is because the move-counter=k slice can be trivially recovered from the move-counter=0 slice.

Applying the DTM-metric leads to a table giving shortest legal mates, but this table can't be collapsed into a "Nalimov-type"-DTM50 table without losing information that is required to find the correct move for move-counter > 0. (However, storing one or more "move-counter"-slices of the full (extended) table in combination with a search might give a practical shortest-mate solver, see this post.)

[guyhaw]

The '6-man Data and Strategy' paper says that mb extended Nalimov's DTM-code to enable it to generate EGTs to the DTC(k), DTMk and DTZ(k) metrics.
I assume mb knew what he meant by these metrics and satisfied himself that the code works - but I have no direct knowledge of any DTMk EGTs existing.

My assumption, based on the argument above, is that in the DTM50 EGT:
- positions which are drawn under the 50-move rule, even given an initial budget of 50 moves, are shown as drawn in the DTM50 EGT EM50,
- depth to mate is then minimaxed back without regard to phase-boundaries, and therefore
- the DTZ50-minimaxing lines are not necessarily followed, which means that
- some DTM50-minimaxing lines might be subject to a 50-move draw claim.

Since I would not expect to avoid all 50m-draw-claims, as I would be using a DTM50 EGT and not a DTZ50 one, I don't think it's broken. But I can see why others might disagree. Of course, an example of following a DTM50-line and not avoiding a 50m-draw-claim would be useful: I expect a DTZ50 = 50 position might be the start of an example.

The DTR EGT only holds DTZR for the best dtr achievable (with DTR-minimaxing play), and does not say how quickly the attacker can achieve a weaker DTR and end the current phase. That's why - as has now been discovered - a degree of forward-searching using the EGT may be necessary for best results.

g

[syzygy]

I don't understand why anyone would call a table "DTM50" if by design it does not properly take into account the 50-move rule.

DTM give shortest mate against any play by the losing side, without any k-move rule.

DTM50 gives shortest mate against any play by the losing side, with the 50-move rule.

I'm convinced that this is what mb had in mind when generating DTM50. And I'm convinced that the tables he has generated (if any) do in fact contain the DTM50 values that fit my definition. However, they only contain those values for move-counter = 0. Therefore they do not contain sufficient information to correctly play out those winning lines.

Since I would not expect to avoid all 50m-draw-claims, as I would be using a DTM50 EGT and not a DTZ50 one, I don't think it's broken. But I can see why others might disagree. Of course, an example of following a DTM50-line and not avoiding a 50m-draw-claim would be useful: I expect a DTZ50 = 50 position might be the start of an example.

Obviously, any position that has a DTZ50-line will have a DTM50-line (and vice versa): for any position that can be won under the 50-move rule there exists a winning strategy that optimizes distance to mate.

(I expect you disagree here. In that case blank your mind, because it is plainly true if you start thinking about this from scratch. Presented to you is a blackbox game X in which players take turns. At each turn, a player has a finite number of moves to choose from. Furthermore, depending on play game X will result in a win, loss or draw in a finite number of moves. Now if a player has a winning strategy, it easily follows that he has a winning strategy that minimizes the maximum number of moves required to win against any play. Now take X = the game of chess including the 50-move rule.)

[guyhaw]

Well, if I have got the definition of mb's DTM50 metric wrong, I hope he will step in and correct me.

Yes, I agree that if a position is decisive under a 50-move rule, there is a line that minimaxes DTM.
You only need the fact that 'decisive' ==> finite number of moves to win.
You don't actually need to use the fact that you have a finite number of choices of move at each turn, as in Chess.
I use this argument to show that DTR and DTZR are 'well defined'.


For an example where the DTM50 EGT (I think) offers an opportunity to go wrong and walk into a 50-move draw-claim, take the endgame KNNKQ.
This example features in my "Strategies for Constrained Optimisation", ICGA_J (2000).

Position Q-NN1 = 8/8/2k5/8/4n3/3Q2n1/8/4K3 w: dtc = 50, dtm = 59 ... and a SV+M-/SM+ line can go, after 37 moves to
Position Q-NN2 = 8/8/1n1K4/n1Q5/k7/8/8/8 w: dtc = 13, dtm = 21 (Black has conceded one in DTM terms) but now White has a choice of ...
38.Qg1, Qc3 and Qf2 ... of which only Qg1 decrements DTC as well as DTM. So 38.Qc3/Qf2 walks into a 50m draw-claim.
Position Q-NN2 with 38.Qg1 can lead to
Position Q-NN3 = 8/8/8/2n5/2K5/8/3Q4/nk6 w: dtc = 2, dtm = 8 (Black has - net - conceded two more in DTM terms)
Now White has 49.Qe2 optimising DTM but not DTC, while 49.Qd1+/Qe1+ optimise DTC.

So, moving to positions which merely optimise DTM, even given a 50m-rule, White will do 49.Qe2 and miss the win.
I don't think mb thought he was providing a guarantee of avoiding a 50m draw-claim in creating the DTM50 EGT: only the DTZ50 EGT does that.

g

[syzygy]

Well, if I have got the definition of mb's DTM50 metric wrong, I hope he will step in and correct me.

Yes, I agree that if a position is decisive under a 50-move rule, there is a line that minimaxes DTM.

Yes, and now it is important to realize that lines that minimax DTM in "chess without any k-move rule" are not lines that minimax DTM in "chess with 50-move rule", at least not general. This is what I think you are ignoring.

You only need the fact that 'decisive' ==> finite number of moves to win.
You don't actually need to use the fact that you have a finite number of choices of move at each turn, as in Chess.

With an infinite number of move choices there might be arbitrarily long winning lines (each finite) and it gets a bit more complicated. What is sufficient is that there is a maximum number of moves in which the game ends (and is won). Then this maximum can be minimized.

For an example where the DTM50 EGT (I think) offers an opportunity to go wrong and walk into a 50-move draw-claim, take the endgame KNNKQ.

You are confusing DTM and DTM50. Winning lines in "chess without 50-move rule" are not winning lines in "chess with 50-move rule". DTM is about the former, DTM50 about the latter.

I don't think mb thought he was providing a guarantee of avoiding a 50m draw-claim in creating the DTM50 EGT: only the DTZ50 EGT does that.

Since mb modified Nalimov's generator, he was most likely thinking of this from a generating point of view. Most likely he seeded his table with values from DTM50 subtables, then did 50 iterations. This gives the correct DTM50 values, but only for move-counter = 0.

[guyhaw]

I'm quite familiar with the fact that lines that minimax DTM without any k-move rule are not necessarily lines that minimax DTM in the context of a k-move rule. For a start, you can't move to a position that is a draw in DTM50 terms. I've published plenty of examples, found by John Tamplin, where the DTZ50-optimal move(s) do not overlap the DTC/M/Z-optimal move(s).

I also agree that MB probably 'seeded' his DTM50 EGT with the values from DTM50 EGTs for successor endgames.

'Arbitrary long winning lines' are not the problem: if you have some depth to winning goal in hand, you need not consider lines longer than some finite multiple [max possible number of phases] of this (in chess). So the finiteness of move-choice is not needed for the argument.

I'm not confusing DTM with DTM50 in the KNNKQ example. What I might have said explicitly to make things clear is that, since the 50-move rule does not affect KQKN, the seeded 'depth to mate' values will be the same, and the more immediate 'depth to mate' values in KNNKQ will be the same - and therefore the example of the DTZ-minimaxing and DTM-minimaxing KNNKQ lines diverging is the same under DTM50 as under DTM.

Maybe there's a better example in KNNKP (probably one already published elsewhere), but I believe the KNNKQ one is ok. Other examples of a SV+M50-/SR+ strategy-pair walking into a 50m-draw-claim are welcome.

As a 'DTR footnote' to the KNNKQ example, note that Black - at the last moment - is at ...
Position Q-NN3, 8/8/8/2n5/2K5/8/3Q4/nk6 w: DTC = 2, DTM = 8, DTR = 5, DTZR = 3 with only 2 moves left.
In fact DTR = 5, DTZR = 5 may have been on offer with DTC = 4, two moves before.
However, the strategy SV+ZoR- is guarding DTZ before minimaxing DTR and DTZR are considered, so the DTR = 5 goal is never pursued.

It is typical for the siren of a sharper-goal to beckon, especially when close to 'the rocks'. A guard like the SZo filter is necessary.

g

[syzygy]

I'm quite familiar with the fact that lines that minimax DTM without any k-move rule are not necessarily lines that minimax DTM in the context of a k-move rule.

Do you agree that DTM50 should refer to DTM in the context of the 50-move rule?

If yes, then how can a DTM50-line ever walk into a 50-move draw? By definition it cannot.

Do you agree that positions that are won according to DTM50 are won according to DTZ50, and vice versa?

'Arbitrary long winning lines' are not the problem: if you have some depth to winning goal in hand, you need not consider lines longer than some finite multiple [max possible number of phases] of this (in chess). So the finiteness of move-choice is not needed for the argument.

In a game in which players have an infinite number of moves choices, one player may have a winning strategy that has no upper bound on the number of moves. The winning player can force a win in a finite number of moves which depends on the opponent's moves, but this finite number may be unbounded. I.e. for any number N, the opponent may have a strategy that delays his loss for N moves.

In chess these complications don't exist. I guess I should have restricted X to "finite games", i.e. games with a finite number of game states.

[syzygy]

To go back to something you wrote earlier:

- the DTZ50-minimaxing lines are not necessarily followed, which means that
- some DTM50-minimaxing lines might be subject to a 50-move draw claim.

This is incorrect. The fact that DTZ50-lines are not necessarily followed does not mean that DTM50-minimaxing lines may be subject to a 50-move draw claim. This should be self-evident if you agree that "if a position is decisive under a 50-move rule, there is a line that minimaxes DTM".

If is not, please reread what I wrote about "chess with the 50-move rule" having game states given by tuples (position, side-to-move, move-counter). Within this space of game states, metrics like DTZ and DTM can be defined in a natural way. Now, a position that is won has DTZ-minimaxing lines and DTM-minimaxing lines. In general, these lines will be different. However, a DTM-minimaxing line will by its definition not walk into a 50-move draw claim. You are minimaxing over lines that are winning in "chess with the 50-move rule", and those lines simply do not walk into a 50-move draw claim. If they would, they would not be winning lines.

Obviously, if in a particular position the winning side needs 50 moves to reach a winning zeroing move against a particular strategy of the losing side (i.e. dtz50 = 50), then the winning DTM50-line will also take exactly 50 moves to reach a winning zeroing move against that particular strategy of the losing side.

Or put in another way, the winning lines in a game X are fully independent of the particular metric that is used. It is the game that defines the winning lines, not the metric used for measuring them. Let X = game of chess without any k-move rule and let X50 = game of chess with 50-move rule. Winning lines in X can be measured by either DTZ and DTM. Building a table based on DTZ results in a DTZ-table. Building a table based on DTM results in a DTM-table. In X50, building a table based on DTZ results in a table that can best be indicated by DTZ50. In X50, building a table based on DTM results in a table that can best be indicated by DTM50. Tables for X50 have 50x or 100x as many positions as tables for X, because the game state is 50x or 100x as large. However, in the particular case of DTZ, the full DTZ50-table can be trivially reconstructed from the move-counter = 0 slice.

[kronsteen]

I’m with every syz’s points of view and explanations about DTM50.

The main points about DTM50 are :

- like DTC50, or “full DTR” as I name it, DTM50 doesn’t refer at (position, side to move) but at (position, side to move, movecount). Extracting DTM50 only for (position, side to move, movecount=0) in an effort to look like already developed metrics is a broken concept, because it won’t be capable of showing lines of play.

- If you want to extract optimal lines of play, you need the whole table for every position and every movecount. For example, if you are playing from the winning side and want to know from a given position with movecount=x which is the optimal move in DTM50 terms, you have to find the move(s) which decrease DTM50 by 1 in the resulting position but with movecount=x+1 if the played move is not a zeroing one, and with movecount=0 if it is. DTM50 for a given position with movecount=x has in general no link with DTM50 for the same position with movecount=0 (the only clue is that the latter is <= to the former). Trying to dig out lines of play using only DTM50 tables at movecount=0 is hopeless, and will inevitably lead to numerous examples (g already pointed some above) where it fails in practice, either by conceding depth or an unnecessary 50-move rule draw.

- For every onboard position (and side to move), DTM50 can be presented as a non-strictly growing series of numbers indexed by movecount (which takes values between 0 and 99). In many cases, above some movecount the series will be +inf as the position cannot be won anymore, i.e. it is impossible to both play (or force) a zeroing move and preserve the win within the remaining number of non-zeroing moves allowed. In general, this series will look like (I cut down to 10 values, the real series do in fact contain 100 values) 30 30 30 30 35 35 40 50 inf inf, or 30 30 30 40 40 40 inf inf inf inf, or 25 25 25 inf inf inf inf inf inf inf… . One can easily understand that such series are heavily compressible, and that a full DTM50 table will therefore weigh far less than 100x DTM Nalimov tables (my own guess is in the 5-10x range). Taking into account the fact that adding 1 man results in raising EGT sizes by a factor of more than 100 (160 between 5 and 6 men EGTs), the 5-10x increase of size needed to step from DTM to DTM50 results only in a loss of 0.3-0.4 men. This means that DTM50 tables will be easily achievable for 5-men, and maybe for some 6-men samples. Such tables are sure to shed new light on endings like kqpkq or knnkp, just as DTR tables would.

[guyhaw]

We can leave the 'finite/infinite move-choice' thing to one side for the moment.

As this dialogue is continuing longer than I expected, I'm increasingly conscious of the fact that it might be invalidated by wrong assumptions by either of us. A few words from Marc might help. I think I still have his 'gtbgen' so a few experiments might help.

I believe that:
- the set of positions marked as wins in the DTZ50 and DTM50 EGTs are the same,
- DTM50 recognises the 50-move rule only in that respect,
- the depths quoted are minimaxed depths to mate assuming 50 moves are available,
- Marc's EGTs do not explicitly include the 'move counter' in the game-states (positions) represented.

This does not however totally define how the DTM50 EGT is generated: there is I think a way in which the DTM50 EGT can be generated to limit number of steps in current phase to 50, and if MB has done this, I think the DTM50 EGT fully recognises the 50-move rule. If, instead of finding DTM50 mates in 0, 1, 2, .... in successive cycles, the retro process retros all available subgame wins/losses for 100 cycles, then no DTM50 mate would be more than 100 plies away from conversion to next phase (or mate in current phase) and all 50m-draw-claims would be avoided. Note that this simulates the move-count in the EGT-generation process, making it unnecessary to store the move-count in the EGT.

This is however a really (RAM)space-expensive and time-expensive way to generate an EGT, and I thought MB had completely dropped that approach. It is done with DTZ EGTs, because all decisive positions found in cycle 'n' have the same DTZ. However, the implications for non-DTZ EGT generation are that different depths are being handled in the same cycle, and one can never be sure until the end that the best depth has been found, so all positions have to be reappraised again if the last cycle changed anything. If I can get gtbgen working again, maybe there's a way to find out if this is the case.

There seems to be an insistence that everything should be 'on the peg' in one EGT. If the EGT only holds 'N' (usually 1, but 2 in the case of DTR/DTZR) pieces of information per position, it is limited in the direct 'pick up' advice it can offer. I would rather have the DTZ50 EGT as well as the DTM50 EGT (2x the DTM50 EGT spacewise instead of the 50x larger DTM50 with move-count), so that I could exercise the strategy SV+Z50oM50-, minimising DTM50 in the context of safeguarding DTZ50.

The set of winning lines from position X depends on the modelled definition of winning, which in the case of the DTC/M/Z metrics does not recognise a k-move rule. If a k-move rule is recognised, the set of winning positions and also the set of winning lines is affected by 'k'.

I wish you luck in generating EGTs with movecounts in if you wish: it's not something I'm going to spend time on.

g

[kronsteen]

- the set of positions marked as wins in the DTZ50 and DTM50 EGTs are the same,

Absolutely right. One can even add that, for a given position, the DTM50 series indexed by movecount (as described above) has exactly 101-2*DTZ50 or 100-2*DTZ50 (depending on ply parity) finite values.

- DTM50 recognises the 50-move rule only in that respect,

Yes, but of course DTM50 isn’t equal to DTM in general (it is in fact always greater or equal to DTM), even on winnable positions under 50-move rule, as escaping 50-move rule draw claims is an added constraint which can sometimes result in longer winning paths.

- the depths quoted are minimaxed depths to mate assuming 50 moves are available,

This is DTM50 assuming movecount=0. if movecount is not 0, DTM50 is greater (and is +inf if movecount exceeds 50-DTZ50), but has no link with DTM50(movecount=0) in general.

- Marc's EGTs do not explicitly include the 'move counter' in the game-states (positions) represented.

This does not however totally define how the DTM50 EGT is generated: there is I think a way in which the DTM50 EGT can be generated to limit number of steps in current phase to 50, and if MB has done this, I think the DTM50 EGT fully recognises the 50-move rule. If, instead of finding DTM50 mates in 0, 1, 2, .... in successive cycles, the retro process retros all available subgame wins/losses for 100 cycles, then no DTM50 mate would be more than 100 plies away from conversion to next phase (or mate in current phase) and all 50m-draw-claims would be avoided. Note that this simulates the move-count in the EGT-generation process, making it unnecessary to store the move-count in the EGT.

To compute DTM50, I think it is more or less necessary to run in some way a recursive algorithm similar to the standard DTM algorithm (finding successively positions with DTM = 0, 1, 2 etc…) but running on (position, stm, movecount) triplets and not only (position, stm) states. If the work is organized in pawn slices (i.e computing only positions with same material and same pawn positions at the same time), this recursive algorithm can be stopped at iteration=100. But note that this algorithm can’t be a DTZ50 algorithm, because positions reached after zeroing moves can have different DTM50 values (at movecount=0 this time). In other words, a position with DTZ50=20 resulting (by following DTZ50 line of play) in positions with at most DTM50 = 30 can have DTM50 of less than 20+30 if for instance it can be forced within 25 moves a zeroing move with a resulting position with at most DTM50=20 (in which case DTM50 will be 25+20=45). The trouble is that in this example the 50-move DTM50 line is usable for as many movecounts as possible, i.e 50-DTZ50 = 50-20 = 30 (if movecount is 31 or greater, position can be forced to 50-move rule draw), but the 45-move DTM50 line is usable only for movecount being at most 50-25 = 25. I might be mistaken, but I think that it is the reason why DTM50 cannot be simply derived from a DTZ50 algorithm using DTM50 info about subendings. This problem is specific to k-move rule introduction, and isn’t met for instance when building DTM tables using a DTC or DTZ algorithm using DTM info of subendings as entry data. I don’t have MB’s code, but if it is presented as capable of generating DTM50 as well as DTM/DTC/DTZ/DTZ50 with similar algorithms, it must be made sure that it doesn’t run into this problem.

[guyhaw]

The issue is that there are two ways of retro'ing-back decisive positions:

a) the old way - retro-back any and all decisive positions which are to hand, regardless of their depth
b) the new way, 'post Wu': retro-back wins/losses in 'n' to define losses/wins in 'n+1' (plies).

The old way will I think identify all DTM50 wins (using just 100 retro-steps) in such a way that no minimaxing path in the EGT will be more than 100 plies long.

The 'new way' will use more than 100 cycles if unconstrained (and can create paths longer than 100 plies). If it is constrained to 100 plies, it will only identify wins with DTC =< 50, not DTM50 wins.

Unfortunately, mb's gtbgen has to have the metric defined at compile time and I'm unable to create DTM50 EGTs.
mb's gtbgen will run either a bit-based algorithm or the old byte-based algorithm, which suggests that he might have done DTM50 EGTs 'the old way'

Guy

[kronsteen]

Your « old way » is in fact building WDL50 tables (which is already a project on 7-men !). These tables give you info about if a position is winnable under 50-move rule, assuming current movecount=0. It is by definition the win/draw/loss information which can be extracted DTZ50/DTC50/DTM50 tables (and which is the same for each, of course). The most sensible way to compute WDL50 tables is to divide work into pawn slices (i.e positions with same material and same pawn positions) and run a recursive algorithm for 100 iterations exactly (although algorithm can be stopped if no progress is made at an earlier step). Computing a pawn slice needs to have first WDL50 info for all subendings (i.e endings resulting from a conversion or a pawn push). When running the algorithm, when you find a new winning position, you can store only its index, which will give you a WDL50 table in final, or store the current iteration number as well, which will give you a DTZ50 table. But unfortunately this method can’t be used to build DTC50 or DTM50 tables.

Your “new way” consists of building a metric upon WDL50, which provides not only WDL assessment of a position, but also how far a won position is from a given goal : checkmating move (DTM50), conversion move resulting in a winnable position under 50 move rule (DTC50), or zeroing move resulting in a winnable position under 50 move rule (DTZ50). As I said above, if you want DTZ50, it is immediately achievable by storing the iteration number in an “old way” process : this is what you call “new way”, and it basically runs on the same algorithm. But DTM50 and DTC50 require a different algorithm, even if you’re only interested in DTM50/DTC50 info at movecount=0 (but such a TB having the big drawback of being unable to show winning lines, as I explained above). When you speak about “old way DTM50”, you in fact speak about WDL50, which is achievable with a different and simpler algorithm then "new way DTM50".

To me, the issue is more that some metrics are computable without indexing movecount : WDL, WDL50, DTZ, DTZ50, DTC, DTM, when others need this indexing (DTC50, DTM50, and maybe also DTR as I currently believe it), unless some clever theorist finds an elegant way to do otherwise (but I seriously doubt it is only possible).

There are two different and completing ways of thinking about raising new EGT knowledge : one way is to strive for as many men as possible, which is best achieved by using most compact metrics, which are WDL(50) first, then DTZ(50). The other way is to develop new metrics and new concepts, such as DTM50 or DTR, and to launch a try on these for the simplest endings first, regarding only later how space storage and computing time limitations will result in number-of-men limitations. Due to historical considerations, the main effort has been made on DTM with Nalimov, which is somewhat in-between, using a “middle-ranked” metric in compacity terms.

[guyhaw]

kronsteen's last contribution is nearly there, but not quite I think ...

The 'old way', used by Nalimov et al, was to promulgate (backwards) any available depth 'D' to create a definite win in 'D+1' or a possible loss in 'D' [moves]. This has a major disadvantage, but one advantage which I now appreciate and which Marc B probably used in his algorithm gtbgen [but I can't tell].
The disadvantage is that, in the same cycle of surveying the EGT, you could be back-propagating a depth of 5 and a depth of 7.
This meant that you had to hold a depth per position, one byte (or maybe two) rather than one byte saying 'decisive position in depth D'.
This took way loads more RAM and held up the creation of 6-man EGTs.

Then Ren Wu, supervised by Don Beal in London, discovered that one could use cycle 'D' to find only those positions won or lost in D moves.
This could be done for DTC and DTM (as well as for DTZ) by 'holding' 'boundary wins' in D-1 until cycle D came round.
Great - only one bit rather than one/two bytes needed per position.
The disadvantage is that a win 100 plies from conversion may only get found on cycle 110 rather than cycle 100.

The advantage of the old method was that those position 'found' on pass 'D' were exactly D plies away from end-of-phase.
So I am as convinced as I can be (without confirmation from mb) that this is how gtbgen did DTC50 and DTM50 EGTs.
It DOES set up the lattice so that no minimaxed path derived from a DTC50 or DTM50 EGT can run into a 50-move draw claim.
And it does so without having to store a move-count in the index of each 'position' in the EGT.

g

[mbourzut]

In gtbgen I included "DTC(50)" because for pawnless endgames DTC=DTZ, and the adaptation of the Nalimov algorithm for DTZ is much slower than for DTC. So I created DTZ(50) by creating pawnless endgames with DTC(50), and then the pawnful endgames with DTZ(50). I don't think I included DTM(50) as a possibility, at least not intentionally. The goal here was simply to create tablebases that obey the 50-move rule, and allow the user to always make progress in a winning position. I think some values may be off by one ply because of the way the 50-move rule can be claimed.

In my work with Yakov Konoval we started with pawnless endgames, so also DTC=DTZ. The algorithm uses king slices, and is very memory efficient, less than 3GB for the worst case, so we could run everything on a 32-bit platform. The monster kqnkrbn 517 endgame took about 4 weeks on a 3.8GHz machine, most normal endings are a lot faster.

Originally we had planned to use pawn slices and DTZ for pawnfull endgames, but then realized that a fairly trivial change in the pawnless DTC code would allow us to run pawnful endings with DTC as well. So that is what we have been doing so far, although DTZ is clearly more efficient but more programming work.

-Marc