How can I design and train a neural network to play a card game (similar to Magic: The Gathering)?

Question

Introduction

I am currently writing an engine to play a card game, as there is no engine yet for this particular game.

About the game

The game is similar to Magic: The Gathering. There is a commander, which has health and abilities. Players have an energy pool, which they use to put minions and spells on the board. Minions have health, attack values, costs, etc. Cards also have abilities, these are not easily enumerated. Cards are played from the hand, new cards are drawn from a deck. These are all aspects it would be helpful for the neural network to consider.

Idea

I am hoping to be able to introduce a neural network to the game afterwards, and have it learn to play the game. So, I'm writing the engine in such a way that is helpful for an AI player. There are choice points, and at those points, a list of valid options is presented. Random selection would be able to play the game (albeit not well).

I have learned a lot about neural networks (mostly NEAT and HyperNEAT) and even built my own implementation. Neural networks are usually applied to image recognition tasks or to control a simple agent.

Problem/question

I'm not sure if or how I would apply neural networks to make selections with cards, which have a complex synergy. How could I design and train a neural network for this game, such that it can take into account all the variables? Is there a common approach?

I know that Keldon wrote a good AI for RftG, which has a decent amount of complexity, but I am not sure how he managed to build such an AI.

Any advice? Is it feasible? Are there any good examples of this? How were the inputs mapped?

Answer 1

I think you raise a good question, especially WRT to how the NNs inputs & outputs are mapped onto the mechanics of a card game like MtG where the available actions vary greatly with context.

I don't have a really satisfying answer to offer, but I have played Keldon's Race for the Galaxy NN-based AI - agree that it's excellent- and have looked into how it tackled this problem.

The latest code for Keldon's AI is now searchable and browseable on github.

The ai code is in one file. It uses 2 distinct NNs, one for "evaluating hand and active cards" and the other for "predicting role choices".

What you'll notice is that it uses a fair amount on non-NN code to model the game mechanics. Very much a hybrid solution.

The mapping of game state into the evaluation NN is done here. Various relevant features are one-hot-encoded, eg the number of goods that can be sold that turn.

---

Another excellent case study in mapping a complex game into a NN is the Starcraft II Learning Environment created by Deepmind in collaboration with Blizzard Entertainment. This paper gives an overview of how a game of Starcraft is mapped onto a set of features that a NN can interpret, and how actions can be issued by a NN agent to the game simulation.

Answer 2

Yes. It is feasible.

Overview of the Question

The design goal of the system seems to be gain a winning strategic advantage by employing one or more artificial networks in conjunction with a card game playing engine.

The question shows a general awareness of the basics of game-play as outlined in Morgenstern and von Neuman's Game Theory.

• At specific points during game-play a player may be required to execute a move.
• There is a fininte set of move options according to the rules of the game.
• Some strategies for selecting a move produce higher winning records over multiple game plays than other strategies.
• An artificial network can be employed to produce game-play strategies that are victorious more frequently that random move selection.

Other features of game-play may or may not be as obvious.

• At each move point there is a game state, which is needed by any component involved in improving game-play success.
• In addition to not knowing when the opponent will bluff, in card games, the secret order of shuffled cards can introduce the equivalent of a virtual player the moves of which approximate randomness.
• In three or more player games, the signaling of partners or potential partners can add an element of complexity to determining the winning game strategy at any point. Based on the edits, it does not appear like this game has such complexities.
• Psychological factors such as intimidation can also play a role in winning game-play. Whether or not the engine presents a face to the opponent is unknown, so this answer will skip over that.

Common Approach Hints

There is a common approach to mapping both inputs and outputs, but there is too much to explain in a Stack Exchange answer. These are just a few basic principles.

