Game Development Reference

In-Depth Information

equilibrium points. Some existing literature about non-zero-sum stochastic

games is mentioned in Section 5.2. The current knowledge is still limited.

•

Games with time.
The modelling power of continuous-time stochastic

models such as continuous-time (semi)Markov chains (see, e.g., Norris

[1998], Ross [1996]) or the real-time probabilistic processes of Alur et al.

[1991] can be naturally extended by the element of choice. Thus, we obtain

various types of continuous-time stochastic games. Stochastic games and

MDPs over continuous-time Markov chains were studied by Baier et al.

[2005], Neuhaußer et al. [2009], Brazdil et al. [2009b] and Rabe and

Schewe [2010]. In this context, it makes sense to consider various types

of strategies that measure or ignore the elapsed time, and study specific

types of objectives that can be expressed by, e.g., the timed automata of

Alur and Dill [1994].

The above discussed concepts are to a large extent orthogonal and can be

combined almost arbitrarily. Thus, one can model very complex systems of

time, chance, and choice. Many of the fundamental results are still waiting

to be discovered.

Acknowledgements:
I thank Vaclav Brozek and Tomas Brazdil for reading a

preliminary draft of this chapter. The work has been supported by the Czech

Science Foundation, grant No. P202/10/1469.

References

P. Abdulla, N. Henda, L. de Alfaro, R. Mayr, and S. Sandberg. Stochastic games

with lossy channels. In
Proceedings of FoSSaCS 2008
, volume 4962 of
Lecture

Notes in Computer Science
, pages 35-49. Springer, 2005.

R. Alur and D. Dill. A theory of timed automata.
Theoretical Computer Science
,

126(2):183-235, 1994. Fundamental Study.

R. Alur, C. Courcoubetis, and D. Dill. Model-checking for probabilistic real-time

systems. In
Proceedings of ICALP'91
, volume 510 of
Lecture Notes in Computer

Science
, pages 115-136. Springer, 1991.

C. Baier, M. Großer, M. Leucker, B. Bollig, and F. Ciesinski. Controller synthesis

for probabilistic systems. In
Proceedings of IFIP TCS'2004
, pages 493-506.

Kluwer, 2004.

C. Baier, H. Hermanns, J.-P. Katoen, and B. Haverkort. E
cient computation of

time-bounded reachability probabilities in uniform continuous-time Markov

decision processes.
Theoretical Computer Science
, 345:2-26, 2005.

C. Baier, N. Bertrand, and P. Schnoebelen. On computing fixpoints in well-structured

regular model checking, with applications to lossy channel systems. In
Pro-

ceedings of LPAR 2006
, volume 4246 of
Lecture Notes in Computer Science
,

pages 347-361. Springer, 2006.

Search Nedrilad ::

Custom Search