Game Development Reference
In-Depth Information
as follows: m 0 =1,and m i +1 = m i + max
{
n u |
u
B ( m i )
}
.Nowwe
Σ G which turns out to be ( P F t )-winning in the
define a strategy σ
G . For every w
V V such that m i ≤|
vertex v of
w
|
<m i +1 we put
V .Nowit
σ ( w )= σ u ( uw 2 ), where w = w 1 uw 2 ,
|
w 1 |
= m i
1 and u
is easy to check that for every i
1 and every strategy π
Π G we have
σ,π
v
( Reach m i ( T, G )) > (1
1
that
P
2 i ) . This means that the strategy σ is
( P F t )-winning in v .
It remains to prove Claim (c). Consider a strategy σ
Σ G which for every
play of G initiated in v behaves as follows:
As long as player
uses only the optimal transitions, the strategy σ
behaves exactly like the strategy σ .
r for the first time, the
strategy σ starts to behave like an ε -optimal maximising strategy in r ,
where ε =( val ( r ,G )
When player
uses a non-optimal transition r
r is not optimal,
val ( r, G )) / 2. Note that since r
we have that val ( r ,G ) > val ( r, G ).
It is easy to check that σ is ( P F t )-winning in v .
5.4 Some directions of future research
There are many challenging open problems and emerging lines of research in
the area of stochastic games. Some of them have already been mentioned
in the previous sections. We close by listing a few attractive topics (the
presented list is of course far from being complete).
Infinite-state games. The existing results about infinite-state games
concern mainly games and MDPs generated by pushdown automata, lossy
channel systems, or one-counter automata (see Section 5.2 for a more
detailed summary). As indicated in Section 5.3, even in the setting of simple
reachability objectives, many questions become subtle and require special
attention. There is a plethora of automata-theoretic models with specific
advantages, and the corresponding games can have specific objectives
relevant to the chosen model. When compared to finite-state games, this
field of research appears unexplored and offers many open problems.
Games with non-conflicting objectives. It has been argued that
non-zero-sum stochastic games are also relevant for purposes of formal
verification of computer systems (see, e.g., Chatterjee et al. [2004c]). In
this case, the main problem is the existence and computability of Nash
equilibria (see Nash [1950]). Depending on the concrete objectives of the
players, a Nash equilibrium may or may not exist, and there can be several
Search Nedrilad ::




Custom Search