  In the distributional Twenty Questions game, Bob chooses a number $x$ from
$1$ to $n$ according to a distribution $\mu$, and Alice (who knows $\mu$)
attempts to identify $x$ using Yes/No questions, which Bob answers truthfully.
Her goal is to minimize the expected number of questions.
  The optimal strategy for the Twenty Questions game corresponds to a Huffman
code for $\mu$, yet this strategy could potentially uses all $2^n$ possible
questions. Dagan et al. constructed a set of $1.25^{n+o(n)}$ questions which
suffice to construct an optimal strategy for all $\mu$, and showed that this
number is optimal (up to sub-exponential factors) for infinitely many $n$.
  We determine the optimal size of such a set of questions for all $n$ (up to
sub-exponential factors), answering an open question of Dagan et al. In
addition, we generalize the results of Dagan et al. to the $d$-ary setting,
obtaining similar results with $1.25$ replaced by $1 + (d-1)/d^{d/(d-1)}$.
