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.

I'm not sure how much it helps, but here's a link to a list of computer games based on the card game:

Magic the Gathering Video Games

Master of Magic was based partially on it, as well, but is more of a 4X game.

I remember briefly pondering how I would do it a few years ago. It made my brain hurt.

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.

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.

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.

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.

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).

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).

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.