# Calculate the first N unknown moves of a chess game

Greetings fellow chess friends,

Here is a quick idea that came to my mind.

I am interested in writing a software that is able to calculate and/or guess the first `n` unknown moves of a given chess game. For example take this game:

1. ?? ??
2. ?? ??
3. Nf3 b6
4. g3 Ba6
5. Nbd2 Bb4
6. a3 Bxd2+
7. Nxd2 Bb7
8. Nf3 d5
9. cxd5 Bxd5
10. Bg2 O-O
11. O-O Nbd7
12. Bf4 c5
13. dxc5 1/2-1/2

You don't know the first two moves. Would it be possible to "calculate" them from the rest of the game and if yes, with what certainty? For example the move `9. cxd5` implies that a pawn has been placed on c4 earlier during the game.

Do you think this would be possible and if yes, for what maximum amount `n` of unknown moves?

Cheers

(Edit: corrected the 8th move, but need 6 characters to edit)

• If it's a recorded game, then you can match the known part to a chess database -- that should filter out lots of possibilities – jf328 Aug 12 '16 at 14:44
• In addition to the comments below, you might be interested in the notion of a Proof Game : find the (unique!) way to reach a given position in a given number of moves. The first example at janko.at/Retros/Glossary/ShortestProofGame.htm is a perfect introductory puzzle: Start with a standard starting position and then remove the WNg1, the Bng8, the Bpd7 and the Bpe7. This is the position after Black's fourth move; how did the game go? Note that even in just four moves there's a remarkably clever little secret hidden in the position... – Steven Stadnicki Aug 12 '16 at 18:18
• It might be possible to make a program to deduce from the previous moves the position of the board before the moves are known(in this example it is move 3), then it could solve it like a retrograde analysis problem. Example: 3: Nf4. The computer could try to attempt all the possible knight routes that bring the knight there, in this case there is only 1, the computer could make more and more deduction on the position like this. It could also deduce what piece cannot have moved by elimination, thus knowing it's position – Ariana Aug 13 '16 at 15:42

Well, this should be semi-simple for a computer, at least. We know with absolute certainty that there are only 20 possible moves for both black and white (pawns and knights) on the first turn. After that, the only possible moves are moving the piece moved again, moving another pawn or knight, or moving a piece freed by the first move.

Knowing this, we can calculate the number of possible board positions after two turns. Luckily this has already been done here:

There are 400 possible chess positions after two ply moves (first ply move for White followed by first ply move for Black). There are 5,362 possible positions (White’s second ply move) or 8,902 total positions after two ply moves each. There are 71,852 possible positions or 197,742 total positions after four moves.

This is a LOT, but it is possible to at least guess which one was used in the game.

The method I propose is to go though all of the movements of the game after the first four, but starting with the default chessboard as if the game had only just started. If a move occurs which is impossible, this indicates that this move has been made by a piece moved in the first two turns.

Despite this, there could be cases where a pawn moved on white's first turn and a pawn moved on white's third turn can take the same piece. If white takes with the pawn moved on the first turn, there would be no way to spot this, since you would assume the pawn moved on the third turn was used.

Sorry that this is only a half-answer; I will try to find more information to improve this.

• Thank you very much for your answer! Some interesting points you make there. Obviously, if only the first move is unknown, it should be pretty easy to calculate it. But with growing number of unknown moves it gets incresingly difficult, it would be interesting to know what is the maximum number of unknown moves before it gets incalculable... – Adrenaxus Aug 12 '16 at 9:09
• I suppose you could also work through the game backwards from checkmate, however this would only work if the games were recorded using chess notation which includes the square the piece is on and where it moves/takes. If it used PGN, where the origin square is only recorded when multiple pieces are eligible for the move, this would also be impossible. – Aric Aug 12 '16 at 9:14

The way I see it, there's no way to know for certain which order the moves were played in. For example, in the game you listed, it's not difficult to determine what the moves are. Following Aric Fowler's method, d4 and c4 for white and Nf6 and e6 for black are the moves. As for the order, however, there are four combinations:

1. d4 Nf6
2. c4 e6

1. d4 e6
2. c4 Nf6

1. c4 Nf6
2. d4 e6

1. c4 e6
2. d4 Nf6

Obviously, case 1 is the most likely, assuming the players know and follow basic opening theory, but I don't think there's any way to determine the order for sure.

• Point taken, its impossible to know in which order the first two moves were in, unless they moved the same piece twice. – Aric Aug 12 '16 at 14:45
• I had a derp moment there, ignore my edits. – Aric Aug 12 '16 at 14:50
• oops i messed up the numbering, sorry – Aric Aug 12 '16 at 14:50