Parameterizing Reinforcement Learning card game state space

Question

I want to model a particular card game as a reinforcement learning problem. For simplicity let's say it is a single standard 52 card deck, and let's say it is just 2 players. The exact details are not so important for the action space; I'm more interested in how to model the state space.

terminal rewards: +1 if I win, -1 if I lose (you win). Zero-sum game, no ties.

Actions: pretty limited: - Play a card that matches suit or value of the face up discard pile - play a wild card (regardless of top face up discard) - draw one card (either voluntarily or because you cannot play a card and must draw). The exact details are not important, I know how to model this.

State space: There are several ways I can think to model this. Besides the cards I have in my hand, it is also important to know what the top card of the discard pile is so I know which actions are available. Also, it is important to know how many cards the opponent has remaining (since we are trying to get rid of cards), or estimates/probabilities of which cards they might have. Similarly, estimates or probabilities of cards in the draw pile. And if the agent is allowed to have perfect memory, can also remember which cards have been played.

So, in the most general case, I could do a 3x52 state space vector. - Elements 1-52 would be the one hot encoded vector of which cards I have. Can be binary since I know deterministic ally which cards I have. - Next 52 elements could be again one hot encoded vector of which cards have been discarded. [Allowing the agent to have perfect memory which is a little unfiair if playing against human, but ok...]. Again binary since know for certain if discarded or not. - Last 52 elements could be probabilities of which cards opponent has. I could assume uniform probabilities over the possible cards (possible meaning I don't have them in my hand, and they haven't already been discarded). They would be either in opponent's hand or in draw pile. (I don't need to explictly model the 52 probabilities of cards in draw pile since if they are not in my hand or in discard pile, then they are either in opponent's hand or in draw pile. So these probabilities are implictly defined by the preceding 3x52 elements).

---

Ok, so 3x52 is a lot of elements to have in the state vector: and even if the elements were only binary that would already be 2^156 states, but it's a lot worse because some of the elements have many possible values. I can think of alternative ways to reduce state space by e.g. just focusing on counts/probabilities of special cards and number of cards remaining in my hand, opponent's hand, and draw pile. This could bring it down to say ~15 elements in state vector, each of which has a few possible values, let's say 5^15 states which is kind of reasonable (way way way less than Chess or Go, e.g.).

My question is: can I successfully use the large state space which has full information, or do I need to use a reduced/compressed state space? Or can you think of a better parametrization of the state space? Remember, my set of actions for a given state is pretty limited, so even though the state space is large the action space is pretty small (maybe 5-10 actions on average; depends on early vs. late stages of game).

Answer 1

I'm not sure if I can answer your question, but let me try.

Whether 5^15 states is acceptable is dependent on your requirements for speed and the specs of your machine. To me, it sounds like a lot. Don't forget your action space adds another dimension to your Q-matrix, which then holds some 5^16th elements (10 actions). During training, all of these state-action-pairs should be visited at least a few times before being able to generate 'wise' actions during play.

I was in a similar situation a short while ago in my thesis work and I dropped discrete state-action descriptions and opted for value function approximation instead. Especially when there is similarity between neighboring states, using approximative methods can be of help. Check out David Silver's lectures on these methods for a more thorough explanation. I developed a set of parameters to describe my state and during learning trained a very basic neural network (NN) to predict Q(s,a). The parameters formed the input to the NN.