CCRL Discussion Board

Thanks, mb: always good to be able to get back to primary sources.

I thought DTMk was part of the potential of your gtbgen: we included mention of DTMk in the paper, but I was never interested in having a DTM50 version of gtbgen myself, so don’t know what was actually done in DTM50 terms, or how the DTM50 variant worked.

’50 (winner’s) move’ phases can be 99 plies (winner plays plies 1 and 99), 100 plies (surely more usual) or 101 plies (loser plays ply 1 and, smiling, claims a draw before having to play a forced P-push and/or capture). So there’s a potential intrinsic one-out issue because depth is measured in moves. Nalimov’s code does not assume that winner converts as did Wirth’s code, so you don’t have that bug.

Perhaps the subject of how you might have done (or did) DTMk EGTs is academic, but – given that sz has insisted that DTM50 EGTs should not walk users into 50-move-draw-claims – I now believe that it is possible to produce such DTM50 EGTs.

However, they would have to be created on the basis of back-propagating all decisive positions as soon as possible, and only back-propagating 100 cycles. This implies not using just a bit-based data-structure, and not ‘holding’ wins of a certain depth until the appropriate cycle in the back-propagation was reached. Thus positions of different depths would be being back-propagated in the same cycle, requiring a byte-based data structure for actual depths.


On another subject, your work with Yakov is of interest to many of us, and we would welcome a publication on how this has been done to date – especially re your indexing scheme which seems to incorporate new thinking and to be based on JdK’s FEG rather than Nalimov’s scheme.

g

guyhaw wrote:Perhaps the subject of how you might have done (or did) DTMk EGTs is academic, but – given that sz has insisted that DTM50 EGTs should not walk users into 50-move-draw-claims – I now believe that it is possible to produce such DTM50 EGTs.

Wrong. At least, Nalimov-type DTM50 tables will run into problems. (The 50x extended ones are fine.)

I've (tried to) explain this many times now in this thread, and the reason is essentially the same as why Nalimov-type DTR does not work. In short, a DTM50-winning line starting out at a position with dtz50 = 50 and say dtm50 = n, has good chances to walk after k moves into a position with dtm50 < n-k (according to the Nalimov-type DTM50-table, which only has information for move-counter = 0) and dtz50 > 50-k. This is not immediately obvious, so please spend some time to think it through...

Btw, I was wrong in my first post of this thread when I suggested that DTM50 would work fine for tables without any successor tables/slices. DTM50 is only guaranteed to work for a table if neither the table itself nor its children are affected by the 50-move rule.

(By "Nalimov-type" I simply mean tables based on (position, side-to-move) as game states instead of (position, side-to-move, move-counter). The tables we're used to.)

To get back to where this started, ernest at the beginning of this thread mentioned:

ernest wrote: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).

The message is that these tables, although they correctly give the distance to (legal) mate provided that move-counter = 0, fail to give the full winning line.

For me this is a reason why DTM50 is not of much practical interest, and a reason to be even more happy with DTZ50. Not only is DTZ50 considerably smaller and easier to compute than DTM50, the resulting table also has the advantage of not being broken. (However, just for fun it might be interesting to build the 'extended' DTM50-tables for <= 5 pieces.)

I believe there is, in fact, a possibility (even if not thrilling) to build a DTM50 table in Nalimov format which also meets the requirement of giving an finite upper bound of the distance to mate from any given position, against any possible strategy from the losing side, considering only lines of play which never cross the 50-move rule limit, and also capable of showing these lines of play. It consists only of a different presentation of DTZ50 tables : first, have all DTZ50 tables available. Then, identify maxDTZ50 of each pawn slice of every ending. Then, consider the tree from a given position of all subendings (in pawn slices), consider every branch of the tree and find m=max(sum(DTZ50 of successive subendings in the branch)). Then, construct the m+DTZ50(current position) tablebase. This table is barely larger than DTZ50 because it requires only storage of m of every pawn slice, and pawn slices are far less numerous than complete positions. It gives you a metric that is sure to get you to mate within the given distance, and minimizing this metric for the winning side gives lines of play that are sure to avoid 50-move rule draws, whatever the losing side’s strategy. Its drawback, as one might easily imagine, is that it may sometimes give very large numbers who far exceed what might be achievable with more optimal play. But I don’t see for now how it could be possible to do better within the requirements quoted before.

I think we are now in an analogous position with DTM50 EGTs to where we are with (DT, DTZR) EGTs. Both positions have a certain irony.

