 Search game

A search game models a strategic interaction between a searcher and an opponent choosing what is hidden, where it is hidden, or how it moves. The searcher chooses a search policy; the payoff may be detection probability, discovery time or search cost. The information and allowed motion must be stated before solving the game.

For a simple zero-sum game, an object is hidden at one of two locations. Checking either location costs one time unit and always detects the object if present. Searching location one first with probability $p$ gives expected discovery times $2-p$ when the object is there and $1+p$ when it is at location two. Minimizing the worst case sets $p=1/2$, with value $3/2$.

A deterministic first choice permits the hider to force time two. Thus mixed strategies have a concrete value even in this small example. Adding unequal travel costs or an evading target changes both the strategy space and the optimization problem.

The term "Search Game" can refer to a couple of concepts depending on the context: 1. **Computer Science and Artificial Intelligence**: In the realm of algorithms, particularly in artificial intelligence (AI) and computer programming, a "search game" can refer to problems involving searching through a space (like a game tree or state space) to find an optimal solution.