You can't get there from here...

[Dann Corbit]

When I was 19, I was in the military and driving in Maine, trying to find "The Old Man In The Mountain".
I got lost and asked a local how to get there.
"You can't get there from here.", he said.
I eventually figured out that what he meant was that I was going the wrong way.
Which brings me to chess, and another kind of problem.
How many ways can we get here?
Can we know if you can't get there from here?

For instance, here is a position that would require 15 captures by the white pawns (5+4+3+2+1) in order to construct it:
[d]4k3/P7/P7/P7/P7/P7/P7/4K3 w - -
That means that if black had anything left on the board besides his king, the position would be impossible.
On the other hand, this position requires fewer captures, since the pawns could form the column from either side:
[d]4k3/4P3/4P3/4P3/4P3/4P3/4P3/4K3 w - -

Now, consider a position like this, where black is about to lose in one move, because his only legal move is Kf8, followed by mate by the rook:
[d]7k/1R6/6K1/8/8/8/8/8 b - -
In the previous ply we know the following:
The rook was not on h7 or b8, having moved to b7, because black would have been in check when it was white's turn to move.
And the white king could not have moved to g6 from h7 or g7 because black would also have been in check in those positions.
But the rook could have arrived on b7 from any other position on rank 7 or file 2.
And there could have been any black chessman except the king on b7 before the move.
Or the white king could have been on h6, h5, g5, f5, or f6 and there could have been any black chessman on g6.
So what I am wondering is:
Is there such a thing as a reverse move generator (a generator that creates every position that could have lead to this position)?
And probably much more difficult, can we know if the previous position that lead to the current was possible (possibly with assistance from the other side)?
It is kind of like retro-chess, I suppose, but I am try to find out if one ply can be generated perfectly in reverse.

[KLc]

I was thinking about exactly this problem yesterday, but maybe more about its ultimate version: is a position reachable from the starting position and how? I was testing some engines on this position
[d]8/8/2k5/3N4/8/4N1p1/4Kprp/B5bn w - - 0 1
from http://talkchess.com/forum3/viewtopic.php?f=2&t=76814 and unfortunately had some crappy engines in my pool that didn't fully implement the UCI protocol, especially the "set position fen" wasn't working. So, I thought, ok, I need to have a move sequence how to get there. It's pretty straightforward:
[pgn]
[Event "?"]
[Site "?"]
[Date "????.??.??"]
[Round "?"]
[White "?"]
[Black "?"]
[Result "*"]
[ECO "A00"]

1.a4 a5 2.b4 b5 3.c4 c5 4.d4 d5 5.e4 e5 6.axb5 axb4 7.dxc5 dxe4 8.Ra3 bxa3 9.Nxa3 Ra5 10.b6 Rxc5 11.b7 Bxb7 12.f4 Be7 13.Nb5 Bd5 14.cxd5 Rxd5 15.Nc3 f5 16.fxe5 Rxe5 17.Bb5+ Rxb5 18.Nxe4 g5 19.g3 Rb3 20.h3 Rxg3 21.Ke2 h5 22.Nc5 Rxh3 23.Nf3 Rxh1 24.Qxd8+ Bxd8 25.Bb2 f4 26.Ba1 g4 27.Nd4 h4 28.Nce6 g3 29.Kd2 f3 30.Kd3 h3 31.Kd2 Bb6 32.Nf5 Bg1 33.Nd6+ Ke7 34.Kd3 Rh2 35.Kc3 Rg2 36.Nb5 Nc6 37.Nc5 Nd4 38.Kb4 Nb3 39.Ka4 Nd2 40.Ka5 Ne4 41.Ka4 Nf2 42.Ka5 Nh1 43.Kb4 h2 44.Ne4 f2 45.Kc3 Rh6 46.Nd2 Rd6 47.Nxd6 Nf6 48.N6e4 Ke6 49.Nxf6 Kd6 50.Nde4+ Kc6 51.Kd2 Kb7 52.Ke2 Kc6 53.Nd5 Kb7 54.Ne3 Kc6 55.Nf6 Kb7 56.Nfd5 Kc6 *
[/pgn]

(It's not a good sequence, I didn't care, I just played quickly. One needs to cram in the knight on h1 early enough, I missed this on my first attempt).

Anyways, I was thinking: is there a program to do this? Obviously, mathematically proving that a given position is or is not reachable from the initial position is infeasible. But I don't care about an optimal solution—just some. I wonder if there is some NN approach to this kind of problem.

[KLc]

