Number of Different Ways to play First n Moves in Chess

From ProofWiki
Jump to navigation Jump to search

Theorem

The sequence formed from the number of ways to play the first $n$ moves in chess begins:

$20, 400, 8902, 197 \, 742, \ldots$

This sequence is A007545 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).


The count for the fourth move is already ambiguous, as it depends on whether only legal moves count, or whether all moves, legal or illegal, are included.

The count as given here does include illegal moves in addition to legal ones.


Proof

There are $20$ ways to make the $1$st move by White:

Each of the $8$ pawns may be moved either $1$ or $2$ squares forward, making $16$ moves
Each of the $4$ knights may be moved to either of $2$ squares before it, making $4$ moves.


For each of those $20$ first moves by White, Black has the same $20$ options.

Thus there are $20 \times 20$ possible different games after the $2$nd move.


To count the $3$rd moves, one needs to consider cases.

First note that after the $1$st move, whatever it was, there are $7$ pawns on the $2$nd rank, each of which can be moved $1$ or $2$ squares forward, making $14$ moves for each of those $400$ possibilities.

Note that if a knight was one of the pieces to have moved first, the pawn in the square behind where it ends up cannot move -- hence the $7$ pawns on the $2$nd rank that can move.

Thus there are $400 \times 14 = 5600$ possible moves involving a so-far unmoved pawn.

For each of the $400$ positions, there are exactly $8$ which consist of two pawns in opposition on the $4$th and $5$th rank.

There are also another $4 \times 20 = 80$ positions in which white moved a knight.

For all other $400 - 88 = 312$ positions, the already-moved pawn has the option of moving another square forward.

This gives another $312$ options for the $3$rd move.

We now need to take into account the possibility that White may be able to capture a Black pawn.



Sources