I play the number guessing game with positive integers and a known constant upper bound. Every time I make a guess about the number I have to pay 1 dollar but if my partner answers 'Yes' I have to pay 9 more.

What is the best strategy to minimize my average cost of the game (other than not playing)?

Does the strategy change if I have to pay more/less for the good guesses?

  • Exchange rôles with your partner! :-) Seriously, does the game continue until you guess the number? – Brian M. Scott Sep 9 '13 at 22:56
  • If you guess wrong, are you given any information, like higher or lower? Otherwise, do you have any information about the probability distribution? If not, you will have to guess half the numbers on average. – Ross Millikan Sep 9 '13 at 23:20
  • I am given an answer to every guess (and my partner doesn't lie), the trick is that my cost depends on the answer. Example: Is the number greater than 10? Yes. => I pay 10. Is the number greater than 12? No => I pay 1. The game goes on until I guess the exact number. If I have info about the distribution I should simply guess for the more probable values first right? – buherator Sep 10 '13 at 5:59
up vote 1 down vote accepted

Ordering doesn't matter here, only the size of the search space. Since every question is yes/no, it splits the space into two parts, and the only parameter that matters for each question is how to size those parts. This allows us to compute the expected cost recursively. Define $T(n)$ to be the average cost of asking enough questions to determine the number from a search space of $n$. By definition $T(1)=0$ (technically the game doesn't end until you have actually guessed the number, but this adds only $O(1)$ to the cost so I'll play fast and loose with this distinction).

For $n \ge 2$, the expected cost of asking "is the number in a given subset of size $k$?" and continuing to play the game on the remaining search space is $1 + \frac{k}{n} (9 + T(k)) + \frac{n-k}{n} T(n-k)$. So we optimize this quantity over all $0 < k < n$:

$$T(n) = \min_{0<k<n} 1 + \frac{k}{n} (9 + T(k)) + \frac{n-k}{n} T(n-k) = 1 + \frac1n \min_{0<k<n} (9k + kT(k) + (n-k)T(n-k)).$$

This gives an optimal value of $T(100) = 26.5$, substantially better than CJ from buherator's answer (assuming we agree on the $O(1)$ convention). I computed the optimal costs and moves up to $n=10000$.

An optimal strategy for $n=10000$ costs about $52.1$, and the first question is to ask "is the number in the range $[1,1607]$?" This has a $0.1607$ chance of costing $10$ plus the cost of solving the size $1607$ problem (which is $\approx 41.956$), and a $0.8393$ chance of costing $1$ plus the cost of solving the size $8393$ problem (which is $\approx 51.127$).

This example suggests that the optimal cutoff is approximately where the two cases balance out in cost, just as in the symmetric case. If we make this assumption then we can do a pretty good job of approximating the optimal strategy. The value of $T(n)$ is a priori somewhere between $\log_2 n$ and $10 \log_2 n$: we make the ansatz that it is asymptotic to $c \log n$ for some constant $c$. Then the optimal cutoff occurs where

$$9 + c \log k = c \log(n-k) \implies \frac{k}{n} = \frac{1}{1 + e^{9/c}}.$$

On the other hand (still under the key assumption) the cost is also equal to the number of iterations that descend into the large half, so $c = -1/\log(1-\epsilon)$. This gives two equations in $\epsilon$ and $c$:

$$\epsilon = \frac{1}{1 + e^{9/c}}, c = -1/\log(1-\epsilon),$$ which has the numerical solution $\epsilon \approx 0.164922, c \approx 5.548537$. So I would conjecture that the optimal strategy is close to "is the number in the first 16.5% of the current range?" The actual ratio appears to be rather non-monotonic, varying up and down between $0.14$ and $0.17$ as $n$ increases, even for large $n$. This could be due to rounding errors in my computation (we could be comparing several $k$ values whose scores are really close), but if not then it suggests that the deviation between the optimal $k$ and $\epsilon n$ is more than just rounding to an integer value of $k$.

  • Thank you for your detailed answer! I'm trying to implement some experiments to test it (I'm not smart enough for a formal proof..), do I understand correctly that if the penalty cost changes only the $\epsilon$ part changes (in e's exponent) in the final equation system? – buherator Oct 6 '16 at 12:22
  • @buherator Yeah I think the relative penalty appears as the $9$ throughout. Of course the final pair of equations is only conjectural. – Erick Wong Oct 6 '16 at 12:34
  • Your solution seems to give convincing results with different parameters too: github.com/v-p-b/campzer0-numberguess . I'm accepting your answer, thank you! – buherator Oct 11 '16 at 15:38
  • @buherator By the way, the first formula should be exactly optimal. The conjecture is that for large $n$ it converges to that value of $\epsilon$. It would be interesting to see how the two strategies compare to each other. – Erick Wong Oct 11 '16 at 18:10
  • (The rounding issue I discuss in the recent edit only affects the computation of the exact optimal value of $k$... it should have only a minimal effect on the simulated or theoretical cost). – Erick Wong Oct 11 '16 at 18:42

So after all, we put together a little sample script for simulation:

https://gitorious.org/campzer0/numberguessing/

We implemented the naive linear approach and two modified version of binary search:

  • synalgo performs simple binary search and tries to estimate the expected remaining cost. If the expected cost of moving on with binary search is higher than the expected cost of the linear search it falls back to linear
  • cj performs a modified binary search where the search space is split in the ration of the good answer/bad answer costs - in the case described in the questions the algorithm always asks if the number is in the lower 1/10 of the current interval. This algorithm also falls back to linear search when the 1/10th of the interval becomes less than 1

After 10000 runs with an upper bound of 100 the results look like this:

naive average of 10000 runs: 59.8012 
synalgo average of 10000 runs: 32.9129 
cj average of 10000 runs: 30.9006

CJ is usually ~10% better than synalgo and they both present good results compared to the naive approach.

These algorithms are of course not proven (close-to) optimal, but provide acceptable efficiency for my actual problem. Any further optimization proposals are welcome though!

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.