Apparently, Natch (http://natch.free.fr/Natch.html) is such a program.

[DrCliche]

Retrograde move generation is obviously trivial, though it's not necessary here. The difficulty lies in efficiently finding a path between any two nodes on a rather large game tree.

You should probably develop a heuristic that scores a position based on how close/similar it is to another. Material counts and move distances from target squares are the most obvious things to consider, but probably more important is pawn structure, since pawns are so immobile.

A more sophisticated idea along those lines might be to score the actual mobility of all the pieces in the terminal position (maybe scaled by piece type), and designing the heuristic in such a way that it prioritizes correctly placing the least mobile pieces.

(Or, better yet, train a neural network to score similarity for you. Feature design is so last decade!)

Anyway, with a similarity heuristic in place, you can then just implement your favorite search algorithm. Stockfish's or Leela's search should do just fine. Don't forget to delete a minus sign here or there, since black and white are now trying to maximize the same thing.

My gut tells me it should be better to have two copies of your search program running from either end at the same time (i.e. one running forward from the initial position, one running backward from the terminal position, dynamically updating each searcher's target so they meet in the middle), but I don't have a formal justification for that claim, and it sounds pretty complicated to implement.

[JohnW]

Did he tell you it was in the next state over?

[Ajedrecista]

Hello Dann:

When I was 19, I was in the military and driving in Maine, trying to find "The Old Man In The Mountain".
I got lost and asked a local how to get there.
"You can't get there from here.", he said.
I eventually figured out that what he meant was that I was going the wrong way.
Which brings me to chess, and another kind of problem.
How many ways can we get here?
Can we know if you can't get there from here?

For instance, here is a position that would require 15 captures by the white pawns (5+4+3+2+1) in order to construct it:
[d]4k3/P7/P7/P7/P7/P7/P7/4K3 w - -
That means that if black had anything left on the board besides his king, the position would be impossible.
On the other hand, this position requires fewer captures, since the pawns could form the column from either side:
[d]4k3/4P3/4P3/4P3/4P3/4P3/4P3/4K3 w - -

Now, consider a position like this, where black is about to lose in one move, because his only legal move is Kf8, followed by mate by the rook:
[d]7k/1R6/6K1/8/8/8/8/8 b - -
In the previous ply we know the following:
The rook was not on h7 or b8, having moved to b7, because black would have been in check when it was white's turn to move.
And the white king could not have moved to g6 from h7 or g7 because black would also have been in check in those positions.
But the rook could have arrived on b7 from any other position on rank 7 or file 2.
And there could have been any black chessman except the king on b7 before the move.
Or the white king could have been on h6, h5, g5, f5, or f6 and there could have been any black chessman on g6.
So what I am wondering is:
Is there such a thing as a reverse move generator (a generator that creates every position that could have lead to this position)?
And probably much more difficult, can we know if the previous position that lead to the current was possible (possibly with assistance from the other side)?
It is kind of like retro-chess, I suppose, but I am try to find out if one ply can be generated perfectly in reverse.

R.I.P. 'The Old Man in the Mountain'. I would have said Natch too, despite not tested it before. There are other tools listed at the retrograde analysis article of the CPW: Euclide (unknown for me), Freezer (well known) and Retractor (unknown for me).

I have tried your first position without success, being short of one capture to leave all the six pawns on the a file. Here are my two best tries:

[pgn][Event "?"]
[Site "?"]
[Date "?"]
[Round "?"]
[White "?"]
[Black "?"]
[Result "1/2-1/2"]
[ECO "?"]
[Annotator "?"]
[PlyCount "99"]
[EventDate "?"]
[TimeControl "?"]
1. Nc3 e5 2. Nd5 Ba3 3. bxa3 Ne7 4. Nf6+ gxf6 5. g4 Ng8
6. g5 Ne7 7. g6 hxg6 8. Bh3 Ng8 9. Be6 fxe6 10. Rb1 Ne7
11. Rb5 Ng8 12. Rd5 exd5 13. h4 Ne7 14. Nf3 Ng8 15. Nh2 Ne7
16. Ng4 Ng8 17. Ne3 Ne7 18. Nc4 dxc4 19. Bb2 Ng8 20. Bd4 exd4
21. Rg1 d3 22. exd3 Ne7 23. dxc4 Ng8 24. Rg5 Ne7 25. Rf5 gxf5
26. h5 Rg8 27. h6 Rh8 28. h7 Rg8 29. h8=Q Nbc6 30. Qe2 Nb8
31. Qe5 fxe5 32. Qh4 Rh8 33. Qe4 fxe4 34. Ke2 d5 35. Ke1 e3
36. fxe3 d4 37. exd4 c5 38. dxc5 b6 39. cxb6 Bd7 40. bxa7 Bb5
41. cxb5 Na6 42. bxa6 Qa5 43. Ke2 Qc3 44. dxc3 Rh4 45. Ke1 Rb4
46. cxb4 Nc6 47. Ke2 Na5 48. bxa5 Rb8 49. Ke1 Rb3 50. cxb3

[Event "?"]
[Site "?"]
[Date "?"]
[Round "?"]
[White "?"]
[Black "?"]
[Result "1/2-1/2"]
[ECO "?"]
[Annotator "?"]
[PlyCount "105"]
[EventDate "?"]
[TimeControl "?"]
1. Nc3 e5 2. Nd5 Ba3 3. bxa3 Ne7 4. Nf6+ gxf6 5. g4 Ng8
6. g5 Ne7 7. g6 hxg6 8. Bh3 Ng8 9. Be6 fxe6 10. Rb1 Ne7
11. Rb5 Ng8 12. Rd5 exd5 13. h4 Ne7 14. Nf3 Ng8 15. Nh2 Ne7
16. Ng4 Ng8 17.Ne3 Ne7 18. Nc4 dxc4 19. Bb2 Ng8 20. Bd4 exd4
21. Rg1 Ne7 22. Rg5 Ng8 23. Rf5 gxf5 24. Qb1 Ne7 25. Qb5 Ng8
26. Qe5+ fxe5 27. h5 Ne7 28. h6 Rg8 29. h7 Nbc6 30. h8=Q Nb8
31. Qh4 d3 32. exd3 Rh8 33. dxc4 b5 34. cxb5 a6 35. bxa6 Ng8
36. Qe4 fxe4 37. Ke2 e3 38. fxe3 d5 39. Ke1 d4 40. exd4 c5
41. dxc5 Qb6 42. cxb6 Ra7 43. bxa7 Be6 44. Ke2 Bb3 45. cxb3 Nd7
46. Ke1 Nc5 47. Ke2 Na4 48. bxa4 Rh3 49. Ke1 Rc3 50. dxc3 Ne7
51. Ke2 Nc6 52. Ke1 Nb4 53. cxb4[/pgn]

Regards from Spain.

Ajedrecista.

[Dann Corbit]

R.I.P. 'The Old Man in the Mountain'.

I am glad I got to see it before it fell.

[Uri Blass]

Hello Dann:

When I was 19, I was in the military and driving in Maine, trying to find "The Old Man In The Mountain".
I got lost and asked a local how to get there.
"You can't get there from here.", he said.
I eventually figured out that what he meant was that I was going the wrong way.
Which brings me to chess, and another kind of problem.
How many ways can we get here?
Can we know if you can't get there from here?

For instance, here is a position that would require 15 captures by the white pawns (5+4+3+2+1) in order to construct it:
[d]4k3/P7/P7/P7/P7/P7/P7/4K3 w - -
That means that if black had anything left on the board besides his king, the position would be impossible.
On the other hand, this position requires fewer captures, since the pawns could form the column from either side:
[d]4k3/4P3/4P3/4P3/4P3/4P3/4P3/4K3 w - -

Now, consider a position like this, where black is about to lose in one move, because his only legal move is Kf8, followed by mate by the rook:
[d]7k/1R6/6K1/8/8/8/8/8 b - -
In the previous ply we know the following:
The rook was not on h7 or b8, having moved to b7, because black would have been in check when it was white's turn to move.
And the white king could not have moved to g6 from h7 or g7 because black would also have been in check in those positions.
But the rook could have arrived on b7 from any other position on rank 7 or file 2.
And there could have been any black chessman except the king on b7 before the move.
Or the white king could have been on h6, h5, g5, f5, or f6 and there could have been any black chessman on g6.
So what I am wondering is:
Is there such a thing as a reverse move generator (a generator that creates every position that could have lead to this position)?
And probably much more difficult, can we know if the previous position that lead to the current was possible (possibly with assistance from the other side)?
It is kind of like retro-chess, I suppose, but I am try to find out if one ply can be generated perfectly in reverse.

R.I.P. 'The Old Man in the Mountain'. I would have said Natch too, despite not tested it before. There are other tools listed at the retrograde analysis article of the CPW: Euclide (unknown for me), Freezer (well known) and Retractor (unknown for me).

I have tried your first position without success, being short of one capture to leave all the six pawns on the a file. Here are my two best tries:

[pgn][Event "?"]
[Site "?"]
[Date "?"]
[Round "?"]
[White "?"]
[Black "?"]
[Result "1/2-1/2"]
[ECO "?"]
[Annotator "?"]
[PlyCount "99"]
[EventDate "?"]
[TimeControl "?"]
1. Nc3 e5 2. Nd5 Ba3 3. bxa3 Ne7 4. Nf6+ gxf6 5. g4 Ng8
6. g5 Ne7 7. g6 hxg6 8. Bh3 Ng8 9. Be6 fxe6 10. Rb1 Ne7
11. Rb5 Ng8 12. Rd5 exd5 13. h4 Ne7 14. Nf3 Ng8 15. Nh2 Ne7
16. Ng4 Ng8 17. Ne3 Ne7 18. Nc4 dxc4 19. Bb2 Ng8 20. Bd4 exd4
21. Rg1 d3 22. exd3 Ne7 23. dxc4 Ng8 24. Rg5 Ne7 25. Rf5 gxf5
26. h5 Rg8 27. h6 Rh8 28. h7 Rg8 29. h8=Q Nbc6 30. Qe2 Nb8
31. Qe5 fxe5 32. Qh4 Rh8 33. Qe4 fxe4 34. Ke2 d5 35. Ke1 e3
36. fxe3 d4 37. exd4 c5 38. dxc5 b6 39. cxb6 Bd7 40. bxa7 Bb5
41. cxb5 Na6 42. bxa6 Qa5 43. Ke2 Qc3 44. dxc3 Rh4 45. Ke1 Rb4
46. cxb4 Nc6 47. Ke2 Na5 48. bxa5 Rb8 49. Ke1 Rb3 50. cxb3

[Event "?"]
[Site "?"]
[Date "?"]
[Round "?"]
[White "?"]
[Black "?"]
[Result "1/2-1/2"]
[ECO "?"]
[Annotator "?"]
[PlyCount "105"]
[EventDate "?"]
[TimeControl "?"]
1. Nc3 e5 2. Nd5 Ba3 3. bxa3 Ne7 4. Nf6+ gxf6 5. g4 Ng8
6. g5 Ne7 7. g6 hxg6 8. Bh3 Ng8 9. Be6 fxe6 10. Rb1 Ne7
11. Rb5 Ng8 12. Rd5 exd5 13. h4 Ne7 14. Nf3 Ng8 15. Nh2 Ne7
16. Ng4 Ng8 17.Ne3 Ne7 18. Nc4 dxc4 19. Bb2 Ng8 20. Bd4 exd4
21. Rg1 Ne7 22. Rg5 Ng8 23. Rf5 gxf5 24. Qb1 Ne7 25. Qb5 Ng8
26. Qe5+ fxe5 27. h5 Ne7 28. h6 Rg8 29. h7 Nbc6 30. h8=Q Nb8
31. Qh4 d3 32. exd3 Rh8 33. dxc4 b5 34. cxb5 a6 35. bxa6 Ng8
36. Qe4 fxe4 37. Ke2 e3 38. fxe3 d5 39. Ke1 d4 40. exd4 c5
41. dxc5 Qb6 42. cxb6 Ra7 43. bxa7 Be6 44. Ke2 Bb3 45. cxb3 Nd7
46. Ke1 Nc5 47. Ke2 Na4 48. bxa4 Rh3 49. Ke1 Rc3 50. dxc3 Ne7
51. Ke2 Nc6 52. Ke1 Nb4 53. cxb4[/pgn]

Regards from Spain.

Ajedrecista.

Here is my first try(second try used your shorter game that is the beginning of a solution and is shorter)

[pgn][Event "Computer chess game"]
[Site "DESKTOP-7QE6S12"]
[Date "2021.03.15"]
[Round "?"]
[White "àåøé"]
[Black "àåøé"]
[Result "*"]
[BlackElo "2400"]
[ECO "A00"]
[Opening "Benko Opening"]
[Time "03:44:25"]
[WhiteElo "2400"]
[TimeControl "3600+20"]
[Termination "unterminated"]
[PlyCount "138"]
[WhiteType "human"]
[BlackType "human"]

1. g3 Nc6 2. Bh3 Nb8 3. Bf5 Nc6 4. Bg6 hxg6 5. Nf3 Na5 6. Nh4 Nc4 7. Nf5
gxf5 8. O-O Ne3 9. fxe3 Rh7 10. Rf4 Rh8 11. Re4 Rh7 12. Re6 Rh8 13. Rf6
gxf6 14. Nc3 f4 15. Nb1 f3 16. Nc3 f2+ 17. Kg2 d5 18. Kf3 d4 19. Ke4 f1=Q
20. exd4 f5+ 21. Ke5 Qf3 22. Nb1 Qd3 23. exd3 Rxh2 24. Kf4 c5 25. dxc5 b6
26. cxb6 Rh3 27. bxa7 Ba6 28. Nc3 Bc4 29. dxc4 Nf6 30. Ke3 f4+ 31. Ke2 fxg3
32. Nb1 Bg7 33. Na3 Nd7 34. Nb1 Bc3 35. dxc3 g2 36. Qd5 g1=Q 37. Bf4 Qc5
38. Nd2 Qb5 39. cxb5 Rh6 40. Rf1 Ra6 41. bxa6 Qa5 42. Re1 Qb4 43. cxb4 Rb8
44. Rg1 Rb5 45. Rg5 Rxd5 46. Rf5 Rxf5 47. Be5 Rxe5+ 48. Kf2 Rd5 49. Kf3
Rxd2 50. Kg3 Rd5 51. Kf3 Ra5 52. bxa5 Nc5 53. Ke2 Nb3 54. cxb3 e5 55. Kd2
e4 56. Kc2 e3 57. Kc3 e2 58. Kc2 e1=Q 59. Kd3 Qb4 60. Kc2 Qa4 61. bxa4 f5
62. Kc3 f4 63. Kc2 f3 64. Kc3 f2 65. Kc2 f1=Q 66. Kd2 Qh3 67. Kd1 Qa3 68.
bxa3 Kd8 69. Ke1 Ke8 *
[/pgn]

[pgn][Event "?"]
[Site "?"]
[Date "?"]
[Round "?"]
[White "?"]
[Black "?"]
[Result "1/2-1/2"]
[BlackElo "2400"]
[ECO "A00"]
[Opening "Dunst (Sleipner-Heinrichsen-Van Geet) Opening"]
[Variation "1...e5"]
[WhiteElo "2400"]
[TimeControl "600"]
[Termination "normal"]
[PlyCount "114"]
[WhiteType "human"]
[BlackType "human"]

1. Nc3 e5 2. Nd5 Ba3 3. bxa3 Ne7 4. Nf6+ gxf6 5. g4 Ng8 6. g5 Ne7 7. g6
hxg6 8. Bh3 Ng8 9. Be6 fxe6 10. Rb1 Ne7 11. Rb5 Ng8 12. Rd5 exd5 13. h4 Ne7
14. Nf3 Ng8 15. Nh2 Ne7 16. Ng4 Ng8 17. Ne3 Ne7 18. Nc4 dxc4 19. Bb2 Ng8
20. Bd4 exd4 21. Rg1 d3 22. exd3 Ne7 23. dxc4 Ng8 24. Rg5 Ne7 25. Rf5 gxf5
26. h5 Rg8 27. h6 Rh8 28. h7 Rg8 29. h8=Q Nbc6 30. Qe2 Nb8 31. Qe5 fxe5 32.
Qh4 Rh8 33. Qe4 fxe4 34. Ke2 d5 35. Ke1 e3 36. fxe3 d4 37. exd4 c5 38. dxc5
b6 39. cxb6 Bd7 40. bxa7 Bb5 41. cxb5 Na6 42. bxa6 Qa5 43. Ke2 Qc3 44. dxc3
Rh4 45. Ke1 Rb4 46. cxb4 Nc6 47. Ke2 Na5 48. bxa5 Rb8 49. Ke1 Rb3 50. cxb3
e4 51. Kd1 e3 52. Kc2 e2 53. Kb2 e1=Q 54. Kc2 Qb4 55. Kd1 Qa4 56. bxa4 Kd8
57. Ke1 Ke8 1/2-1/2
[/pgn]

[Dann Corbit]

Incredible, Uri.
I was always one square away when I tried it.

[Ajedrecista]

Hello:

How could I be so blind to not queen the pawn in my solution? Thank you Uri for finishing the job.

I tried Natch 3.3 (64-bit Windows) to get the shortest proof game (or one of them if there are more with the same number of moves) but it seems unfeasible for me. Setting 2 GB of hash in my system, I get the following solution times (or lack of solutions):

Code: Select all

Plies   Time (s)   Solutions found
  28       0.00           0
  29       0.46           0
  30       1.23           0
  31       1.37           0
  32       3.32           0
  33       3.95           0
  34       9.73           0
  35      29.10           0
  36      71.61           0
  37      71.78           0
  38     170.43           0

Uri's solution has got 57 full moves = 114 plies. OTOH, we finally found that you could get there from here!

Regards from Spain.

Ajedrecista.