What should the action space for the card game Crib be?

I'm working on creating an environment for a card game, which the agent chooses to discard certain cards in the first phase of the game, and uses the remaining cards to play with. (The game is Crib if you are familiar with it.)

How can I make an action space for these actions? For instance, in this game, we could discard 2 of 6 cards, then choose 1 of 4 remaining cards to play, then 1 of 3 remaining cards, then 1 of 2 remaining cards. How do I model this?

I've read this post on using MultiDiscrete spaces, but I'm not sure how to define this space based on the previous chosen action. Is this even the right approach to be taking?

• I am not familiar with the game, but the way it looks - you are performing only one action - which is discarding cards. The only thing that changes is the number of times you are performing that action. May 23, 2020 at 17:17

I've actually implemented this game before using deep reinforcement learning. You are dealing with a dynamic action space here, where the action space may change at each time step of the game (or more generally the MDP). First, let's discuss the actual action spaces in each one of the two phases of Crib (or Cribbage) and formalize the question.

Phase 1: The Discard:In this phase, you are concurrently discarding 2 cards without respect to order. Therefore, you have a fixed discrete action space of size $${{6}\choose{2}} = 15$$.

Phase 2: The Play: In this phase, you and your opponent are sequentially playing one of each of your remaining 4 cards (the original 6 minus the 2 discarded from phase 1). Therefore, you have a discrete action space of size $$4! = 24$$. Here's the catch - not every one of these actions is legal. The current state of the game restricts which cards you are allowed to play (the sum of all cards currently played must not be greater than 31). Since you do not know your opponent's cards and/or policy, you do not know which of these 24 actions are valid. To remedy this, the action space should dictate which of your remaining cards may be played at the current time step. Thus, you have a dynamic discrete action space of size 1, 2, 3, or 4 at each time step.

How can I make an action space for these actions?

Since you didn't specify any implementation standard (e.g. OpenAI Gym), there are multiple paths to take, and they usually depend on your implementation of the state feature vector. In my own implementation, I tinkered with two possible state representations, which are fairly simple to describe.

Possibility 1: Separate State Representations for each Phase: In phase 1, you need to know the cards in your hand and the scores; i.e., the state feature vector could be encoded as a list of [card0, card1, card2, card3, card4, card5, your score, opponent score]. This state represents all information known about the game during phase 1 from a single player's viewpoint; after each time step, the current player may change, and the state must be updated according to the current player's viewpoint. Each card can be encoded as an integer from 1 to 52 (not starting from 0, as we will see in the next paragraph), and the score is an integer from 0 to 120 (tip: sort your cards for a reduced state space and faster convergence). Your action space can be the set of integers from 0 to 14 that maps to a 2-card combination in your hand. Alternatively, you could have a dynamic action space that sequentially asks for 1 of your 6 cards to discard and then for 1 of your remaining 5 cards to discard. The action space can be a subset of integers from 0 to 5 that maps to a single card in your hand. Be careful here - when choosing the second card to discard, your algorithm must know which card was discarded first. You can solve this by adding another component to your state vector that represents the first card that was discarded (set to 0 at the beginning of the phase), and therefore, make sure to update the state after the first discard.

In phase 2, you need to know the 4 cards in your hand, the cut card, the scores, and the cards currently played. Another helpful but unnecessary feature for learning is the current sum of played cards. A possible representation is a list of [card0, card1, card2, card3, card played0, card played 1, card played 2, …, card played 7, your score, opponent score, cut card, current sum of played cards]. The values of played cards should be initialized to 0 at the beginning of the phase. The state can be updated so that any card in your hand that you have played is set to 0, and any card played by your opponent can be set to its negative value. This will correctly encode which cards have been played from your hand, which cards played are your from your opponent, and all other available information. Consequently, the action space is dynamic and is a subset of integers from 0 to 3 that maps to a single card in your hand.

Possibility 2: Identical State Representations for each Phase Another possibility is to have all of the above information for each phase encoded into a single state representation along with the phase number. State features that are unique to phase 2 that aren't relevant for phase 1 can be set to 0 during phase 1 and vice versa. With this representation, the state feature vector is of the same length at all time steps of the game, and the action space will change as described above. The important ideas for the encoding are exactly the same as above and will change based on your particular implementation, so I won't include the details here.

How do I model this?

If you are going to implement something similar to Possibility 1, then you may need two agents that each learn a policy for a separate phase. For starters, you could use Q-learning or DQN and take the action with greatest q-value at each timestep, making sure that the chosen action is always a member of the current action space.

If you are going to implement something similar to Possibility 2, then you may only need a single agent that learns a policy for each phase, simply because the phase is a feature of the state. Essentially you are trading off a more complicated state representation for a simpler learning algorithm.

I've read this post on using MultiDiscrete spaces, but I'm not sure how to define this space based on the previous chosen action. Is this even the right approach to be taking?

After reading the OpenAI Gym documentation, it looks like the MultiDiscrete space is a product of Discrete spaces. Therefore, it is a fixed action space and inherently not what you want here (a dynamic action space). I don't believe that OpenAI Gym standards will support dynamic action spaces natively. You would need to do some extra work such as providing a method that returns the current action space of the environment. Alternatively, if you want to follow the (state, reward, done, info) signal paradigm from OpenAI Gym, you may provide the current action space in the info dictionary. Finally, another idea is to allow the agent to always choose an action from a larger fixed action space (e.g. the set of integers from 0 to 3 for phase 2) and then penalize the agent through the reward signal whenever it chooses an action that is not a member of the current action space (e.g. if the chosen card was already played in phase 2). Afterward, you would return the current game state as the next state and make the agent try again.

My advice is to first determine the state representation, and the rest of your implementation should follow, using the ideas above.

• Wow, thanks for your reply, It really helps me out a lot! I am using OpenAI Gym, so this information is very actionable for me. It looks like this is exactly what I'm after so I'll try to implement one of your suggestions. Jun 6, 2020 at 16:37