Shannon number

src: i.pinimg.com

The Shannon number, named after Claude Shannon, is a conservative lower bound (not an estimate) of the game-tree complexity of chess of 10¹²⁰, based on an average of about 10³ possibilities for a pair of moves consisting of a move for White followed by one for Black, and a typical game lasting about 40 such pairs of moves.

Video Shannon number

Shannon's Calculation

Shannon showed a calculation for the lower bound of the game-tree complexity of chess, resulting in about 10¹²⁰ possible games, to demonstrate the impracticality of solving chess by brute force, in his 1950 paper "Programming a Computer for Playing Chess". (This influential paper introduced the field of computer chess.)

Shannon also estimated the number of possible positions, "of the general order of ${\displaystyle \scriptstyle {\frac {64!}{32!{8!}^{2}{2!}^{6}}}}$, or roughly 10⁴³". This includes some illegal positions (e.g., pawns on the first rank, both kings in check) and excludes legal positions following captures and promotions. Taking these into account, Victor Allis calculated an upper bound of 5×10⁵² for the number of positions, and estimated the true number to be about 10⁵⁰. Recent results improve that estimate, by proving an upper bound of only 2¹⁵⁵, which is less than 10^46.7 and showing an upper bound 2×10⁴⁰ in the absence of promotions.

Allis also estimated the game-tree complexity to be at least 10¹²³, "based on an average branching factor of 35 and an average game length of 80". As a comparison, the number of atoms in the observable universe, to which it is often compared, is roughly estimated to be 10⁸⁰.

After each player has moved 5 times there are 69,352,859,712,417 possible games that could have been played.

Maps Shannon number

Number of sensible chess games

As a comparison to the Shannon number, if chess is analyzed for the number of "sensible" games that can be played (not counting ridiculous or obvious game-losing moves such as moving a queen to be immediately captured by a pawn without compensation), then the result is closer to around 10⁴⁰ games. This is based on having a choice of about three sensible moves at each ply (half a move), and a game length of 80 ply (40 moves).

src: 3.bp.blogspot.com

See also

• Solving chess
• Go and mathematics

src: s-media-cache-ak0.pinimg.com

Notes and references

src: i.ytimg.com

External links

• Mathematics and chess

Source of article : Wikipedia