4
$\begingroup$

Consider a single-player card game which shares many characteristics to "unprofessional" (not being played in casino, refer point 2) Blackjack, i.e.:

  • You're playing against a dealer with fixed rules.
  • You have one card deck which is played completely through.
  • etc. An exact description of the game isn't needed for my question, thus I remain with these simple bullet points.

Especially the second point bears an important implication. The more cards that have been seen, the higher your odds of predicting the subsequent card - up to a 100% probability for the last card. Obviously, this rule allows for precise exploitation of said game.

As far as the action and state space is concerned: The action space is discrete, the player only has a fixed amount of actions (in this case five - due to the missing explanation of the rules, I won't go in-depth about this). Way more important is the state space. In my case, I decided to structure it as follows:

A 2 3 4 5 6 7 8 9 10 J
4 4 4 4 4 4 4 4 4 14 2

First part of my state space describes each card value being left in the stack, thus on the first move all 52 cards are still in the deck. This part alone allows for about 7 million possible variations.

Second part of the state space describes various decks in the game (once again without the rules it's hard to explain in detail). Basically five integers ranging from 0-21, depending on previous actions. Another 200k distinct situations.

Third part are two details - some known cards and information, though they only account for a small factor, but still bring in a considerable amount of variation into my state space.

Thus a complete state space might look something like this: Example one would be the start setup: 444444444142;00000;00. Another example in midst of the game: 42431443081;1704520;013. Semicolons have been added for readability purposes.

So now arises the question: From my understanding my state space is definitely finite and discrete, but too big to be solved by SARSA, Q-learning, Monte Carlo or alike. How can I approach projects with a big state space without loosing a huge chunk of predictability (which I might fear with DQN, DDPQ or TD3)? Peculiarly due to the fact that only one deck is being used - and it's played through in this game - it seems like a more precise solution would be possible.

$\endgroup$
8
  • $\begingroup$ If there are any questions left, feel free to post them below. $\endgroup$ Sep 9 '21 at 7:20
  • $\begingroup$ 1. The explanation of the state/action space is unclear. You mention "rules" with no explanation as to what these are or how they affect the game. It seems to me like the state space should be 12 dimensional (number of each of the 11 cards in deck, + value of your current hand). I don't understand this second part "various decks in the game" or the third part "details". Are the 5 actions corresponding to en.wikipedia.org/wiki/Blackjack#Player_decisions? $\endgroup$
    – Taw
    Sep 11 '21 at 7:15
  • $\begingroup$ 2. What do you mean by "losing a huge chunk of predictability" when using something like DQN/DDPG? Also I should point out that you don't have to use neural network function approximators - one popular option is using linear combinations of hand picked features as your function approximator. $\endgroup$
    – Taw
    Sep 11 '21 at 7:18
  • $\begingroup$ Also, as far as I'm aware, blackjack is a solved game, so that offers a precise solution to the optimal blackjack policy. $\endgroup$
    – Taw
    Sep 11 '21 at 7:19
  • $\begingroup$ @Taw Thanks for your replies. To clear things up a bit: The game resembles Blackjack in some rudimentary characteristics, i.e. cards can be counted - but it’s not Blackjack. Should have mentioned that more clearly. My simple problem is the sheer size of the underlying state space (it can’t be shortened further or else considerable losses in performance would arise). As far as your second question is concerned, I was referring to the approximating of my state space - which, if Implemented poorly, could end up with a horrible performance. Nonetheless, I’d be curious to how you’d approach that. $\endgroup$ Sep 12 '21 at 9:29
2
+50
$\begingroup$

How can I approach projects with a big state space without loosing a huge chunk of predictability (which I might fear with DQN, DDPQ or TD3)?

You can impact this by choosing a combination of function approximator and engineered features which are a good match to predicting either the value functions or policy function that an agent will need to produce.

It is hard to tell a priori how much work you would need in this regard. Given that you play as many training games as you have time for, use a deep neural network with hardware acceleration, then one approach is to simply normalise/scale your feature vector as it is, and train heavily. This approach in RL has repeatedly shown new state-of-the-art results for e.g. AlphaZero, Open AI's DoTA agent and others. This appears to work provided the compute resource that you can throw at the problem is large enough. As you mention, card-counted blackjack is a solved problem, so doing this may be within your reach on consumer hardware.

Some smart feature engineering may help though, by making the core problem easier for the agent. As this is a hobby project, what you do will depend on what you want the agent to learn. Is the purpose of your project to teach the agent how to card-count from scratch? Given that you have told the agent the count of remaining cards in the state, it does not appear so.

Next question: Do you need the agent to learn to sum up all remaining cards in order to calculate the raw probability of revealing a card of each type amongst cards so far unseen? That's currently what your main state feature is doing. If you don't need the agent to learn that, you could help by using the probability of each card being seen as a feature instead of the remaining count. This feature is likely to reduce the complexity of value and policy functions, thus it will reduce compute time, and may also improve accuracy.

With a game that can be solved analytically, you could take this up to the point of deriving the optimal policy directly and not using RL at all (i.e the input to your NN would be the correct action or the action values!). The question for your project is then this: What precisely are you hoping to demonstrate that your agent can learn? Or maybe: What do you want to gain by applying RL to this problem?

$\endgroup$
5
  • $\begingroup$ Yes, you’re right, I could parse the probability of each card appearing as an input - though that wouldn’t condense my state space, would it? I’d still input an integer value for each card type into my action space, except this time it represents a probability (which could be calculated by simple dividing the amount of said card left and the total amount of cards left). I don’t see any advantage of deriving this value beforehand? For my specific problem, it’s important to consider the probability of each card appearing in the next turn. $\endgroup$ Sep 12 '21 at 9:34
  • $\begingroup$ My goal is to programmatically determine the best choice for each stage in the game. My first approach was to backcalculate any decision tree within the MDP, though this ended up to be ineffective due to sheer amount of calculation required (even with alpha beta pruning and other shorting techniques). After that I went ahead and tried to implement an agent playing the game, but as mentioned ended up with monstrous state spaces, therefore making it ineffective. $\endgroup$ Sep 12 '21 at 9:40
  • $\begingroup$ "I don’t see any advantage of deriving this value beforehand?" Although the calculation is trivial, it is specific, very likely to be useful when calulating expected return, and a learning algorithm could take some time to stumble across an approximation to it statistically from the data. $\endgroup$ Sep 12 '21 at 11:19
  • $\begingroup$ tho the size of a single digit in comparison to multiple might be valuable in a huge q-table - as you’re apparently proposing. $\endgroup$ Sep 12 '21 at 11:27
  • $\begingroup$ I am not proposing any Q table at all. You will need to use an approximator such as a neural network. Your question is about making that neural network more accurate. My first paragraph explains in general wht you might need to do tyo make it more accurate. The second para explains why you might not need that. Third para onwards suggest some specific things you may want to consider. $\endgroup$ Sep 12 '21 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.