(for Guy Haworth?) Shortest legal mate

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

(for Guy Haworth?) Shortest legal mate

Postby ernest » Thu Aug 30, 2007 7:05 pm

Hi,

I want to use John Tamplin's DTZ50 EGTB in http://chess.jaet.org/endings,
in order to obtain the shortest legal mate (of course with Black's best defense) for the following KNNKP position:
6k1/8/8/1N3p2/6K1/6N1/8/8 w
6k1/8/8/1N3p2/6K1/6N1/8/8 w
6k1/8/8/1N3p2/6K1/6N1/8/8 w

The DTM EGTB shows that it is a mate in 55, ignoring the 50-move rule.

How do you combine the results of the DTZ50 and DTM EGTBs to find that shortest legal mate?

Note: I found this, but I am not sure it is correct... (curiously, it is also a mate in 55, not more)

[Event "?"]
[Site "?"]
[Date "2007.08.26"]
[Round "?"]
[White "?"]
[Black "?"]
[Result "*"]
[SetUp "1"]
[FEN "6k1/8/8/1N3p2/6K1/6N1/8/8 w - -"]

1. Kf4 Kf7 2. Nd4 Ke7 3. Ke5 f4 4. Ngf5+
Kd7 5. Nf3 Kc6 6. Kd4 Kb5 7. Ne7 Kb6 8. Kd5 Kb5 9. Nc6 Ka6
10. Ncd4 Kb7 11. Nb5 Kb6 12. Nd6 Kc7 13. Nc4 Kd7 14. Nb6+
Kc7 15. Kc5 Kb7 16. Nd5 Kc8 17. Kc6 Kd8 18. Kd6 Kc8
19. Nb6+ Kb7 20. Nd7 Ka6 21. Kc6 Ka5 22. Nde5 Ka4 23. Kc5
Kb3 24. Nc6 Kc3 25. Nb4 Kb3 26. Nd5 Ka3 27. Nc3 Kb2 28. Kb4
Kc2 29. Kc4 Kc1 30. Nb5 Kb2 31. Nbd4 Ka2 32. Kc3 Ka3
33. Nb3 Ka2 34. Nc5 Ka3 35. Kc4 Kb2 36. Nd3+ Kc2 37. Nf2
Kb2 38. Nd2 Ka3 39. Kb5 Kb2 40. Kb4 Kc2 41. Nde4 Kb2
42. Ka4 f3 43. Kb4 Ka2 44. Kc3 Ka3 45. Nc5 Ka2 46. Nd7 Ka3
47. Nb6 Ka2 48. Nc4 Kb1 49. Kd2 Ka2 50. Kc2 Ka1 51. Kb3 Kb1
52. Nd3 Ka1 53. Nd2 f2 54. Nb4 f1=Q 55. Nc2# *
ernest
 
Posts: 63
Joined: Tue Nov 21, 2006 6:31 pm
Location: Paris

Re: (for Guy Haworth?) Shortest legal mate

Postby guyhaw » Sat Feb 09, 2008 12:41 pm

Pachnes,

Apologies - your post escaped my attention, maybe because I have not been visiting this board recently.

When one is looking for an 'optimal line', one has to define the basis used by both White and Black to choose their moves. My perspective on this, introduced with a notation in an ICGA paper some years ago, is that each side successively subsets the available moves using an ordered set of criteria, thus ...

1) Strategy-pair SM-/SM+ is the familiar one where the attacker (White) is minimising Depth to Mate, and Black is maximising DTM

2) Strategy-pair SC-/SC+ uses the (DTC) Depth to Conversion metric rather than DTM

3) Strategy-pair SZ-/SZ+ uses the DTZ50 metric

4) Strategy-pair SZ50-/SM+: White attempts to limbo under the bar of the 50-move-rule, while Black toils along with the familiar DTM metric
Thus Black may fail to reach a draw-claim situation which the SZ50-/SZ50+ strategy-pair might reach
Note that White and Black are using different metrics in their strategies.

5) Strategy-pair SM-C-/SM+C+: White minimises first DTM then DTC, while Black maximises DTM then DTC
This produces a narrower tree of options than SM-/SM+

6) Strategy-pair SM-C-/SC+M+: White minimses first DTM then DTC, while Black, looking for a 50-move draw-claim maximises first DTC then DTM

7) Strategy-pair SZ50-Z-C-M-/SZ50+Z+C+M+ has White minimising (Black maximising) by metrics DTZ50, DTZ, DTC and DTM in turn

8) 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
Metrics DTR and DTZR are relatively new and unfamiliar, but were first defined in an ICGA_J paper of mine, and have been mentioned in MB/JT/GH papers.

