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.
Get full access to this article
View all access options for this article.