How would you program an AI to play Magic the Gathering?
Author
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?
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.
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
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
Author
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.
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.
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.
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.
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.
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.
Author
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?
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?
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.
Quote:Original post by gryfangI think that is a big problem right there. The possibilities are VERY large given the number of cards available.
... then tests them in an Alpha Beta with the cards it guesses are elsewhere.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
