Every Chess Configuration

This page is based on the idea of Every Icon Project, John F. Simon. This reference was given to the author by Johan E. Mebius, so the author's thanks go to him.

The legal chessboard configurations are bounded above by all chessboard configurations t (legal & illegal). A simple counting argument shows that t = 1364, since we have the 6 possible values for a piece (P,N,B,R,Q,K), 2 possible colors for a piece (B,W) and an empty square. We have a total of 64 squares, so the total number of configurations is (2*6+1)64=1364[1].

We next choose an encoding for the chessboard configuration. The most natural choice is the chessboard being a base-13 word of maximum length 64. If we now write a simple program which runs from 0 to t-1, the program will eventually display all chessboard configurations, hence necessarily all legal configurations as well.

The program will start with an empty board and end with a board full of white Kings and then the cycle will repeat. Before it repeats, it will pass through every possible legal chess configuration, which means that it will eventually display all chessboard positions of every possible game, including not only all the games that were ever played, but also all the games that will ever be played.

A Maple 9 classic worksheet can display all possible chessboard configurations. Obviously you won't live long enough to see most interesting configurations appear (the entire human race or even the universe may be extinct by then), so the program is slightly modified to just bench-mark your machine so you can input a specific configuration and see how long it will take for this configuration to appear on your machine and with your version of Maple. Just modify one of the existent configurations and run the entire sheet.

Here are the timing results for some chessboard positions on the author's machine[2].

chess starting position
Estimated time to reach this configuration on this machine: 3.401570e+65 secs = 1.078631e+58 years

check mate position
Estimated time to reach this configuration on this machine: 2.849663e+65 secs = 9.036222e+57 years

stalemate position
Estimated time to reach this configuration on this machine: 3.706851e+16 secs = 1.175435e+09 years

draw position
Estimated time to reach this configuration on this machine: 9.559885e+64 secs = 3.031420e+57 years

Notes/References

  1. On page 78 of book "Computers, chess and long-range planning" by three-time World Chess Champion Mikhail Botvinnik, the author mentions estimates for an upper bound for all legal chess configurations, given by Krinitskii as ~1.6*1055 and by Claude Shannon as ~1043, both of which are (correctly) less than t=1364~1071.3, given above, which is the total number of configurations (legal and illegal).
  2. Chessboard configurations are made with Apronus' The Online Chess Diagram Editor.

Back to Mathematics

Web Analytics

Valid HTML 4.01 Transitional