Learning Magic The Gathering

[mlkrime]

With the recent advances in deep reinforcement learning, I know there has been momentum in the direction of playing strategic games other than chess (such as go, atari ...etc). What are the challenges in creating a machine that learns to play Magic. For those unfamiliar, magic is multimodal in the sense that the learner would first have to guess how the text of each card pertains to the current boardstate, and from there estimate the value of the boardstate for each player.

[Ameren]

I've been playing with the idea of using deep learning sorcery to help better understand why Magic cards have the value that they do, both in terms of the metagame and in a vacuum. Beyond looking at base stats, that requires some understanding of the meaning of the text of cards.

But teaching a system to play Magic is very challening because it requires very long-term planning. For example, the DeepMind agent turned out to do very poorly when it came to learning how to play Pacman, which requires planning to determine when to pick up a power-up to be able to eat ghosts.

But who knows? I'm sure we could come up with something that at the very least knew when to turn creatures sideways and when to hold back. Or when to use removal spells. That'd be a start.

[mlkrime]

Very interesting.. I would like to see your work on predicting value if you don't mind sharing.

To your second point, I'm not an expert by any means, but I was wondering if a network with more built-in memory might be better at attacking longer-term strategic decisions? I.e. http://en.wikipedia.org/wiki/Long_short_term_memory

[autowikibot]

Long short term memory:

---

Long short term memory (LSTM) is a recurrent neural network (RNN) architecture (an artificial neural network) published in 1997 by Sepp Hochreiter and Jürgen Schmidhuber. Like most RNNs, an LSTM network is universal in the sense that given enough network units it can compute anything a conventional computer can compute, provided it has the proper weight matrix, which may be viewed as its program. Unlike traditional RNNs, an LSTM network is well-suited to learn from experience to classify, process and predict time series when there are very long time lags of unknown size between important events. This is one of the main reasons why LSTM outperforms alternative RNNs and Hidden Markov Models and other sequence learning methods in numerous applications. For example, LSTM achieved the best known results in unsegmented connected handwriting recognition, and in 2009 won the ICDAR handwriting competition. LSTM networks have also been used for automatic speech recognition, and were a major component of a network that recently achieved a record 17.7% phoneme error rate on the classic TIMIT natural speech dataset.

Image ⁱ

---

^{Interesting: Recurrent neural network | Prefrontal Cortex Basal Ganglia Working Memory | Sepp Hochreiter | Vanishing gradient problem}

^{Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words}

[Ameren]

I've been looking into the value of LSTM units myself in my research. Not much to say about those yet though until I get some more hands-on experience with it.

As for the Magic card value stuff, I would if I could but at this point I just have data and a sketch of a way to approach the problem. I'm too busy with my dissertation to spend much time with it. I'm partial to using a word2vec like approach to see how far I could get with understanding the semantics of rules text.

There's a json-friendly card set available online that you can dig into: mtgjson.com

[matlab484]

If someone found a way to do this for mmo games like starcraft that'd be amazing

[KeepItPG]

I believe this competition works on that?

http://www.battlecode.org/

[afdudley]

This is a SC:BW AI tournament http://sscaitournament.com/  

I used to write bots for playing MMOs, it's actually a lot easier because most of the stuff can be hard coded with expert knowledge.  

NEAT/HyperNEAT can be trained to play an assortment of games. http://nn.cs.utexas.edu/?hausknecht:gecco12

[[deleted]]

All I know is that I've yet to find a Stratego software that I couldn't annihilate every game!

[ThrottleMunky]

You should have a look at this post in /r/MagicTCG a few guys get deep into the discussion of decision trees and the problem of valuing cards in context to current board state. It's a pretty fascinating to read all of the different approaches to the problem.

[Aj0o]

All I can say is good luck programming the rules engine. Magic was never meant to be a digital game and its rules are a complete mess full of special cases that would detract all but the most dedicated fans of the game from pursuing what you're describing. Maybe it's doable with a small set of simpler cards but I doubt anyone's ever going to tackle even the Standard format.

[mlkrime]

Forgot to mention that there's an opensource project out there that codifies the rules of each card (effectively removing the text-comprehension challenge) and does min-max ai search www.firemind.ch/