Even so, strategy 8 will not maximise the probability of winning a game against a fallible opponent in the context of the 50-move draw-claim rule.

Regards - Guy
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: Shortest legal mate

Postby jkominek » Sun Feb 10, 2008 3:00 am

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
jkominek
 
Posts: 142
Joined: Mon Dec 04, 2006 9:02 am
Location: Pittsburgh, PA

Re: (for Guy Haworth?) Shortest legal mate

Postby guyhaw » Mon Feb 18, 2008 5:06 pm

With jokes like that, I must visit this board more often than I now do. I was that mathematician**.

I think that what 'ernest' meant to ask was "How do I mate in the shortest time consistent with avoiding a draw under the 50-move rule?"
JK makes a fair attempt at understanding the concepts I discussed, but "shortness assumes a metric" is wrong. First, White might be minimising with regard to first the DTC metric and then the DTM metric. Black might be maximising with regard to first the DTM metric and then the DTC metric, so there is no requirement on the two sides to optimise in the same way. "Optimising requires a defined subsetting strategy" covers the case more generically. But I haven't even thought through what happens when White minimises <b> and also knows and uses the fact that </b> the strategy that Black is using.
There is a 'guard filter' that I didn't mention before, which I indicated with a 'degree sign' in papers I've written but which will have to be a lower-case 'o' here. SZ50o restricts the choice of moves to those moves (if any) which retain the win rather than allowing a 50-move-draw claim. If there are none, then SZ50o allows all moves through. Similarly SZo restricts the choice of moves to all moves not allowing a 50-move-draw claim in the current phase.

And so to the 'bottom line': the strategies that ernest seeks are SZ50oM- and (for Black) SZ50M+. White guards the win under the 50-move rule with SZ50o and minimises DTM within that. Black will hang on to the draw under the 50-move rule if presented with it, but will otherwise maximise DTM. Another case of more than one metric being 'in play'.

The proposed DTR (Depth to Rule) EGTs provide more than 'local information' as JK puts it. This took some thinking about but is clear when thought about the right way. Suppose you have the win and you are going to win, but you give your opponent $MC if the 'move count' climbs to MC at any time in the game. You want to minimise MC, i.e. you want to limbo under as many M-move-rules are possible. So 'White' aims to minime MC and Black aims to maximise it. DTR is what White will pay out in dollars with best play. MC =< DTM and so is well defined ... and can be calculated with the help of another metric DTZR, which is the best 'DTZ' available when first minimising DTR.