• All of the modeling that can be done explicitly should be done. For instance, although an artificial net can theoretically learn how to count cards (keeping track of the possible locations of each of the cards), a simple counting algorithm can do that, so use the known algorithm and feed those results into the artificial network as input.
• Use as input any information that is correlated with optimal output, but don't use as inputs any information that can not possibly correlate with optimal output.
• Encode data to reduce redundancy in the input vector, both during training and during automated game-play. Abstraction and generalization are the two common ways of achieving this. Feature extraction can be used as tools to either abstract or generalize. This can be done at both inputs and outputs. An example is that if, in this game, J > 10 in the same way that A > K, K > Q, Q > J and 10 > 9, then encode the cards as an integer from 2 through 14 or 0 through 12 by subtracting one. Encode the suits as 0 through 3 instead of four text strings.

The image recognition work is only remotely related, too different from card game-play to use directly, unless you need to recognize the cards from a visual image, in which case LSTM may be needed to see what the other players have chosen for moves. Learning winning strategies would more than likely benefit from MLP or RNN designs, or one of their derivative artificial network designs.

What an Artificial Network Would Do and Training Examples

The primary role of artificial networks of these types is to learn a function from example data. If you have the move sequences of real games, that is a great asset to have for your project. A very large number of them will be very helpful for training.

How you arrange the examples and whether and how you label them is worth consideration, however without the card game rules it is difficult to give any reliable direction. Whether there are partners, whether it is score based, whether the number of moves to a victory, and a dozen other factors provide the parameters of the scenario needed to make those decisions.

Study Up

The main advise I can give is to read, not so much general articles on the web, but read some books and some of the papers you can understand on the above topics. Then find some code you can download and try after you understand the terminology well enough to know what to download.

This means book searches and academic searches are much more likely to steer you in the right direction than general web searches. There are thousands of posers in the general web space, explaining AI principles with a large number of errors. Book and academic article publishers are more demanding of due diligence in their authors.

Answer 3

This is completely feasible, but the way the inputs are mapped would greatly depend on the type of card game, and how it's played.

I'll take into account a few possibilities:

1. Does time matter in this game? Would a past move influence a future one? In this case, you'd be better off using Recurrent Neural Networks (LSTMs, GRUs, etc.).

2. Would you like the Neural Network to learn off of data you collect, or learn on its own? If on its own, how? If you collect data of yourself playing the game tens or hundreds of times, feed it into the Neural Net, and make it learn from you, then you're doing something called "Behavioural Cloning". However, if you'd like the NN to learn on its own, you can do this 2 ways:

   a) Reinforcement Learning - RL allows the Neural Net to learn by playing against itself lots of times.

   b) NEAT/Genetic Algorithm - NEAT allows the Neural Net to learn by using a genetic algorithm.

However, again, in order to get more specific as to how the Neural Net's inputs and outputs should be encoded, I'd have to know more about the card game itself.

Answer 4

You would definitely want your network to know crucial information about the game, like what cards AI agent has(their values and types), mana pool, how many cards on the table and their values, number of the turn and so on. These things you must figure on your own, the question you should ask yourself is "If I add this value to input how and why it will improve my system". But the first thing to understand is that most of NNs are designed to have a constant input size, and I would assume this is matters in this game since players can have a different amount of cards in their hand or on the table. For example, you want to let NN know what cards it has, let's assume the player can have a maximum of 5 cards in his hand and each card can have 3 values(mana, attack and health), so you can encode this as 5*3 vector, where first 3 values represent card number one and so on. But what if the player has currently 3 cards, a simple approach would be to assign zeros to last 6 inputs, but this may cause problems since some cards can have 0 mana cost or 0 attack. So you need to figure out how to solve this problem. You may look for NN models that can handle variable input size or figure out how to encode input as a vector of constant size.

Secondly, outputs are also constant size vectors. In case of this type of game, it can be a vector that encodes actions that the agent can take. So let's say we have 3 actions: put a card, skip turn and concede. So it can be one hot encoder, e.g. if you have 1 0 0 output, this means that agent should put some card. To know what card it should put you can add another element to output which will produce a number in the range of 1 to 5 (5 is max number of cards in the hand).

