A search game is a two-person zero-sum game which takes place in a set called the search space. The searcher can choose any continuous trajectory subject to a maximal velocity constraint. It is always 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. 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. The area of search games was introduced in the last chapter of Rufus Isaacs

Rufus Isaacs (game theorist)

Rufus Philip Isaacs was a game theorist especially prominent in the 1950s and 1960s with his work on differential games.-Biography:...

' classic book "Differential Games" and has been developed further by Shmuel Gal

Shmuel Gal

Shmuel Gal is a professor of statistics at the University of Haifa in Israel.Gal received a Ph.D. in mathematics from the Hebrew University of Jerusalem....

  and Steve Alpern

Steve Alpern

Steven Alpern is a professor of mathematics at the London School of Economics. He has made a significant contribution to both the fields of search games and Rendezvous, informally introducing the rendezvous problem as early as 1976. His collaborators include Shmuel Gal, Vic Baston and Robbert...

.

What is the best way to search a stationary target in a graph? A natural strategy is to find a minimal closed curve L that covers all the arcs of the graph. (L is called a Chinese postman tour). Then, encircle L with probability 1/2 for each direction. This strategy seems to work well if the graph is Eulerian

Eulerian path

In graph theory, an Eulerian trail is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is a Eulerian trail which starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of...

. 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. 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. The optimal way to search these three arcs is surprisingly complicated ^[2] .

The princess and monster game

Princess and monster game

In game theory, the princess and monster game is a pursuit-evasion game played by two players in a region. The game was devised by Rufus Isaacs and published in his book Differential Games as follows. "The monster searches for the princess, the time required being the payoff. They are both in a...

 deals with a moving target.

Searching unbounded domains is also interesting. In general, the reasonable framework, as in the case of an online algorithm

Online algorithm

In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...

, is to use a normalized cost function (called the competitive ratio

Competitive analysis (online algorithm)

Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance...

 in Computer Science literature). The minimax

Minimax

Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...

 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

Linear search problem

In computational complexity theory, the Linear search problem is an optimal search problem introduced by Richard E. Bellman. .- The 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. 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.
Searching a set of concurrent rays was later re-discovered in Computer Science literature as the 'cow-path problem'.