Answers.Body: <p>There are several different ways you can model the state and action spaces in such <a href="https://en.wikipedia.org/wiki/Extensive-form_game#:%7E:text=An%20extensive%2Dform%20game%20is,player%20has%20about%20the%20other" rel="nofollow noreferrer">sequential (extensive-form) environments/games</a>. For environments with small action spaces or those typically introduced to beginning-RL students, the state space and action space remains constant along an agent's trajectory (termed <a href="https://en.wikipedia.org/wiki/Normal-form_game#:%7E:text=The%20normal%2Dform%20representation%20of,strategy%20spaces%20and%20payoff%20functions" rel="nofollow noreferrer">normal form games</a> when there are multiple agents). In sequential games which can be illustrated as trees, a &quot;state&quot; is analogous to &quot;information set&quot; which is defined as the sequence (tuple) of actions and observations since the beginning of the game's episode. Terminal states (leaf nodes) exist, and the action space <span class="math-container">$\mathcal{A}[x]$</span> at an information set <span class="math-container">$x$</span> can be defined as a union of action sequences that can be taken to each terminal state, not counting terminal states that cannot be reached from the current information set.</p>
  <p>In the above examples, I discussed games such as the examples you stated where more than one agent can interact with the environment, but this is a generalization over RL and can be applied to when only one agent is maximizing its reward.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-23T17:50:33.997Z
Answers.Text: Thank you so much for your response. I'll probably take a look at a single minimaxing agent first. Then, I'll look into some of the other resources you raised.
  
  Again, thank you!
Answers.UserDisplayName: Why Not
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-20T13:20:12.703Z
Answers.LastActivityDate: 2020-12-20T13:20:12.703Z
Answers.UserDisplayName: rhdxor
Body: <p>I'm trying to learn about reinforcement learning techniques. I have little background in machine learning from university, but never more than using a CNN on the MNIST database.</p>
  <p>My first project was to use reinforcement learning on tic-tac-toe and that went well.</p>
  <p>In the process, I thought about creating an AI that can play a card game like <a href="https://en.wikipedia.org/wiki/Magic:_The_Gathering" rel="nofollow noreferrer">Magic: The Gathering</a>, <a href="https://en.wikipedia.org/wiki/Yu-Gi-Oh!" rel="nofollow noreferrer">Yu-gi-oh</a>, etc. However, I need to think of a way to define an action space. Not only are there thousands of combinations of cards possible in a single deck, but we also have to worry about the various types of decks the machine is playing and playing against.</p>
  <p>Although I know this is probably way too advanced for a beginner, I find attempting a project like this, challenging and stimulating. So, I looked into several different approaches for defining an action space. But I don't think this example falls into a continuous action space, or one in which I could remove actions when they are not relevant.</p>
  <p>I found this post on this <a href="https://ai.stackexchange.com/q/2219/2444">stack exchange</a> that seems to be asking the same question. However, the answer I found didn't seem to solve any of my problems.</p>
  <p>Wouldn't defining the action space as another level of game states just mask the exact same problem?</p>
  <p>My main question boils down to:</p>
  <p>Is there an easy/preferred way to make an action space for a game as complex as Magic? Or, is there another technique (other than RL) that I have yet to see that is better used here?</p>
  
Tags: <reinforcement-learning><ai-design><action-spaces>
Title: How should I define the action space for a card game like Magic: The Gathering?
UserDisplayName: Why Not
ThreadText: # How should I define the action space for a card game like Magic: The Gathering?
  
  (Asked by: username_0 on 2020-12-18)
  
  I'm trying to learn about reinforcement learning techniques. I have little background in machine learning from university, but never more than using a CNN on the MNIST database.
  
  My first project was to use reinforcement learning on tic-tac-toe and that went well.
  
  In the process, I thought about creating an AI that can play a card game like [Magic: The Gathering](https://en.wikipedia.org/wiki/Magic:_The_Gathering), [Yu-gi-oh](https://en.wikipedia.org/wiki/Yu-Gi-Oh!), etc. However, I need to think of a way to define an action space. Not only are there thousands of combinations of cards possible in a single deck, but we also have to worry about the various types of decks the machine is playing and playing against.
  
  Although I know this is probably way too advanced for a beginner, I find attempting a project like this, challenging and stimulating. So, I looked into several different approaches for defining an action space. But I don't think this example falls into a continuous action space, or one in which I could remove actions when they are not relevant.
  
  I found this post on this [stack exchange](https://ai.stackexchange.com/q/2219/2444) that seems to be asking the same question. However, the answer I found didn't seem to solve any of my problems.
  
  Wouldn't defining the action space as another level of game states just mask the exact same problem?
  
  My main question boils down to:
  
  Is there an easy/preferred way to make an action space for a game as complex as Magic? Or, is there another technique (other than RL) that I have yet to see that is better used here?
  
  **Tags:** reinforcement-learning, ai-design, action-spaces
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-12-20. Score: 2 | Accepted answer
  
  There are several different ways you can model the state and action spaces in such [sequential (extensive-form) environments/games](https://en.wikipedia.org/wiki/Extensive-form_game#:%7E:text=An%20extensive%2Dform%20game%20is,player%20has%20about%20the%20other). For environments with small action spaces or those typically introduced to beginning-RL students, the state space and action space remains constant along an agent's trajectory (termed [normal form games](https://en.wikipedia.org/wiki/Normal-form_game#:%7E:text=The%20normal%2Dform%20representation%20of,strategy%20spaces%20and%20payoff%20functions) when there are multiple agents). In sequential games which can be illustrated as trees, a "state" is analogous to "information set" which is defined as the sequence (tuple) of actions and observations since the beginning of the game's episode. Terminal states (leaf nodes) exist, and the action space $\mathcal{A}[x]$ at an information set $x$ can be defined as a union of action sequences that can be taken to each terminal state, not counting terminal states that cannot be reached from the current information set.
  
  In the above examples, I discussed games such as the examples you stated where more than one agent can interact with the environment, but this is a generalization over RL and can be applied to when only one agent is maximizing its reward.
  
  > **Comments:**
  > **username_0**: Thank you so much for your response. I'll probably take a look at a single minimaxing agent first. Then, I'll look into some of the other resources you raised.  Again, thank you!  
  
  ---
  
  