4

The challenge is to create the longest list of half moves whereby an AI could re-create that list of moves perfectly only given the ending board state and the number of moves.

As example I will first give a short example that does NOT work.

[FEN ""]
1. a3 a6 2. b3 

From that final board state, it is impossible to differentiate it from 1. b3 a6 2. a3

And a short example that DOES work

[FEN ""]
1. a3 a6 2. a4 a5 

There is no way to get this board state in exactly 2 moves other than what was done here.

Scoring will work as follows 1. +1 point per move 2. +5 points if the game is complete (the last move in the sequence is a check mate)

My best solution so far is

[FEN ""]
1. a4 h5 2. a5 h4 3. a6 h3 4. axb7 hxg2 5. Rxa7 Rxh2 6. Rxa8 Rxh1 7. Rxb8 Rxg1 8. Rxc8 Rxf1 

This would score 21 points: 1 point for each of the 16 moves plus 5 points for ending in a checkmate for black.

Note: opening pawns moving 2 spaces instead of one is necessary in this particular solution. A 9 turn game where the pawns each move one space per turn would be undifferentiated from an identical game where pawns open with the two space move and then rooks spend an extra turn making their first capture. Also, the game cannot be extended by slipping in Bxg2 at any point in time for white, because it would be unclear, when looking back, when such a move had occurred, since there are several possible turns for such a move to occur.

  • mmm, no, for the same reason we can't slip in the bishop move. There's no way to know on precisely which move it happened – jbernard3396 Apr 29 at 15:17
  • yep, its possible we could slip in Na6 for black before the white rook moves a7. Then the sequence for white would be Rxa6, Rxa7, Rxa8. I'd have to consider that some more, though to be sure it works – jbernard3396 Apr 29 at 15:21
  • 1
    This seems related to the concept of the "shortest proof game" from retrograde chess. – RemcoGerlich Apr 29 at 15:29
  • 1
    You have (re-invented) the "shortest proof game genre" (aka "unique proof game")! Congratulations! You also have an intuition for the kind of thinking required. There are currently 2462 computer validated proof games in PDB. pdb.dieschwalbe.de/overview.jsp. Type: k='unique proof game' and cplus and not G='Fairies', taking care with the quote characters – Laska Apr 30 at 14:36
4

The current length record is an astounding 57.5 moves (115 half-moves):

[Title "Pronkin & Frolkin, PG In 57.5, Die Schwalbe, 1989, Prize"]
[FEN ""]

1. a4 h5 2. a5 h4 3. a6 h3 4. axb7 hxg2 5. h4 d5 6. h5 d4 7. h6 d3 8. h7 dxc2 9. d4 a5 10. Bh6 c1=R 11. e4 Rc5 12. Ne2 Rh5 13. e5 c5 14. e6 Nc6 15. b8=R a4 16. Rb4 a3 17. Ra4 c4 18. b4 c3 19. b5 c2 20. b6 c1=R 21. b7 Rc4 22. b8=R Qa5+ 23. Rbb4 Bb7 24. Nbc3 O-O-O 25. exf7 e5 26. Rc1 Bc5 27. f8=R a2 28. Rf3 a1=R 29. Na2 g1=R 30. Rfa3 Rg6 31. f4 Re6 32. f5 g5 33. f6 g4 34. f7 g3 35. f8=R g2 36. Rf5 g1=R 37. Bf8 Rg7 38. Ng3 e4 39. Bd3 e3 40. O-O e2 41. Rcc3 e1=R 42. Bc2 R1e3 43. d5 Rdd7 44. d6 Rdf7 45. d7+ Kb8 46. Qd6+ Ka8 47. Qc7 Nge7 48. d8=R+ Nc8 49. Rdd3 Rhg8 50. h8=R Rae1 51. Rh6 R1e2 52. R1f2 Rce4 53. Kf1 Bd4 54. Rfc5 Ne5 55. Nf5 Nc4 56. Nd6 Nb2 57. Rbc4 Nb6 58. Qb8+

