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. It is believed that chess was played in India as early as the sixth century AD.

In a game of 40 moves, the number of possible board positions is at least 10^{120} according to Peterson (1996).
However, this value does not agree with the 10^{40} possible positions given by Beeler *et al. *(1972, Item 95). This
value was obtained by estimating the number of pawn positions (in the no-captures situation, this is ), times all
pieces in all positions, dividing by 2 for each of the (rook, knight) which are interchangeable, dividing by 2 for each
pair of bishops (since half the positions will have the bishops on the same color squares). There are more positions with one
or two captures, since the pawns can then switch columns (Schroeppel 1996). Shannon (1950) gave the value

The number of chess games which end in exactly plies (including games that mate in fewer than plies) for , 2, 3, ... are 20, 400, 8902, 197742, 4897256, 120921506, 3284294545, ... (K. Thompson, Sloane's A006494). 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). The number of chess positions after moves for , 2, ... are 20, 400, 5362, 71852, 809896?, 9132484?, ... (Schwarzkopf 1994, Sloane's A019319).

Cunningham (1889) incorrectly found 197,299 games and 71,782 positions after the fourth move. C. Flye St. Marie was the
first to find the correct number of positions after four moves: 71,852. Dawson (1946) gives the source as *Intermediare des Mathematiques* (1895), but K. Fabel writes that Flye St. Marie corrected the number 71,870 (which he found
in 1895) to 71,852 in 1903. The history of the determination of the chess sequences is discussed in Schwarzkopf (1994).

Two problems in recreational mathematics ask

- 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.

**References**

Ball, W. W. R. and Coxeter, H. S. M. *Mathematical Recreations and Essays, 13th ed.* New York:
Dover, pp. 124-127, 1987.

Beeler, M.; Gosper, R. W.; and Schroeppel, R. *HAKMEM.* Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, Feb. 1972.

Dawson, T. R. ``A Surprise Correction.'' *The Fairy Chess Review* **6**, 44, 1946.

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, 1970.

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, 1947.

Fabel, K. ``Die ersten Schritte.'' *Rund um das Schachbrett*, 107-109, 1955.

Fabel, K. ``Eröffnungen.'' *Schach und Zahl* **8**, 1966/1971.

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, 1942.

Madachy, J. S. ``Chessboard Placement Problems.'' Ch. 2 in *Madachy's Mathematical Recreations.*
New York: Dover, pp. 34-54, 1979.

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.'' tech-news@cs.arizona.edu 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**, 256-275, 1950.

Sloane, N. J. A. A006494, A019319, and A007545/M5100 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.

Stout, R. ``Gambit.'' In *Seven Complete Nero Wolfe Novels.* New York: Avenic Books, p. 475, 1983.

© 1996-9

1999-05-26