Information Technology Reference
In-Depth Information
always wins, by digging a tunnel that runs from
−
1to1.If
h
<
2 then the hider
ensures a 50 % probability win by putting both nuts either at
+
1or
−
1. Conversely,
3
2
then the searcher ensures a 50 % probability win by digging either to
if
h
≥
+
1
or
1 in the opposite direction. To see why this
guarantees a 50% probability, observe that the hider wins if he digs in the direction
that contains the hidden object that is farthest away from the origin. If
h
−
1 all the way, and digging
h
−
<
3
/
2
1
2
1
2
1
2
1
2
{−
,−
}
{−
,
+
}
{
+
,
+
}
then the hider places the objects either at
,
equiprobably. The distance between these three positions is such that the searcher
can only reach one of these three placements. So the hider wins with probability
two thirds, at least. The searcher, on the other hand, has a strategy that guarantees
that he wins with probability one third, as follows. He digs into one directions, and
if he finds an object, then he continues digging in that direction with probability
2
1
or
or
1
1
3
. This guarantees
that the searcher finds both objects with probability one third. So the value of the
game, which we define as the probability of a searcher win, is equal to one third if
1
3
, or he starts digging in the other direction with probability
≤
h
<
3
/
2.
In the caching game with two objects and two directions the hider either places
both objects in the same location, or he places them in such a way that if the
hider finds one object, then the remaining object is optimally placed. Indeed, if
the searcher finds the first object at say
1
2
, then the remaining object is either at
+
1
+
2
, equiprobably. In the remaining game, the searcher is looking for a
single object, for which he has to dig a distance
2
, either to the left or to the right.
The hider has made sure that the remaining object is optimally placed. This seems
to be a general principle that applies to all versions of the caching game that we can
solve.
1orat
−
One can increase the number of directions in which the hider can dig, or the num-
ber of objects that he hides. The game with three tunnels and two objects has been
solved in [
3
]. The game with four tunnels and two objects appears to be difficult,
and has not been fully solved yet. The value of the game and the optimal strategies
for the players have been determined for a substantial range of the parameter
h
and
can be found in [
8
]. The following table for the game value has been taken from that
report:
h
value
[
0
,
1
)
0
3
2
)
1
10
[
1
,
3
5
3
20
[
2
,
3
)
5
3
,
7
4
)
1
5
[
7
[
4
,
2
)
?
11
5
2
5
[
2
,
)
11
7
[
5
,
3
)
?
7
3
1
2
[
,
3
)
3
4
[
3
,
4
)
[
4
,
∞
)
1
Search WWH ::
Custom Search