Exploring Chess Positions and Counts

Introduction

In our earlier article “How Many Chess Games are Possible?” we derived that the number of typical short chess games is around 10¹⁵¹. This turned out to be much larger than the “Shannon number” 10¹²⁰ side-note from Shanon’s remarkable 1950 paper “Programming a Computer for Playing Chess” Philosophical Magazine, Ser.7, Vol. 41, No. 314 – March 1950.

John Tromp has an interesting estimate for the number of chess positions reachable in legal games. Instead of whole games (which are long sequences of positions) he is counting individual board positions (with the caveat they must be reachable in a legal chess game). His estimate is: (4.59 +- 0.38) × 10⁴⁴ legally reachable board positions, with a 95% confidence level.

In this note we will outline an effective stand-in definition of “sensible” chess positions. That is a position that looks like it could have come from a legal game, independent of it really would or not.

Checking if a there is a game that generates a position is hard

A key element in Tromp’s estimate is doing the work to confirm if generated board positions could in fact arise in legal chess games. Checking if there exists a legal game generating a given chess board position is hard. The issue is that pieces have to get out of the way of each other, and one has a limited number of captures, pawn moves, and pawn promotions to spend in the solution. One group even exploits this to make constrained move puzzles out of chess pieces.

Sherzod Khaydarbekov’s Assassin Puzzle

This type of moving things around puzzle can be Pspace hard.

Most legal chess positions are weird

Most legal board positions have many more promoted pieces than tend to occur in actual played chess games. Tromp gives the following example of a uniformly randomly generated legal position reachable from the usual starting chess position:

Tromp example index: 2389704906374985477664262349386869232706664089

Notice the large number of clearly promoted white and black pieces. Also notice how crowded and puzzle like the position is.

Restricting to sensible positions

Positions reachable in legal games and sensible positions are different beasts. If we had an effective mechanical approximation of “sensible” we could sample sensible positions. In this note we propose one family of such definitions: positions with summaries similar to what is seen in sampled or played games.

We propose a sensible chess position should:

• Pass the Python chess package .is_valid() check. This means: one king of each color, not both kings in check, no pawns on the first or last rank, and a few other important points.
• Have a reasonable number of pieces. That is no more than 8 pawns, no more queens, rooks, knights or bishops of a given color than can be explained by starting pieces plus piece promotions.
• Have at least one piece missing for every two evident pawn promotions. This is modeling that pawns don’t leave their file without a capture.

In addition to the above we insist the board position have summary statistics compatible with what we seen from inspecting 10000 short games from “How Many Chess Games are Possible?”. Which games we inspect will affect the filter definition, and to get usable bounds we have to avoid examples of clowning games.

The example statistics we started with are:

• Number of pawn reversed files: the number of files on the board that have a black pawn in a lower rank than a white pawn in the same file. Pawns dancing around each other like this is possible, but not common. Two cooperating players could drive this number as high as 8. The largest value we observed in our games-played sample was 3.
• Number of implied white pawn promotions: The minimum number of white pawn promotions one can infer from looking at the board. For example if there are 4 white queens, then at least 3 white pawn promotions must have occurred. The largest value we observed in our games played sample was 2. They may have been many more promotions in our games, this is just the lower bound forced by observing a single board. The filter is so sensitive to the implied promotions parameter, that one may want to limit that even against evidence in the data.
• Number of implied black pawn promotions: The minimum number of black pawn promotions one can infer from looking at the board. Largest value seen was again 2.
• Number of 3 pawn files: the number of files that have 3 pawns in them. Largest number of such files observed was 3.
• Number of 4 pawn files: the number of files that have 4 pawns in them. Largest number of such files observed was 1.
• Number of 5 pawn files: the number of files that have 5 pawns in them. Largest number of such files observed was 0.
• Number of 6 pawn files: the number of files that have 6 pawns in them. Largest number of such files observed was 0.

Each of these summaries was designed to be a non-negative integer where larger is roughly more surprising. This gives us a direction for each number, and we could even consider relaxing to larger bounds to include more organized game variations.

