Skip to main content
1 of 2
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

I count $173558929221226891302430767615551561533417485504 = 1.7356 \times 10^{47}$ ways to place a legal collection of chessmen on the board. Of these, $24639467089379915386890365075260915223928803040 = 2.4639 \times 10^{46}$ have no pawns on the first or last ranks, so at most $14.2\%$ of ways to place a legal collection of chessmen on the board produce a legal position. It is likely that improvements would find more significant restrictions on the set of legal positions.

It takes some effort to determine the possible collections of legal chessmen. ("Chessmen" includes pawns. "Piece" technically refers to a non-pawn.) For example, if White has 8 pawns, 2 bishops, 2 knights, and a king, then it is not possible for Black to have 4 pawns, 3 queens, 4 rooks, 2 bishops, 2 knights, and a king. However, Black could have 4 pawns, 3 queens, 4 rooks, 2 bishops, 1 knight, and a king. If White still has 8 pawns, then each promotion of a Black pawn can be paired with a capture for one side or the other, and in the first collection there were at least 4 promotions and at most 3 captures.

I started by finding the possible vectors of opposed pawns, unopposed pawns, and original pieces not counting kings for each side. Call a pawn opposed if it has not moved from its original column, and neither has the opponent's pawn in that column. Each side starts with $8$ opposed pawns, $0$ unopposed pawns, and $7$ original pieces. Moves include $(-2,+2,0,-2,+1,0)$, which occurs when a White opposed pawn captures a Black opposed pawn, which converts $2$ White opposed pawns into unopposed pawns, and converts $1$ Black pawn into an unopposed pawn. There are $17932$ possible vectors of opposed pawns, unopposed pawns, and original pieces.

Next, convert each vector into the possible vectors of pawns, promotions, and captures. Each unopposed pawn can promote or stay a pawn. Convert each vector of pawns, promotions, and captures into the possible vectors of pawns, knights, bishops, rooks, queens, and king for each side. I used a hash table to avoid duplicates, since the same vector of counts may occur from different numbers of promoted pawns. Count how many ways there were to place these chessmen on the board, and how many ways there were under the restriction that the pawns have to be placed within the $48$ squares in the second through seventh ranks. I used C# with a big integer package. The computation took $2$ hours $34$ minutes on a $2$ GHz processor.

The $14.2\%$ value from restricting pawns to $3/4$ of the board indicates that typical positions of legal sets of chessmen have many pawns, about $\log .142/\log .75 \sim 7$, which is not obvious because there are many ways a pawn could underpromote or could be captured. Perhaps one could get a better restriction by keeping track of pairs of opposed pawns, which have to be in their original columns in order. This would add a lot of complexity to the bookkeeping, but it would produce a severe restriction for collections of chessmen which can only occur with a pair of opposed pawns still in their original column, perhaps trimming a few percent off of the $14.2\%$.

Douglas Zare
  • 28k
  • 6
  • 90
  • 130