6
$\begingroup$

High Low game is one where one person picks a number between a range (say 1-100) and another person have to guess it. With each guess, s/he is told whether the guess was high, low or correct.

If the person picking the number picks it at random, then the best strategy would be to use binary search algorithm (start at middle of range, and then keep dividing sample space in half) to minimize the number of guesses.

(1) If the players however are playing adversarially, i.e. Person picking the number wants to maximize the guesses taken by guesser and Guesser wants to guess the number in minimum guesses; what is best strategies for both of them?

(2) Also, related question : If it is known that Person picking the number is trying to defeat the Binary search algorithms, what would be the best strategy to guess the number in least amounts of guesses?

$\endgroup$
  • 2
    $\begingroup$ I mentored a student at Illinois Math and Science Academy studying this and related games. Together, we found optimal hiding solutions that for most $N$ up to about 250. The patterns are fascinating: Many cases are solved by merely doubling the likelihood of choosing the numbers $1$ and $N$. Others fall into one of about three other patterns. But for some cases, the solution is pretty much different from any other case. I will supply a detailed answer in about a week if nobody else nails this one. $\endgroup$ – Mark Fischler Dec 25 '14 at 15:38
  • $\begingroup$ @MarkFischler Thanks. I did thought about choosing 1, since it will always fall as leave node if we construct a binary tree; and thus is worst case scenario for random numbers. However, what I could not prove is that it is better than any other leaf node. I may be able to do it if I devote some time to the problem though; and solve (2) part of my question myself. However, pure adversarial strategy (1st part of my question) has me baffled with little idea as how to proceed. [One idea may be use base cases and try to formulate patterns, but it seemed complex] $\endgroup$ – kushj Dec 25 '14 at 17:07
  • $\begingroup$ A much more difficult game yet (one which we solved for up to about $N=8$), is that the hider is allowed to lie once (if the searcher has not guessed the right number. $\endgroup$ – Mark Fischler Dec 26 '14 at 2:56
  • $\begingroup$ @MarkFischler I tried that too. I tried with guesser lying exactly with probability 0.5 on each wrong guess, and limiting that to one lie. That is totally different than adversarial lie, I know; but this was start. .. Er, and I think no one else is answering this question. So you could post your solution, or perhaps just the start of it, and I can try to infer it from there $\endgroup$ – kushj Jan 5 '15 at 13:44
  • $\begingroup$ @MarkFischler: Hi Mark -- I'd be interested in the solution you announced :-) $\endgroup$ – joriki Mar 1 '16 at 10:56
6
$\begingroup$

A high-school student at IMSA and I analyzed the adversarial High-Low finding game of numbers $1\ldots N$ for $N$ up to $100$ about a decade ago.

Before presenting the answers, let me distinguish these games, in which the adversary has to choose a number in advance, and a game in which the adversary is free to alter the number chosen as long as all the answers given to date remain true. Allowing the adversary to change the answer makes the game much easier to analyze (it is no longer an imperfect information game!) and this is particularly true if we consider a variant of the game in which a single lie is permitted.

In general, there is a unique optimal hiding strategy (that is, a unique optimal distribution of probabilities of choosing the number $k$ with $1 \leq k \leq N$). But for many values of $N$, there are a range of optimal finding strategy mixes (that is, there are various decision trees that all lead to the same optimal expected finding time). In this answer I will only describe one finding strategy for a given $N$.

$N=3$: Hiding strategy is $2 \,|\, 1\,|\, 2$, meaning that the hider chooses $$P(k=1) = \frac{2}{5} \\P(k=2) = \frac{2}{1} \\P(k=3) = \frac{2}{5} $$ Henceforth, I will describe hiding strategies as just that sequence of relative values. The finding strategy is $$ P( (2)) = 3/5 \\ P(1;(3)) = 2/5 $$ This notation means the finder chooses an initial guess of $2$ 60% of the times, and the combination of [an initial guess of $1$ intending to guess $3$ next] and [the mirror reflection of that strategy, guessing 3 first] 40% of the time.

For $N=3, V(3) = \frac95$ which is 0.13333 worse than the optimum obtained by a binary search if the hider must choose $k$ as a uniform random on $[1,3]$.

For $N=4$ the optimum hiding strategy is $1 \,|\, 1\,| \, 1\,| 1$ (how boring!) and the optimum finding strategy is $P(2;(4)) = 1$, again with the understanding that that $1$ is split (half-half) between the strategy shown of choosing $2$ and then, if the answer is "higher", choosing $4$, and its mirror image of choosing $3$ and then $1$. This mirror property will hold for all the solutions I will present (although there are other finding optimal strategies for some of the games that do not have mirror symmetry). For $N=4$ the adversarial hiding game has the same value as the uniform-distribution binary search.

For $n=5$ the optimum hiding strategy is $5 \,|\, 3\,| \, 2\,| 3\,| \,5$ and the finding strategy is $$ P( (3;(1)(5) ) = 4/9 \\ P(2;(4) )= 4/9 \\ P(2;(5;(4))) = 1/9 $$ A final notation tidbit here -- the first of these strategies exhibits, for the first time so far, the information as to what you will do for each of two possible answers, saying that if you guess $3$ and the number low, you use the strategy $(1)$ but that if it is high you use the strategy $(5)$. This is why some single numbers are written in parentheses; items in parentheses represent complete finding strategies for some sub-interval.

Note that even though the numbers $1$ and $5$ are significantly more common than the other numbers, you can never (in an optimum strategy) start by guessing one of those endpoints. That sacrifices too much information in the case that the first guess does not hit $k$ immediately. $V(5) = 20/9$, which is $0.2222$ worse than the non-adversarial (uniform distribution) finding problem.

For $N=6$ The optimum hiding strategy is $5 \,|\, 3\,| \, 2\,| \, 2\,| 3\,| \,5$ and the finding strategy is $$ P( (3;(1)(5) ) = 3/5 \\ P(3;(1)(6;(5)) )= 1/5 \\ P(2;(5;(4))) = 1/5 $$ (Don't forget that since you must split these between the stated strategies and their mirrors, this is really a six-component mixed strategy.) $V(6) = 12/5$ which is 0.066667 worse than the value of the non-adversarial game (which I will $B(6)$.

For $N=7$ thru $N=10$ the optimum hiding strategy is $2 \,|\, 1\,| \, 1\,| \cdots \,|\, 1\,| 1\,| \,2$ and $$V(N) = \frac{4N-5}{N+2} = B(N) + \frac{22-2N}{N(N+2)}$$ so the adversarial game is worse than the uniform game by an amount tan falls from $0.127$ down to $0.0167$.

It would be tempting to suppose that that pretty property of hiding by doubling the chances of each end number, and otherwise choosing the number as a uniform random, holds from then on. Not that simple!

For $N=11$ the optimum hiding strategy is $58 \,|\, 29\,| \, 29\,| 34 \,| 25 \,| 22 \,| 25 \,| 34 \,| 29 \,| 29\,| 58$ and an optimum finding strategy is $$\begin{array}{lll} P(6;(3;(1)(4))(9;(8)(11))) &=& 117/744 \\ P(6;(2;(4))(10;(8))) &=& 123/744\\ P((5;(2;(4))(9;(7)(11))) &=& 348/744\\ P((4;(2)(8;(6)(10))) &=& 54/744\\ P(4;(2)(9;(7;(5))(11))) &=& 72/744 \\ P(4;(1;(3))(8;(6)(11;(9)))) &=& 30/744 \end{array} $$ I should mention the technique for solving these games: It is easy enough to write a simplex solver and tie it to something that fills in the expected values (which may have halves because a strategy includes its mirror image) for each combination of number chosen and strategy employed. The tough part is to feed in a suitable set of candidate strategies. You can't afford (for large $N$) to simply generate all possible strategies, as the number grows exponentially. For example, with $N=11$ we initially fed in $17$ plausible finding strategies. The key next step is to assume the hiding strategy found by the simplex solver is fixed, and solve for the best possible search. If the expected value is the same as the game values you just solved, then you are through; otherwise, you need to add in at least the superior finding strategy you just determined, possibly chop out some of the discarded strategies, and try again.

For $N=12$ the optimum hiding strategy looks qualitatively like that for $N=11$, it is $68 \,|\, 34\,| \, 34\,| 43 \,| 31 \,| 24 \,| 24 \,| 31 \,| 43 \,| 34\,| 34\,| 68$. Note that both of these look a lot like the basic $2,1,1,1,\ldots,2$ pattern, but with some waviness.

$N=13$ and $N=14$ fall into a third common pattern: $$129 \,|\, 77\,| \, 52\,| 62 \,| 64 \,| 48 \,| 48 \,| \cdots \,| 48 \,| 48\,| 64\,| 62\,| 52\,| 77\,| 129$$.

$N=15$ through $N=19$ obey the same pattern found for $N=5$ and $N=6$, namely $5 \,|\, 3\,| \, 2 \,| 2 \,| \cdots \,| 2 \,| 2\,| 3\,| 5$. $N=20$ foall back into the simpler $2\,| \, 1 \,| 1 \,| \cdots \,| 1 \,| 1\,| 2$ pattern. That pattern persists until $N=28$ which has a fairly ghastly hiding pattern where the least common multiple of the denominators is a 25 digit number; it still looks like a slightly wavy shallow bathtub with the end elements precisely double their neighbors.

By the time we get to $N=30$ we are back to the simple $2$ pattern, but $N=31$ has the pattern that starts with $129$. The highest one I remember is for $N=63$, for which the optimal hiding strategy is the "Fibonacci" pattern $5 \,|\, 3\,| \, 2 \,| 2 \,| \cdots \,| 2 \,| 2\,| 3\,| 5$. It may be a deep problem to determine what drives the changes in these patterns.

We also solved the one-lie fully adversarial (but no "cheating" by changing the selected number) game, for up to $N=9$. That problem is vastly more difficult, since both the finder and the hider have large sets of plausible strategies. One thing that emerged is that the naive single-error-correcting finding strategies (based on assuming that the number originally chosen was uniformly random and that lies are equally probable at each guess) are markedly inferior; typically more than $0.25$ of a guess worse than the optimal finding strategies.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.