9
$\begingroup$

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

I am hoping to be able to introduce a neural net to the game afterwards, and have it learn to play the game.

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. I am still unsure how best build an AI that can take into account all the variables in one of these types of games. Is there a common approach? I know that Keldon wrote a good AI for RftG which has a decent amount of complexity, 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?

EDIT: I have looked online and learned how neural networks work and usually how they pertain to image recognition or steering a simple agent. I'm not sure if or how I would apply it to making selections with cards which have a complex synergy. Any direction towards what I should be looking into would be greatly appreciated.

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.

$\endgroup$
  • $\begingroup$ Hey, welcome to AI.SE! As this currently stands, it looks a little too broad for us to be able to answer it well. Do you think you could edit it to narrow it down a bit? Thanks! $\endgroup$ – user58 Sep 18 '17 at 13:57
  • $\begingroup$ While the question is broad, it is an obvious and common question for somebody new to the field. Also one where answers are hard to find using Google (as most tutorials about NN seem to focus on image recognition and language examples). I think it deserves an answer pointing to good resources about approaches and techniques for using NN to play games, in this case in particular card games. $\endgroup$ – user12889 Sep 18 '17 at 23:56
  • $\begingroup$ Thanks for the feedback. I've edited my question a bit. Any direction towards learning material would be helpful. I find mostly image recognition as you mentioned. I am eager to learn and am happy to have a large set of recommended reads, rather than just a simple answer. $\endgroup$ – pcaston2 Sep 19 '17 at 3:05
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hello, thanks for the answer! I will investigate these areas to see what applies. I have added a short description of the game in the hopes this narrows it down for you. My engine supports undos so that may be useful in conjunction with NN. As the engine is unfinished, I do not have a sample set but plan on keeping all game histories from the hosting server between 2 players. I was considering using back propagation to accelerate the process. $\endgroup$ – pcaston2 Sep 20 '17 at 11:18
  • $\begingroup$ If the game state matters, but not how you got to that state, would you then say that time matters? Can you give any examples of games where time matters and some where time does not matter? At the moment I can only think of situations where the current state matters (who's turn it is, what known cards or game pieces are where) but not how you got there (the only thing that matters is where they are now, not where they were two turns ago) $\endgroup$ – Simon Forsberg Nov 7 '17 at 18:42
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.