I originally drafted a long response to this thread with some ideas about the possible approaches to solving this problem... but after reading it I realised that many of the sub-problems you would need to solve for a good quality, intelligent solution were not realisable in a game with play time limitations or would need too much development time. I also think that you don't actually want a very intelligent opponent in games as complex as MT:G, because they'd beat you too often. Instead, I think you could get by with a heuristic approach to game play... so I deleted my draft and wrote this brief reply! ;)

For any given deck of cards, consider when you might want to play each individual card. It may be that you want to play it as soon as you can, or only if certain other cards are in play (on either side of the table), or not if other cards are in play. You may only want to play it in response to an event (think 'counterspell'). While it would take some time, I believe you could get a working heuristic player by considering each card in the deck and designing a set of conditional rules for its play. You could also have a few overriding rules, like 'play a card with maximum affect if I would otherwise have to discard at the end of turn'.

Of course, once you start incorporating performance measures into your rules, then it gets a lot harder, because your performance objective function has to also encapsulate your play strategy.

While a heuristic player would not be optimal, it would be far easier to craft than a player that solves a dynamic optimisation problem taking into account the opponents behaviour and your preferred behaviour (as you would if you were modelling the game as a game tree and solving something like a minimax problem).

Cheers,

Timkin

This does sound like a tricky problem... If I had to write this, I would probally consider a "group" of related cards and derive a formula to determine which cards are the best based on the stats of the cards.

If I had a hand of cards and wanted to determine which one to play, then I would caculate this percentage for each card and then order them by group so that the best cards in each group were at the top. Then it is a matter of picking which group of cards that the AI wants to play, which could be determined randomly but with the cards the AI favors more given a higher probability.

Of course then you have a few special cases such as countering cards.... In that case it would probally be wise to store in the data structure of the card which cards can be used to counter that card, and then if the AI finds such a card in it's hand then it could play it.

- some kind of memory/expectation system is needed

Bayesian statistical methods? Markov chains? Simple probability/statistics?

- to guess what capabilities the opponent(s) has (cards in his hand)

I think finding a good way to abstractly represent a capability is important here. However I think you can probably go a long way without needing to do much prediction - most of the key decisions are probably made based on what is already in play.

- and how to effectively counter his strategy with the AI's capabilities

As mentioned previously, a heuristic approach is good here. They can be based on abstractions of key game mechanics, allowing them to generalise to 95% of the cards.

But if you're using this to test a game in development, as is the impression I get, you may not yet have a well-weighted set of heuristics. Perhaps a little meta-training is in order then - start some AI opponents off playing randomly, see who does best, look at play patterns, and abstract them into weighted rules.

But to be honest, I think a human is going to be a far better judge of these heuristics than a program.

- while advancing it's own strategy despite the opposition of its opponent(s).

Tricky, though a good strategic heuristic should allow you to combine this into one simple "what is the best move to take" choice, as with chess games and the like.

- card draws are random and the strategy of any player can change completely with a single draw or card play)

One could argue that the strategy is fixed when you choose your deck of cards, and that what changes with each draw is the tactics. This might prove to be a fruitful dividing line to base a 2-tier system around - strategic to analyse their deck vs. yours, and tactical to analyse their situation vs. yours.

eg. The strategic manager could decide to put cards in your deck that are good vs. the expected strategy of a given player. Then the tactical manager, when it finds such a card in its hand, will evaluate its usefulness every turn, and play it when most appropriate (ie. when it yields the best estimated improvement in status).

<< << The fact that some to most human player almost play "randomly" (without an in depth strategy) might be a proof that this is a complex problem :) >>


First off this statement is completely false.I've never seen anyone other than first timers play cards randomly. Even crappy players usually have complex and multilayered strategies. I've been playing Magic since the original Unlimited set. People incapable of strategy loose interest really quickly.

I also played the old Magic PC game and while it did a good job with the rules, the AIs were fairly idiotic. They made basic mistakes that no human ever would and the only way a good player would lose to it was if they got a completely shit hand. Also, all of the computer controlled decks in that game were built by the designers not generated by an AI.

As for how to approach an AI for it, the really difficult part is how to represent the wide variety of card effects in a manner the AI can store in it's knowledge base so it can weigh the potential use of each. The scope of that challenge alone is huge. You have to keep track of all the cards in hand, in play, and in both graveyards and all the possible interactions of each one. This doesn't even begin to approach foreward thinking strategies such as when to hold a card to wait on a combo.

A heuristic might be faster but probably not a good compromise since it's turn based game and the system can take the extra time to think if it really needs it. Although many players cut corners the game has very discreet phases in each round and a different solution must be discovered for each. The PC game was very literal about each phase of the game and often the ai would take a while to think between phases.