Knowledge check The answer is in fact $c = \binom{d+2}{2}$. Claim: Any polynomial in ${\mathbb R}[x, y]$ of degree at most $d$ can be decided based off its value at $c$ general points $(x_i, y_i)_I$ such that $P(x_i, y_i) \ne 0$ for each $i$. Proof. By stars and bars such polynomials form a subspace of ${\mathbb R}[x, y]$ of dimension $c$, call it $P$. Then there exists a linear evaluation map at $P$ mapping to ${\mathbb R}^c$ of \[ p \mapsto (p(x_1, y_1), p(x_2, y_2), \dots, p(x_n, y_n)) \]It remains to show this map has trivial kernel, or that $\det p = 0$. $\det p$ is a integer polynomial in $x_1, y_1, x_2, \dots, x_n, y_n$, Laplace Expand to get a nontrivial coefficient. Then combo null tells us that a polynomial with a nonzero coefficient can't always be $0$. $\blacksquare$ Claim: It is impossible to win in $c - 1$ moves. Proof. Take the map $p$ from before. Now, it must have nontrivial kernel element $Q$. Since $Q$ is $0$ on each $(x_i, y_i)$ and $P$ is not, if $Q = P \cdot R$ then $R$ is also $0$ on each $(x_i, y_i)$. As such, take $Q$ which is not divisible by $P$. Then Allen can't distinguish between $1434 P(x)$ and $1434 P(x) + Q(x)$. $\blacksquare$

YaoAOPS wrote: The answer is in fact $c = \binom{d+2}{2}$. If $d=2$, $P(x,y)=y$ you can always win by asking $(0,0), (1,0), (2,0)$ (and in general if $P(x,y)=y$ you can always find out with $d+1$ queries). Edit, misread

$P(0,0) = P(1,0) = P(2,0) = 0$ so you can't actually ask about it.

The answer is $\frac{(d+2)(d+1)}{2}$. In this amount of moves Allen can interpolate the polynomial $Q$, and thus he would know whether it is divisible by $P$ or not Now let Alan answer $0$ to all queries. Suppose he made less than $\frac{(d+2)(d+1)}{2}$ queries and solved the problem. Because $Q(s,t)=0$ satisfies all queries, he must have concluded that $Q \vdots P$. A famous interpolation fact says that there exists a polynomial $A(s,t) \neq 0$ that is also zero in all queries. Take such a polynomial with the lowest possible degree. Then if $A \vdots P$, then the polynomial $\frac{A}{P}$ is of a smaller degree and also zero in all queries, contradiction. Hence $A$ is not a multiple of $P$, and so $Q(s,t)$ could still be not divisible by $P$, contradicting the assumption of solving the problem.