Our idea is to consider the downward closure of all observations as a possible region of “sensible” or “reasonable” summaries. For our problem the downward closure is all non-negative integer vectors x such that we have an observation v such that x ≤ v. These summaries compete, so the closure is much smaller that the smallest axis aligned box containing all the observed summaries.

Trying our restriction filter

The sensible board position summary filter could easily be added to most chess position estimate systems. I’ll try it with the Knuth path product estimation procedure I described in an earlier note.

An example sampled sensible board position is given below.

FEN: 2R1b1R1/3P2P1/Pn1K2pb/3N4/2p5/Nb1b1pRP/2P1qk2/2R5 w – – 2 68

This position has a pawn reversal in the g-file, and is part of a legal game (PGN proof in appendix, move annotation on board from that PGN).

The number of sensible board positions

Our estimate of the number of board positions obeying the game search summary bounds is around 2 × 10⁴⁴. It helps that we have the Tromp estimate to target. This estimate is from a sample, so there is sampling uncertainty. Unfortunately the estimate currently includes positions not reachable through legal play and even some trivially illegal positions such as those with no legal previous position.

Conclusion

We propose enforcing summary bounds from observed games to get an effective board position filter. By using the downward closure filter, we hope to more fully represent possible legal games. Additional filter criteria such as not being in check too often, or having even one legal preceding position could easily be added to the method.

Appendix: The unexplained number in Shannon’s paper

In reading Shannon’s paper I was interested where another magic number came from. Shannon states, without explicit derivation, that the the probability of random moves beating a world chess champion is on the order of 10^-75 . I think we can relate that to the other estimates in Shannon’s paper. These estimates include claims of:

• 
  About 10³ possibilities for every two half moves. Taken from examining data from De Groot.
• Games lasting around 40 full moves. Likely Ibid.
• Easily 10¹²⁰ possible games. A Fermi problem estimate combining the previous two estimates as (10³)⁴⁰.
• Roughly 10⁴³ possible chess positions. From the combinatorics of shuffling chess boards. This ignores legality, captures, and promotions. However the estimate isn’t so far off as some of the estimation errors cancel each other.
• And that stand-out, quoting from the paper’s Note[6]: “probability, of the order of 10^-75, that random play would win a game from Botvinnik”. No citation, so likely derived by the author.

Plausibly the 10^-75 is another “back of the envelope” or Fermi estimate (with nice round numbers) of the form:

• Take probabilities as over the random move selection, so we model Botvinnik as being deterministic
  
• It would take about 50 best moves to beat Botvinnik.
• Each 2 such moves could be found with probability 10^-3 if chosen uniformly at random from the an assumed 10³ two half move pairs (in this case two half moves for the uniform random player, not alternating players as before).
  
• Then (10^-3)^50/2 gives us the 10^-75

This says we could consider a player that always moves randomly as having an Elo match making rating 75 * 400 = 30000 points below Botvinnik’s estimated peak Elo of 2730. This isn’t reliable as one does not expect Elo to be effective at such extraordinary ranges (and some variations such as FIDE don’t allow for scores below 100).

Appendix: Personal note

These notes have been inspired by The Chess Mysteries of Sherlock Holmes, Raymond Smullyan, 1979. Smullyan was a mathematician who amazingly translated reverse chess, lambda calculus, combinators, and Gödel sets into mass-market puzzle books! Some of my notes on these topics are here and here. Tromp also turned out to be a key source for exciting lambda calculus and combinator results.

Appendix: An unreachable board

The following sample (or “sensible” by our curent filter) board appears superficially legal (passes the Python code .is_valid() test), yet has no legal board that precedes it.

FEN: 4Bk2/4QQ2/r1pP1B1p/1p1p2rp/b4n1P/3N2bQ/3K2bp/1BnN3N b – – 0 1

Under FIDE chess rules a player can not end their turn in check. That is: the game is adjudicated a loss before any player ends their turn still in check. This will allow us to disqualify this position.

A retrograde analysis is then:

• This is not a valid chess position with white to move, as black is in check.
• This is not a valid position with black to move, as there is no preceding position where black is not in check. No move reverse move for white gets black’s king out of contact with both of the white queens.

As this is not a valid chess position either for white to move or black to move this position is not part of a legal chess game.

We should add a few more conditions- such as non-initial positions having at least one apparently valid preceding board position.

Appendix: More on our sampling procedure

Our sampling procedure works as follows.

• We pick the simultaneous number of white pieces of each type. We over specify the counts by separately counting bishops and pawns by what square color they are on. This is restricted to an achievable number of piece promotions and turns out to have 67104 possibilities.
• We independently pick the number of black pieces of each type. This is again
  67104 possibilities.
• If the two piece distributions are compatible the sense the number of captures is at least half the number of implied promotions, we continue.
• We treat the final board position as the product of five independent permutations:
  1. The pawns that are on white squares.
  2. The pawns that are on black squares.
  3. The bishops that are on white squares.
  4. The bishops that are on black squares.
  5. The rest of the pieces.

  The idea is to sample from a simpler structure (permutations) that isn’t too much larger than what we are interested in (chess positions).

  These permutations can be considered independent by renaming squares after each one. That is: each permutation works on the squares left after the previous, and the number of such left is independent of each permutation. We place pawns first as they have the restriction that they don’t place in the first and last rank. We separate the square colors pawns are on so the square counts for bishops of different colors are known independent of the detailed pawn placement.

• We then accept only boards that have summaries in the closure of observed summaries from our games sample.

This lets us estimate the number of possible such boards as the average of 67104 × 67104 × permutation_size × white_or_black_to move × accepted_or_rejected over all of our samples. For 10000000 board draw attempts the estimate of the number of possible sensible chess positions came to 2 × 10⁴⁴.

To uniformly sample board positions: we first draw samples from the earlier sequential process. We then use the Knuth path product method (mentioned in our earlier chess article) to write down a correction weight that will convert our distribution to uniform. We then sub-sample from the original draw proportional to the correction weights to get a uniform sample.

Appendix: Demonstration that the sensible example position arises from a legal game

Our example sample sensible position arises from the following game (proof written in PGN notation).

1. e3 g5 2. Bd3 g4 3. f4 Nf6 4. Qf3 gxf3 5. h4 f2+ 6. Kd1 f1=B 7. Bg6 hxg6 8. h5 e6 9. h6 Bc5 10. a4 Ke7 11. b4 Ne8 12. Bb2 Ng7 13. hxg7 Rh3 14. gxh3 a5 15. bxa5 Ra6 16. Na3 Rd6 17. Rc1 b5 18. a6 b4 19. a7 b3 20. a8=R Bc4 21. Bc3 b2 22. e4 b1=B 23. f5 Be3 24. d4 Bh6 25. a5 Rc6 26. a6 Kd6 27. fxe6 Qh4 28. e7 f6 29. e8=R Bb3 30. Rg8 Bc4 31. Rh2 Bd3 32. Rg2 Ba2 33. Rg3 Bb3 34. d5 f5 35. Bd2 f4 36. Be3 f3 37. Kd2 Ke5 38. d6 Rc5 39. Ne2 Bb7 40. Bg5 Nc6 41. Rad8 Ne7 42. Rxd7 Rd5 43. Rdd8 c5 44. Rc8 c4 45. Kc3 Bc6 46. Kb4 Be8 47. d7 Rd4 48. Rb8 Nc8 49. Kc5 Nb6 50. Rc8 Rd6 51. Be7 Bg5 52. Nf4 Rf6 53. Nd5 Bh6 54. Nc7 Kf4 55. Nd5+ Ke5 56. Nc7 Kf4 57. Na8 Ke3 58. Nc7 Kf2 59. Nd5 Qg5 60. Rb8 Qd2 61. Rc8 Qe2 62. Bxf6 Bg5 63. Kd6 Bxf6 64. Kc6 Bg5 65. Kd6 Bh6 66. Ke6 Bxe4 67. Kd6 Bd3

Categories: Computer Science Uncategorized

Tagged as: chess Combinatorics