Information Technology Reference
In-Depth Information
An optimal strategy for the hider has never been determined. One might try an al-
gorithmic approach to this open problem, by giving the searcher a bounded number
of questions, say 20 as in 20 questions, and taking
20
n
∑
|
g
n
−
h
|
as the payoff to the
=
1
hider.
One can modify the continuous guessing game following Gilbert, by allowing
the hider to move from one secret number
h
n
to the next
h
n
+
1
between consecu-
tive guesses. There are various choices for the payoff: it could be either
∑
|
−
|
g
n
h
n
∑
|
−
h
∞
|
or
,where
h
∞
denotes the limiting value of the hider's secret numbers.
Alpern's pure minimax strategy still works for the payoff
g
n
, even though
the hider has a larger strategy space. It should be easier to prove that the pure min-
imax strategy is optimal in this case. Instead of
∑
|
g
n
−
h
∞
|
one may also consider
other norms or other payoffs. Tom Ferguson has studied a game with two guesses
only, in which the payoff to the hider is
∑
|
g
n
−
h
|
2
. Despite its apparent simplicity,
this game is non-trivial and the optimal strategies are not easy to find, see [
6
].
(
g
2
−
h
)
Finally, we would like to mention the following conjecture of Johnson: in
Dresher's guessing game, the probability that Blue chooses the secret number 1
is equal to the probability that Blue chooses the secret number in
4.
This problem has remained unsolved for almost 50 years now, and may very well be
the longest standing open problem on search games.
{
2
,
3
}
,if
n
>
References
1.
S. Alpern, Search for point in interval, with high-low feedback, Math. Proc. Camb. Phil. Soc.
98 (1985), 569-578.
2.
S. Alpern, R. Fokkink, R. Lindelauf, and G. J. Olsder. Numerical Approaches to the 'Princess
and Monster' Game on the Interval, Annals Soc. Dynamic Games 10 (2009), 1-9.
3.
B. Bollobás, The art of mathematics, coffee time in Memphis, Cambridge University Press,
2006.
4.
A. Bonato, R.J. Nowakowski, The game of cops and robbers on graphs, American Mathemat-
ical Society, 2011.
5.
M. Dresher, Games of Strategy: theory and application, Prentice Hall, 1961.
6.
T.S.Ferguson, A problem of minimax estimation with directional information, Statistics and
Probability Letters 26 (1996), 205-211.
7.
R.J. Fokkink, Tossing coins to guess a secret number, Amer. Math. Monthly 119 no. 4 (2012),
337-339.
8.
R.J. Fokkink, M. Stassen, An asymptotic solution of Dresher's guessing game, Gamesec 2011,
LNCS 7037 (2011), 104-116.
9.
S. Gal, Search Games, Academic Press, New York 1980.
10.
L. Geupel, The 'Princess and Monster' Game on an Interval, BSc thesis, TU München (2011),
11.
R. Isaacs, Differential games, John Wiley and Sons, New York, 1965.
12.
Gilbert, E.: Games of identification and convergence, SIAM Rev., vol. 4 (1), 16-24 (1962).
13.
S. Johnson, A search game, in Advances in Game Theory, M. Dresher, L.S. Shapley,
A.W. Tucker (eds), Princeton University press, Princeton 1964, 39-48.
Search WWH ::
Custom Search