Shannon number
Encyclopedia
The Shannon number, named after Claude Shannon, is an estimated lower bound on the game-tree complexity of chess
. Shannon calculated it as an aside in his 1950 paper "Programming a Computer for Playing Chess". (This influential paper introduced the field of computer chess.) He notes:
Shannon also estimated the number of possible positions, "of the general order of
, or roughly 1043". 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×1052 for the number of positions, and estimated the true number to be about 1050. Recent results improve that estimate, by proving an upper bound of only 2155, which is less than 1046.7.
Allis also estimated the game-tree complexity to be at least 10123, "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 estimated to be between 4×1079 and 1081.
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
. Shannon calculated it as an aside in his 1950 paper "Programming a Computer for Playing Chess". (This influential paper introduced the field of computer chess.) He notes:
Shannon also estimated the number of possible positions, "of the general order of
, or roughly 1043". 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 AllisVictor Allis
Louis Victor Allis is a Dutch computer scientist working in the artificial intelligence field. In his graduate work, he revealed AI solutions for Connect Four, Qubic, and Gomoku. His dissertation introduced two new game search techniques: proof-number search and dependency-based search...
calculated an upper bound of 5×1052 for the number of positions, and estimated the true number to be about 1050. Recent results improve that estimate, by proving an upper bound of only 2155, which is less than 1046.7.
Allis also estimated the game-tree complexity to be at least 10123, "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 estimated to be between 4×1079 and 1081.