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 A or B]
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 (A or B) 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 curren state?