szyzygy correctly raised an issue as to whether mb's DTM50 EGTs not only had the same wins and draws as the DTZ50 EGT but also avoided leading the winner into a 50-move draw-claim. There was some discussion as to whether mb's 'DTM50' label was intended to imply that the DTM50 EGT had both properties. I thought 'probably not - so what' and szyzygy thinks it should not be called a DTM50 EGT if not.

After some pondering, I realised that I did not know for certain how mb had generated the DTM50 EGTs, and showed with an example from KNNKQ that a position possibly labelled DT50 = 50 could lead to a 50m draw-claim. I then realised how that situation could be avoided, and that mb might in fact have generated DTM50 EGTs in a different way - one which, over the intervening four years, I have come to assume he had stopped using.

Now I am satisfied that there is a way of generating DTC50 and DTM50 EGTs, correctly capturing just those wins which are DTx50 wins _and_ leading the winner safely down to the win without encountering a 50m draw-claim. However, sz and kr are not yet satisfied in the same way.

The algorithm must:
a) hold the DTx50 depth of each position in one or two bytes, rather than just represent it by a bit - this was the 'old way' of doing things
b) back-propagate from any and all decisive positions already recognised - again, this was the 'old way' of doing things
............that is to say, _not_ harvesting wins in 'd' until cycle 'd'
c) only back-propagate 2*k cycles for a DTxk EGT

Think about traversing such an EGT, and let's imagine depth is measured in plies. Each step reduces the depth by 1 ply, and there can be no more than 100 steps (for a 50-move rule) before a phase-change as we have limited the number of cycles to 100. It is as if the 'move count' were built into the back-propagation: positions given a depth at cycle 'd' take no more than d steps to phase-change, even though they might have different DTMs.

The problem with the KNNKQ position was that it was given its new, sharper, DTM in a cycle after the 100th, and required more than 50 moves in the current phase to achieve it.

So I believe this way of generating a DTxk EGT does exactly what sz wanted - it creates a DTxk EGT with both desired properties.

That is 'case rests' for me, I think. Thanks again to sz for asking the questions.
g

kronsteen wrote:Its drawback, as one might easily imagine, is that it may sometimes give very large numbers who far exceed what might be achievable with more optimal play. But I don’t see for now how it could be possible to do better within the requirements quoted before.

What you are describing is a table that gives an upperbound on the distance to mate. The path to mate chosen by the winning side will still be a DTZ50-path.

I agree it would work and that it has the benefit of making it possible to announce a win in (at most) N, but it doesn't give the "shortest legal mate" which is what I would consider a DTM50-table should give. And this is also what ernest is looking for (also see this thread).

Re viewtopic.php?f=6&t=2590, I don't think I 'got to the pitch of the ball' with that question.

We eventually decided, I'm sure rightly, that the SZ50oM- strategy (while being the closest strategy given the EGTs I would consider holding) is not the same as the SM50- strategy, though a counterexample is difficult to find.

If a DTM50 EGT 'EM50' is properly constructed to meet both the draw-claim-avoidance and depth-minimaxing goals (for which we now have an algorithm), then SM50- is the correct strategy to use on it.

g

guyhaw wrote:If a DTM50 EGT 'EM50' is properly constructed to meet both the draw-claim-avoidance and depth-minimaxing goals (for which we now have an algorithm), then SM50- is the correct strategy to use on it.

With a Nalimov-type table that stores for each position and side-to-move a single value, with SM50- choosing the move that leads to the smallest such value?

Won't work...

guyhaw wrote:szyzygy correctly raised an issue as to whether mb's DTM50 EGTs not only had the same wins and draws as the DTZ50 EGT but also avoided leading the winner into a 50-move draw-claim.

I never claimed to be discussing mb's DTM50 tablebases (which actually seem not to exist). I was reacting to ernest, pointing out that DTM50 for "shortest legal mate" is broken insofar as Nalimov-type table are concerned. You then gave your own interpretation of DTM50, which however is rather distinct from the quite natural interpretation that ernest and others give to "DTM50".

The problem with DTM50 (the natural interpretation) is that, although there is a natural way to generate a Nalimov-type table that stores dtm50-values for move-counter=0, this table simply fails to give full winning lines. Reasons are as for DTR, I'm not sure why you seem to think you have somehow solved it for DTM50..

I'm having second-thoughts ... again.

