Affiliations: [a] Minneapolis, Minnesota | [b] Baltimore, Maryland | [c] College Park, Maryland
Note: [1] This article is a reformulation and extension of two previous publications, viz. Glenn, Fang, and Kruskal (2007b; 2007c). They were presented at the CG 2006 Conference and CGW 2007 Workshop. The current article has been subjected to the regular refereeing procedure.
Note: [2] Dept. of Comp. Sci. and Eng., University of Minnesota, 200 Union St. S.E., Minneapolis, MN, 55455, USA. Email: hrfang@cs.umn.edu
Note: [3] Dept. of Computer Science, Loyola College in Maryland, 4501 N Charles St. Baltimore, MD 21210, USA. Email: jglenn@cs.loyola.edu
Note: [4] Dept. of Computer Science, University of Maryland, A.V. Williams Bldg., College Park, MD 20742, USA. Email: kruskal@cs.umd.edu
Abstract: We study algorithms for solving one-player and two-player stochastic games with perfect information, by modelling a game as a finite, possibly cyclic graph. We analyze a family of jeopardy stochastic games, prove the existence and uniqueness of optimal solutions, and give approximation algorithms to solve them by incorporating Newton’s method into retrograde analysis. Examples of jeopardy stochastic games include Can’t Stop, Pig, and some variants. Results of experiments on small versions of the game Can’t Stop are presented.
DOI: 10.3233/ICG-2008-31203
Journal: ICGA Journal, vol. 31, no. 2, pp. 77-96, 2008
