I asked essentially this on math.SE slightly more than
3 days ago, and it hasn't received any answer there.
Do finite-state 2-player zero-sum games of perfect information with only win-draw-loss outcomes always have deterministic-and-memoryless optimal strategies for both players?
In other words, consider 2-player games of the following form:
There is a non-empty finite set of states such that neither -1 nor +1 is a state.
One of the states is designated the initial state, and each state has [a label that's either P1 or P2]
and [a finite list of probability distributions on the union of {-1,+1} with the set of states].
Starting with the initial state, the indicated player (P1 or P2) chooses one of the probability distributions,
an element is sampled from that distribution, if the element is -1 then the game
ends with the indicated player scoring -1 and the other player scoring +1, if the element is +1 then
the game ends with the indicated player scoring +1 and the other player scoring -1, and if the
element is a state then reveal that state to that player and repeat this process from that state.
If the game continues forever then both players score 0.
Is it always the case that both players have optimal strategies
that are deterministic and only depend on the current state?