• Advertisement
Sign in to follow this  

M:tG AI

This topic is 3938 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Are there any existing AIs for the Magic : the Gathering collectable card game? I'm looking for anything: official or unofficial, proprietary or open source, programs or libraries, or even unimplemented theoretical articles and documentS.

Share this post


Link to post
Share on other sites
Advertisement
It does not make my brain hurt as much, and I have a couple of ideas about how going around to do this. The problem is that it obviously involves programming the entire M:tG ruleset myself, which I'd rather not if it can be avoided.

My approach would be to define a game state (as the set of information individuall and globally available to players), then associate each state to a probability of winning. The player is faced every step of the game with a finite and usually small number of actions to perform (cast one of N spells, activate one of M abilities, select attackers among L creatures, and so on) which results in several possible game states. The best tactic is to choose the action which results in the highest winning probability.

The only difficulty would then be to associate a game state with the probability, which can be done with an heuristic (based on the number of cards and the nature of abilities available and the life count) for the leaf cases, and an evaluation of the enemy's possible retaliation for the node cases based on available knowledge and recursive combination of resulting situations. I would probably add several other approximations, such as game states being nearly equal (almost same amount of life, almost same number of cards in library) to speed up this.

Share this post


Link to post
Share on other sites
There is some information in my previous thread about the related subject of AI for (Collectible) Card Games?
I still haven't found any information I could directly apply to the problem, but maybe that is just because I don't have enough grounding in AI to be able to implement the abstract explanations of algorithms.

Share this post