The current challenge (for me) is to define an optimal strategy for securing the win when DTR > 50, and one's opponent is known to be fallible - which all human opponents are. Note that a computer with perfect information would almost certainly have won the KNNKRB Karjakin-Shirov (2007) endgame as Black. The opponent's fallibility can be estimated (see other papers of mine), modelled using a 'space' of Reference Fallible Agents. Repetition of position may be judiciously allowed (see a paper I haven't written yet). All this would be needed to get down from the heady heights of DTC = 517 in KRBNKQN.

** An engineer, physicist and mathematician cross into Yorkshire in a train. The engineer sees a field of black sheep and says "All the sheep in Yorkshire are black". The physicist corrects him, saying that one can only say "All the sheep in this field are black". The mathematician cries "Hold! All we know is that at least one side of every sheep in that field is black."

g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Some more comments on jk's note

Postby guyhaw » Tue Feb 19, 2008 9:43 am

The metrics DTM, DTC, DTZ50 do not "only summarize the total path length". In fact, only DTM does that. The DTR metric is a 'summary statistic' about the whole optimal path but does not specify the total path length. The DTC, DTZ50 and DTZR metrics are about 'the current phase to next relevant event', whether that event is mate/capture, or mate/capture/P-push.
A paper by Tamplin and self includes a lot of positions where the optimal DTZ50 move is not DTC-, DTM- or even DTZ-optimal ... and where optimal moves in these three metrics actually throw away the win. I'll post some of these positions shortly. John Tamplin's site http://chess.jaet.org/endings/ (which ought to be in Kirill's list of interfaces to EGT-banks) allows one, as available, to see the DTC, DTM, DTZ and DTZ50 options alongside each other.
g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: (for Guy Haworth?) Shortest legal mate

Postby Kirill Kryukov » Tue Feb 19, 2008 11:48 am

Thanks Guy, I added it to the web site.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: (for Guy Haworth?) Shortest legal mate

Postby jkominek » Tue Feb 19, 2008 7:34 pm

The metrics DTM, DTC, DTZ50 do not "only summarize the total path length". In fact, only DTM does that. The DTR metric is a 'summary statistic' about the whole optimal path but does not specify the total path length. The DTC, DTZ50 and DTZR metrics are about 'the current phase to next relevant event', whether that event is mate/capture, or mate/capture/P-push.


Right, an important correction. Thanks.

About DTZ "relevant events": I find it most helpful to think of them as a non-reversible moves (an consequence of the laws of chess), that has the effect of resetting the move counter (a manifestation of the rules of chess). Let us not forget that castling is the 4th category of non-reversible moves. Can anyone confirm if castling resets the move counter? If so, then technically Z={mate,capture,pawn move,castle). That said - like everyone before me - I don't care to deal with castling in tablebase generation.

Your reply two posts up helps clarify, but I'm not convinced SZ50oM-/SZ50M+ is exactly it. ... I can be slow at times - i.e. before a morning coffee relevant event - and slow in general, so let me ponder a bit longer.

john
jkominek
 
Posts: 142
Joined: Mon Dec 04, 2006 9:02 am
Location: Pittsburgh, PA

Re: (for Guy Haworth?) Shortest legal mate

Postby guyhaw » Wed Feb 20, 2008 5:24 am

The fourth category of non-reversible moves is 'changing castling rights' rather than "castling": it does not zero the move-count but (?) should.
The fifth category of non-reversible moves is 'not accepting an opportunity for an e.p.-capture': ditto.
As you say, jk, I leave you to ponder SZ50oM-/SZ50M+: my bet is that you will be successful.
g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Some examples of DTZ50 being an important metric

Postby guyhaw » Wed Feb 20, 2008 6:08 am

These positions can be checked on John Tamplin's site http://chess.jaet.org/endings/
In each case, the move(s) to win under a 50-move rule are not DTC-, DTM- or DTZ-optimal.
" indicates only value-preserving move; ' indicates only strategy-optimal move.
These positions are among those where all of the SC-, SM- and SZ- strategies fail to preserve the win, and are among such positions listed in the two papers:

J.A.Tamplin and G.McC.Haworth (2003). Chess Endgames: Data and Strategy. Advances in Computer Games 10, pp. 81-96. ISBN 1-4020-7709-2.
M.S.Bourzutschky, J.A.Tamplin and G.McC.Haworth (2005). Chess Endgames: 6-man Data and Strategy. J. of Theoretical Computer Science, Vol. 349, Issue 2, pp. 140-157. ISSN 0304-3975.

BB-P 1-0 dtm=123, dtz=1, dtz50=13, 8/8/8/1k6/88/8/p4BB1/3K4 b: 1...Kc4", not 1...a1=Q+??
NN-P 1-0 dtm=64, dtz=20, dtz50=44, 8/8/8/8/2K3Np/7N/3k4/8 w: 1.Ngf2', not 1.Ng1??
QP-Q 1-0 dtm=63, dtz=1, dtz50=50, 8/8/1P5Q/1K6/3q4/8/5k2/8 w: 1.Qg5", not 1.b7??
RP-P 0-1 dtm =80, dtz=1, dtz50=6, 8/8/5K2/8/2R2P2/8/6p1/k7 b: 1...Kb2", not 1...g1=Q??
RP-Q 0-1 dtm=82, dtz=2, dtz50=21, 8/4q2R/k5K1/8/5P2/8/8/8 b: 1...Qe6+", not 1...Qd6+?? or 1...Qe4+??

BB-BN 1-0 dtm=66, dtz=2, dtz50=18, 7b/6nB/8/8/3B4/8/2K5/4k3 w: 1.Kd3", not 1.Bd3??
BB-NN 1-0 dtm=67, dtz=1, dtz50=28, 8/8/6n1/8/k3BB2/8/n1K5/8 w: 1.Bd6", not 1.Bxg6??
QN-BB 0-1 dtm=65, dtz=1, dtz50=4, 1b6/8/8/K6N/8/8/6Q1/3k1b2 b: 1...Bc7+", not 1...Bxg2??
BNN-Q 0-1 dtm=63, dtz=1, dtz50=36, 7N/6q1/8/8/2N5/3K1k2/8/B7 b: 1...Qh7+", not 1...Qxa1??

KBBKN takes a big hit under the 50-move rule: 21.05% of wtm wins, and 48.20% of btm losses, are drawable under the 50m-rule.
For KNNKP, the figures are 26.35% and 46.87%, and a further 42.16% of wtm wins and 30.80% of btm losses are delayed.
For KBBKNN, 50.15% of wtm wins and 70.98% of btm losses are drawable.

g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

legal mate within '50 move rule'

Postby gambit3 » Sun Jun 15, 2008 10:32 am

1. Kf4 Kf7 2. Nd4 Ke7 3. Ke5 f4 4. Ngf5+
Kd7 5. Nf3 Kc6 6. Kd4 Kb5 7. Ne7 Kb6 8. Kd5 Kb5 9. Nc6 Ka6
10. Ncd4 Kb7 11. Nb5 Kb6 12. Nd6 Kc7 13. Nc4 Kd7 14. Nb6+
Kc7 15. Kc5 Kb7 16. Nd5 Kc8 17. Kc6 Kd8 18. Kd6 Kc8
19. Nb6+ Kb7 20. Nd7 Ka6 21. Kc6 Ka5 22. Nde5 Ka4 23. Kc5
Kb3 24. Nc6 Kc3 25. Nb4 Kb3 26. Nd5 Ka3 27. Nc3 Kb2 28. Kb4
Kc2 29. Kc4 Kc1 30. Nb5 Kb2 31. Nbd4 Ka2 32. Kc3 Ka3
33. Nb3 Ka2 34. Nc5 Ka3 35. Kc4 Kb2 36. Nd3+ Kc2 37. Nf2
Kb2 38. Nd2 Ka3 39. Kb5 Kb2 40. Kb4 Kc2 41. Nde4 Kb2
42. Ka4 f3 43. Kb4 Ka2 44. Kc3 Ka3 45. Nc5 Ka2 46. Nd7 Ka3
47. Nb6 Ka2 48. Nc4 Kb1 49. Kd2 Ka2 50. Kc2 Ka1 51. Kb3 Kb1
52. Nd3 Ka1 53. Nd2 f2 54. Nb4 f1=Q 55. Nc2# *
Hi,

I want to use John Tamplin's DTZ50 EGTB in http://chess.jaet.org/endings,
in order to obtain the shortest legal mate (of course with Black's best defense) for the following KNNKP position:
6k1/8/8/1N3p2/6K1/6N1/8/8 w
6k1/8/8/1N3p2/6K1/6N1/8/8 w
6k1/8/8/1N3p2/6K1/6N1/8/8 w

The DTM EGTB shows that it is a mate in 55, ignoring the 50-move rule.

How do you combine the results of the DTZ50 and DTM EGTBs to find that shortest legal mate?

Note: I found this, but I am not sure it is correct... (curiously, it is also a mate in 55, not more)

[Event "?"]
[Site "?"]
[Date "2007.08.26"]
[Round "?"]
[White "?"]
[Black "?"]
[Result "*"]
[SetUp "1"]
[FEN "6k1/8/8/1N3p2/6K1/6N1/8/8 w - -"]

1. Kf4 Kf7 2. Nd4 Ke7 3. Ke5 f4 4. Ngf5+
Kd7 5. Nf3 Kc6 6. Kd4 Kb5 7. Ne7 Kb6 8. Kd5 Kb5 9. Nc6 Ka6
10. Ncd4 Kb7 11. Nb5 Kb6 12. Nd6 Kc7 13. Nc4 Kd7 14. Nb6+
Kc7 15. Kc5 Kb7 16. Nd5 Kc8 17. Kc6 Kd8 18. Kd6 Kc8
19. Nb6+ Kb7 20. Nd7 Ka6 21. Kc6 Ka5 22. Nde5 Ka4 23. Kc5
Kb3 24. Nc6 Kc3 25. Nb4 Kb3 26. Nd5 Ka3 27. Nc3 Kb2 28. Kb4
Kc2 29. Kc4 Kc1 30. Nb5 Kb2 31. Nbd4 Ka2 32. Kc3 Ka3
33. Nb3 Ka2 34. Nc5 Ka3 35. Kc4 Kb2 36. Nd3+ Kc2 37. Nf2
Kb2 38. Nd2 Ka3 39. Kb5 Kb2 40. Kb4 Kc2 41. Nde4 Kb2
42. Ka4 f3 43. Kb4 Ka2 44. Kc3 Ka3 45. Nc5 Ka2 46. Nd7 Ka3
47. Nb6 Ka2 48. Nc4 Kb1 49. Kd2 Ka2 50. Kc2 Ka1 51. Kb3 Kb1
52. Nd3 Ka1 53. Nd2 f2 54. Nb4 f1=Q 55. Nc2# *


1. Kf4 Kf7 2. Nd4 Ke7 3. Ke5!! f4 this white move is critical as it forces the pawn to move
4. Ngf5+ Kd7 5. Nf3 Kc6
6. Kd4 Kb5 7. Ne7 Kb4 8. Nc6+ Kb5 9. Kd5 Ka6 10. Ncd4 Kb7
11. Nb5 Kb6 12. Nd6 Kc7 13. Nc4 Kd7 14. Nb6+ Kc7 15. Kc5 Kb7
16. Nd5 Ka6 17. Nc3 Kb7 18. Nb5 Kc8 19. Kc6 Kd8 20. Nbd4 Ke7
21. Kc7 Kf7 22. Kd6 Ke8 23. Nc6 Kf8 24.Ke5 Kf7 25. Kf5 Kf8
26. Kf6 Ke8 27. Ke6 Kf8 28. Nce5 Kg8 29. Nc4 Kg7 30. Nd6 Kg6
31. Ke5 Kg7 32. Kf5 Kh7 33. Kf6 Kh6 34. Nc4 Kh7 35. Nce5 Kh6
36. Ke6 Kh7 37. Kf7 Kh6 38. Kf6 Kh5 39. Kf5 Kh6 40. Nd7 Kg7
41. Ke6 Kg8 42. Ke7 Kh8 43. Kf7 Kh7 44. Nc5 Kh6 45. Kf6 Kh5
46. Kf5 Kh6 47. Ne6 Kh5 48. Ng7+ Kh6 49. Kf6 Kh7 50. Nf5 Kg8
51. Ke7 Kh7
(51... Kh8 52. Kf7 Kh7 53. Ng5+ Kh8 $11 {50 move rule, but mate in 2 after nh4,ng6, which is sometimes still called a win under the displayable mate rule.})
52. Kf7 Kh8 53. Ng5 f3 54. Nh4 (54.Ne7 f2 55. Ng6#) 54... f2 55. Ng6# 1-0

there are about 2000 more of them, but i think you get the idea. this is one of the ones that doesn't ignore 50 move rule with notes to one that does and another that doesn't right at the end. the one that ignores the dtz50 (50 move rule) is not actually the first one i found. as you can see, the mating theme in all is the same. the only differneces are that some allow black not to move the pawn and therefore become drawn under the archaic 50 move rule. in all cases the theme of the strategy is the same - black k in corner, one n covering rank and file, whit k covering diag and other n applying mate.

there is no hard and fast rule anymore because fide has brought in a policy of 'arbiter's discretion' regarding the 50 move rule after the evidence of kbbnkbn containing a forced win of black's bishop in 340-odd moves a few years ago. in practice, this means that some high level games are often left to their own devices until either there is a result or the players agree to a draw.
those who can, do
those who can't, teach
gambit3
 
Posts: 57
Joined: Mon Mar 06, 2006 8:06 am

Re: legal mate within '50 move rule'

Postby ernest » Tue Jun 17, 2008 12:20 am

gambit3 wrote:...this white move is critical as it forces the pawn to move ...

Thanks again, gambit3, but I don't expect from the mathematician you are, a chess lesson... :D

I want to know, in a theoretical way, how to get the shortest legal mate.

What do I need : DTM, DTZ50, ... any other table? and how do I use them (assuming DTM shows mate in more than 50)?
ernest
 
Posts: 63
Joined: Tue Nov 21, 2006 6:31 pm
Location: Paris

FIDE decision on Arbiter's Discretion?

Postby guyhaw » Wed Jun 18, 2008 6:28 am

gambit3,

Do you have a reference to a FIDE decision (which postdates MB's findings on 7-manchess) on the applicability (or ad hoc suspension) of the 50-move rule?
Maybe I missed something.

jk may be right to ponder my suggestion as to the optimal strategies for White and Black if they are minimaxing DTM within the 50-move rule...

Certainly, White must play SZ50oM- which is to say:
1) White will not play a move which allows Black to force a draw under the 50-move rule
2) With the moves left, White will then minimise Depth to Mate

The question is whether Black can do better than the strategy SM+.
g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: (for Guy Haworth?) Shortest legal mate

Postby gambit3 » Wed Jun 18, 2008 8:58 pm

Do you have a reference to a FIDE decision (which postdates MB's findings on 7-manchess) on the applicability (or ad hoc suspension) of the 50-move rule?
Maybe I missed something.


it was made clear after the abovementioned mate was found that, due to the increasing number of mates outside the 50 move rul that were demonstrable, and with the evidence that there were more to come, that the arbiter's decision whether an appealed position was drawn was irrespective of the 50 move rule. unfortunately i don't have complete fide rulebook post-1997, but it was certainly brought up and ruled on in the 2005-6 AGM. minutes from that meeting should be sufficient to point you to the desired addundum in the rules, i would imagine.

my apologies for being unable to be more specific in this, i read it in the news at chessbase, and thought of the implications even then. as a side question that may or not be relevant, did the last carbon world championship contain any games drawn by 50 move rulings? if it did then fide may have not implimented their decision in their rulebook (which i believe is annually updated), however i know the decision predated that particular tournament.
those who can, do
those who can't, teach
gambit3
 
Posts: 57
Joined: Mon Mar 06, 2006 8:06 am

Re: (for Guy Haworth?) Shortest legal mate

Postby gambit3 » Mon Jun 23, 2008 10:55 pm

original question:
How do you combine the results of the DTZ50 and DTM EGTBs to find that shortest legal mate?

Note: I found this, but I am not sure it is correct... (curiously, it is also a mate in 55, not more)

my answer at this point is correct, as you say, and useless, however it may be poignant to ask why it is you ask what you ask. that is, what is the ultimate purpose of your query?
final qualifier:
I want to know, in a theoretical way, how to get the shortest legal mate.


at last, right question! and from the formulation of it, already answered two different ways.

Guy, found latest copy of rule here. article 5.3 covers the ending of the game. It shows that the 50 move rule still stands and that the discussion i remember didn't result in a rule change. It DID result in a predictate (section 9.3a) that means that now the 50 move rule must be claimed on the claiming player's move, rather than it being (as in the rulebook i have) claimable at any point up to the end of the game. also please note that the recording requirement means that blitz games are clearly not confined by 50 move rule since no recording is required (or else there would be more arbiters than blitz-chess players; article 8.4, 8.5), and that even longplay endings low on time may forego the 50 move rule (article 10.2). these articles, when taken together, provide a set or circumstances wherein the 50 move rule may not be applied.
those who can, do
those who can't, teach
gambit3
 
Posts: 57
Joined: Mon Mar 06, 2006 8:06 am

Re: (for Guy Haworth?) Shortest legal mate

Postby ernest » Tue Jun 24, 2008 6:14 pm

gambit3 wrote:
I want to know, in a theoretical way, how to get the shortest legal mate.

at last, right question! and from the formulation of it, already answered two different ways.


Please tell me where... :?
ernest
 
Posts: 63
Joined: Tue Nov 21, 2006 6:31 pm
Location: Paris

Various...

Postby guyhaw » Tue Jun 24, 2008 9:00 pm

gambit3's observes that the 50-move rule cannot apply when the game is not recorded: good point.

I had previously said that the quickest mate avoiding a 50-move-rule draw claim could be found by following strategy SZ50oM-. However, this is not strictly correct (though I cannot give a counterexample).

In fact, the quickest mate (avoiding ...) can of course be found by:
1) creating the DTZ50 EGT for the endgame
2) setting all 'wins' to draws if they are draws under the DTZ50 rule
3) constructing a DTM EGT with the wins that are left

