Consider the following game, played between Alice and Bob: Alice chooses a polynomial $p(x) \in \mathbb{Z}[x]$, where the coefficients are all greater than or equal to $-1$. Bob's goal is to determine the polynomial; to this end he may ask Alice to evaluate the polynomial on any rational point.
Is there a protocol Bob can follow s.t. he will eventually find $p(x)$ (i.e., find all its coefficients)? If so, what is the best bound on the number of steps required?
Background: This is a generalization of a riddle I heard from Sergiu Hart. The question is the same as above, but $p(x)$ is known to have non-negative integer coefficients (and not just greater than $-1$). With this additional constraint, Bob can find $p(x)$ with a surprisingly small number of queries.
Additional note: If Bob is allowed to ask for evaluations on real, rather than just rational, points it is almost trivial that he can find $p(x)$ with a single query (though this is arguably cheating).
Start by querying $p(2)$. Now I claim that the leading coefficient of $p$ is less than or equal to $M=\max(1,p(2)+1)$. Indeed, if $p(x)=a_nx^n+a_{n-1}x^{n-1}\dots+a_0$, then $$p(2)\geq a_n2^n-2^{n-1}-\dots-1=a_n2^n-2^n+1>(a_n-1)2^n$$ which is at least $a_n-1$ unless $a_n\leq 1$. It follows that $a_n\leq M$.
Now note that if $q$ is a prime which does not divide the leading coefficient of $p$, then the denominator of $p(1/q)$ in least terms will be $q^n$ where $n=\deg p$. So, let $q$ be a prime greater than $M$, and query $p(1/q)$ to determine the degree of $p$. Once we have the degree of $p$, we can determine $p$ with $\deg p+1$ queries.
This method generalizes to the case where there is any lower bound on the coefficients of $p$. Indeed, if the coefficients of $p$ are all at least $-N$, then we can query $p(N+1)$ first to similarly get an upper bound on the leading coefficient of $M$ (since the negative lower degree terms will not be able to catch up to the leading term). It makes crucial use of being able to query rational inputs, and not just integer inputs. I don't know if it's possible to do it with just integer inputs. I also don't know whether it's possible to do it with a bound (independent of $p$) on the number of queries.