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