This length record was reportedly beaten in 2017 by Pronkin, Frolkin and Keym (to 58.5 moves) but unfortunately it turned that the longer problem had more than one solution. I do not know if the authors managed to make the problem sound.

Although this problem is not computer-checked, it has withstood human testing for 41 years, so it might as well be considered computer checked by the greatest computer of them all-the human mind.

| improve this answer | |
  • You're right, didn't notice the requirement on 'AI'. It's a weird requirement, because there's is absolutely no AI in proof game solving programs ! I guess the user meant "computer program". – Étienne Apr 30 at 12:34
3

Such a sequence of moves, where there is only one way to reach the given position on the given number of moves, are called Shortest Proof Games. There are many chess programs that solve such problems.

Long chess problems like this are usually checked with computers using these specially built chess programs, i.e. they are the A.I. that finds the solution you speak of in your answer. The longest one I know of that is computer checked and verified, often shortened to C+, is *41.5 moves*** long according to the Die Schwalbe database.

[Title "Nicolas Dupont, PG In 41.5, FIDE Olympic Tourney 39 Khanty-Mansiysk, 2010, 3rd Prize,"]
[FEN ""]

1. e4 d5 2. e5 d4 3. e6 d3 4. exf7+ Kd7 5. a4 e5 6. a5 e4 7. a6 e3 8. axb7 e2 9. Ra6 exd1=B 10. Rb6 a5 11. h4 a4 12. h5 a3 13. h6 a2 14. hxg7 Ba3 15. f8=B a1=N 16. Bb4 c5 17. Rhh6 Kc7 18. Rhd6 h5 19. g4 h4 20. g5 Rh5 21. g6 Nh6 22. g8=B Nb3 23. g7 Nxd2 24. Bb3 Ne4 25. g8=N Nf6 26. Kd2 h3 27. Kc3 h2 28. Kc4 h1=B 29. Be1 d2 30. c3 Bc2 31. Ne7 Bh7 32. Nf5 d1=R 33. Ng3 Bcf5 34. f4 Nbd7 35. b8=N Qc8 36. Nc6 Qb7 37. Nb4 Bc6 38. Nh1 Rd5 39. Bd1 Kb8 40. b3 Bb2 41. Nc2 Ra3 42. Na1

By your system, this problem has a score of 83 points.

The longest computer-checked one ending in checkmate that I know of is worth 59 points, 54 for the moves and 5 for the mate.

[Title "Silvio Baier, Die Schwalbe 4/24/2010"]
[FEN ""]

1. h4 a5 2. h5 Ra6 3. Rh4 Rg6 4. hxg6 h5 5. Rc4 h4 6. g4 h3 7. Bg2 h2 8. Bc6 Rh3 9. Bb5 Rb3 10. axb3 Nf6 11. Raa4 Ne4 12. Rab4 a4 13. d3 a3 14. dxe4 a2 15. Qd5 a1=R 16. Nd2 Ra8 17. Ba6 h1=R 18. Qa5 d5 19. Nf1 d4 20. Nf3 d3 21. Nd4 Rh8 22. f3 d2+ 23. Kf2 d1=N+ 24. Kg3 Ne3 25. g5 Nf5+ 26. Kg4 Nh6+ 27. Kh5 Ng8#

Also, your proof game in 8 moves is computer-verified by Jacobi.

enter image description here

| improve this answer | |
  • Just for clarification. Is this human-composed and computer-checked or computer-composed and computer-checked? – user1583209 Apr 29 at 16:06
  • 1
    @user1583209 The problem is human-composed and computer-checked. – Rewan Demontay Apr 29 at 16:10
  • Impressive. I get a headache just thinking about much simpler problems of this type. – user1583209 Apr 29 at 16:24
  • 1
    @jbernard3396 You are in correct-they are computer verified meaning that there is one solution only, which is the given one, and it is possible to know-it just takes lots of effort. – Rewan Demontay Apr 29 at 20:04
  • 1
    Hmm, turns out I forgot to check for check in both cases. – jbernard3396 Apr 29 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.