5 ms·

> 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 "wors

> 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.

hulium 2y ago
> 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.
- deleted 2y ago
  [deleted]
- sltkr 2y ago
  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.
  - hulium 2y ago
    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.
- hamburglar 2y ago
  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.
wrvn 2y ago
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.
- wrvn 2y ago
  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.
  - gukoff 2y ago
    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.
furyofantares 2y ago
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.

hulium 2y ago

> 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.

deleted 2y ago
[deleted]
sltkr 2y ago
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.
- hulium 2y ago
  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.
hamburglar 2y ago
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.

wrvn 2y ago

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.

wrvn 2y ago
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.
- gukoff 2y ago
  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.

furyofantares 2y ago

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.