I have been reading about deterministic and stochastic environments, when I came up with an article that states that tic-tac-toe is a non-deterministic environment.
But why is that?
An action will lead to a known state of the game and an agent has full knowledge of the board and of its enemies' past moves.
The game of TIC-TAC-TOE can be modelled as a non-deterministic Markov decision process (MDP) if, and only if:
The opponent is considered part of the environment. This is a reasonable approach when the goal is to solve playing against a specific opponent.
The opponent is using a stochastic policy. Stochastic policies are a generalisation that include deterministic policies as a special case, so this is a reasonable default assumption.
An action will lead to a known state of the game and an agent has full knowledge of the board and of Its enemies past moves.
Whilst this is true, the next state and reward as observed by an agent may not be due to the postion it plays in (with the exception being if it wins or draws on that move), but the position after the opponent plays.
It is also possible to frame TIC-TAC-TOE as a partially observed MDP (POMDP) if you consider the opponent to not have a fixed policy, but to be reacting to play so far, perhaps even learning from past games. In which case, the internal state of the opponent is the unknown part of the state. In standard game playing engines and in games of perfect information, this is resolved by assuming the opponent will make the best possible (or rational) move, which can be determined using a search process such as minimax. When there is imperfect information, such as in poker, it becomes much harder to allow for an opponent's action.
