  In two-player finite-state stochastic games of partial observation on graphs,
in every state of the graph, the players simultaneously choose an action, and
their joint actions determine a probability distribution over the successor
states. We consider reachability objectives where player 1 tries to ensure a
target state to be visited almost-surely or positively. On the basis of
information, the game can be one-sided with either (a)player 1 or (b)player 2
having partial observation, or two-sided with both players having partial
observation. On the basis of randomization (a)players may not be allowed to use
randomization (pure strategies), or (b)may choose a probability distribution
over actions but the actual random choice is not visible (actions invisible),
or (c)may use full randomization. Our results for pure strategies are as
follows: (1)For one-sided games with player 2 perfect observation we show that
belief-based strategies are not sufficient, and present an exponential upper
bound on memory both for almost-sure and positive winning strategies; we show
that the problem of deciding the existence of almost-sure and positive winning
strategies for player 1 is EXPTIME-complete and present symbolic algorithms
that avoid the explicit exponential construction. (2)For one-sided games with
player 1 perfect observation we show that non-elementary memory is both
necessary and sufficient for both almost-sure and positive winning strategies.
(3)We show that for the two-sided case finite memory strategies are sufficient
for both positive and almost-sure winning. We establish the equivalence of the
almost-sure winning problem for pure strategies with randomized strategies with
actions invisible. Our equivalence result exhibit serious flaws in previous
results in the literature: we show a non-elementary memory lower bound for
almost-sure winning whereas an exponential upper bound was claimed.
