Game Development Reference

In-Depth Information

questions about the variable hierarchy in the modal
μ
-calculus, as explored

by Berwanger and Gradel [2004].

See the annotated bibliography of graph searching by Fomin and Thilikos

[2008] for further applications and references.

As different applications require different types of games, it is not surprising

that graph searching games come in many different forms. We will give an

overview of some of the more commonly used variants of games in the

Section 7.3.

Organisation.
This chapter is organised as follows. In Section 7.2 we first

define graph searching games in an abstract setting and we introduce formally

the concept of monotonicity. We also explore the connection between graph

searching and reachability games and derive a range of general complexity

results about graph searching games. In Section 7.3 we present some of the

more commonly used variants of graph searching games. The monotonicity

problem and some important tools to show monotonicity are discussed in

Section 7.4. Formalisations of winning strategies for the fugitive in terms of

obstructions
are discussed in Section 7.5. We will explore the connections

between graph searching and graph decompositions in Section 7.6. Finally,

in Section 7.7 we study the complexity of deciding the minimal number of

searchers required to search a graph in a given game and we close this chapter

by stating open problems in Section 7.8. Throughout the chapter we will

use some concepts and notation from graph theory which we recall in the

appendix.

7.2 Classifying graph searching games

In the previous section we have described one particular version of graph

searching, also known as the
Invisible Cops and Robber
games. Possible

variants of this game arise from whether or not the fugitive is invisible, from

the type of graph the game is played on, i.e., undirected or directed, a graph

or a hypergraph, whether the searchers can move freely to any position or

whether they can only move along one edge at a time, whether searchers only

dominate the vertex they occupy or whether they dominate other vertices as

well, whether the fugitive or the searchers can move in every round or only

once in a while, and many other differences. The great variations in graph

searching games has made the field somewhat confusing. The fact that the

same names are often used for very different games does not help either. In

Search Nedrilad ::

Custom Search