Game Development Reference

In-Depth Information

Figure 7.6 Search tree for the strategy tree in Figure 7.4

Nisse [2008]. More recently, Amini et al. [2009], Lyaudet et al. [2009] and

Adler [2009] gave very abstract monotonicity proofs for games defined by

sub-modular borders which apply to a wide range of games played on graphs,

hypergraphs, matroids, etc. unifying many previous results.

7.4.2 Approximate monotonicity

In the previous section we have seen an important tool to establish mono-

tonicity for certain types of games whose border function is sub-modular.

However, not all games have sub-modular border functions and not all games

are monotone. In some cases where games are not monotone they are at least

approximately monotone
in the following sense.

Definition 7.26

of graph searching games is
approximately

monotone
if there is a function
f
:

A class

C

N
ā
N

such that for all games

GāC

and all
k

ā
N

,if
k
searchers have a winning strategy on

G

then at most
f
(
k
)

searchers have a monotone winning strategy on

G

.

An important tool for establishing approximate monotonicity is to use

obstructions
. In this section we demonstrate this idea by showing the following

theorem whose proof is derived from Johnson et al. [2001]. We will say more

about obstructions in Section 7.5

Search Nedrilad ::

Custom Search