In fact, I believe Marc B created a code which would create such a 'DTM50' EGT directly: I had forgotten.
SM50- play is not necessarily identical to SZ50oM- play.
g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: (for Guy Haworth?) Shortest legal mate

Postby Vegan » Wed Jun 25, 2008 6:22 pm

Actually the shortest legal mate is a 32 piece position.

1. f3 e5
2. g4?? Qh4++

You missed this mate? Its the shortest mate, for 32 piece tablebases. :lol:
Vegan
 

Re: (for Guy Haworth?) Shortest legal mate

Postby ernest » Wed Jun 25, 2008 6:43 pm

Vegan wrote:You missed this mate?

Better drop a subject where you only can utter a lame joke... :evil:
Go back eating your beans!
ernest
 
Posts: 63
Joined: Tue Nov 21, 2006 6:31 pm
Location: Paris

Re: (for Guy Haworth?) Shortest legal mate

Postby Vegan » Wed Jun 25, 2008 10:06 pm

well the subject was the shortest legal mate, just because you don't have 32 piece tablebases yet.
Vegan
 

Re: (for Guy Haworth?) Shortest legal mate

Postby kronsteen » Wed Oct 30, 2013 8:03 am

Ernest,
If you're still with us, I have (finally) the solution of your problem. I hope you won't mind getting the answer 6 years after the problem was posted :lol: , but now the knnkp DTM50 tablebase exists and if you or anybody else has the same demand about any other knnkp position, the response should come within days or weeks at worst instead of years…

You want to know what is the shortest mate from a given position, playing with the 50-move rule. This is exactly the information provided by a DTM50 tablebase, and a DTM50 tablebase is necessary for that (DTM and DTZ50 tablebases are not sufficient, even together). DTM50 optimal play is something unique, sometimes sticking to DTZ50 when the threat of a 50-move rule draw is close by, sometimes sticking to DTM when the threat is far away, often switching its “preference” between DTM and DTZ50 during play, and even sometimes taking its own path.

Looking back at your problem, this position is a MATE IN 59 playing with the 50-move rule.

6k1/8/8/1N3p2/6K1/6N1/8/8 w - - 0 1
6k1/8/8/1N3p2/6K1/6N1/8/8 w - - 0 1

One optimal line is :

1. Kf4 Kf7 2. Nd4 Ke7 3. Ke5 f4 4. Ngf5+ Kd7 5. Nf3 Kc6 6. Kd4 Kb5 7. Ne7 Kb4 8. Nc6+ Kb5 9. Kd5 Ka6 10. Ncd4 Kb7 11. Nb5 Kb6 12. Nd6 Kc7 13. Nc4 Kd7 14. Nb6+ Kc7 15. Kc5 Kb7 16. Nd5 Ka6 17. Nc7+ Kb7 18. Ne6! Ka6 19.Nd8 Ka7 20. Kb5 Kb8 21. Kc6 Ka7 22. Ne6 Ka6 23. Nc7+ Ka7 24. Nd5 Kb8! 25. Nb6! Ka7 26. Nd7 Ka6 27. Nb8+ Ka5 28. Kc5 Ka4 29. Nc6 Ka3 30. Kd5 Kb3 31. Kd4 Ka2! 32. Na5! Kb1! 33. Nb3! Kc2 34. Nbd2! Kb2 35.Kd3 Ka2 36. Kc3 Ka3 37. Kc4 Ka2 38. Ne4 Kb2 39. Kb4 Kc1 40. Nf2 Kc2 41. Kc4 Kb2 42. Nd2 Ka3 43. Kb5 Kb2 44. Kb4 Kc2 45. Nde4 Kb2 46. Ka4 f3 47.Kb4 Ka2 48. Kc3 Ka3 49. Nc5 Ka2 50. Nd7 Kb1 51. Ne5 Kc1 52. Nc4 Kb1 53. Kd2 Ka2 54. Kc2 Ka1 55. Kb3 Kb1 56. Nd3 Ka1 57. Na3 f2 58. Nb4 f1=Q 59. Nbc2#

Notation :
normal font = moves that are DTM and DTZ50 optimal
bold = a move that is DTM optimal but not DTZ50 optimal
underlined + ! = a move that is DTZ50 optimal but not DTM optimal
underlined+bold+!! = a move that is neither DTZ50 nor DTM optimal (none here)

So what happens ? If Black refuses to play f4 early he will be cornered and mated long before the 50-move limit, so he plays f4 at move 3. And this is where the real story begins : if White sticks to the DTM line, he will sooner or later create a situation where Black can delay the forced play of f3 until move 54 (only one move before the mate as the initial position has DTM=55), and therefore can claim a 50-move rule draw at move 53. White lacks only one move to follow the DTM line (which would win under a 51-move rule), but one move is enough. What he must do instead is immobilizing the Black king at its 53th move or before, in a situation where he can mate quickly afterwards while Black uses his 3 undesired reserve tempi (f3, f2, f1=Q). The maneuver required to do this is slightly different and has the effect of delaying the mate by 4 moves. Surprisingly the influence on the play begins quickly, in the DTM50 optimal line given above White must abandon the DTM line as early as move 18 when he is still in the process of chasing the Black king off the a8 corner (mate is delivered on a1 or h8 against best defence). This is only after move 34 that White has created the proper conditions and is able to follow a DTM optimal line without walking into a 50-move rule draw.

