Magic The Gathering, maths and AI

When I was a kid I used to play Magic the Gathering in the comic store against the shopkeeper, with my pre-made green/red deck. Currently I re-started playing MTG firstly because I got interested in tokens creation and alters , but also returned playing with a control white-black deck. But now, as an engineering student, I became curious about how an AI would play Magic (theoretically) and what kind of maths are involved in this game.

For the ones who don't know about MTG, it's a card game created by a computer mathematician in the nineties, that turned out to be very popular years after. Currently, this game host tons of tournaments worldwide, and there's a serious amount of money involved.

Artificial Intelligence development has evolved through the last years greatly, creating amazing agents, such as the one which plays Go or the one which is created to negotiate, as Turing speculated in his study Computer Machinery and Intelligence, AI is expecting great evolves in the future.

Magic the Gathering itself involves lots of rules. Not only it has a huge amount of rules of how proceeding in the game, but also each card has its own rules to be considered. But even if the AI is able to store all of that information in a huge database, there are more issues to face.

First of all the information of each game is incomplete. This means, even knowing your own deck (or even having knowledge of the opponent deck) there's a random component, as the first turn starts grabbing seven random cards from the top of the deck and next turns taking one. If the opponent's deck is unknown (a plausible scenario) it's even worse.

Actually, I'm lying a bit here. An Ai can handle "easily" the random component of a known range of strategies with a limited numbers of cards. An example I found nice is Hanafuda Koi Koi, a game in which players are meant to organize cards to create compositions. I found this repository, for example. Anyway this kind of game could be solved using a MAX-MIN programming strategy updating the information in the table each time.

For example, this is a MIN-MAX way of approaching a game (tip-tap-toe) :

So what's the matter with Magic?

Strategy is not that clear. Seeking the greater points (as in Hanafuda) can lead in a mathematical analysis of the table, but strategy is more complex in this case. Surely there are some patterns players usually take, and can be analysed studying lots of games (like the ones in the tournaments) but it's pretty common players creating their own strategy and decks, which at the same time creates a growing almost unlimited number of strategies.Not only this is problematic, but also the player can try to improvise a strategy in the middle of the game.

Also the way a player can approach an opponent is not determinant, unless the action is clearly developing a one turn strategy, but player is more likely to develop a 2+ turns strategy that can vary depending on the opponent's new hand each turn. In a limited game of perfect information (such as chess) this 2+ turn analysis is possible because all the information is already in the table (all the tokens and possible movements) but that's not the case in MTG, as we already explained.

Again here's a MIN-MAX example of a chess movement.

We already said we can found a countless number of strategies in a single game of MTG, and I'd like to explain some of the patterns I saw in the game. First of all let me explain a simple detail. Game strategy is open to the players, but there are certain roles assigned to each color. This mean, cards of the same color tend to follow a specific strategy, which can be manipulated and bend in convenience, but usually determines the style of a deck. White, black and blue are usually meant for control (specially blue); red and green are more used as direct attacking. Again this is a general idea, as it could be changed in specific strategies.

Once this is said, let me ask you something. Have you ever guys heard about the "Chicken Game" ? This is a very representative game (alongside the Prisoner's dilemma) which explain an specific situation of two players.

The game is easy: Two drivers are faced one against another in their cars. Both of them speed up, and the points of the game are distributed like this:

• If they crush because none of them move both get 0 points (duh)
• If both of them go away from the crush in the last moment, they both get 3 points.
• If one of them goes away form the crush and the other one stays in the same trajectory, the first one gets 1 point and the second one 5 points.

This can be seen for example in Rebel Without a cause!

This is a very hardcore game indeed, but it can be applied in daily matters such as politics or negotiations. This example only describes the dominant desire of players in the game, and surely this can also be seen in MTG. I can see this kind of pattern when two similar decks (or certain turns) are being played, and this could involve, for example, similar colors. This situation, tho, implies similar strategies, which are not necessary implied by the same color.

And speaking of Chickens there's also another mathematical study of behavior, commonly called "Hawks and Doves". In this example, Hawks have advantage in direct attack, but having many of them cause conflict between hawks, decreasing its number and having again balance with doves.

I saw this in a certain strategy of a control that causes life loss by it's user each turn but creates an advantage such as tokens (creatures that can be generated, mostly with low attack) with no support of a card that heals the damage. If the opponent lets the first player have the life loss card on the table, this player will surely be damaged each turn but also have table control with tons of creatures. Hawks resemble to the time the player has the card on the table, and doves are the opponent. If the opponent destroys the card when possible, he/she is removing the constant life loss of his/her enemy, but also taking away the constant table control.

Proceeding in this kind of problems not only requires a logical calculus that an AI could certainly approach, but also some kind of cooperation with the enemy in order to find a way to be a dominant player without slipping on going extremely aggressive.This is a subtle subjective action that can be described for some humans as "intuition" or in its absence "experience". Experience can be gained by an AI the same as humans, studying, winning and losing tons of times, but learning this pattern in a general term is very difficult for such an artificial agent. If I was asked to create a shortcut for a MTG agent in this matter, I would take a list of every card that tends to generate this strategy (like the one above) and create an specific way of acting, but again this can lead in a stupid action depending on the context.

To sum up, strategies with imperfect unlimited games with random components are very difficult to manage by an AI agent, and the game can have several strategies already studied for the real life issues. If Skynet takes our world, dare it with a Magic play!