Where is everyone?

[notnale]

This forum hasn't been very active lately.

[h.g.muller]

I was busy making a new XBoard release. But that is out now.

[koistinen]

I am trying to get going writing a baseline generator for DTZ. (It need not be efficient in any way, as long as it gives the correct result in reasonable time for small tablebases, i.e. 4-man in 24h is enough.) Correct result is the priority.
I have also looked at order of computation.
When computing DTZ it is reasonable to do the computation for two half-move depths at a time, or with Muller's leapfrog, four.
If you do so, there are two ways of doing it:
: btm, dtz=0,1, wtm, dtz=1,2, ..., btm, dtz=100
or
: btm, dtz=0, wtm, dtz=1, btm, dtz=1,2, ..., btm, dtz=99,100, wtm, dtz=100.
I am not sure it makes any big difference which you pick.

[notnale]

Well I'm still learning the basics of C++

I just finished making an Othello playing console program

[h.g.muller]

Let me think aloud about this: When all won(<N ply) positions have been identified, and used to verify all lost(N+1 ply) positions (i.e. this cycle is complete), leap-frog can immediately start working on the currently cached slice for identifying a partial set of won(N+1 ply) positions (accessible with the currently treated white moves from the lost(N ply)). From those it could get to the lost(N+2 ply) positions. But it could not conclusively identify any won(N+2) positions yet, as some of the candidates for this (reachable from a just identified lost(N+1 ply) position) might in fact be won(N+1 ply) positions through the other white moves, not treated in this pass.

So it seems that leapfrog degenerates into no-communicating parallel lines, (N-1->N+1; N->N+2), (N->N+2; N+1->N+3), ..., the numbers giving the dtz in ply of lost btm positions. The second cycle of a leap-frog pass would thus not built on the lost positions just generated by its first cycle. Only if one of the lines has globally died out, it can switch to more aggressively plowing ahead.

My feeling so far was that one of the lines (where black does the conversion) would be sparsely populated and die out quickly. But I am not completely confident on this: DTZ are strange beasts. As black avoids conversion wherever he can, it is like white is playing with 'iron pieces'. So in KQBNK the main majority of the lines might consist of undefended contact checks with the Queen driving the bare King to the edge, where it is finally forced to capture that Queen. This effect only can occur in the less interesting end-games where you have an overwhelming majority. In the interesting end-gamesloss of a white piece is likely to salvage the draw for black, and black will hardly ever be able to afford postponing capturing a hanging piece without losing the possibility to capture it at all. An black can hardly ever be forced to initiate a losing trade, as it would in a DTM-based strategy, because in DTZ black will always preferred to be checkmated on the next move (dtz=1) over eliminating this threat by a losing capture a white piece.

In fact this is a highly unnatural behavior of DTZ. Wouldn't it be more logical to award checkmates within the current end-game with a dtz that is better for black than immediate conversion? E.g. assign the position the conversion move is played DTZ=3 ply (or 2, as a mate-in-1 position actually has dtz=0, as it is equivalent to a conversion and can be played as 50th non-reversible move without falling for the draw axe.)? I guess you might get in trouble with end-games that exceed the 50-move limit, but in others it would lead to much more sensible play.

[notnale]

If you actually want 'sensible' play, just use a combination of DTM and DTZ50

DTM for cases where mate can be forced in less then 50 moves, and DTZ50 when it takes longer then 50 moves.

[koistinen]

So it seems that leapfrog degenerates into no-communicating parallel lines, (N-1->N+1; N->N+2), (N->N+2; N+1->N+3), ..., the numbers giving the dtz in ply of lost btm positions. The second cycle of a leap-frog pass would thus not built on the lost positions just generated by its first cycle. Only if one of the lines has globally died out, it can switch to more aggressively plowing ahead.

I believe it will make the biggest difference when black pawns are included.
While the lines might not be communicating, it can still be profitable to compute them together as that can save much disk i/o + if you don't know in advance which line will die out, computing them in parallel allows you to find out in time.

In fact this is a highly unnatural behavior of DTZ. Wouldn't it be more logical to award checkmates within the current end-game with a dtz that is better for black than immediate conversion? E.g. assign the position the conversion move is played DTZ=3 ply (or 2, as a mate-in-1 position actually has dtz=0, as it is equivalent to a conversion and can be played as 50th non-reversible move without falling for the draw axe.)? I guess you might get in trouble with end-games that exceed the 50-move limit, but in others it would lead to much more sensible play.

Logical != popular. It sure has been more popular to get inaccurate results that fit peoples preconceptions of what is natural. If you want a quicker mate rather than quickest conversion, the suggestion of notnale is good as it will still result in perfect play with regards to win/draw/loss.
ps. I have been reading some ewd.

[h.g.muller]

In general I would want the quickest conversion. But I am starting to realize now that this only applies to conversions that capture an opponent piece or move my own Pawns towards promotion. Not to forcing a conversion by senseless sacrifice of my own material, just for the sake of having a conversion!

I guess it is theoretically possible to have strategies that minimax a one-sided reversible move counter, which only resets when hite captures something or pushes a Pawn, but simply keeps counting when black does either of these things.

Of course you run risks by not paying attention to the move counter, even when you do this for only one side. But in practice, I would be surprised if there were any end-games that take too long to win, and that you have to keep going by forcing the opponent to capture one of your pieces. Because I would say that after losing this piece, it would in general be even more difficult to win, so that phase would last even longer (and thus certainly longer than 50 moves). This might be different for pawn pushes; forcing the opponent to do a Pawn push (or lose the Pawn) can be sensible, as the Pawn advance does not make it more difficult to win per se. So perhaps only black captures should be exempted from resetting the move counter.

[notnale]

A lot of KNNkP mates force a knight sacrifice

It's not necessarily harder to win with fewer peices

[h.g.muller]

Well, in general, it is. For end-games where this strategy could require over 50 moves, you can always use DTZ. I know little about KNNKP, but it hardly seems it could be a problem there: if you sac a knight, the only way I can imagine to win the remaining KNKP is if the black King is trapped in a corner so you can force its own edge Pawn to lock it in, and then check it for mate. So you won't need the sacrifice to zero the move counter; the forced Pawn moves will do it for you.

If it is the only way to win, any sound strategy would do it anyway.

[guyhaw]

Sound thinker and reasonable writer: I learned from him, and no Dining Philosophers have died on my watch. Not a man for the 'small talk' though.
See also http://www.cs.utexas.edu/users/EWD/
g