Open Problems on Search Games - Search Theory: A Game Theoretic Perspective - page 75

chooses a secret number h and tells Red whether his guess is too high, too low, or
correct. However, after doing this, Blue may change the secret number, but it has to
be in accordance with the answers that have been given so far. Dresher's guessing
game has an immobile hider, the secret number remains the same. In Gilbert's guess-
ing game, the hider is mobile between consecutive guesses. Ordinarily, a search
game with a mobile hider is a more difficult game to solve, but in this case that is
not true. A guessing game is played over rounds and in Gilbert's game the play-
ers play the same game each round, over a reduced set of numbers. This recursion
should make the game easier to solve. It certainly makes the value of the game easier
to compute, and it is conjectured in [ 7 ] that the value of the game satisfies

lim
n → ∞

V ( n ) − log 2 ( n )= c

for some constant c = 0 . 487 ... .

There are many other versions of the high-low guessing game. The following
continous version of the game was first proposed by Vic Baston and Fred Bo-
stock: Blue chooses a secret number h

. Red repeatedly guesses it and is
told whether the guess is too high or too low (the probability of guessing the ex-
act number is zero). If g n is the sequence of guesses, then Blue's payoff is equal
to

∈ [ 0 , 1 ]

.SteveAlpern[ 1 ] found a pure minimax strategy for the searcher,
see Fig 5.1 . One should realize that a pure strategy in a guessing game is equal
to a binary search tree. The next guess depends on the fact whether the previous
guess is too high or too low. Alpern introduces a state variable that keeps track of
the excess of guesses that were too low. After n guesses g i , the state variable is
k

∑ |

g n − h |

= |{ ≤ < }|−|{ ≤ > }| < λ k <

1
for every integer k , which has the property that if the remaining interval that con-
tains h is

i n : g i h i n : g i h . There exists a unique number 0

[ a , b ] and if the searcher guesses λ k a +( 1 − λ k ) b in the next round, then

∑ |

is constant for every h , with the exception of h that are in the countable set
of guesses. The searcher uses a single binary tree, which is illustrated in the figure,
partly and for the first few guesses, that has equal payoff against almost every secret
number. However, it is unknown if there exists a mixed strategy that performs better.

g n − h |

Fig. 5.1 A part of Alpern's minimax tree, rounded to three decimals