Chess

Chess is a game played on an $8\times 8$ 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¹²⁰ according to Peterson (1996). However, this value does not agree with the 10⁴⁰ 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 $15^8$), 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

$$P(40)\approx {64!\over 32! (8!)^2 (2!)^6} \approx 10^{43}.$$

The number of chess games which end in exactly $n$ plies (including games that mate in fewer than $n$ plies) for $n=1$, 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 $n$ moves for $n=1$, 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.

The answers are given in the following table (Madachy 1979).

Piece	Max.	Min.
Bishops	14	8
Kings	16	9
Knights	32	12
Queens	8	5
Rooks	8	8

See also Bishops Problem, Checkerboard, Checkers, Fairy Chess, Go, Gomory's Theorem, Hard Hexagon Entropy Constant, Kings Problem, Knight's Tour, Magic Tour, Queens Problem, Rooks Problem, Tour

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.