Link to post
Share on other sites
Another thing to consider is the probability of drawing a particular card. You can assume the AI knows what cards are in its library (unless you're playing with sealed decks, in which case you can ignore probability altogether). This should affect the agent's choices, for example, if it needs to save a particular card for a combination play with another card that is likely to be drawn soon.

As for the actual implementation, you have to approach it much as you would a game of chess. If you want only a rudimentary AI to play against, you can simply teach it the rules of the game (i.e., how the cards work), and it will do what it can with what it has, and probably lose most of the time. If you want the AI to provide a challenging opponent, it has to think ahead in terms of what it has available versus what the player has in play (or might have in his hand), cost to activate abilities that may need to be used defensively (Circle of Protection), activation cost of poly-artifacts (Wooden Sphere, Ivory Cup, etc.), instants that may need to be used (Giant Growth, Righteousness).

I suppose you could think of cards in terms of pieces on the chess board and go from there. You're looking at a similar application anyway. I've recently taken it upon myself to develop an engine for playing M:tG online, but I foresaw the futility in trying to develop my own AI for it, so I dispensed with this right from the go. However, it is an option for future endeavors. I hope you have better luck with it than Microprose did.

Share this post


Link to post
Share on other sites
There is a combination effect going on here. One, it's like poker, bridge or any other imperfect knowledge card game: "I don't know what he has, but I think he might have this based on what I have, what I've seen and the way he's playing at the moment." This extends to what is in YOUR deck (as mentioned).

The second factor is the strategy. With poker, for example, getting a card is the final step. You only need to evaluate your strength relative to what you believe the other guy has. With MtG, given the cards you have in front of you, you now have to run through possibilities in the manner of a turn-based game - for example, with a planning algorithm. Sure, it's not as simple as tic-tac-toe or even a chess search, but some of the same principles apply. The issue is complicated by the fact that you don't know what HE has available... which brings us back around to the imperfect knowledge problem.

Share this post


Link to post
Share on other sites
InnocuousFox: Paper MtG might be different, but in online play, there are a very limited set of decks people play with, and that makes guessing what the opponent has in their deck almost trivial after the first 3-4 turns. At least, this is true in "Standard" - in "Extended", there are far more cards available and I haven't played enough to see all the patterns, but there are still only a few decks in a conceptual sense (lots of one-turn-win artifact combos, for example) that a good deck building AI could easily figure out.

In fact, I really think the game all comes down to a deck building AI - if you can figure out what the opponent has available in the long term (in their whole deck) based on what they play after only a few turns in, and you have a deck that can possibly deal with it, you have a very good chance of winning by applying that knowledge. Unfortunately, deck building seems to be the part everybody has the most difficulty developing an AI for - I haven't heard any ideas for it at all (that made any sense to me).

Share this post


Link to post
Share on other sites
Tom: AFAIK, you always know the contents of your deck, even in sealed.

Extrarius: I've been thinking of using this AI to "plan" a deck by selecting the probability of each card being in the deck, and then clipping said probabilities to a 60-card deck.

To be honest, I'm not an AI specialist either. However, my main area of study outside of CS is game theory, and we have several very interesting theories out there about this. The one I'm thinking of using here is the valuation theory I mentioned above (using the victory probability in each game state).

So, the main question resides in evaluating this probability heuristically. The basic idea is that you can evaluate it recursively by stating that some random events can happen (such as drawing cards), the opponent can answer with a known ability (card on the table) or unknown probabilistic one (morph creature, hand contents), new events (state-based or triggered) are run or placed on the stack, and the priority's back to you, so the value of the resulting state can be evaluated. Then, the value of a given state is the average of the values of the reachable states weighted by the probabilities of reaching these states (while letting the opponent maximise his own value).

In a perfect world with infinite computation power (and assuming that the AI knows the other player's decklist), this yields a perfect player, which always utterly maximizes its probability to win. Obviously, the world is not perfect, so I have to cut corners...

So, the first heuristic here would be to let the AI think in terms of threats, just like human players do (so, evaluation would ignore anything which is not either an opponent's threat to which we could possibly respond, or an opponent's response to a threat).

Then, instead of performing a complete recursion, it might be possible to stop at a finite depth, and evaluate heuristically all leaves at this depths (as discussed before).

All this would be done while eliminating courses of action for the opponent that are too improbable ex ante and adding them to the possibility of "no response from opponents". So, we'd probably miss a killer combo on the first way through, but not ex post (repeatable opponent actions are always considered if they were performed, even if low-probability).

Share this post


Link to post
Share on other sites
I think one of the toughest parts will be coping with the "metagame" of deciding what cards go into a deck. If both players pick from a selection of premade decks then this isn't as much of an issue.

Share this post


Link to post
Share on other sites
ToohrVyk: If you just want a basic probability-based deck-design AI, something like a bayesian inference system could easily make a system that can guess the cards likely to be in the deck given enough training on N-card combos likely to show up in decks (ie, use it to predict whether an Nth card is in the deck given that two cards have been seen, and repeat the process with each group of N cards seen so far each time a new card is played).

My problem is that I want to made a "card-based" deck designer that will figure out good card combos on it's own and be able to build a deck without any direct input besides some kind of abstract representation of each card available. I'd love to hear any ideas on algorithms suitable to this kind of thing.

Share this post


Link to post
Share on other sites
just let it know what is in the opponents deck. Not the best solution but probably the most workable.

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
Quote:
Original post by Glak
just let it know what is in the opponents deck. Not the best solution but probably the most workable.
Also known as "cheating" and generally frowned upon by AI developers.


Perhaps someone knowledgeable in DCI rulings could tell us when decklists are public and when they aren't (I know they aren't in Limited formats, but what about Constructed?)

Share this post


Link to post
Share on other sites
The "solution" I found to this problem was to let each card have a scripted AI and let it be an adviser to the "master" AI.

This adviser AI would examine the current state of affairs, have the ability to know what is in our deck yet to be played, what went to the graveyard, what cards of the opponent we have seen already, etc, and, from its point of view as a card with certain abilities and objectives it would advise the master AI on a line of play.

Bare in mind that the card can be active, on the table, or inactive, in the player's hand, so its advices could range from "«put me in play now for defense reasons», you have mana" to "«don't attack with me», the opponent has a high attacker only I can defend".

So the cards talk to the master AI in sentences like:
- attack with me (because the opponent cannot stop me, I fly)
- don't attack with me (because only I can block that huge guy without getting murdered)
- use my special ability on target card (I've got a bow and arrow and i can inflict 1dmg anytime, use it on that guy with 1hp)
- etc

There is a certain complexity here, because each card is an adviser, yet, to correctly give any sort of advice about itself and its range of uses, it has to examine the whole play field, so you're struggling to keep something that should be focused from becoming global. Case in point, a certain card might miss the effects of an artifact and advise the master AI to attack with it, but the artifact would turn all damage against the attacker, so we would suffer badly. So it is our role as technical designers to make sure the master AI gets good advices, but it has to be the master AI to see the whole of the playing field and have the last word.

Also, it's a weirdish technical design decision, but it makes sense if you ran the opponent's cards' AI (that you know of, of course), and reversed their suggestions. The AI for that Artifact would advise us to attack (let's not forget it serves the other player), so we would reverse that suggestion, and make a mental note that attacking might be a bad idea because the other guy's cards would harm us in this and this way.

In the game, the AI player does not know all the cards (new cards can be imported into the game many months after the game has launched), so it has to be able to respond to cards it has never seen before. This means that if the game is released on day 1, it has to be able to deal with cards released on day 30, without the dev team constantly patching the core engine.

This "solution" hasn't yet been tested by me, I haven't had the time yet, but if implemented correctly, it could work. The down side is that any minor error in implementation can cause huge play mistakes, and perhaps the biggest down side is that each card may require extensive scripting to be correctly interpreted by the AI, which creates a huge development burden.

Share this post


Link to post
Share on other sites
Wow... that's an interesting approach. And yes, I can see how it would be a bitch to make sure that the controller AI was tweaked properly to balance all those suggestions. It seems to me that a more mathematical model would add another level of detail to make the comparisons easier - such as attack and defense strengths. Did you do that but leave it out of your post?

Share this post


Link to post
Share on other sites
(I had a short lunch hour, and the post was already long enough...)

Well, even though each card has its own adviser-script, advising the Master AI, we can tweak or actually program in entirely different ways the Master AI, the AI player itself, so that we can actually mimic different play-personalities, an aggressive player, a defensive player that uses ranged attacks, etc...

How you, in exact terms, would program the Master AI, can vary extensively. There are a number of ways to do it.

You can simulate everything you are aware of, the same way a human player simulates plays in his head not only using his own cards, but also simulating the responses of the opponent's cards (again, that he is aware of).

None the less simulation means little in this context, if you cannot give a score to the outcome of an action. In WotC's MtG, three of the most important aspects of the gameplay are:
- Your Health
- The Health of your Units
- Minimum sum Damage of unblockable Units
- A Low difference in the number of cards left in the Decks

In any simulation, the actions you take have an impact on the above aspects, changing the status quo of the game, and giving you something to measure.

This allows us to have a brute-force search for the best play for a particular spell, for example.

We run our simulated spell attack, and re-score the resulting status. We do this for all legal targets of the spell, and we then real-play the spell on the legal target that resulted in the highest score loss for our opponent.

The amount of cards on the table is always fairly low, so I would say brute-force programming of the Master AI could be the most promising avenue to have a proficient AI player.

One could also suggest Fuzzy Logic as an approach to examining the advices the cards gave, but that is unknown territory for me.

Regarding the play field, it seems to be a simple event/response system. The arbiter fires off game phase events in their usual sequence, pick card, play card, attack, play land, etc. Inside each game phase different events can be triggered by either player.

Finally, I would design the Master AI system in such a way that it would also remember past games, so that it could evolve its play style, and have GA-style variables in the AI script so that they could be micro-tweaked from game to game.

One could also let thousands of iterations of AI players play against each other, and see what type of decks they would evolve, and what play styles would come out of the simulations.

Share this post


Link to post
Share on other sites
If you could pull this off then gawd blesha! I used to play Magic back in college and had thought about basing a game on the idea. My problem was a lot of cards had arbitrary, specific verbal instructions. Not only would programming the cards be difficult, but the AI to comprehend what each card did seemed virtually impossible.

On another note (and somewhat OT), the game seems to have changed since I was in college. I bought some decks a couple of years ago (just for old times sake) and found the game to be MUCH less strategic and not much more than a monster brawl. The old decks allowed players to get into "cat & mouse" situations where the newer games always seemed to end in "Oh well, I guess your monster is bigger than my monster. In the old days, it wasn't the size of your monster that mattered, it was how you used it. Does this seem to be true for most people or did I just happen upon some shitty decks/expansions? (and please don't answer that if you've never played on the original cards =/) Are the original cards still for sale?

Are there any games out there currently that allow you to match against the computer?

Share this post


Link to post
Share on other sites
Quote:
Original post by coderx75
"Oh well, I guess your monster is bigger than my monster. In the old days, it wasn't the size of your monster that mattered, it was how you used it.
[looksaround] Uh... whoa.

Quote:
Are there any games out there currently that allow you to match against the computer?
My step-daughter got an intro set to the game a few years back. It had two very simple decks. It also came with a computer training CD that played against you. However, she (at age 9) could beat the snot out of it. I mean, she would gain points over the game while crushing the opponent. Very disappointing. It also was limited to those two, small decks.

Share this post


Link to post
Share on other sites
I haven't play magic in years but I remember it being a very strategic game, one that would be difficult to make a good AI for without using scripted strategies.

Even simply strategies like enchanting a basilisk with lure, and regeneration. So that it destroys any monster that it blocks or is blocked by, forces all defending monster to block it, and can regenerate from any damage it receives. Thus effectively eliminate any monster defense that your opponent relies on.

Without scripting strategies I don't see how it could be done effectively.

The real trick with developing an AI for a game like magic is devising an evaluation function. That can decided the best way to use the combination of cards currently available in a given game state.

Do you destroy the artifact that gives your opponent 2 life a turn or the one that deal 2 damage to you? Do you save 4 mana in order to tap all your opponents’ lands on their next turn or use it yourself?

Both of those depend entirely on the current state of the game.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Quote:
Original post by InnocuousFox
Quote:
Original post by Glak
just let it know what is in the opponents deck. Not the best solution but probably the most workable.
Also known as "cheating" and generally frowned upon by AI developers.


Perhaps someone knowledgeable in DCI rulings could tell us when decklists are public and when they aren't (I know they aren't in Limited formats, but what about Constructed?)
The top 8 competitors in a Pro Tour tournament are provided with one anothers' decklists the evening before the playoffs. Even in an ordinary tournament setting, it's usually possible to guess your opponent's list to within a few cards after two or three turns of play. So as a Magic player, I wouldn't consider it cheating if the AI magically knew what was in my deck.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement