Nalimov EGTB problem related to DTM?

[bob]

An example:

[D]8/4K3/8/4B1n1/B7/8/5k2/8 w - - 0 1

It's a win in 62. If I am not doing anything wrong, Nalimov 3-4-5 men EGTB, at least in their implementation, fail to convert it. I checked with Houdini 4 and Shredder 12.

It seems you have a configuration problem, at least in the Fritz GUI having loaded the Nalimov all engines see the mate in 62.
Nalimov online does not have a problem with any of the positions.
http://www.k4it.de/?topic=egtb&lang=en

I am worried about my tests here with egtbs, but that it's showing mate in 62 doesn't mean it actually converts it. My tests were Houdini/Shredder Nalimov versus Komodo/Stockfish Syzygy with 5 men at the root.

I am not sure what the problem is here. I tested this position a hundred times against multiple opponents and never saw a loss or draw by any program for the winning side. The knight is captured well before the 50 move rule limit with optimal play (here is Crafty's output from the starting position:

White(1): 8/4K3/8/4B1n1/B7/8/5k2/8 w - - 0 1
White(1): egtb
1. Bf4! Nh3 2. Bh6 Ng1! 3. Kf6 Nf3! 4. Kf5! Ne1 5. Bf8 Nd3 6. Ke4!
Ne1! 7. Bc5+ Kg3! 8. Bb6 Ng2! 9. Bd1! Ne1 10. Ke3! Ng2+! 11. Kd2!
Kf4! 12. Ke2! Kf5! 13. Bc2+! Ke6! 14. Bb3+! Kf5 15. Kf3! Nh4+! 16.
Kf2! Ng6! 17. Bc2+! Kf6! 18. Bd8+! Kf7! 19. Ke3! Ne7! 20. Bb3+! Ke8!
21. Bc7! Kd7! 22. Bf4! Kc6! 23. Kd4! Nf5+ 24. Ke5! Nd6! 25. Bd5+!
Kd7! 26. Bg3! Ke7! 27. Bb3! Nf7+! 28. Ke4! Nd6+! 29. Kd5! Ne8! 30.
Ke5! Nd6! 31. Bh4+! Kd7! 32. Kd5! Nf7! 33. Ba4+! Kc7! 34. Kc5! Kc8!
35. Bg3 Kd8! 36. Kd5! Ke7! 37. Bh4+! Kf8! 38. Bf6 Nh6 39. Ke6! Ng4
40. Bb2! Nh6! 41. Bd1! Ng8! 42. Bh5! Nh6! 43. Kf6! Ng8+! 44. Kg6!
Ke7 45. Kg7! Nf6 46. Bxf6+! Ke6! 47. Bg6 Kd5 48. Kf7! Kc5 49. Be4
Kb4 50. Bd3! Ka3 51. Bc3 Ka2 52. Bc4+ Kb1 53. Bb3! Kc1 54. Ke7 Kb1
55. Kd6! Kc1 56. Kc5! Kb1 57. Kb4! Kc1 58. Ka3! Kb1 59. Bd2! Ka1
60. Bg8 Kb1 61. Bh7+! Ka1 62. Bc3#). Move 46 resets the counter.

[bob]

Syzygy website gives different moves to mate
https://syzygy-tables.info/?fen=8/4K3/8 ... 0-%200%201
Lomosov site coincides with Nalimov.
Although the capture of the horse, is move 52.

Therefore Nalimov shows a draw (if claimed).

For me Nalimov shows the knight being captures on move 46:

White(1): 8/4K3/8/4B1n1/B7/8/5k2/8 w - - 0 1
White(1): egtb
1. Bf4! Nh3 2. Bh6 Ng1! 3. Kf6 Nf3! 4. Kf5! Ne1 5. Bf8 Nd3 6. Ke4!
Ne1! 7. Bc5+ Kg3! 8. Bb6 Ng2! 9. Bd1! Ne1 10. Ke3! Ng2+! 11. Kd2!
Kf4! 12. Ke2! Kf5! 13. Bc2+! Ke6! 14. Bb3+! Kf5 15. Kf3! Nh4+! 16.
Kf2! Ng6! 17. Bc2+! Kf6! 18. Bd8+! Kf7! 19. Ke3! Ne7! 20. Bb3+! Ke8!
21. Bc7! Kd7! 22. Bf4! Kc6! 23. Kd4! Nf5+ 24. Ke5! Nd6! 25. Bd5+!
Kd7! 26. Bg3! Ke7! 27. Bb3! Nf7+! 28. Ke4! Nd6+! 29. Kd5! Ne8! 30.
Ke5! Nd6! 31. Bh4+! Kd7! 32. Kd5! Nf7! 33. Ba4+! Kc7! 34. Kc5! Kc8!
35. Bg3 Kd8! 36. Kd5! Ke7! 37. Bh4+! Kf8! 38. Bf6 Nh6 39. Ke6! Ng4
40. Bb2! Nh6! 41. Bd1! Ng8! 42. Bh5! Nh6! 43. Kf6! Ng8+! 44. Kg6!
Ke7 45. Kg7! Nf6 46. Bxf6+! Ke6! 47. Bg6 Kd5 48. Kf7! Kc5 49. Be4
Kb4 50. Bd3! Ka3 51. Bc3 Ka2 52. Bc4+ Kb1 53. Bb3! Kc1 54. Ke7 Kb1
55. Kd6! Kc1 56. Kc5! Kb1 57. Kb4! Kc1 58. Ka3! Kb1 59. Bd2! Ka1
60. Bg8 Kb1 61. Bh7+! Ka1 62. Bc3#

The moves with ! following them are singular best moves and any other move extends the mate in 62 further.

[Laskos]

Syzygy website gives different moves to mate
https://syzygy-tables.info/?fen=8/4K3/8 ... 0-%200%201
Lomosov site coincides with Nalimov.
Although the capture of the horse, is move 52.

Therefore Nalimov shows a draw (if claimed).

For me Nalimov shows the knight being captures on move 46:

White(1): 8/4K3/8/4B1n1/B7/8/5k2/8 w - - 0 1
White(1): egtb
1. Bf4! Nh3 2. Bh6 Ng1! 3. Kf6 Nf3! 4. Kf5! Ne1 5. Bf8 Nd3 6. Ke4!
Ne1! 7. Bc5+ Kg3! 8. Bb6 Ng2! 9. Bd1! Ne1 10. Ke3! Ng2+! 11. Kd2!
Kf4! 12. Ke2! Kf5! 13. Bc2+! Ke6! 14. Bb3+! Kf5 15. Kf3! Nh4+! 16.
Kf2! Ng6! 17. Bc2+! Kf6! 18. Bd8+! Kf7! 19. Ke3! Ne7! 20. Bb3+! Ke8!
21. Bc7! Kd7! 22. Bf4! Kc6! 23. Kd4! Nf5+ 24. Ke5! Nd6! 25. Bd5+!
Kd7! 26. Bg3! Ke7! 27. Bb3! Nf7+! 28. Ke4! Nd6+! 29. Kd5! Ne8! 30.
Ke5! Nd6! 31. Bh4+! Kd7! 32. Kd5! Nf7! 33. Ba4+! Kc7! 34. Kc5! Kc8!
35. Bg3 Kd8! 36. Kd5! Ke7! 37. Bh4+! Kf8! 38. Bf6 Nh6 39. Ke6! Ng4
40. Bb2! Nh6! 41. Bd1! Ng8! 42. Bh5! Nh6! 43. Kf6! Ng8+! 44. Kg6!
Ke7 45. Kg7! Nf6 46. Bxf6+! Ke6! 47. Bg6 Kd5 48. Kf7! Kc5 49. Be4
Kb4 50. Bd3! Ka3 51. Bc3 Ka2 52. Bc4+ Kb1 53. Bb3! Kc1 54. Ke7 Kb1
55. Kd6! Kc1 56. Kc5! Kb1 57. Kb4! Kc1 58. Ka3! Kb1 59. Bd2! Ka1
60. Bg8 Kb1 61. Bh7+! Ka1 62. Bc3#

The moves with ! following them are singular best moves and any other move extends the mate in 62 further.

Can you try an engine with 3-4-5-men Nalimov as white against Stockfish with 3-4-5-men Syzygy as black? My guess is that the losing side (black) doesn't defend optimally using Nalimov (or not using egtb at all).

[Laskos]

It is related to ignoring the 50- move rule. Even in a DTM framework you could do better. You would have to keep track of DTZ during building, though.

I only now realized how important this might be in harder (longer) wins. Out of a set of 250 hard 5-men wins I collected, about 50 were unsolved by Nalimovs. This problem should be even more pronounced with 6-men. I am surprised that Syzygy does so well comparatively, even if it theoretically lacks DTR/DTZR.

There are 5 types of positions:
- wins
- cursed wins (i.e. win but 50-move draw)
- draws
- blessed losses (i.e. loss but 50-move draw)
- losses

DTZ50 will win wins and will at least draw cursed wins, draws and blessed losses.

DTM will at least draw wins, cursed wins and draws. It may lose blessed losses and losses.

So if DTZ50 plays DTM:
- win results in win
- cursed win results in draw or win
- draw results in draw
- blessed loss results in draw
- loss results in draw or loss

Or symmetrically, if DTM plays DTZ50:
- win results in win or draw
- cursed win results in draw
- draw results in draw
- blessed loss results in draw or loss
- loss results in loss

DTZ50 v DTZ50 gives "perfect play". Once the opponent uses DTZ50, you will not be able to win a cursed win or to draw a loss.

If the opponent uses DTM, then you can hope to win a cursed win or to draw a loss.

How to play cursed wins or losses optimally is a very interesting question.

When trying to draw a lost position, the most obvious thing to do is to maximise DTZ on each move. But that is not necessarily optimal. If the current position has, say, DTZ = 50 ply, you probably won't be able to last till 101 plies. But there might be a way to force or trick the opponent into playing or allowing a pawn move after 20 ply that transitions the game into a position with DTZ = 98 ply, which gives much better chances.

Similar considerations apply to trying to win a cursed win. Cursed win means you can force a mate, but the opponent can force the path to mate to include a "phase" (between two zeroing moves) lasting more than 100 plies. Ideally you want to minimise the length of the longest phase and then minimise DTZ during that phase and hope for opponent mistakes.

Syzygy TBs store "DTZ50+". A value from 1 to 100 is the distance in plies to a zeroing move leading to a won position. A value > 100 is either the distance to a zeroing move leading to a won position or the distance plus 100 to a zeroing move leading to a cursed win. It is enough to implement the simple strategy of minimising or maximising DTZ, but it does not give "global" information, i.e. information on the length of phases after the current phase.

DTR is an attempt to encode more global information, but since its value depends on the value of the 50-move counter it is not very usable when it comes to generating practical TBs. (But dependency on the current value of the 50-move counter is unavoidable if you want "best" play against fallible opponents: if you can barely reach a zeroing move before the 50-move counter runs out, you have no room for manoeuvre. If you have plenty of moves left, then you can spend those on manoeuvring into a position with a much more promising next phase.)

Very illuminating, I had very vague clues on these issues. If my file of general 5-men wins with "perfect play" is not flawed, it seems Nalimov fails to convert in about 6% of cases with these positions at the root, which is a lot. When I selected harder wins, the percentage went to 20%. For some reasons I thought egtbs using DTM fail to convert from the root in few freak cases only.

[kgburcham]

I assume you are saying it sees the mate in 62 but it cant play it though for the win?

[D] 8/4K3/8/4B1n1/B7/8/5k2/8 w - -

8 processor(s) found, POPCNT available
NUMA configuration with 1 node(s), offset 0
Nalimov 6 men EGTB available - 999 MB cache
Engine: Houdini 4 Pro x64 (8192 MB)
by Robert Houdart

99/124 0:09 +M62 1.Bf4 Nh3 2.Bc1 Ng1 (1.165) TB:1.025

[syzygy]

I am not sure what the problem is here. I tested this position a hundred times against multiple opponents and never saw a loss or draw by any program for the winning side. The knight is captured well before the 50 move rule limit with optimal play

I don't know what you call optimal play, but black can postpone the knight's capture until the49th move.

So the position is won for white under the 50-move rule, but white needs to play carefully and merely following Nalimov might be insufficient.

[syzygy]

For me Nalimov shows the knight being captures on move 46:

White(1): 8/4K3/8/4B1n1/B7/8/5k2/8 w - - 0 1
White(1): egtb
1. Bf4! Nh3 2. Bh6 Ng1! 3. Kf6 Nf3! 4. Kf5! Ne1 5. Bf8 Nd3 6. Ke4!
Ne1! 7. Bc5+ Kg3! 8. Bb6 Ng2! 9. Bd1! Ne1 10. Ke3! Ng2+! 11. Kd2!
Kf4! 12. Ke2! Kf5! 13. Bc2+! Ke6! 14. Bb3+! Kf5 15. Kf3! Nh4+! 16.
Kf2! Ng6! 17. Bc2+! Kf6! 18. Bd8+! Kf7! 19. Ke3! Ne7! 20. Bb3+! Ke8!
21. Bc7! Kd7! 22. Bf4! Kc6! 23. Kd4! Nf5+ 24. Ke5! Nd6! 25. Bd5+!
Kd7! 26. Bg3! Ke7! 27. Bb3! Nf7+! 28. Ke4! Nd6+! 29. Kd5! Ne8! 30.
Ke5! Nd6! 31. Bh4+! Kd7! 32. Kd5! Nf7! 33. Ba4+! Kc7! 34. Kc5! Kc8!
35. Bg3 Kd8! 36. Kd5! Ke7! 37. Bh4+! Kf8! 38. Bf6 Nh6 39. Ke6! Ng4
40. Bb2! Nh6! 41. Bd1! Ng8! 42. Bh5! Nh6! 43. Kf6! Ng8+! 44. Kg6!
Ke7 45. Kg7! Nf6 46. Bxf6+! Ke6! 47. Bg6 Kd5 48. Kf7! Kc5 49. Be4
Kb4 50. Bd3! Ka3 51. Bc3 Ka2 52. Bc4+ Kb1 53. Bb3! Kc1 54. Ke7 Kb1
55. Kd6! Kc1 56. Kc5! Kb1 57. Kb4! Kc1 58. Ka3! Kb1 59. Bd2! Ka1
60. Bg8 Kb1 61. Bh7+! Ka1 62. Bc3#

23...Nf5+ is suboptimal in terms of DTZ.
23...Kd7 maximises DTZ and gives white more opportunity to make half-point mistake.
https://syzygy-tables.info/?fen=8/4n3/2 ... 0-%200%201

[bob]

For me Nalimov shows the knight being captures on move 46:

White(1): 8/4K3/8/4B1n1/B7/8/5k2/8 w - - 0 1
White(1): egtb
1. Bf4! Nh3 2. Bh6 Ng1! 3. Kf6 Nf3! 4. Kf5! Ne1 5. Bf8 Nd3 6. Ke4!
Ne1! 7. Bc5+ Kg3! 8. Bb6 Ng2! 9. Bd1! Ne1 10. Ke3! Ng2+! 11. Kd2!
Kf4! 12. Ke2! Kf5! 13. Bc2+! Ke6! 14. Bb3+! Kf5 15. Kf3! Nh4+! 16.
Kf2! Ng6! 17. Bc2+! Kf6! 18. Bd8+! Kf7! 19. Ke3! Ne7! 20. Bb3+! Ke8!
21. Bc7! Kd7! 22. Bf4! Kc6! 23. Kd4! Nf5+ 24. Ke5! Nd6! 25. Bd5+!
Kd7! 26. Bg3! Ke7! 27. Bb3! Nf7+! 28. Ke4! Nd6+! 29. Kd5! Ne8! 30.
Ke5! Nd6! 31. Bh4+! Kd7! 32. Kd5! Nf7! 33. Ba4+! Kc7! 34. Kc5! Kc8!
35. Bg3 Kd8! 36. Kd5! Ke7! 37. Bh4+! Kf8! 38. Bf6 Nh6 39. Ke6! Ng4
40. Bb2! Nh6! 41. Bd1! Ng8! 42. Bh5! Nh6! 43. Kf6! Ng8+! 44. Kg6!
Ke7 45. Kg7! Nf6 46. Bxf6+! Ke6! 47. Bg6 Kd5 48. Kf7! Kc5 49. Be4
Kb4 50. Bd3! Ka3 51. Bc3 Ka2 52. Bc4+ Kb1 53. Bb3! Kc1 54. Ke7 Kb1
55. Kd6! Kc1 56. Kc5! Kb1 57. Kb4! Kc1 58. Ka3! Kb1 59. Bd2! Ka1
60. Bg8 Kb1 61. Bh7+! Ka1 62. Bc3#

23...Nf5+ is suboptimal in terms of DTZ.
23...Kd7 maximises DTZ and gives white more opportunity to make half-point mistake.
https://syzygy-tables.info/?fen=8/4n3/2 ... 0-%200%201

I am not sure what sub-optimal in terms of DTZ means here. Since the mate in 64 is completely optimal and doesn't run afoul of the 50 move rule either.

23. Kd7 and Nf5+ are equal in terms of both leading to a mate in 39. Nf5 delays the capture of the knight a bit but I am not sure it makes things harder for white. Do you believe that giving up the knight sooner rather than later makes it harder for white to win (KBB vs K vs KBB vs KN)???

Looks the other way around to me.

[bob]

I am not sure what the problem is here. I tested this position a hundred times against multiple opponents and never saw a loss or draw by any program for the winning side. The knight is captured well before the 50 move rule limit with optimal play

I don't know what you call optimal play, but black can postpone the knight's capture until the49th move.

So the position is won for white under the 50-move rule, but white needs to play carefully and merely following Nalimov might be insufficient.

I call "optimal play" playing the sequence of moves that leads to the shortest possible mate. DTZ handles the 50 move rule where DTM currently does not, of course. But here 50 move is irrelevant. If black tries to postpone the knight loss, he gets mated even quicker however.

[bob]

It is related to ignoring the 50- move rule. Even in a DTM framework you could do better. You would have to keep track of DTZ during building, though.

I only now realized how important this might be in harder (longer) wins. Out of a set of 250 hard 5-men wins I collected, about 50 were unsolved by Nalimovs. This problem should be even more pronounced with 6-men. I am surprised that Syzygy does so well comparatively, even if it theoretically lacks DTR/DTZR.

There are 5 types of positions:
- wins
- cursed wins (i.e. win but 50-move draw)
- draws
- blessed losses (i.e. loss but 50-move draw)
- losses

DTZ50 will win wins and will at least draw cursed wins, draws and blessed losses.

DTM will at least draw wins, cursed wins and draws. It may lose blessed losses and losses.

So if DTZ50 plays DTM:
- win results in win
- cursed win results in draw or win
- draw results in draw
- blessed loss results in draw
- loss results in draw or loss

Or symmetrically, if DTM plays DTZ50:
- win results in win or draw
- cursed win results in draw
- draw results in draw
- blessed loss results in draw or loss
- loss results in loss

DTZ50 v DTZ50 gives "perfect play". Once the opponent uses DTZ50, you will not be able to win a cursed win or to draw a loss.

If the opponent uses DTM, then you can hope to win a cursed win or to draw a loss.

How to play cursed wins or losses optimally is a very interesting question.

When trying to draw a lost position, the most obvious thing to do is to maximise DTZ on each move. But that is not necessarily optimal. If the current position has, say, DTZ = 50 ply, you probably won't be able to last till 101 plies. But there might be a way to force or trick the opponent into playing or allowing a pawn move after 20 ply that transitions the game into a position with DTZ = 98 ply, which gives much better chances.

Similar considerations apply to trying to win a cursed win. Cursed win means you can force a mate, but the opponent can force the path to mate to include a "phase" (between two zeroing moves) lasting more than 100 plies. Ideally you want to minimise the length of the longest phase and then minimise DTZ during that phase and hope for opponent mistakes.

Syzygy TBs store "DTZ50+". A value from 1 to 100 is the distance in plies to a zeroing move leading to a won position. A value > 100 is either the distance to a zeroing move leading to a won position or the distance plus 100 to a zeroing move leading to a cursed win. It is enough to implement the simple strategy of minimising or maximising DTZ, but it does not give "global" information, i.e. information on the length of phases after the current phase.

DTR is an attempt to encode more global information, but since its value depends on the value of the 50-move counter it is not very usable when it comes to generating practical TBs. (But dependency on the current value of the 50-move counter is unavoidable if you want "best" play against fallible opponents: if you can barely reach a zeroing move before the 50-move counter runs out, you have no room for manoeuvre. If you have plenty of moves left, then you can spend those on manoeuvring into a position with a much more promising next phase.)

Very illuminating, I had very vague clues on these issues. If my file of general 5-men wins with "perfect play" is not flawed, it seems Nalimov fails to convert in about 6% of cases with these positions at the root, which is a lot. When I selected harder wins, the percentage went to 20%. For some reasons I thought egtbs using DTM fail to convert from the root in few freak cases only.

DTM handles mate in <= 50 perfectly. For longer mates, they can lead to a draw. DTZ tries to zero the 50 move counter ASAP to avoid that problem, which generally extends the mates but makes them winnable.