  We study the problem of solving discounted, two player, turn based,
stochastic games (2TBSGs). Jurdzinski and Savani showed that 2TBSGs with
deterministic transitions can be reduced to solving $P$-matrix linear
complementarity problems (LCPs). We show that the same reduction works for
general 2TBSGs. This implies that a number of interior point methods for
solving $P$-matrix LCPs can be used to solve 2TBSGs. We consider two such
algorithms. First, we consider the unified interior point method of Kojima,
Megiddo, Noma, and Yoshise, which runs in time $O((1+\kappa)n^{3.5}L)$, where
$\kappa$ is a parameter that depends on the $n \times n$ matrix $M$ defining
the LCP, and $L$ is the number of bits in the representation of $M$. Second, we
consider the interior point potential reduction algorithm of Kojima, Megiddo,
and Ye, which runs in time $O(\frac{-\delta}{\theta}n^4\log \epsilon^{-1})$,
where $\delta$ and $\theta$ are parameters that depend on $M$, and $\epsilon$
describes the quality of the solution. For 2TBSGs with $n$ states and discount
factor $\gamma$ we prove that in the worst case $\kappa =
\Theta(n/(1-\gamma)^2)$, $-\delta = \Theta(\sqrt{n}/(1-\gamma))$, and $1/\theta
= \Theta(n/(1-\gamma)^2)$. The lower bounds for $\kappa$, $-\delta$, and
$1/\theta$ are obtained using the same family of deterministic games.
