I flunked calculus. My pathetic performance was due not to inability, but lack of time. I took the course as a junior in college when I was deep in my upper division history, political science, and education classes. I was also active in student government. I tried to do all the week's homework on Saturdays. The quizzes were every Friday. I did okay on the exams, but flunked most quizzes, and finally dropped the class after the deadline.
That was twenty-five years ago.
I bring up this history to emphasize that I am not a mathematician, but that I went far enough in school that I should understand the rudiments of algebra.
Others have calculated the exact figure I'm looking for, but instead of finding their work, I tried to estimate it myself. My rough estimate is 16 million.
Method of Calculation
Each pawn has 48 legal squares. If an enemy pawn is on the board, this number is reduced by 1.
47 x 47 = 2209
Each king has 64 legal squares. If one king is in the corner (4 squares), the other king's number must be reduced by 4. On the edge, but not a corner (24 squares) reduces the other king's number by 6. A king that is not on the edge (36 squares) reduces the other king's legal squares by 9.
4 x 60 = 240
24 x 58 = 1392
36 x 55 = 1980
240 + 1392 + 1980 = 3612
The number of possible pawn positions must be multiplied by the number of possible king positions to arrive at an upper limit.
2209 x 3612 = 7,978,908
For each position, it can be White on move or Black on move
2 x 7,978,908 = 15,957,816
Our upper limit is just under sixteen million.
This number is too high. Each placement of the pawns reduces each king's placement by 3-4 squares. Neither king may occupy the same square as a pawn. A pawn not on the edge controls two squares, while a pawn on the edge controls one. The occupied squares plus the controlled squares is usually 4, but sometimes 3.
The actual number may be several thousand below that number.
Significance
This figure of sixteen million is a subset of all four-piece endgames, all of which were calculated to completion in the creation of endgame tablebases. Most chess engines contain these tablebases as part of the package. Thus the engine will play all these positions to perfection.
Humans are another matter.
We spend years studying elementary king and pawn endgames, yet still we blow them from time to time.
Mark Dvoretsky presents the following position as one of his many tragicomedies. See Dvoretsky's Endgame Manual (2003), 14.
White to move =
White resigned.
Postscript: 5 December 2008
Eric Holcomb wrote a two-part article for Northwest Chess: "So How Many Chess Board Positions Are There?" (August 2008), 13-14, and "An Inconvenient Chessic Coincidence?" (September 2008), 22-23. I asked him to look at this post and offer critique. He noted that the first pawn has 48 squares and the second 47, so the calculation above should be
47 x 48 = 2256
That pushes the upper limit above sixteen million to 16,297,344. He also wrote an Excel macro to perform these calculations, and found the result of 14,872,176, 91.26% of the upper limit.
In practical terms--constructing tablebases or human learning of critical positions--the number of unique positions is a fraction of the nearly fifteen million Holcomb found.
David Levy and Monty Newborn explain significance of symmetry in How Computers Play Chess (1991), 141-142. They present the example of a KQK database. The black king can be placed on any of 64 squares, but only ten must be considered.
With respect to pawn endgames, symmetry would seem to reduce the number of possibilities at least three quarters.
Tragicomedy
White's resignation in the position above overlooked that even though the pawn is lost, after 1.Kd4 Kf5 2.Kd3 Ke5 3.Ke3 Kxd5 4.Kd3 White seizes the opposition and draws.
No comments:
Post a Comment