How should I define the action space for a card game like Magic: The Gathering?

Question

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, 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 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?

Answer 1

There are several different ways you can model the state and action spaces in such sequential (extensive-form) environments/games. 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 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.