Chess is a two-player board game believed to have been played in India as early as the sixth century AD . In different parts of this world, different chess games
are played. The most played variants are western chess, Shogi
(in Japan), and Xiangqi (in China).
The western version of chess is a game played on an board, called a chessboard,
of alternating black and white squares. Pieces with different types of allowed moves
are placed on the board, a set of black pieces in the first two rows and a set of
white pieces in the last two rows. The pieces are called the bishop (2), king (1),
knight (2), pawn (8), queen (1), and rook (2). The object of the game is to capture
the opponent's king.
Hardy (1999, p. 17) estimated the number of possible games of chess as . In
a game of 40 moves, the number of possible board positions is at least
according to Peterson (1996). However, this
value does not agree with the possible positions given
by Beeler et al. (1972), which was obtained by estimating the number of pawn
positions (in the no-captures situation, this is ), multiplying
by the possible positions for all pieces, then dividing by two for each of the (rook,
knight) pairs that are interchangeable, and dividing by two for each pair of bishops
(since half the positions will have the bishops on the same color squares). (However,
note that there are more positions with one or two captures, since the pawns can
then switch columns; Schroeppel 1996.) Shannon (1950) gave the estimate
Rex Stout's fictional detective Nero Wolfe quotes the number of possible games after ten moves as follows: "Wolfe grunted. One hundred and sixty-nine million, five
hundred and eighteen thousand, eight hundred and twenty-nine followed by twenty-one
ciphers. The number of ways the first ten moves, both sides, may be played"
(Stout 1983). To be precise, the number of distinct chess positions after moves for , 2, ... are
20, 400, 5362, 71852, 809896?, 9132484?, ... (Schwarzkopf 1994, Sloane's A019319). The number of chess games that end in exactly moves (including games that mate in fewer than plies) for , 2, 3, ... are 20, 400, 8902, 197742, 4897256, 120921506, 3284294545,
... (K. Thompson, Sloane's A006494).
Cunningham (1889) incorrectly found 197299 games and 71782 positions after the fourth move. C. Flye St. Marie was the first to find the correct number of positions after
four moves: 71852. Dawson (1946) gives the source as Intermediare des Mathematiques
(1895), but K. Fabel writes that Flye St. Marie corrected the number 71870 (that
he found in 1895) to 71852 in 1903. The history of the determination of the chess
sequences is discussed in Schwarzkopf (1994).
The analysis of chess is extremely complicated due to the many possible options at each move. Steinhaus (1999, pp. 11-14), as well as many entire books, consider clever end-game positions which may be analyzed completely.
Two problems in recreational mathematics ask the questions
1. How many pieces of a given type can be placed on a chessboard without any two attacking?
2. What is the smallest number of pieces needed to occupy or attack every square?
The answers are given for the usual chessboard in the following table (Madachy 1979).
Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York:
Dover, pp. 124-127, 1987.
Beeler, M. et al. Item 95 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239,
p. 35, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/proposed.html#item95.
"The Chess Variant Pages." http://www.chessvariants.com/.
Culin, S. "Tjyang-keui--Chess." §82 in Games of the Orient: Korea, China, Japan. Rutland, VT:
Charles E. Tuttle, pp. 82-91, 1965.
Dawson, T. R. "A Surprise Correction." The Fairy Chess Review 6,
Dickins, A. "A Guide to Fairy Chess." p. 28, 1967/1969/1971.
Dudeney, H. E. "Chessboard Problems." Amusements in Mathematics. New York: Dover, pp. 84-109,
Elkies, N. D. "New Directions in Enumerative Chess Problems." Elec. J. Combin. 11, No. 2, A4, 2004. http://www.combinatorics.org/Volume_11/Abstracts/v11i2a4.html.
Ewerhart, C. "Backward Induction and the Game-Theoretic Analysis of Chess."
Games and Economic Behavior 39, 206-214, 2002.
Fabel, K. "Nüsse." Die Schwalbe 84, 196, 1934.
Fabel, K. "Weihnachtsnüsse." Die Schwalbe 190, 97, 1947.
Fabel, K. "Weihnachtsnüsse." Die Schwalbe 195, 14, 1948.
Fabel, K. "Eröffnungen." Am Rande des Schachbretts, 34-35,
Fabel, K. "Die ersten Schritte." Rund um das Schachbrett, 107-109,
Fabel, K. "Eröffnungen." Schach und Zahl 8, 1966/1971.
Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and
Work, 3rd ed. New York: Chelsea, 1999.
Hunter, J. A. H. and Madachy, J. S. Mathematical Diversions. New York: Dover, pp. 86-89, 1975.
Kraitchik, M. "Chess and Checkers." §12.1.1 in Mathematical Recreations. New York: W. W. Norton, pp. 267-276,
Lasker, E. Lasker's Manual of Chess. New York: Dover, 1960.
Madachy, J. S. "Chessboard Placement Problems." Ch. 2 in Madachy's Mathematical Recreations. New York: Dover, pp.
Parlett, D. S. Oxford History of Board Games. Oxford, England: Oxford
University Press, 1999.
Pegg, E. Jr. "Math Games: Chessboard Tasks." Apr. 11, 2005. http://www.maa.org/editorial/mathgames/mathgames_04_11_05.html.
Peterson, I. "The Soul of a Chess Machine: Lessons Learned from a Contest Pitting
Man against Computer." Sci. News 149, 200-201, Mar. 30, 1996.
Petkovic, M. Mathematics and Chess. New York: Dover, 1997.
Schroeppel, R. "Reprise: Number of Legal Chess Positions." email@example.com posting, Aug. 18, 1996.
Schwarzkopf, B. "Die ersten Züge." Problemkiste, 142-143, No.
92, Apr. 1994.
Shannon, C. "Programming a Computer for Playing Chess." Phil. Mag. 41,
Sloane, N. J. A. Sequences A006494, A007545/M5100, and A019319 in "The On-Line Encyclopedia of Integer Sequences."
Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 11-14,
Stout, R. "Gambit." In Seven Complete Nero Wolfe Novels. New York: Avenic Books,
p. 475, 1983.
Velucchi, M. "Some On-Line PostScript MathChess Papers." http://anduin.eldar.org/~problemi/papers.html.
Watkins, J. Across the Board: The Mathematics of Chessboard Problems.
Princeton, NJ: Princeton University Press, 2004.