alt Hacker NewsI find it somewhat surprising that the optimal play when you're ahead is still just binary search. Is there an intuitive reason why it's not productive to make riskier guesses? Why not use my lead to have some chance of sealing my victory immediately, while still maintaining my lead if I'm wrong?
Replies
Binary search minimizes the number of expected moves until you find the target. If you are already ahead, this is a natural thing to want to do. The reason why this doesn't work when you're behind is that your opponent can also do that and probabilistically maintain their lead.
In addition to other answers, one way to think about it is that the options are symmetric around the midpoint: a guess that partitions the space into (1/4 of options, 3/4 of options) is the same as one that does (3/4, 1/4). So (1/2, 1/2) is special in some way – it has to be either a local minimum or local maximum. And if the function is convex (or close enough), then (1/2, 1/2) is a global minimum/maximum.
But (1/2, 1/2) is clearly a better choice than just guessing a specific individual. So it must be the best choice.
If you're behind and you're doing the same strategy as your opponent, you'll never catch up. If you're behind doing the risky bet strategy, most times you will never catch up either because your risky bets don't pay off, but a few times they will pay off.
> Why not use my lead to have some chance of sealing my victory immediately, while still maintaining my lead if I'm wrong?
There's no advantage to winning immediately. You aren't scored on time taken.
So, it's better to use the better strategy.
An entropy argument for optimal strategy when winning? Finite size/bounds arguments for losing?
If you have 100 options available to you, the maximum information gain is if you eliminate half. So, if you can, you always want to employ that strategy.
The problem comes with when you're losing, you might get maximum entropy gain by eliminating half but, because of finite effects of the game ending, that might not matter.
Take the example I gave: the next move you lose and you have 4 options to choose from. Eliminating half (2 in this case) will give you maximum entropy gain but guarantee a loss, since you're not whittling down the remaining list to 1 option. Better to take the hit on entropy in order to at least have a chance at winning.
I don't claim to have deep knowledge but this seems like finite size scaling effects. There's a kind of "continuum limit" of these processes but when you get to actual real-world/finite instances, there are issues "at the edges", where the continuum becomes finite. The finite size of the problems creates a kind of non-linear issue at the edges. All this is very hand-waivy, so don't take it too seriously but that's the intuition I have, at least.