I’ve assumed the initial position has movecount = 0. If it is not the case, the complete DTM50 results for this position are :

DTM50 = 59 for mc <= 56 halfmoves
DTM50 = 72 for mc = 57 or 58 halfmoves
50-move rule draw for mc >= 59 halfmoves
Last edited by kronsteen on Fri Nov 01, 2013 7:57 am, edited 1 time in total.
kronsteen
 
Posts: 88
Joined: Fri Aug 01, 2008 11:20 am
Location: France

Re: (for Guy Haworth?) Shortest legal mate

Postby ernest » Thu Oct 31, 2013 11:42 pm

kronsteen wrote:One optimal line is :

1. Kf4 Kf7 2. Nd4 Ke7 3. Ke5 f4 4. Ngf5+ Kd7 5. Nf3 Kc6 6. Kd4 Kb5 7. Ne7 Kb4 8. Nc6+ Kb5 9. Kd5 Ka6 10. Ncd4 Kb7 11. Nb5 Kb6 12. Nd6 Kc7 13. Nc4 Kd7 14. Nb6+ Kc7 15. Kc5 Kb7 16. Nd5 Ka6 17. Nc7+ Kb7 18. Ne6+! Ka6 19.Nd8 Ka7 20. Kb5 Kb8 21. Kc6 Ka7 22. Ne6 Ka6 23. Nc7+ Ka7 24. Nd5 Kb8! 25. Nb6! Ka7 26. Nd7 Ka6 27. Nb8+ Ka5 28. Kc5 Ka4 29. Nc6 Ka3 30. Kd5 Kb3 31. Kd4 Ka2! 32. Na5! Kb1! 33. Nb3! Kc2 34. Nbd2! Kb2 35.Kd3 Ka2 36. Kc3 Ka3 37. Kc4 Ka2 38. Ne4 Kb2 39. Kb4 Kc1 40. Nf2 Kc2 41. Kc4 Kb2 42. Nd2 Ka3 43. Kb5 Kb2 44. Kb4 Kc2 45. Nde4 Kb2 46. Ka4 f3 47.Kb4 Ka2 48. Kc3 Ka3 49. Kc5 Ka2 50. Nd7 Kb1 51. Ne5 Kc1 52. Nc4 Kb1 53. Kd2 Ka2 54. Kc2 Ka1 55. Kb3 Kb1 56. Nd3 Ka1 57. Na3 f2 58. Nb4 f1=Q 59. Nbc2#

