Sign in to follow this  
Telamon

How would you program an AI to play Magic the Gathering?

Recommended Posts

This is just something I've been curious about for a long time. Microprose put out a program in 1996 that did a pretty good job of playing most any kind of deck you gave it, though it was mostly limited to 4th edition cards. I think it would be a cool project to write a program that could play M:TG, potentially using any card ever published, or even custom cards. I don't really know how you would do it though. I guess you would have to come up with a general computer-understandable language that could describe the function of any existing card in such a way that the program could evaluate the utility of playing any particular card at a given time. But beyond that, it just seems like a really thorny AI problem. Has anyone played with this at all?

Share this post


Link to post
Share on other sites
I have never played magic but I would imagine that if you had some sort of game tree that knew all the rules you may have some chance at making an AI. I would imagine that you would have a lot of rules that the AI would need to know. I wish you luck, this sounds tough.

Share this post


Link to post
Share on other sites
I personally feel that the people who made the actual card game could program on a computer. The game is insanely logical and limited to what all is in the decks/hands/etc.
There is even a spell stack (that works like a CS Stack), resource alocation, and process management (enchantments and creatures). The game is kinda like a random wierd unfunctional OS.
I'd assume it's be Alpha Beta mixed with a baysean network ... sorta like an alpha beta probability network. It would solidly choose what to do based off what it KNOWS is in it's deck (and guesses as to where) and what it guesses is in the opponent(s) deck based off what it sees.
Also most magic decks are paired with a general theme of how to win (decking, fighting, concession, win condition) and what cards to do it with.

Added more that's all

Share this post


Link to post
Share on other sites
I guess the meat of my question was really more "how would knowledge be represented in this game". Or do you think Microprose hardcoded functions to define how every single card worked?

And, as a followup, given some snazzy knowledge format, how do you use it to reason out what to do?

I don't think any kind of minimax tree search strategy is going to work very well at all for M:TG. If you consider all the cards the player could potentially have in his hand, from all the existing cards, you're looking at a branching factor of 11,000. And if the chance of any one card being played is 1/11,000 - I don't see how it's worth even considering. No, I think a less general approach would be required.

Note: I get the 11,000 figure from the fact there are 11,000 different cards. If we let the computer cheat and know ahead of time the cards in the opponent's deck, this goes down a bit - but that's not a very pleasing solution. I don't think this simplicification would even make the problem much easier to solve.

Share this post


Link to post
Share on other sites
Well, if you've got a whole lot of time and a fast computer you could use a neural network that uses as inputs all of the cards it has in it's deck, in play, and in it's hand along with the opponent's cards in play (and possibly the opponent's discard pile). Have it play itself a whole bunch of times, and step in with a manual game every now and then to make sure it's going the right direction. When it gets trained well enough, go in and snip off parts of the neural network with extremely small weights to make it faster.
You could use different goals to train different types of AI with this technique. Train one that tries to never be hurt. Train one that only cares about killing it's opponent at the expense of being hurt itself. Train one that's whole goal is to have as many cards as possible on the table.
There's still a lot more to be done to flesh out the idea, of course, but it could probably work with enough CPU time and some clever tweaking.

Share this post


Link to post
Share on other sites
I think that any sort of planning algorithm based on the huge unknown space in the game (the other player's cards as well as your own unplayed cards) would be pointless. The best bet to do as an approach is to take the known space (the cards in your hand/in play plus the visible cards of the opponent) and devise a broad strategy from there. Leave yourself in a position to do things but don't become vulnerable.

Share this post


Link to post
Share on other sites
I actually thing it takes into consideration the unknowns, because it plays to well not to think of it. I'm sure it least Guesses of the unknowns. As well as is every card hardcoded, I think you have to be able to play it so that part of it is handled so you can play the card and the Agent tests with itself if it's actions work by playing the card in sercret and seeing if it's actions were good or not.

Share this post


Link to post
Share on other sites
DoughBoy:

The problem with hammers is that when you have one, everything looks like a nail.

Neural networks are the same way. I really don't think they are applicable here.

Everyone else:

So what you guys are saying is that a program that played M:TG would look something kind of like an automated theorum prover?

Share this post


Link to post
Share on other sites
KINDA ... only for a theorm that couldn't be proven, I'm saying one way to do it is it composes a network of actions that it can do (Baysean network) with the cards it knows then tests them in an Alpha Beta with the cards it guesses are elsewhere.

Share this post


Link to post
Share on other sites
True ... but in a best of three games it may lose the first hands down, but then the possibility of cards is reduced to app 10 - 20 cards + land assuming the players follow normal deck building conventions. Also it should fully know what is in it's deck (just not where) so the probabilities are far less. Then for the first game all the cards are in a large probability tree (sorted by color, type, casting cost, other subdivisions) which is then pruned by guesses. Like I said though it'll probably lose the first game.
And if there is only one game for each and you don't change your deck the other agents can benefit off the previous agent's knowledges

Share this post


Link to post
Share on other sites
Another thing to consider is that they just may have cheated. It's hard enough to play the game when you don't know what the opponent has, and what your next cards are. If you knew your deck structure it would be easier to plan your actions.

One thing I do know is they had a hell of a time getting a good way of representing all the cards and rules into the game. I recall it was delayed a year or two because they were having so many problems with it.

If I were to take a first shot at it though, I'd probably go about representing each card as something within a group. So you'd have your lands, creatures, player affecting sorcery, creature affecting sorcery, card affecting interrupt, etc.

Then I'd probably have a whole bunch of rules for evaluating which cards are "good" to play. Sure, it's not amazing, but it could probably end up playing well if you knew what the opponent has (and was going to have in the future). So for each card that had some action attached to it, I'd see if that action was possible, and pick the best possible action, then keep doing that until I have no actions left (or decide it would be better to save some mana).

A little example might be if you have a creature available for attacking, a fireball and creature in your hand and 5 untapped mana. So you look at the creature and say, this guy can attack, but if he attacks I look at what I will have left defending me, and what the opponent will be able to attack me with. If he can knock off more than 5 life or so, I leave my creature untapped. Otherwise it's off to the races. And similarly, I look at my cards in my hand.

Now that I think about it a bit more, you might have to do a search of the possibilities for your own play (not even considering the opponent). But knowing your upcoming cards would help out here.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this