  Simple Stochastic Games (SSGs) were introduced by Anne Condon in 1990, as the
simplest version of Stochastic Games for which there is no known
polynomial-time algorithm. Condon showed that Stochastic Games are
polynomial-time reducible to SSGs, which in turn are polynomial-time reducible
to Stopping Games. SSGs are games where all decisions are binary and every move
has a random outcome with a known probability distribution. Stopping Games are
SSGs that are guaranteed to terminate. There are many algorithms for SSGs, most
of which are fast in practice, but they all lack theoretical guarantees for
polynomial-time convergence. The pursuit of a polynomial-time algorithm for
SSGs is an active area of research. This paper is intended to support such
research by making it easier to study the graphical structure of SSGs. Our
contributions are: (1) a generating algorithm for Stopping Games, (2) a proof
that the algorithm can generate any game, (3) a list of additional
polynomial-time reductions that can be made to Stopping Games, (4) an open
source generator for generating fully reduced instances of Stopping Games that
comes with instructions and is fully documented, (5) a benchmark set of such
instances, (6) and an analysis of how two main algorithm types perform on our
benchmark set.
