# Number guessing game with expensive answers

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

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!

-