Hacker News Reader

Comment by thedavibob | Hacker News Reader

> you can select an initial guess that is offset from 50

Given that 7 guesses covers 128 numbers, you can offset by +/- 14 without actually affecting the "worst case" of the algorithm (i.e. provided you have at most 64 either side of your guess). As you say, randomly selecting this offset would neuter most adversarial examples (purposefully chosen to fall into the gaps of binary search) and would possibly completely remove the benefits from adversarial choice (though a tailored distribution on offset might be required there).

I'd be interested in such an analysis too.

View on HN

> Given that 7 guesses covers 128 numbers

I might be confused, but don't 7 guesses actually cover 255 numbers? I think you have to count all nodes in the search tree, not only the leafs, because you can get the correct number before reaching a leaf node.

Or more generally k guesses cover 2^(k+1)-1 numbers, e.g. with one guess you get the answers correct/high/low, which can cover 3 numbers)

Maybe there is a mistake in my thinking, because this would mean you can cover 127 numbers with 6 guesses so you could not lose the original game.

Edit: My mistake is that you still have to explicitly guess even if you know the precise answer already, so you cannot cover 3 numbers with 1 guess. This means 7 guesses cover 127 numbers.

Your logic is correct but you are off-by-one. 1 guess gets you 1 number, so the formula is 2^k - 1, and 7 guesses thus covers 127 numbers.

You can also view it as a recurrence:

  f(1) = 1
  f(n) = 2*f(n - 1) + 1 = 2^n - 1

But your binary search tree example is more intuitive.

Yes, you are right. In this game, you can know the answer after 6 guesses, but then you also have to tell him, which counts as the 7th guess.

You are correct that you can know the answer in 6, but actually winning requires you to “guess” that one last time once you know it.

That approach would still leave you weak to always picking 1 or 100. Without proof, I believe the optimal guessing strategy would perform equal (on average) for every number, to not give the opponent any standout choice (common for optimal strategies, but not always the case). If my math serves me right, that would be an average of log2(100) = 6.64 guesses for any number, which would make you lose 0.64$ on average.

Although upon further thinking, you could then sprinkle in some binomial searches to abuse the uniformity. So the -0.64$ is merely a lower bound.

You forget that the quick guesses bring you more than $1!

As the original article says, on average you can win $0.20. But that's indeed the upper bound if we speak of the adversarial number picking.

I don't think you have to put your random offset all in the first guess either. Maybe you could random offset +/- 7 on the first guess, +/- 3 or 4 on the next, something like that.

Reply on news.ycombinator.com