Guess Who? Simulator

The optimal strategy for Guess Who (or number guessing game) is NOT binary search!

...unlike what common wisdom or this one particular Mark Rober video suggests.

Based on this research paper arXiv:1509.03327v3

Here, you can play against the computer (playing the optimal strategy)

If for some reason you want to know what the computer choose, check console log.

If you do not do that, then the computer will win against binary search (mark rober strategy) 86.05\% of the time. (bounds 100)

In a best of 5 that works out to an 97.82\% winrate against Mark Rober!

Scroll down for graphs and the optimal strategy and a partial proof (I left out the 4 pages of boring proof by induction)

Number bounds: 1 to

Choose or your number (the computer does not know this)

Or, times

Human

Choosen number: 1

Remaining numbers: 1,2,3,4,5,6 (6 remaining)

Your question: is it between and ?

Last question: is it between 1 and 20?, answer: YES!

Computer WINNER!

Choosen number: ???

Remaining numbers: 1,2,3,4,5,6 (6 remaining)

Asked question: is it between 1 and 20?

Answer: YES!

Stats

Total games: 0

Human wins: 0

Computer wins: 0

Graph:

The optimal strategy

Let b^{*}(n,m) be the optimal "bid size" (how many numbers should the question contain) for player 1, where player 1 has n numbers remaining and player 2 has m numbers remaining.

Let p^{*}(n,m) be the probability that player 1 will win if both players are using the optimal strategy and player 1 has n numbers remaining and player 2 has m numbers remaining.

If n\ge 2^{k+1}+1 while 2^{k}+1\le m\le 2^{k+1} for some k \in \mathbb{N} (i.e. k=\lfloor\log_{2}(m-1)\rfloor), then player 1 is in the weeds and must make a bold move to catch up!

b^{*}(n,m)=2^{k} or 2^{\lfloor\log_{2}(m-1)\rfloor}

p^{*}(n,m)=\frac{2^{k+1}}{n}-\frac{2}{3}\cdot\frac{2^{2k+1}+1}{nm}

If 2^{k}+1\le n \le 2^{k+1} while 2^{k}+1\le m\le 2^{k+1} for some k \in \mathbb{N}, then player 1 has the upper hand an can afford to do low-risk moves

b^{*}(n,m)=\lfloor\frac{n}{2}\rfloor

p^{*}(n,m)=1-\frac{2^{k}}{m}+\frac{2}{3}\cdot\frac{2^{2k}+2}{nm}

Proof

p^{*} and b^{*} satisfy the following recurrence relation

p^{*}(n,m) = \max_{b\in\left[1,n-1\right]}\left\{1-\frac{b}{n}p^{*}(m,b)-\frac{n-b}{n}p^{*}(m,n-b)\right\}

b^{*}(n,m) = \arg \max_{b\in\left[1,n-1\right]}\left\{1-\frac{b}{n}p^{*}(m,b)-\frac{n-b}{n}p^{*}(m,n-b)\right\}

If the argmax is not unique, any b that maximizes the function will work for the optimal strategy

If this seems confusing,

the first equation says that the probability of you winning is 1 minus the probability of the other person winning.
it then expands the "probability of other person losing" into the probability of them winning into "probability of winning if the answer is yes" and "probability of winning if the answer is no"
then it multiplies those by the probabilty of there being a yes or no answer respectively
finally, the \max operator is added to find the case where the bid size is optimized for the highest probability of winning
for the other equation, the difference is it uses an \arg \max instead of a \max. this returns the value of b in the optimal case instead of the probability

Using these, we can enter the equations into a computer to solve it numerically. Then a huge proof by induction is needed to prove that this guess is correct (you can see the entire proof in the accompanying paper).

(yes it is that unsatisfying sorry)