Answers.Body: <p>The game of TIC-TAC-TOE can be modelled as a non-deterministic Markov decision process (MDP) if, and only if:</p>
  <ul>
  <li><p>The opponent is considered part of the environment. This is a reasonable approach when the goal is to solve playing against a specific opponent.</p>
  </li>
  <li><p>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.</p>
  </li>
  </ul>
  <blockquote>
  <p>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.</p>
  </blockquote>
  <p>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 <em>opponent</em> plays.</p>
  <p>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 <em>rational</em>) move, which can be determined using a search process such as <a href="https://en.wikipedia.org/wiki/Minimax" rel="nofollow noreferrer">minimax</a>. When there is imperfect information, such as in poker, it becomes much harder to allow for an opponent's action.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-03T14:08:17.140Z
Answers.Text: Thank you. But from this answer, every multi agent environment can be viewed as a non deterministic because `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`. Is there any example of a multi-agent system with a deterministic environment ?
Answers.UserDisplayName: EEAH
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-03T14:25:20.517Z
Answers.Text: @EEAH: That is correct. It will depend on how you define and implement multi-agent environments. However, if the agent needs to account for the behaviour of the other agents then the result can be non-deterministic. You can reasonably say that the core of the environment is deterministic, in the same sense that TIC TAC TOE is a deterministic game, but the agents may often need to deal practically with non-deterministic and/or partially-observable features, regardless of whether you say that is due to the agents separately, or if you consider other agents to be part of the environment.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-03T08:29:41.793Z
Answers.LastActivityDate: 2020-08-03T14:59:52.240Z
Answers.LastEditDate: 2020-08-03T14:59:52.240Z
Answers.UserDisplayName: Neil Slater
Body: <p>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.</p>
  <p>But why is that?</p>
  <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-08-03T02:24:40.470Z
Comments.Text: You say "when I came up with an article that states that TIC TAC TOE is a non-deterministic environment.". Can you please provide the link to the article?
Comments.UserDisplayName: nbro
Tags: <game-ai><markov-decision-process><game-theory><pomdp><tic-tac-toe>
Title: Why is tic-tac-toe considered a non-deterministic environment?
UserDisplayName: EEAH
ThreadText: # Why is tic-tac-toe considered a non-deterministic environment?
  
  (Asked by: username_0 on 2020-08-02)
  
  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.
  
  **Tags:** game-ai, markov-decision-process, game-theory, pomdp, tic-tac-toe
  
  > **Comments:**
  > **username_1**: You say "when I came up with an article that states that TIC TAC TOE is a non-deterministic environment.". Can you please provide the link to the article?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-08-03. Score: 3 | Accepted answer
  
  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](https://en.wikipedia.org/wiki/Minimax). When there is imperfect information, such as in poker, it becomes much harder to allow for an opponent's action.
  
  > **Comments:**
  > **username_0**: Thank you. But from this answer, every multi agent environment can be viewed as a non deterministic because `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`. Is there any example of a multi-agent system with a deterministic environment ?  
  > **username_2**: @username_0: That is correct. It will depend on how you define and implement multi-agent environments. However, if the agent needs to account for the behaviour of the other agents then the result can be non-deterministic. You can reasonably say that the core of the environment is deterministic, in the same sense that TIC TAC TOE is a deterministic game, but the agents may often need to deal practically with non-deterministic and/or partially-observable features, regardless of whether you say that is due to the agents separately, or if you consider other agents to be part of the environment.  
  
  ---
  
  