Guy's reply recalls the old joke about the baloonist and the mathematician. (*)
Okay, that's a bit unfair because he reminds us that
a) there is more than one sense of "shortest" path
b) every shortest path assumes a pair of minimaxing competitors (helpmate puzzles excepted)
c) shortness assumes a metric, and while it is typical to conceive of competitors acting to minimize/maximize the same metric, this is not necessarily so
d) it is fruitful to formalize player strategies, and there are a basket full of these (details in [1]).
The summary is pretty clear, though pertaining to Guy's item (c) I believe that strategy SZ-/SZ+ is not the same thing as SZ50-/SZ50+. No?
Back to ernest's "how can I combine the multi-metric tablebases to find the shortest legal mate?" question, the answer is, sadly, "not easily". From a given position, when asking for the shortest path that does not violate the 50-move rule, the violating arc can appear anywhere in the path. Endgame tablebases (to DTM, DTC, DTZ50,
et al.) only summarize the total path length. Information about the multitude of possible subpaths is not preserved. Extracting it requires a search.
Here's a simplified example. Suppose we have a position with 4 moves, and when disregarding the 50-move rule they are all won by white . For simplicity, assume also that each of the moves leads to completely forcing lines. I now cook up some numbers.
Code: Select all
Move Value DTM DTZ Arc Lengths
a) draw 120 40 40 + 10 + 60 + 10
b) draw 130 65 65 + 60 + 5
c) win 140 40 40 + 50 + 50
d) win 150 30 30 + 40 + 40 + 40
Arc lengths are the lengths of the path segments of the DTM line between zeroing moves (capture, pawn push, checkmate). Move a) yields the shorted DTM line, but the third arc is 60 moves long and so the game result is a draw. Move b) is also a draw, but because the first arc is 50-move-rule violating, it can be detected and excluded by a DTZ50 tablebase. Move c) is the one we want. It leads to the shortest overall path with each arc less than or equal to 50 moves. (It is rule compliant.) Move d) is also a rule-compliant win, but the total length is longer. But observe a catch. A DTZ minimizing strategy will choose this suboptimal move. It looks good in the here and now, but doesn't know what tomorrow brings.
To sum up, tablebases provide local decision information, but what ernest is seeking is a global graph-theoretic optimization.
I don't grasp Guy's idea of Distance to Rule tables well enough to know if it provides the answer. Short of that, the only solution I have is to search the DTM+DTZ tablebases in order to construct a graph, then apply a classic path minimization algorithm [2] under imposition of a maximum arc length constraint. The search can apply pruning [3], but still I bet it will be pretty slow for practical usage.
john
(*) A man takes a balloon ride at a local country fair. A fierce wind suddenly kicks up, causing the balloon to violently leave the fair and carry its occupant out into the countryside. The man has no idea where he is, so he goes down to five meters above ground and asks a passing wanderer: "Excuse me, sir, can you tell me where I am?"
Eyeing the man in the balloon, the passer-by says: "You are in a downed red balloon, five meters above ground."
The balloon's unhappy resident replied, "You must be mathematician."
How could you possible know that?" asked the passer-by.
"Because your answer is technically correct but absolutely useless, and the fact is I am still lost".
-----
[1] M. Boursutschky, J. Tamplin, G. Hawworth, Chess engames: 6-man data and strategy, Journal of Theoretical Computer Science, vol. 349, 2005, pp. 140-157.
[2]
http://en.wikipedia.org/wiki/Dijkstra's_algorithm
[3]
http://en.wikipedia.org/wiki/A-star_algorithm
Strategy-pair SZR-R-Z-C-M-/SZR+R+Z+C+M+ has White minimising (Black maximising) by metrics DTZR, DTR, DTZ, DTC and DTM in turn