Hi Kronsteen,

Indeed I am still with this Forum, and I appreciate and congratulate you for producing this DTM50 which answers the question I asked 6 years ago.
Actually, I have a very good friend (in France) who produced, by June of this year, his own (private) 5-men DTM50 (it also took him quite a few months...), so it would be interesting to compare some of the results.
In particular, I asked him to look at your
viewtopic.php?p=79892#p79892 (Mate in 137)
and he found 2 differences which we can discuss in a few days (either here or in private message).

Coming back to the pgn quoted here above (Mate in 59), it would also be interesting to compare, but it seems there are some typos.
For instance 48. Kc3 is followed by 49. Kc5
Can you show us a corrected pgn?
Thanks and looking forward.
ernest
 
Posts: 63
Joined: Tue Nov 21, 2006 6:31 pm
Location: Paris

Re: (for Guy Haworth?) Shortest legal mate

Postby ernest » Fri Nov 01, 2013 7:39 pm

ernest wrote:it seems there are some typos.
For instance 48. Kc3 is followed by 49. Kc5

Well it seems 49. Kd5 is the only typo, should be corrected to 49. Nd5

The DTM50 of my friend then agrees with your pgn (mate in 59)
ernest
 
Posts: 63
Joined: Tue Nov 21, 2006 6:31 pm
Location: Paris

Re: (for Guy Haworth?) Shortest legal mate

Postby kronsteen » Sat Nov 02, 2013 7:04 am

Hi ernest, glad to see you again.

I've corrected the pgn above. For now I use a self-made probing code that works poorly and must be ameliorated. I produce the pgns manually, so there can be a few errors. 49. Kc5 is 49. Nc5 instead. 18. Ne6 is also not a check. The rest is correct.

I'm glad to learn that other DTM50 EGTs than mines exist, as cross-verifications will be possible. I wish to release my DTM50 EGTs when they'll be completed and want to be sure that the data produced are correct. Up to now the data I've checked my EGTs against are the nalimov tbs stat files (number of positions with DTM=n for each set of pieces, must match DTM50 at mc=0 for n<=50). I also use the Wilhelm program and the DTZ50 online EGTs at chess.jaet.org. to check some particular positions and identify DTM50/DTM and DTM50/DTZ50 divergences. I welcome the idea of comparing our respective results (using PMs for that will be okay).

Feel also free to post other DTM50 queries if you have any (I'll have generated all 32/23 with 0-1 pawn soon).

ernest wrote:The DTM50 of my friend then agrees with your pgn (mate in 59)


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

Re: (for Guy Haworth?) Shortest legal mate

Postby ernest » Fri Nov 08, 2013 1:05 pm

kronsteen wrote:I welcome the idea of comparing our respective results (using PMs for that will be okay).

Just sent you a PM concerning the two differences in viewtopic.php?p=79892#p79892 (Mate in 137)
ernest
 
Posts: 63
Joined: Tue Nov 21, 2006 6:31 pm
Location: Paris

Re: (for Guy Haworth?) Shortest legal mate

Postby pa1ny » Mon Sep 12, 2016 11:43 am

When I take 6k1/8/8/1N3p2/6K1/6N1/8/8 w - - 0 1

.. and do the following moves

1. Kf4 Kf7 2. Nc7 Ke7 3. Na8 Kd6

Stockfish 7 with Syzygy TBs still shows me a legal DTZ50 winning and Nalimov/Gaviota says it's DTM in 63
--> N7/8/3k4/5p2/5K2/6N1/8/8 w - -

I wondered if this could be the maximum legal(!) Mate in X position for KNNvKP

What do you think?
pa1ny
 
Posts: 8
Joined: Tue Sep 06, 2016 3:36 pm

Next

Return to Endgame Tablebases

Who is online

Users browsing this forum: No registered users and 3 guests