While I have described a construction that, provided the two sides play SM50-/SM50+, gives a set of paths through the EGT that decrement DTM by 1 ply each time and take no longer than 100 plies in the phase, it's not obvious that the defender cannot 'bail out' and just play SZ50+.

So I think I'm back to the drawing board. I don't think the reasons why my attempt at EM50 fails are the same as for ER50 (where 'hidden paths' were the problem) but if you see an analogy, fair enough.

g

guyhaw wrote:While I have described a construction that, provided the two sides play SM50-/SM50+, gives a set of paths through the EGT that decrement DTM by 1 ply each time and take no longer than 100 plies in the phase, it's not obvious that the defender cannot 'bail out' and just play SZ50+.

I would say SM50- minimizes distance to mate against any play. (Indeed, if you define SM50- as minimizing distance to mate against SM50+, then how do you define SM50+ without running in cycles?) So the defender cannot bail out by playing SZ50+.

The problem is different. Do you realize that:
1. The set of moves selected by SM50-, i.e. the set of moves that maximize distance to (legal) mate, is dependent on the value of the move-counter?
2. Nalimov-type DTM50 only stores information for move-counter = 0.
And therefore:
3. Nalimov-type DTM50 does not suffice to execute SM50-?

Re 1.: suppose the current position has 2 winning lines, one of 50+10 moves, one of 40+30 moves.
If you have 50 moves available in the current phase, the 50+10 line is available as well as the 40+30 line. SM50- selects the 50+10 line.
If you have 49 moves available in the current phase, only the 40+30 line is available. SM50- selects the 40+30 line.

I keep mentioning that DTM50 only stores information for move-counter = 0 (point 2 above), but this point somehow isn't getting through. Even if you still don't agree, do you at least see what I mean by that? To execute SM50- when move-counter = 1, you need DTM50 information for move-counter = 1. This information is different than the information for move-counter = 0 (point 1).

What in my view is the most natural way to see all of this I've tried to explain in the last 5 paragraphs of this post.

So I think I'm back to the drawing board. I don't think the reasons why my attempt at EM50 fails are the same as for ER50 (where 'hidden paths' were the problem) but if you see an analogy, fair enough.

The same hidden paths / overwriting of values established in earlier iterations occurs when generating DTM50.

I thought I'd proved that my algorithm for the DTM50 EGT was correct, but the flaw comes right at the end:

1) any 'win/loss in the DTZ50 metric' will be placed, initially in cycle 'dz50', in my 'DTM50' lattice
2) 'DTZ50 draws' will not be placed in the lattice - ever
3) the defender can step down one or more layers in the lattice, losing one or more plies of depth, and
4) the attacker can always step down one ply in depth

So, all looks good - except that when a position is moved to a greater depth in the lattice in pursuit of a better 'DTM' - its dependant positions might be pushed out of the 100 cycles. Those dependant positions really 'wish' the position had been left at the lower level, pursuing a less ambitious depth to mate.

If one could hold a list of facts along the lines:
- the best DTM achievable is dm1 but takes dz1 plies in this phase
- the next bet DTM achievable is dm2 and takes dz2 < dz1 plies in this phase etc.

then all would be well, without a move-count, but that's a new kind of data-structure no-one has thought about yet.

Bottom line: we cannot explicitly represent constrained navigation in a 2D space with a 1D data structure.

Ok: thanks again to sz whose radar picked up on this.
g

guyhaw wrote:If one could hold a list of facts along the lines:
- the best DTM achievable is dm1 but takes dz1 plies in this phase
- the next bet DTM achievable is dm2 and takes dz2 < dz1 plies in this phase etc.

then all would be well, without a move-count, but that's a new kind of data-structure no-one has thought about yet.

We did think about that. What you describe is a disguised form of "including the move-counter in the index". In several posts kronsteen has mentioned that the array (move-counter = x, dtm(x)) for 0 <= x < 50/100 should have a quite efficient representation using much fewer than 50 or 100 separate numbers. See for example this post, last paragraph. See also here.

[ Maybe I lost concentration once or twice when the 'move counter' idea was being discussed. ]

Small point: in reality, we are interested in 'moves needing to be available' rather than move-counter.

If I stopped earlier DTM values being overwritten in the 'back-propagate immediately' attempt at a DTM50 EGT, I would actually get the best DTM resulting from the SZ50-/SZ50+ strategy, which certainly would not always be the best DTM50 available.

g

I wonder if Marc B has the DTC-stats files for KQBNKQB White wins and Black losses.

I would like to know if there are exactly 2 wtm wins in (dtc =) 330.

g