Must the target move?

No. Many classical search games use an immobile hider.

Does the searcher always need to randomize?

No. The existence and usefulness of deterministic strategies depend on the model.

Is a search game always about physical locations?

No. Locations can represent abstract alternatives, provided actions, information and payoffs are defined clearly.

AI Glossary / Graphs and symbolic AI / Intermediate

Search game

Definition

A search game is a game-theoretic model in which a searcher tries to locate a target while a hider chooses a location or behavior that opposes the searcher's objective. Many classical versions are zero-sum: reducing detection time benefits the searcher and disadvantages the hider.

What it means

The defining feature is strategic interaction. Searching for misplaced keys under a known probability distribution is a search problem, but the keys do not choose where to be in response to the search policy. A hider in a search game does make a strategic choice.

The search space may be a finite collection of locations, a network or a continuous region. Some models keep the target stationary; others allow movement. Detection can be certain on inspection or imperfect, and these alternatives lead to different games.

This term should not be confused with using a search algorithm to choose moves in chess. A search game describes the interaction being modeled. A search algorithm may help solve that model, but it is a different concept.

How it works

Specify what the hider and searcher can choose, what they know and when choices occur. A finite-location model might let the hider select one box and let the searcher select an inspection order without observing the hiding choice.

Define the effort needed to inspect each location and the probability of detection when the target is there. If detection is imperfect, an unsuccessful inspection does not necessarily eliminate that location; revisiting it may be sensible.

Choose a payoff, such as expected time until discovery or probability of detection before a deadline. In a zero-sum formulation, one player minimizes the quantity the other maximizes, or the signs are reversed for a success probability.

Analyze strategies rather than only individual moves. A mixed strategy randomizes among possible choices, which can prevent a strategic opponent from exploiting a predictable pattern. Whether randomization is needed depends on the game's exact rules; it is not a universal instruction to act randomly.

Three practical examples

A classroom hide-and-seek simulation compares fixed inspection orders with randomized orders against a strategic hider.
A research model studies how unequal inspection times affect a searcher's allocation of effort across discrete locations.
A testing exercise evaluates a detection policy when simulated targets choose difficult locations, while clearly distinguishing this adversarial model from ordinary random placement.

Think of it this way

Think of a simplified hide-and-seek game with a small number of agreed hiding places. Always checking the same place first gives the hider useful information about the search pattern.

The analogy is bounded by the model's rules. Real hide-and-seek can involve movement, sound and partial clues, whereas a mathematical example may deliberately exclude all three. Conclusions should not be transferred across those differences without analysis.

Worked example

Consider two boxes, A and B. The hider chooses one before the search begins and cannot move. Each inspection takes one minute and finds the hider with certainty if it is in that box. The searcher chooses either A then B or B then A.

Always searching A first lets a hider choose B and force discovery at minute two. Let p be the probability that the searcher instead starts with A. If the hider chooses A, expected discovery time is p×1+(1−p)×2=2−p. If it chooses B, the time is p×2+(1−p)×1=1+p.

The searcher minimizes the worse of these two values by setting p=1/2. Both become 1.5 minutes. A hider choosing each box with probability one-half also makes either inspection order average 1.5 minutes, establishing the value for this small game.

That expectation does not mean every search lasts 90 seconds: individual searches still finish after one or two minutes.

Illustrative case study

In a fictional project, Alder Search Lab evaluates a simulated search policy only against targets placed uniformly at random. It then describes the policy as robust to a strategic hider.

The reviewers note that a fixed placement distribution and an opponent choosing a difficult location are different evaluation settings. They add the stated hider choices and information rules to the simulation and report results separately.

The case illustrates why a strategy claim requires a matching opponent model. It does not report a real deployment or establish that adversarial placement is appropriate for every search task.

Common misconceptions and mistakes

A search game is any program that searches a game tree. The term here concerns a searcher and a strategically placed or moving target.
Every target is adversarial. Many ordinary search problems have no strategic hider.
Inspecting a location always rules it out. Imperfect detection can leave the target undiscovered.
Randomization means ignoring the model. A probability distribution can be a carefully derived strategy.
Expected detection time is a guaranteed deadline. Individual outcomes can differ.
A result for stationary boxes automatically covers moving targets on a network. The changed rules require new analysis.

Business use

Search games are useful for evaluating policies when the location or behavior of a target may be chosen strategically. Before applying one, explain why an adversarial model is appropriate and what information the target is assumed to possess.

Check detection reliability and inspection costs rather than assuming equal effort everywhere. A policy designed for perfect detection can fail if a negative observation is treated as conclusive when it is not.

For AI systems, separate the model's optimal strategy from evidence about implementation and the actual environment. A mathematically sound strategy is only as relevant as its assumptions about movement, observation and available resources.

Check your understanding

In the two-box example, what happens if the searcher always starts with A and the hider knows that policy?

Answer: The hider can choose B, forcing two minutes until discovery. Randomizing equally between the two inspection orders reduces the worst expected time to 1.5 minutes under the stated rules.

Related terms

Game theory
Zero-sum games
Mixed strategy
Minimax
zero-sum game
detection probability
expected search time
pursuit-evasion
search policy

Learn next

Change the worked example so that inspecting A takes one minute and B takes two. Write the expected discovery times for each hiding choice as functions of the probability of starting with A, then find the probability that equalizes them.

Sources

Clarkson, Lin and Glazebrook, A Classical Search Game in Discrete Locations: https://arxiv.org/abs/2103.09310

Bui, Lidbetter and Lin, Optimal Pure Strategies for a Discrete Search Game: https://arxiv.org/abs/2306.10908

The authors' abstracts and model descriptions were reviewed. The two-box derivation and Alder Search Lab case are original illustrations; no full-paper proof audit is claimed.

Previous: Search engine Next: Search suggest drop-down list