Abstract
We advance and apply the mathematical theory of search games to model the problem faced by a predator searching for prey. Two search modes are available: ambush and cruising search. Some species can adopt either mode, with their choice at a given time traditionally explained in terms of varying habitat and physiological conditions. We present an additional explanation of the observed predator alternation between these search modes, which is based on the dynamical nature of the search game they are playing: the possibility of ambush decreases the propensity of the prey to frequently change locations and thereby renders it more susceptible to the systematic cruising search portion of the strategy. This heuristic explanation is supported by showing that in a new idealized search game where the predator is allowed to ambush or search at any time, and the prey can change locations at intermittent times, optimal predator play requires an alternation (or mixture) over time of ambush and cruise search. Thus, our game is an extension of the wellstudied ‘Princess and Monster’ search game. Search games are zero sum games, where the payoff is the capture time and neither the Searcher nor the Hider knows the location of the other. We are able to determine the optimal mixture of the search modes when the predator uses a mixture which is constant over time, and also to determine how the mode mixture changes over time when dynamic strategies are allowed (the ambush probability increases over time). In particular, we establish the ‘square root law of search predation’: the optimal proportion of active search equals the square root of the fraction of the region that has not yet been explored.
1. Introduction
When searching for a potentially mobile prey, a predator can adopt a behaviour lying between two extreme modes: (i) active, or cruising search, seeking to maximize the area searched in a given time period, or (ii) sitandwait, or ambush search, remaining still in such a way so as to maximize the probability of detecting any motion of the prey. The earlier literature was synthesized and abstracted in the study of Schoener [1], which analyses the predator behaviour of these two types. Since then, considerable literature describes species that alternate between the two search modes in various mixtures. The traditional explanation of the alternation of strategies is as a response to changing external (e.g. weather) or internal (e.g. hunger) parameters observable by the predator. The thesis of this article is that there is an alternative explanation of the observed alternating behaviour that holds even in a constant internal and external environment: the possibility of an ambush decreases the propensity of the prey to frequently change locations, thereby making it more susceptible to detection through systematic search (cruising).
We come to this and other more precise conclusions through the analysis of a new Ambush Search Game that extends the wellknown ‘Princess and Monster’ search game [2] by giving the Monster (the predator) an additional strategy at any time, namely the possibility of adopting the ambush mode. When in the ambush mode, he detects and captures the Princess (prey) if she moves, but simply wastes time (covering no new ground in search) if she stays still. For this reason, the Princess will be stationary except for intermittent ‘dashes’ to new random locations. With this model, we are able to determine, as a function of certain exogenous parameters, the ideal (minimax search time) stationary mixture of cruising versus ambushing for the predator. In a fully dynamic version of the game, we can further determine the ideal mixture (cruising probability) for the predator to adopt when the prey has been excluded by search from a fraction of the search region. Our answer is what we call the Square Root Law of Predation: Adopt the cruising mode with probability equal to the square root of the unexplored fraction of the search region. This implies in particular that when beginning the search, the cruising mode should predominate, but when the prey location has been narrowed to a small area, the ambush mode should predominate. This discourages the prey from moving to escape back into the full region.
A related attempt to model the ambush–cruise search mixture has been recently presented in Zoroa et al. [3] in a more geometrical context. On the prey side, the question of when to move to a new location (though with more information than we allow) has been studied by Broom & Ruxton [4].
2. Search games with mobile hider
The gametheoretic background to the problem we consider lies in the search game with mobile hider, more colourfully named by Isaacs [2] as the Princess and Monster Game. This is a zero sum game between a single predator (the Monster) and a single mobile prey (the Princess), with the capture time T as the payoff (obviously the Monster is the minimizer). The two players move about in a known search region Q, until the first time T that the Princess comes within the Monster's detection radius. If the search region is a network, the game ends when the two players meet (detection radius is zero). The Monster has a maximum speed, taken as 1, which is also the rate at which he explores new territory. The mathematical theory of Princess and Monster Games was begun in Zeliken [5] and Alpern [6], where the search region was considered a circle, and extended [7] to games on networks or regions of ndimensional space. Alternative approaches to the latter problem were given by Lalley & Robbins [8] and Garnaev [9]. Further work on related search games was carried out by Kikuta & Ruckle [10], Pavlovic [11] and Alpern et al. [12] (see also the monographs [13,14]).
As far as we are aware, the only biological application of Princess and Monster Games is [15,16] in the context of a contest between a wasp (Monster) of the genus Sympiesis (Hymenoptera: Eulophidae) and a leafminer larvae (Princess) of Phyllonorycter blancardella (Lepidoptera: Gracillariidae). The search region X is a roughly planar area between the two surfaces of an apple leaf, where the feeding activity of the larvae produces a socalled windows, randomly placed translucent and whitish small spots in which only the upper cuticula remains, while the plant tissue underneath is eaten up. The wasp is attracted in flight by the visual appearance of the mines, lands on the leaf and thus starts the game. Leaf vibrations cause the larvae to cease any feeding and become ‘alert’. The wasp violently inserts its ovipositor, nearly exclusively in the feeding windows, as the rapid escape reactions of the larva command blazing fast attacks, unfeasible if the wasp has to pierce thick tissues. A successful search ends with the larva being parasitized and the wasp laying an egg on it. Thus, this is a discrete location approximation of the Princess and Monster Game.
The search game that we introduce in this article adds an extra strategy for the Monster (predator), namely an ambush mode that he may adopt at any time, which results in immediate capture if the Princess is moving at that time. The presence of this strategy keeps the Princess still most of the time, except for intermittent short (actually instantaneous) dashes to new random locations. On the other hand, if the Princess is stationary during a time interval when the Monster is ambushing, the Monster effectively does no searching and accomplishes nothing in this time interval. The possibility of ambush behaviour in the Princess and Monster Game was first considered by Alpern & Asic [17,18] in the context of ‘bottlenecks’ in the search region, where the Monster might do well to wait in ambush, such as at the central node of the ‘figure eight’ network. Our interpretation here is not that the Monster will wait at a particular point of the search region but rather that he will hover or perch somewhere above it, where he can survey the whole region (or a part of it—see §4.6).
We point out that there is a related literature on what are called ambush games, where the mobile hider (prey) has to move between two known locations (e.g. a known migration pattern) and the Searcher (ambushing predator) has to choose locations at which to ambush (intercept) the mobile prey. This problem is more geometrical than ours, in that the Searcher has to pick locations rather than, as in our model, speed or cruise–ambush alternation. The literature for such ambush games [19–22] may well have applications to the relationship between predator location and migratory patterns of prey. For example, it is suggested by Walter [23] that colonies of Eleonora's falcon are placed to intercept migrations.
There is another literature on pursuitevasion games, within the field of differential games (see Isaacs [2]), which has applications to the next stage of the predator–prey interaction: what happens between the detection of prey and capture of prey. This is an important problem but not one that we address here. We assume that the predator wishes to minimize the time to detect (find) the prey, keeping our analysis firmly within the field of search games.
3. Relationship with the behavioural and ecological literature
Nearly all of the many works done on the searching and escaping modes of predator and prey have been done on evolutionary and ecological timescales (see Helfman [24] and Cooper [25] for reviews and Michel & Adams [26] for one of the latest studies). This ranges from studies focusing on the matching between the searching modes and the group's phylogeny, to studies highlighting the switch of searching modes according to internal state, or external conditions such as temperature, obstacles and habitat complexity to prey densities. In this context, speed does not vary within a single interaction between a predator and a prey. By contrast, exceedingly few studies focus on the ethological time scale at which search occurs, and during which motivational or environmental factors do not change much. For the same reasons, most studies do not address the problem of information acquisition by the opponents during the search game. A monograph about the ethology of predation [27] already reported a lack of quantitative ethological studies on the geometrical and speed components of predator–prey interactions and lamented that many results were based on anecdotes. This remains basically true as of today.
A quantitative assessment of the predator speed during the interaction has been however carried out in a few cases, often related to pursuit–evasion games. In the first case [28,29], the bimodal attacking speed distribution observed in wolf spiders is interpreted as an optimization strategy trading speed on the one hand and production of unwanted information used by prey for escape on the other hand: spiders in ambush or walking slowly towards prey do not produce a large recognizable aerodynamical signature, so they may achieve capture before revealing their presence to the prey; spiders attacking at full speed do produce a lot of such information for the prey, but their speed may suffice to overtake even an escaping prey; spiders running at an intermediate speed produce sufficient information to be spotted and are not quick enough to get their prey, so these hunting speeds are therefore avoided. In that example, speed is nearly constant during a single pursuit. The second case is a searching strategy, the saltatory search. This strategy consists of making small hops or short dashes followed by short pauses and is thus a mixture of speeds displayed during a single interaction [30,31]. It is common in fishes and birds: predators look for prey when they pause and move bitbybit, producing a kind of pseudosystematic pattern of search. Pausing enables them also to attend to other tasks, such as looking out for top predators [30]. Saltatory search in fishes has been explained using hydrodynamical forces acting against cruise search [32]. Other functional explanations for this behaviour have been given, related to information acquisition by the predator, rather than by the prey as in the invertebrate example. Either the radius of perception is nearly similar to the length of the move in the case of fishes [32], or speed itself is a handicap to sensory acquisition, such as for stabilizing visual images of potential prey in birds and lizards [33]. These hypotheses are backed up by recent work showing that speed decreases acuity [34–36]. In summary, saltatory search lies in the middle of a continuum between ambush and cruise search. The proportion of either behaviour remains however constant during the saltatory search, in contrast to our model. Varying speed during an interaction, when prey become cornered or when prey are difficult to subdue, has been observed [27].
4. The Ambush search game
This section describes and analyses our modification of the Princess and Monster Game, which we call the Ambush Search Game. The Hider (modelling the prey, or the Princess in the version of Isaacs [2], and considered female) is stationary at a random location of a search region X of measure (or area) 1, except for intermittent times of her choosing, when she can relocate (in a quick dash, which we take to be instantaneous) to a new random location. The Searcher (modelling the predator, or the Monster in Isaacs [2], and considered male) can explore X at a maximum speed (or discovery rate) of 1. This means that if the Searcher never ambushes, he can search the whole region in unit time. In this case, if the Hider does not move, she will be found in an expected time of 1/2. In any time interval, the Searcher may ambush (in which case, the Searcher will certainly detect a moving Hider but not do any exploring) or he may adopt active, cruising search (in which case he will explore a maximum amount of new territory but will not catch a moving Hider). We assume that when the Hider successfully moves (to a new random location), this event is detected by an active Searcher (perhaps through the vibration of a leaf, in the leafminer case), but the new location of the Hider cannot be ascertained. Thus, the information available to the Searcher is the same as at the start of the game, when he arrived at the patch, namely that the Hider is uniformly distributed over the search space X. Hence, we say that in this event the original game is repeated. Note that when we say that the Hider's movement is detected by the Searcher, we do not mean that the Hider is captured, only that the Searcher knows that the Hider is no longer contained in the smaller region in which he was known to be located prior to the move. Of course, if the move occurs during a period of ambush, the game ends.
A pure search strategy for the Searcher is fully described by a function s(t), with s(0) = 0 and 0 ≤ s′(t) ≤ 1, where s(t) is the fraction of X that he has searched up to time t, assuming the Hider has not moved. In socalled saltatory, or alternating search, periods of ambush are characterized by derivatives s′(t) = 0 and periods of cruising by s′(t) = 1. We also allow intermediate speeds between 0 and 1, for which we have two interpretations. In the probabilistic interpretation, we assume that the Searcher may divide an interval containing time t into many tiny time intervals, on each of which he cruises with probability s′(t) and ambushes with probability 1 − s′(t). So if the Hider moves, the Searcher will be in an ambush interval with probability 1 − s′(t), in which case she will be caught. The other interpretation, which we shall adopt henceforth, is that s′(t) is simply the speed at which the Searcher is moving through the search region (and also his rate of exploring new territory). In this interpretation, we assume that his ability to detect prey decreases linearly with his speed, so that when moving at speed s′(t), he detects a prey movement with probability 1 − s′(t). The assumption that visual acuity (or other measures of ‘accuracy’) is decreasing in predator speed is well founded in neuroethological terms in diverse situations such as pollination or crypsis [36].
To evaluate the efficiency of a particular search strategy s(t), we suppose that the Hider plans to move to a new random location at some time t = m > 0, assuming she is not found by the Searcher before then. What is the expected capture time in this situation? This time satisfies the following equation: 4.1
The first term corresponds to the case where the Hider is caught by a moving Searcher before time m because the probability of her being found in a small time interval [t,t + Δt] is approximately s′(t) · Δt. The second term corresponds to the case where the Hider has not been found by time m, which occurs with probability 1 − s(m). In this case, the capture time is at least m for sure. Furthermore, the Hider is successful in her move at time m with probability s′(m), in which case the search game is played again so she gets an additional expected time of .
Our aim is to find the (minimax) search function, , which gives the least expected capture time for the worst (highest) case of the Hider's choice of m, that is,
We expect (and show later) that, against the optimal search function , the expected capture time will be the same for all Hider moving times m. We first analyse the case where the Searcher is restricted to a constant search speed a (that is, s(t) is of the form at) and find the optimal speed in this case. However, the expected capture time with this restriction always depends on m, so there is no minimax strategy of constant speed. Then, we analyse quadratic search functions and find an optimal solution.
There is an additional technical question (which the reader can disregard for the moment) as to what happens if the Hider is always relocating, which we interpret as moving at time m = 0. In this limiting case, the Hider's expected lifetime is 0 unless the Searcher is putting all his effort into active search, so that s′(0) = 1 and there is no probability of ambush. In this limiting case, we have 4.2
Since the second derivative arises in this context, we require that our search strategies s belong to the space 𝒮 of C^{2} functions, functions with a continuous second derivative, which we now take as the predator pure strategy space.
4.1. Restricted optimization for constantspeed predators
Suppose we restrict the Searcher to searching with a constant speed a ≤ 1, so that at time t he has searched a fraction of the search space X given by s(t) = at. As usual, this assumes that t < m, that the Hider has not yet moved. Substituting at for s(t) in equation (4.1), we have an expected capture time satisfying 4.3
For fixed speed a, the Hider (prey) maximizes the capture time by moving after time , as drawn in figure 1. Note that against a fullspeed predator, the prey should always be moving so as to remain at a random location—there is no downside to moving caused by ambush. Thus, the worst case capture time when the Searcher moves at speed a is , with minimum at of , as drawn in figure 2.
Summarizing our results from this section, we have the following.
Proposition 4.1.
If the Searcher (predator) is restricted to moving at a constant speed a (interpreted as a constant mixture over time of ambush and cruise search) his best speed is , which guarantees an expected capture time not exceeding against any moving time m of the Hider.
The interpretation of this result is that a predator who cannot keep track of how long it has been searching should employ active search about 87 per cent of the time and ambush about 13 per cent of the time. Of course, this result assumes that an ambushing Searcher always detects a moving prey, regardless of the prey's location. A more realistic version of this result, without certain detection of moving prey by an ambushing predator, is given in §4.6.
4.2. An indifferenceinducing search strategy
In this section, we determine a particular search strategy for which the Searcher is indifferent to the time m when the Hider moves. This is a common heuristic for solving zero sum games, but is not a sufficient condition for optimality. We show in §4.3 that this strategy is indeed the pure minimax strategy. It turns out that the Searcher can reduce the worst case expected capture time from the 0.7698 he could ensure using constant speed down to 2/3 = 0.6666 if he uses a quadratic function, rather than a linear one. Since s(0) = 0 (at time 0 he has searched none of the space), there is no constant term, so we assume that s(t) has the form 4.4for unknown constants c and b. Substituting this quadratic form of s into the expected capture time formula (4.1) gives
Solving for b, c and so that the coefficients of powers of m are all zero (independence of m) gives the optimal search strategy , as shown in figure 3.
The method of deriving the formula for given here avoids the need for differential equations, and in any case the required constancy can be verified directly from equation (4.1). Our model predicts a slowing down of predator speed.
4.3. Proof that is optimal
We now show that the pure search strategy is the optimal (minimax) search function. Since does not depend on m, it is enough to show that for any other search function s = s(t), there is some m such that . To this end, we need the following simple result. We adopt the notation τ = τ_{s} to denote the time taken for a strategy s(t) to explore all of the region X (e.g. ).
Proposition 4.2.
For any search strategy s ∈ 𝒮,s ≠ either

