I recently came across a github repo by John Tromp with an exceedingly simple premise: generate a bunch of random chess positions, verify whether they’re legal, and use statistics to approximate how many legal games there are. Clearly that idea has the precise simplicity and novelty to make one feel like an idiot for not having come up with it oneself. He did that with a sample of 1000 games and found a 95% confidence interval of games. Then he decided to crowdsource a sample of 10000 games, which should produce an estimate with one digit within the confidence interval. I proved that 8 of them are legal by finding games that result in the random position. It was… odd. I expected a randomly generated chess game to be weird, but I wasn’t prepared for just how weird they were going to be. I think that’s sort of like how old movies imagined aliens to be little green men. The weirdness we can up with is within the bounds of what we know. Here’s an example:
Anarchy! How many queens are there? And why does black have five knights? Anyway, the position is legal, as I found a game that produces it.
As of writing there are still 132 positions missing proofs that they’re either legal or illegal. So I encourage everyone reading to go there and try to do them. The procedure I came up with to produce the proof games is:
- Count the number of black and white pieces. Subtract those from 16 to get the number of pieces you need to capture from each side.
- Find out whether either side is missing a piece they started with, for example if they don’t have a light square bishop. If so, you have to capture that piece, otherwise capturing pawns is usually more convenient.
- If either player has more than one light square or dark square bishop, make sure you can produce it by promotion.
- Get the pawns out of each others’s ways for promotion. This is the trickiest part in my opinion. In the example above I had to preserve the white B and G pawns and the C and G black ones. I also had to make room for 5 black and 4 white promotions, and get rid of the black dark squares bishop. I had finished this step by move 11, the last capture of the game, when the board looked like this:
- Get the kings into their final positions, and if possible get the pieces around them too, so you don’t produce too many checks when getting the other.
- Do all the promotions necessary.
- Get all the pieces into position.
Edit: the 10 thousand game sample is complete. It yielded a 95% confidence interval of games.