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. So we set empty=0, bP=1, wP=2, bN=3, wN=4, bB=5, wB=6, bR=7, wR=8, bQ=9, wQ=10, bK=11, wK=12.

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.

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 it's easier 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.

Download a Maple 9 worksheet that does all this benchmarking automatically, after you input a configuration.

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

Stalemate
Encoding value:17543043497050476099565
Estimated time to reach this configuration on this machine: 1.370112e+16 secs = 4.344598e+08 years

Fool's Mate
Encoding value: 160982710484073203411598150107697658831806815622730620943765052902956266
Estimated time to reach this configuration on this machine: 1.257276e+65 secs = 3.986795e+57 years

Starting Position
Encoding value: 160982710494793918338933795702781595512782442590013287680996893581323066
Estimated time to reach this configuration on this machine: 1.257276e+65 secs = 3.986795e+57 years

Draw
Encoding value: 45243109945560247691690713945961183337427228171187157454358027311245179
Estimated time to reach this configuration on this machine: 3.533489e+64 secs = 1.120462e+57 years

Notes/References

  1. This bound is of course much larger than all legal configurations. 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