  Stochastic games are a classical model in game theory in which two opponents
interact and the environment changes in response to the players' behavior. The
central solution concepts for these games are the discounted values and the
value, which represent what playing the game is worth to the players for
different levels of impatience. In the present manuscript, we provide
algorithms for computing exact expressions for the discounted values and for
the value, which are polynomial in the number of pure stationary strategies of
the players. This result considerably improves all the existing algorithms,
including the most efficient one, due to Hansen, Kouck\'y, Lauritzen, Miltersen
and Tsigaridas (STOC 2011).
