How can you represent the state and action spaces for a card game in the case of a variable number of cards and actions?

Question

I know how a machine can learn to play Atari games (Breakout): Playing Atari with Reinforcement Learning. With the same technique, it is even possible to play FPS games (Doom): Playing FPS Games with Reinforcement Learning. Further studies even investigated multiagent scenarios (Pong): Multiagent Cooperation and Competition with Deep Reinforcement Learning.

And even another awesome article for the interested user in the context of deep reinforcement learning (easy and a must-read for beginners): Demystifying Deep Reinforcement Learning.

I was thrilled by these results and immediately wanted to try them in some simple "board/card game scenarios", i.e. writing AI for some simple games in order to learn more about "deep learning". Of course, thinking that I can apply the techniques above easily in my scenarios was stupid. All examples above are based on convolutional nets (image recognition) and some other assumptions, which might not be applicable in my scenarios.

I have two main questions.

1. If you have a card game and the AI shall play a card from its hand, you could think about the cards (amongst other stuff) as the current game state. You can easily define some sort of neural net and feed it with the card data. In a trivial case, the cards are just numbered. I do not know the net type, which would be suitable, but I guess deep reinforcement learning strategies could be applied easily then.

   However, I can only imagine this, if there is a constant number of hand cards. In the examples above, the number of pixels is also constant, for example. What if a player can have a different number of cards? What to do, if a player can have an infinite number of cards? Of course, this is just a theoretical question as no game has an infinite number of cards.

2. In the initial examples, the action space is constant. What can you do, if the action space is not? This more or less follows from my previous problem. If you have 3 cards, you can play cards 1, 2, or 3. If you have 5 cards, you can play cards 1, 2, 3, 4 or 5, etc. It is also common in card games, that it is not allowed to play a card. Could this be tackled with a negative reward?

So, which "tricks" can be used, e.g. always assume a constant number of cards with "filling values", which is only applicable in the non-infinite case (anyways unrealistic and even humans could not play well with that)? Are there articles, which examine such things already?

Answer 1

Instead of having the AI learn what action to take, you can alternatively train it to judge how "good" a position is. In order to determine what move to make, you don't ask the AI "This is the current state, what move should I make", you iterate through all possible moves, and feed the the resulting state into the AI asking "How good do you think this new state is?". You then chose the move with the resulting state that the AI liked best. (Or you probably even can combine this with a traditional MinMax approach) I'm new to this area myself, but I'd guess you would use this approach when the action space is large, and in particular when most possible actions are not a legal option in most states.

Answer 2

1. Filling values is totally fine. In the case of image recognition the filling will be the background of the image (examples). For example in Belot you have total of 32 cards, which can be 32 boolean features. You can set the ones the player has to 1, while the rest are 0. Note that the in most games you'll need more features than the cards in your hand. I.e number of the round, cards that have been played so far, calls that have been made etc.
2. Defining the scope of the "action space" will be specific to the game. For Belot, it can be number encoding for each of the 32 cards.

You can find articles via Google. Here is a paper about ML for a card game. Instead of articles, I'd recommend checking out a course on ML (i.e. Coursera and Udacity have good free online courses).

Answer 3

Considering your use case, I would not use Deep Learning methods... what is the point?

Instead of just winning, good AI is fun to play with. In practice when fine tuning game mechanics, you will want to analyze the game for churning events. Then it would be nice, if you could show the AI that "Hey, this is messed up, could you come up with a nice way of playing, when this situation happens?" and then the AI would be like "Okay, sure, I didn't know, that me winning all the time was not, what humans considered fun... I'll be more fun next time, while also trying to win".

Lately I have been toying around with Computational Creativity and specifically Partial Order Causal Link planners (POCL) and Agents.

POCLs attempt to create plans, which fulfill goals; this makes them computationally effective as they only need to fulfill a flaw in a goal (having best possible cards on the table) and iterate towards the initial condition (specific cards on table and some cards on hands etc.). I believe, that with Conflict driven POCL you could easily introduce bluffing. I have written POCL algorithm in declarative way, so you don't have to code the action space, but instead have them configured by using modal logic.

Then you would have agents, who would use Plan artifacts generated by the POCL algorithm in order to play in a fun way (evaluation function of the Agent), while also trying to win (search towards best odds for winning). The fun thing with Agents is, that you can compose them and discover personalities easily; I have no idea how Deep Learning methods would provide that easily.

So, by using POCL and Agents, you could first teach the Agents to win efficiently or optimize the Plans to provide good "basic moves" by using some heuristic system (like you will do when using Reinforcement Learning). I don't know about the computational complexity issues regarding specific games; however, such POCL algorithms have been implemented, which are context aware (= reduced action space), so if you add a bit more strategic gameplay abstraction, the POCL should be fine (remember to use some kind of damping factors for reducing the path length of plans, in similar way to PageRank).

In all programming a good mental model will make many things a lot easier. With Deep Learning, you will be using image recognition or similar algorithms / methods to solve a different problem, because nobody is preventing you from using wrong tool for the problem at hand. In real games, there are players (Agents), strategies (POCL plans), bluffing (POCL conflicts) and rules (action space of POCL defined by modal logic). Of course some games might have computational complexity issues; however, usually those are solvable by minor optimization to the algorithms, which provide a good mental model of the problem.