logoalt Hacker News

thaumasiotesyesterday at 5:39 PM1 replyview on HN

You can't beat binary search in Guess Who. From the abstract:

>> Instead, the optimal strategy for the player who trails is to make certain bold plays in an attempt catch up.

The reason that's optimal, if you're losing, is that you assume that your opponent, who isn't losing, is going to use binary search. They're going to use binary search because it's the optimal way to find the secret.

Since you're behind, if you also use binary search, both players will progress toward the goal at the same rate, and you'll lose.

Trying to get lucky means that you intentionally play badly in order to get more victories. You're redistributing guesses taken between games in a negative-sum manner - you take more total guesses (because your search strategy is inferior to binary search), but they are unevenly distributed across your games, and in the relatively few games where you perform well above expectation, you can score a victory.


Replies

gobdovanyesterday at 7:06 PM

You're mixing two different objectives the paper presents. You can't beat binary search when the objective is to minimise the expected number of turns in a single player setting.

However, in a two player setting, using the strategies presented in the paper, you will beat an adversary that uses binary search in more than 50% of the games played.

Here's another visual demonstration: https://www.youtube.com/watch?v=zmvn4dnq82U

show 1 reply