Shannon's number growth rate

Question

Where does Shannon's number lie on the fast growing hierarchy?

Also, consider the function of (# of moves so far) -> (# of chess games). How does the growth rate of this function compare to the growth rates on the fast growing hierarchy?

Answer 1

Assuming we ignore the 50-move and 75-move rules, as well as the draw by repetition rules, the number of possible games with n plies grows exponentially. One can show that there cannot be more than 300 moves available in any given position (218 is the most number of moves that have been found), which gives an upper bound of $300^n$. On the other hand, it's not hard to get to a position where each player has a rook or queen that can move along an empty file, which yields a lower bound of $c \cdot 7^n$. Heuristics suggest that the actual number is on the order of $50^n$.

So, this function will grow a little faster than $f_2(n) = n 2^n$, but much slower than $f_3 (n) > 2^{2^{2^{\cdots^2 }}}$ with $n$ $2$'s.