Share
Explore BrainMass

Bounds on the number of states in a chess game

A step by step analysis is given for the following questions,

1. Find an upper bound for the number of possible states in the game of chess, assuming that draw-by-repetition is enforced if the same position is repeated three times.

2. Find an upper bound for the number of possible moves in a single turn in the game of chess.

3. Use Question 2 above to find an upper bound for the number of possible sequences of moves in 10 consecutive turns in the game of chess.

4. Chess experts sometimes think 10 turns ahead, but do not consider every possible sequence of moves. Given a computer capable of processing one billion moves per second, find the maximum number of options it could consider at each move if it must think 10 turns ahead within a 3-minute time period. [Note: what we have called a "turn" is actually called a "half-move".]

Solution Preview

Please see attachment for properly formatted copy.

1. The maximum number of pieces in a given state of the game is 32. The number of squares is 64. The pieces are one king, one queen, two rooks, two knights, two bishops, and eight pawns.

We first find the number of possible position of 32 pieces in the 8x8 chessboard. Now we need to consider that there are indistinguishable pieces, for example two pawns of the same color are indistinguishable.

For instance there are eight black pawns, so a permutation of them does not alter a configuration of the chessboard. There are 8! permutations of 8 objects. We have: 2! permutations of the two black rooks, 2! permutations of the two black knights, 2! permutations of the two black bishops and 8! permutations of the two black pawns, and same for white pieces. Then the maximum possible number of position of the pieces in the chessboard is as follows:

(1) choose a subset of 8 elements of a total of 64 to put the 8 black pawns: 64 choose 8 possibilities. We denote this as
binom{64}{8}.

(2) choose a subset of 8 elements of the remaining 56 to put the 8 white pawns: 56 choose 8 possibilities.

(3) choose a subset of 2 elements of the remaining 48 to put the 2 black bishops: 48 choose 2 possibilities.

(4) and so on with all the rest

Then the total number of possibilities to place 32 pieces in a chessboard is the product:

binom{64}{8}*binom{56}{8}*binom{48}{2}*binom{46}{2}*binom{44}{2}*binom{42}{2}*binom{40}{2}*
binom{38}{2}*binom{36}{1}*binom{35}{1}*binom{34}{1}*binom{33}{1}

Now binom{n}{k}=(n!/(k!(n-k)!)), so the previous expression simplifies to

(64!/(8!56!))*(56!/(8!48!))*(48!/(2! 46!))*...*(34!/(1! ...

Solution Summary

Upper bounds for the number of states in the game of chess are established. We then give an upper bound on the number of moves a computer can calculate ahead of time having a time restriction.

$2.19