Abstract: 
In twoplayer finitestate 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. The game is played for infinitely many rounds and thus the players construct an infinite path in the graph. We consider reachability objectives where the first player tries to ensure a target state to be visited almostsurely (i.e., with probability 1) or positively (i.e., with positive probability), no matter the strategy of the second player. We classify such games according to the information and to the power of randomization available to the players. On the basis of information, the game can be onesided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or twosided with (c) both players having partial observation. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. Our main results for pure strategies are as follows: (1) For onesided games with player 2 having perfect observation we show that (in contrast to full randomized strategies) beliefbased (subsetconstruction based) strategies are not sufficient, and we present an exponential upper bound on memory both for almostsure and positive winning strategies; we show that the problem of deciding the existence of almostsure and positive winning strategies for player 1 is EXPTIMEcomplete and present symbolic algorithms that avoid the explicit exponential construction. (2) For onesided games with player 1 having perfect observation we show that nonelementarymemory is both necessary and sufficient for both almostsure and positive winning strategies. (3) We show that for the general (twosided) case finitememory strategies are sufficient for both positive and almostsure winning, and at least nonelementary memory is required. We establish the equivalence of the almostsure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence result exhibit serious flaws in previous results of the literature: we show a nonelementary memory lower bound for almostsure winning whereas an exponential upper bound was previously claimed.