But the most important part of training a neural network is that you will have to come up with a loss function that is suitable for your task. Maybe standard loss functions like Mean-squared loss or L2 will be good, maybe you will need to change them in order to fit your needs. This is the part where you will need to make a research. I've never worked with NEAT before, but as I understood correctly it uses some genetic algorithm to create and train NN, and GA use some fitness function to select an individual. So basically you will need to know what metric you will be using to evaluate how good you model performs and based on this metric you will change parameters of the model.

PS. It is possible to solve this problem with the neural network, however, neural networks are not magic and not the universal solution to all problems. If your goal is to solve this certain problem I would also recommend you to dig into the game theory and its application in the AI. I would say, that solving this problem would require complex knowledge from different fields of AI.

However, If your goal is to learn about neural networks I would recommend taking much simpler tasks. For example, you can implement NN that will work on benchmark dataset, for example, NN that will classify digits from MNIST dataset. The reason for this is that a lot of articles was written about how to do classification on this dataset and you will learn a lot and you will learn faster from implementing simple things.

Answer 5

I'm not sure if or how I would apply neural networks to make selections with cards, which have a complex synergy. How could I design and train a neural network for this game, such that it can take into account all the variables? Is there a common approach?

Advice 0.

I would highly recommend to design it the way most neural networks are designed. The most common pattern is to have n layers, each one might have different size, one input layer, one output layer, a few hidden layers between them.

Advice 1.

Differentiate between neural network itself (brain), its environment (game conditions and rules), its sensors (inputs) and its "hands" (outputs). Why you might want to call it "hands"?  If you simulate a player in a card game, you basically want him to use his hands to play. In other situations it might be legs, or wings, or even the gas pedal.

How to design the inputs:

Just create a neural network with a common pattern, figure out, what variables a real player would analyze before throwing a card, then try to translate those variables into signals. This step might actually be a bit tricky and it's also what actually happens in biological neural networks. The electrical signals in our brains are really weak, even though they might carry bits that make up big numbers. What I mean by making weak signals out of numbers is dividing varying diapasons of numbers by their maximal values. For example, instead of putting in 5, which would represent a card with rank 6, divide 5 by 13 (or whatever value represents the highest rank). Basically if your diapason of input for one neuron is 0 to 13, divide it by 13 to get a value (or signal) in codomain [0; 1], which is a suitable input for the sigmoid function compared to the values in codomain [0; 13]. To visualize, take a look at the graph of the sigmoid function.

The difference between f(10) and f(8) is ~0.00029, whereas the difference between f(10/13) and f(8/13) is ~0.034, which obviously has much more impact on the output. So, make sure you translate all the values into the diapason where your function is most "sensitive", in this case in [-4; 4]

Advice 2.

Every time you need a decision from the AI, create a pool of possible decisions (e. g. pool of possible cards the player can throw right now) that you can index by an integer. Then you might want to multiply the output value in its codomain [0; 1] by the amount of possible decisions - 1 to be able to interpret it as index. Or you might have the amount of output neurons that corresponds to the maximal amount of possible moves and interpret the index of the neuron with the highest value as the index of the array with possible decisions.

How to train it:

If you create AI for a game, I would recommend to take a look at genetic algorithms. The basic idea is to create a population of players (hundreds or thousands) with randomly generated weights and biases in their NNs, restrict their possibilities by the rules of the game, and let them play. Then perform selection by their fitness function, which in this case might just be the score of each player, crossover and mutation of their genes (of single bits or even numbers) to create the next generation, and so on. Repeat this process until you come up with a satisfying solution. I recommend you genetic algorithms for this case, because it might be quite hard to find training data for traditional methods of training NNs. And if you're able to generate training data yourself, then you might also be able to program all the behaviour manually, in which case you don't even need NNs. If you're interested in training NNs using genetic algorithms, you should read some external literature, since it's a pretty big topic. You can also check out my github repo, where I train AI to play snake using GAs.