-1

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?

Luke Videckis
  • 3
  • It's not even on the hierarchy, because it is finitely bounded (there are only a finite number of possible chess games). There is a maximum number of chess moves possible before the game is declared drawn by the $50$ move rule. I think the "fast-growing hierarchy" you mention is about the asymptotic growth rates of functions defined for arbitrarily large inputs.

    Edit: It would not make sense to talk about the asymptotic growth rate of a function that is only defined for a finite number of inputs.

     – Zubin Mukerjee Dec 01 '19 at 18:33
  • You could think of another function that is defined on infinitely many inputs as follows: Consider an $n\times n$ chessboard with some well-defined initial setup and rules for the game, then counting the number of possible games as a function of $n$ would be something for which you could calculate the asymptotic growth rate. – Zubin Mukerjee Dec 01 '19 at 18:39

1 Answers1

0

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.

Deedlit
  • 7,062