s′(0) = 1 and s″(0) ≥ 1/2, or

for all t in some interval (0,ɛ). In this case, either (i) τ_{s} > 2 or (ii) there is a least time t_{1} > 0 with and
Proof. Since s′(0) ≤ 1 for all s ∈ 𝒮, if condition 1 fails, then the first sentence of condition 2 must hold. If part 2(i) fails, so that τ_{s} ≤ 2, then by the Intermediate Value Theorem, there is a time t_{2} such that Then since , it follows from the Mean Value Theorem that there is a time t_{1} > 0, such that Since the set of such t_{1} is compact, there is a least such time.▪
Figure 4 illustrates five curves, from top to bottom: t; a type 1 curve t − t^{2}/8; the minimax curve the type 2(ii) curve t^{2}/3, with 2t_{1}/3 = 1 − t_{1}/2, or t_{1} = 6/7 = 0.86; the type 2(i) curve t^{2}/5 with τ_{s} > 2.
Proposition 4.3.
The strategy is the minimax pure Searcher strategy. That is,
Proof. We show that for each type of strategy s in proposition 4.2, we can determine a Hider move time m, such that . If s is of type 1 of proposition 4.2, then . If s is of type 2(i) of proposition 4.2, . If s is type 2(ii), take m = t_{1}, where t_{1} is the time given by proposition 4.2 part 2(ii). For this value of m, define f_{s}(T) to be the linear function given by the right side of equation (4.1). We claim that the line f_{s}(T) has a higher slope and is higher at T = 0 than , so it intersects the diagonal at a higher point. Since T = T(s,m) is the solution of T = f_{s} (T) and is the solution of , we have . To demonstrate our first claim, observe that
For the second claim, observe that f_{s}(0) is the expected time to find a stationary Hider in the truncated form where the capture time is taken to be m if it is not found before then. Since finds such a Hider by any given time with a higher probability than does s, it follows that this expected truncated capture time is higher for s than for .▪
4.4. The square root rule
If the Searcher is adopting the optimal (minimax capture time) pure strategy , then the time at which a fraction of the space is unexplored is given by
So the optimal search speed (or cruising probability) is given by
Proposition 4.4.
When the prey location is restricted to an unsearched fraction u of the search region, the minimax strategy for the predator is to adopt a speed, or cruising probability, of the square root of u.
4.5. Mixed strategies and noisy predators
So far we have taken the perspective of the predator (Searcher) and found the pure strategy , which minimizes the worst case capture time. If we take a game theoretic viewpoint which includes the perspective of the prey (Hider), there are two cases, which we call ‘silent predator’ and ‘noisy predator’. In the silent predator case, the Hider only knows that time since she last moved, as she cannot hear the speed of the Searcher and hence does not know how much territory has been searched. In the noisy predator case, she can hear the speed of the Searcher and can conclude the amount of territory s that has been searched—and can base her strategy on this parameter. The noisy game is one of ‘perfect information’ in that each player knows the portions of the other's strategy that has already been played. Such games typically (in finite versions) have pure strategy solutions, and indeed we find such a solution for the noisy version of the ambush game.
We have shown in proposition 4.3 that the Searcher can ensure an expected capture time not exceeding 2/3 by using the pure strategy , and that this is the best possible estimate. A question that naturally arises is whether or not he can do better (lower estimate on expected search time) by employing mixed strategies. The answer to this question depends on the information available to the Hider, whether the game is ‘noisy’ or ‘silent’. The terms noisy or silent predator refer to the information available to the prey as to the speed of the predator, and hence as to the amount of territory the predator has already searched. In the noisy version, if the prey knows that the unsearched territory is very small, then the predator has an added incentive to move to avoid being found very soon.
First, we consider the ‘silent predator’ model, where the Hider knows only the time t since she last moved. For this version, consider the two pure Searcher strategies s_{1}(t) = t − (1/8)t^{2} and s_{2}(t) = t − (3/8)t^{2} on either side of the minimax strategy . The mixed strategy consisting of s_{1} with probability 5/13 and s_{2} with probability 8/13 has a maximum expected search time (against any moving time m) of 60/91, which is less than the pure strategy minimax time of 2/3. So in the silent predator model, the Searcher can improve on the expected search time of 2/3 by adopting mixed strategies. The optimal mixture of pure strategies is not known.
Next, we consider the ‘noisy predator’ model, where at every time t_{0} the Hider knows the prior Searcher path s(t), t ≤ t_{0}. In the noisy predator game, a Hider strategy is a function H : 𝒮 → R, where the moving time is m = H(s), such that for any s_{a}, s_{b} ∈ 𝒮 we have 4.5which simply means that the Hider cannot predict the Searcher's future motion.
Proposition 4.5.
In the noisy predator game, where the Hider knows the Searcher's motion up to the current time, the value is 2/3 and the pure Searcher strategy is the optimal mixed strategy. The Hider also has an optimal pure strategy .
Proof. The Hider moves at time , with as follows. If s′(0) = 1 and s″(0) ≥ 1/4, then . Otherwise, let be the least time t that . If there is no such t, let . The fact that for any s ∈ 𝒮 follows from the fact that , where m = H(S), as in the proof of proposition 4.3.▪
So the question of whether the Searcher can improve on the 2/3 value of proposition 4.3 depends on whether the game is silent or noisy. In the silent predator version, the Searcher can improve (slightly) on an expected search time of 2/3 by adopting mixed strategies. However, in the noisy predator version, he cannot as 2/3 is the value of the game.
4.6. Unreliable ambush, unsafe prey move
We have been assuming that an ambushing predator (moving at speed 0) always catches a moving prey. However, this is a simplifying but unrealistic assumption. Suppose we simply assume that in this situation the predator (Searcher) catches a moving prey (Hider) with some given probability r, called the ambush reliability factor. If the predator moves at a constant speed a (ambushes with probability 1 − a), the formula (4.3) for the expected capture time now becomes 4.6
Analysing this problem as in §4.1, the optimal time for the prey to move is easily calculated as: and figure 5 shows that for fixed predator speed, the prey will wait longer before moving when the reliability of ambush is higher.
We plot the worst case expected capture time for a predator moving at constant speed a, below in figure 6 for various ambush reliability factors r. Note that as the ambush reliability factor r increases (going to lower curves in the figure), the minimizing value of a decreases. So, for example, if visibility conditions improve, the predator should move slower (more time spent ambushing). This agrees with the studies Gendron [37] on quail, where ‘the colour of the prey was varied to achieve different degrees of camouflage … the birds adjust their search speed to maximize the rate of prey capture’.
We could also relax the assumption that a prey that moves during a cruising period will definitely be successful, by estimating the probability that such a move will pass within the detection radius of the predator. If D denotes the mean distance of such a randomizing prey move, and ρ is the detection radius, then this probability is the area of a rectangle of length D and width 2ρ, so coefficient of in equation (4.6) becomes r · s′(m) + 2ρD(1 − s′(m)). This probability was taken to be very small in Gal [7].
5. Conclusion
This paper introduces an additional Searcher strategy of ambush to the Princess and Monster Game of search theory, which models a tactic known to be used by some predators. The structure of the resulting game, the Ambush Search Game, allows us to consider how the use of the ambush strategy might be optimized. Our results can be interpreted as optimizing the frequency of ambush, or equivalently, as optimizing the predator's speed (either in a constant speed or variable speed context).
There are a number of ways in which some of the assumptions of our basic model might be relaxed to make it more applicable. Here, we considered that the predator might only discover the prey with some given probability when its location is explored. In this case, we were still able to find the optimal constant speed for a predator. We also showed how to modify our basic equation (4.1) to incorporate the possibility that a moving prey might be captured even by a cruising predator, if it came too near it during the move. Other assumptions that could be relaxed to make our model more applicable are: the predator might only discover the prey with some given probability when its location is explored; the predator might only sometimes perceive that the prey has just made of new randomizing move; the prey might not be aware of the predator's arrival at its patch. Of course, the simplicity of our results, particularly the square root law, would have to give way to numerical simulations in these cases.
Mixtures of cruising and ambushing as we find here are known to exist in other domains of search theory and practice: for example, when a convict escapes from prison, the police search the known hideouts (active search) but also put up roadblocks to prevent the escapee from switching between them (ambush). In conclusion, our model raises new functional questions regarding the dynamics of the search phase of many predator–prey interactions and adds a new dimension to the general theory of search games with mobile hiders.
Acknowledgements
S.A. and R.F. were supported by NATO Collaborative Research Grant CLG 983583.
 Received March 19, 2011.
 Accepted April 8, 2011.
 This Journal is © 2011 The Royal Society