{{short description|Two-person zero-sum game}} A '''search game''' is a zero-sum game between at least one searcher and one or more immobile or mobile targets which takes place in a set called the search space. The searcher(s) must detect or capture the target(s) under resource constraints. The searcher can choose any continuous trajectory subject to a maximal velocity constraint. As mathematical models, search games can be applied to areas such as hide-and-seek games that children play or representations of some tactical military situations, such as anti-submarine warfare or air defense, in which a searching vehicle sweeps a region to intercept an adversary historically.<ref>{{Cite journal |last=Hohzaki |first=Ryusuke |date=2016 |title=Search Games: Literature and Survey |url=https://www.jstage.jst.go.jp/article/jorsj/59/1/59_1/_article |journal=Journal of the Operations Research Society of Japan |volume=59 |issue=1 |pages=1–34 |doi=10.15807/jorsj.59.1|doi-access=free }}</ref> Today, these models extend to cybersecurity, where a defender traverses a "state space" of systems and networks in search of adversarial intrusions. There are also used in biology to model predator-prey interactions,<ref>{{Citation |last1=Ydenberg |first1=R.C. |last2=Dill |first2=L.M. |title=The Economics of Fleeing from Predators |date=1986-01-01 |series=Advances in the Study of Behavior |volume=16 |pages=229–249 |url=https://www.sciencedirect.com/science/chapter/bookseries/abs/pii/S0065345408601928 |access-date=2026-02-21 |publisher=Academic Press |language=en-US |doi=10.1016/S0065-3454(08)60192-8|isbn=978-0-12-004516-7 |url-access=subscription }}</ref><ref>{{Cite book |last1=Broom |first1=Mark |title=Game-theoretical models in biology |last2=Rychtář |first2=Jan |date=2013 |publisher=CRC press |isbn=978-1-4398-5321-4 |series=Chapman and Hall/CRC mathematical and computational biology series |location=Boca Raton (Fla.)}}</ref><ref>{{Cite journal |last1=Gal |first1=Shmuel |last2=Casas |first2=Jérôme |date=2014-05-06 |title=Succession of hide–seek and pursuit–evasion at heterogeneous locations |journal=Journal of the Royal Society Interface |language=en |volume=11 |issue=94 |article-number=20140062 |doi=10.1098/rsif.2014.0062 |issn=1742-5689 |pmc=3973372 |pmid=24621817}}</ref> where a predator can have finite resources (number of daylight hours, motivation,<ref>{{Cite journal |last=McNair |first=James N. |date=April 1982 |title=Optimal Giving-Up Times and the Marginal Value Theorem |url=https://www.journals.uchicago.edu/doi/abs/10.1086/283929 |journal=The American Naturalist |volume=119 |issue=4 |pages=511–529 |doi=10.1086/283929 |bibcode=1982ANat..119..511M |issn=0003-0147|url-access=subscription }}</ref> etc.)
== Definition == A search game introduces:
* A search space X, which can be a Euclidean domain, a graph, or a more abstract state space. * One or more searchers whose trajectory is a measurable function of time, subject to a maximal speed constraint or a movement budget. * One or more hiders or targets, static or mobile, that choose an initial location or a trajectory under their own constraints. * the set of strategies for the hider(s) and the searcher(s) * A detection rule, often formulated as "capture" when the distance between searcher and target becomes smaller than a detection radius, or when an observation region is visited. * A performance criterion, such as time to detection, detection probability before a horizon, or a more general cost–reward combination.
The game is typically played under uncertainty: players do not necessarily observe each other's exact positions until within detection range; instead, they may have partial information.<ref>{{Cite book |title=Search theory: a game theoretic perspective |date=2013 |publisher=Springer |isbn=978-1-4614-6824-0 |editor-last=Alpern |editor-first=Steve |location=New York}}</ref> Strategies may be pure, mixed, feedback, or information-based, depending on the observation structure and the game dynamics.
== Origins == The area of search games was introduced in the last chapter of Rufus Isaacs' classic book "Differential Games",<ref>Rufus Isaacs, ''Differential Games'', John Wiley and Sons, (1965),</ref> where Isaacs studies pursuit–evasion and search scenarios with partial information.
=== Princess and Monster game === The princess and monster game deals with a moving target, a searcher must find a "princess" moving on an interval or a domain with limited visibility and continuous dynamics. This game illustrates the difficulty of designing optimal strategies when player trajectories are continuous and information is very restricted. It is assumed that neither the searcher nor the hider has any knowledge about the movement of the other player until their distance apart is less than or equal to the discovery radius and at this very moment capture occurs. The game is zero sum with the payoff being the time spent in searching. A natural strategy to search for a stationary target in a graph (in which arcs have lengths) is to find a minimal closed curve L that covers all the arcs of the graph. (L is called a Chinese postman tour). Then, traverse L with probability 1/2 for each direction. This strategy seems to work well if the graph is Eulerian. In general, this random Chinese postman tour is indeed an optimal search strategy if and only if the graph consists of a set of Eulerian graphs connected in a tree-like structure.<ref>{{cite journal | first1=Shmuel | last1=Gal | title=On the optimality of a simple strategy for searching graphs | journal=International Journal of Game Theory | volume=29 | pages=533–542 | year=2001 | issue=4 | doi=10.1007/s001820000056 | doi-access=free}}</ref> A misleadingly simple example of a graph not in this family consists of two nodes connected by three arcs. The random Chinese postman tour (equivalent to traversing the three arcs in a random order) is not optimal, and the optimal way to search these three arcs is complicated.<ref name="Gal">S. Gal, ''Search Games'', Academic Press, New York (1980)</ref>
=== Unbounded domains === In general, the reasonable framework for searching an unbounded domain, as in the case of an online algorithm, is to use a normalized cost function (called the competitive ratio in Computer Science literature). The minimax trajectory for problems of these types is always a geometric sequence (or exponential function for continuous problems). This result yields an easy method to find the minimax trajectory by minimizing over a single parameter (the generator of this sequence) instead of searching over the whole trajectory space. This tool has been used for the linear search problem, i.e., finding a target on the infinite line, which has attracted much attention over several decades and has been analyzed as a search game.<ref>{{cite journal | first1=Anatole | last1=Beck | first2=D.J. | last2=Newman | title=Yet More on the linear search problem | journal=Israel Journal of Mathematics | volume=8 | pages=419–429 | year=1970 | issue=4 | doi=10.1007/BF02798690 | doi-access=free}}</ref> It has also been used to find a minimax trajectory for searching a set of concurrent rays. Optimal searching in the plane is performed by using exponential spirals.<ref name="Gal" /><ref name="Alpern&Gal">S. Alpern and S. Gal, ''[https://books.google.com/books?id=BBrvBwAAQBAJ&dq=%22The+Theory+of+Search+Games+and+Rendezvous%22&pg=PR11 The Theory of Search Games and Rendezvous]'', Springer (2003).</ref><ref>M. Chrobak, A princess swimming in the fog looking for a monster cow, ACM Sigact news, 35(2), 74–78 (2004).</ref> Searching a set of concurrent rays was later re-discovered in Computer Science literature as the 'cow-path problem'.<ref>MY Kao, JH Reif and SR Tate, [https://www.sciencedirect.com/science/article/pii/S0890540196900929/pdf?md5=129f6c53511fe88b0314aa2af1d113d3&pid=1-s2.0-S0890540196900929-main.pdf&_valck=1 Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem], SODA 1993.</ref>
=== Future developments === They has been developed further by Shmuel Gal<ref name="Gal" /><ref name="Alpern&Gal" /> and Steve Alpern<ref name="Alpern&Gal" />, who developed the mathematical foundations of search games, especially for continuous search spaces, diverse information structures, and minimax optimality criteria. From the 1990s–2000s onwards, the literature expanded towards variants on networks, discrete environments, and problems inspired by economics, security, or autonomous robotics.
== Modern taxonomy of search games == Recent reviews propose a detailed classification of search games according to the strategies available to searcher and target.<ref>{{Cite journal |last=Hohzaki |first=Ryusuke |date=2016 |title=Search Games: Literature and Survey |url=https://www.jstage.jst.go.jp/article/jorsj/59/1/59_1/_article |journal=Journal of the Operations Research Society of Japan |language=en |volume=59 |issue=1 |pages=1–34 |doi=10.15807/jorsj.59.1 |issn=0453-4514|doi-access=free }}</ref>
* In '''Stationary-target''' search games, only the searcher moves and the target is described by an initial distribution over the search space. * In '''Mobile-target''' search games, the target actively chooses a trajectory, often under speed or topology constraints, bringing them close to pursuit–evasion games. * In '''Path-constrained''' games, both players must move along prescribed paths, for example along a road network, corridors, or shipping lanes. For the searcher, optimal solutions often involve cyclic or randomized sweep policies, sometimes with randomization in time to avoid predictability. * In '''Search–search''' games, multiple searchers or multiple targets interact, such as competing patrols or coordinated defense and attack coalitions.
An unifying view between search games and pursuit-evasion games sees many adversarial systems as a succession of phases: a hiding and searching phase (hide–seek), a pursuit–evasion phase after detection, and a possible capture or engagement phase. Each phase has its own information, dynamics, and payoff structure.<ref>{{Cite journal |last1=Gal |first1=Shmuel |last2=Casas |first2=Jérôme |date=2014-05-06 |title=Succession of hide–seek and pursuit–evasion at heterogeneous locations |journal=Journal of the Royal Society Interface |language=en |volume=11 |issue=94 |article-number=20140062 |doi=10.1098/rsif.2014.0062 |issn=1742-5689 |pmc=3973372 |pmid=24621817}}</ref><ref>{{Cite journal |last1=Clémençon |first1=Paul |last2=Alpern |first2=Steve |last3=Gal |first3=Shmuel |last4=Casas |first4=Jérôme |date=September 2023 |title=Counterintuitive prey strategies against predators with finite budgets: protection heterogeneity among sites matters more than their number |journal=Journal of the Royal Society Interface |volume=20 |issue=206 |article-number=20230216 |doi=10.1098/rsif.2023.0216 |issn=1742-5662 |pmc=10509579 |pmid=37727074}}</ref>
Decisions made during the search phase determine the initial conditions of the pursuit, such as distance, interception angle, or remaining energy.
A current trend is the study of dynamic search games in which players learn<ref>{{Cite journal |last1=Alpern |first1=Steve |last2=Gal |first2=Shmuel |last3=Lee |first3=Viciano |last4=Casas |first4=Jérôme |date=2019-04-26 |title=A stochastic game model of searching predators and hiding prey |journal=Journal of the Royal Society Interface |language=en |volume=16 |issue=153 |article-number=20190087 |doi=10.1098/rsif.2019.0087 |issn=1742-5689 |pmc=6505550 |pmid=30940027}}</ref> or adapt during the game rather than having complete prior knowledge of the environment. This framework is relevant when the searcher gradually accumulates experience about typical target behaviours or terrain properties. Hybrid models combine game theory with learning techniques, such as reinforcement learning or Bayesian learning, to progressively adjust search and hiding strategies.
== Methods == The theoretical analysis of search games relies on tools from game theory, optimization, and optimal control. For simple models, analytical solutions can be obtained by exploiting symmetries, coupling arguments, or geometric transformations.
However, most realistic problems require numerical or approximate methods, such as discretized dynamic programming, value iteration algorithms, or semi-Lagrangian schemes. Challenges arise from the high dimensionality of the state space, nonlinear dynamics, and complex information structures. Acceleration techniques such as phase separation, pruning, or heuristic value estimates mitigate combinatorial explosion while preserving optimality in some cases.
==References== <references/> {{Game theory}}
{{DEFAULTSORT:Search Games}} Category:Non-cooperative games Category:Search algorithms