Game Development Reference
In-Depth Information
of a searcher. In particular in the invisible fugitive case, such games model
the fact that often searchers can see further than just their current position,
for instance using torch lights, but they still cannot see the whole system of
tunnels they are asked to search. Such games, called domination games ,
were introduced by Fomin et al. [2003]. Kreutzer and Ordyniak [2009] study
complexity and monotonicity of these games and show domination games are
not only algorithmically much harder compared to classical cops and robber
games, they are also highly non-monotone (see Section 7.4.3 below).
Besides graph searching games inspired by applications related to graph
searching, there are also games which fall under the category of graph
searching games but were inspired by applications in logic. In particular,
Berwanger and Gradel [2004] introduce the game of entanglement and its
relation to the variable hierarchy of the modal μ -calculus.
7.4 Monotonicity of graph searching
As mentioned before, monotonicity features highly in research on graph
searching games for a variety of reasons. In this section we present some
of the most important techniques that have been employed for proving
monotonicity results in the literature.
In Section 7.4.1, we first introduce the concept of sub-modularity , which
has been used (at least implicitly) in numerous monotonicity results, and
demonstrate this technique by establishing monotonicity of the visible cops
and robber game discussed above.
Many graph searching games on undirected graphs have been shown to be
monotone. Other games, for instance many games on directed graphs, are
not monotone and examples showing that searchers can be saved by playing
non-monotonic have been given. In some cases, however, at least approximate
monotonicity can be retained in the sense that there is a function f :
N N
such that if k searchers can win by a non-monotone strategy then no more
then f ( k ) searchers are needed to win by a monotone strategy. Often f is
just a small constant. Many proofs of approximate monotonicity use the
concept of obstructions . We will demonstrate this technique in Section 7.4.2
for the case of directed graph searching.
7.4.1 Monotonicity by sub-modularity
The aim of this section is to show that the visible cops and robber game on
undirected graphs is monotone. The proof presented here essentially follows