2
$\begingroup$

I'm currently in the process of developing an AI for a popular card game here in Germany (called "Schafkopf"). Obviously, one could try to find a perfect strategy with the help of some game theory, but I tried the path with ML. Now after implementing the game and going down the line with a deep q-learning (reinforcement learning) approach, I faced the following issue:

I ran the agent for about five hours and my q-table grow to a size of ~49k rows. Therefore concluding that a q-table is ineffective for a game with a tremendous amount of states (i.e. cards dealt to you, cards left in the stack for each given round ("card counting"), what cards are considered to be trump cards and so forth).

Now my question arises: Is there a more efficient way / approach to such card games? Genetic algorithms? Supervised learning?

Improve this question
$\endgroup$
1
  • $\begingroup$ Does anyone have experience with enormous q-table states (i.e. card games) and is able to help? $\endgroup$
    – J. M. Arnold
    Jun 26, 2021 at 12:09

1 Answer 1

Reset to default
2
$\begingroup$

How is it possible to use DeepQ along with a tabular Q representation? The whole purpose of Q-learning with action-value function approximation (= DeepQ) is to overcome the limitations of a tabular approach.

In any case, you need to consider that, in a sense, game theory + RL $\approx$ multi-agent RL (MARL). The game that you are trying to tackle is (most likely) a zero-sum game as it is a competitive game among 2 or more players. If you try to use one agent vs another opponent agent (how did you model the opponents?) you treat the opponent as part of the environment and that will lead to a non-stationary policy. This problem is quite critical as most of the times, except if opponent is easily exploitable and has very limited strategies, it will lead to conditions that won't allow your training agent to converge. Then you have to deal with the problem of partial observability as players cannot see each other's hands. In other words, treating a MARL problem as RL is not a good idea.

Here is Hanabi a cooperative multi-agent card game. There are lots of MARL "solutions" (there is no actual solution just better performance) for this game out there. This might give you a starting point.

Before starting, consider that MARL contains quite advanced material and if you are not skilled with RL (and understand the math behind) it won't actually help you. Whatever algorithm you find it won't be an easy plug-n-play solution.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks for your reply! I'll go into detail regarding each of your questions. 1.) I expressed myself unclearly. At first, I tried vanilla q-learning, but after encountering said problem with the table size I dug into deep q-learning. Though still, my guess is that such a sheer amount of flexible variables make reinforcement learning impracticable. As mentioned, it's just a guess - there were no improvements after around 50k q-table rows (am I supposed to train it longer)? 2.) You are correct. For now, I used some hard-coded rules for the other player's behavior. I thought of training [1/2] $\endgroup$
    – J. M. Arnold
    Jun 27, 2021 at 21:17
  • $\begingroup$ the other two players with the help of supervised learning and a dataset of games I scraped. I'm quite aware of the implications of using rule-fixed enemy, though for now my main problem is the size of my q-table. 3.) Generally speaking, what approach is best for such state-heavy card games? My first research lead me to look up imperfect information games like Poker (papers about AIs like Pluribus and co.) - though it differs too much from my situation. Thus it really boils down to the fundamental question on how to tackle games with lots of data / states.. $\endgroup$
    – J. M. Arnold
    Jun 27, 2021 at 21:22
  • $\begingroup$ The answer is simple: MARL with function approximation (so forget q-table). When state space explodes we use a regressor to estimate the action/state-value function. So this fixes your problem of large state space. Now, as I said, your DeepQ is treating other agents as part of the environment and that is not good as you end up with a non-stationary policy (it will never converge!). You need to treat the problem as a MARL and not RL.[1/2] $\endgroup$
    – Constantinos
    Jun 28, 2021 at 3:36
  • $\begingroup$ If you take a look at the code I referenced above you will see a DeepRL algorithm solving MARL problems such as the card game Hanabi. Scripted opponent is fine but another technique we often use is to have the same network for every opponent (self-play). Then the agent's network that scores the more points is the winner and we use its parameters for the next round for al agents. There are many schemes for training in competitive games. Furthermore, as I said if each player cannot see the other player's hand the underlying MDP is actually a POMDP and that has many algorithmic implications[2/2]. $\endgroup$
    – Constantinos
    Jun 28, 2021 at 3:43
  • $\begingroup$ At the end if you really need to SOLVE a task and not necessarily LEARN to solve it from scratch, you should go with the best method available. If this game can be solved with game theory or other approaches that are NOT based on learning literally everything then go for them. $\endgroup$
    – Constantinos
    Jun 28, 2021 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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