I'm trying to find information on the algorithms that would be used to implement AI for a card game like Magic the Gathering, where cards have many varied effects (ranging from a combination of a few common abilities to a few cards that introduce practically unique new rules). I use MtG as an example because there is a huge database of cards called Gatherer where those unfamiliar with these types of games can read various cards (and both summarized and comprehensive rules are available at the MtG site). At the very least, some kind of memory/expectation system is needed in combination with a goal/planning system to guess what capabilities the opponent(s) has (cards in his hand), how likely he is to use those capabilities for various purposes (based on his strategy) and how to effectively counter his strategy with the AI's capabilities (cards in it's hand, cards in it's deck that might come up soon) while advancing it's own strategy despite the opposition of its opponent(s). This sounds somewhat simple, but there are many complicating factors (such as the depth to guess ahead - card draws are random and the strategy of any player can change completely with a single draw or card play) and I have no idea how to even begin to implement such a system. I'd appreciate any keywords, suggestions, links, paper or book references, etc on the implementation of such algorithms with the kind of complicated state found in such games.

Seriously I'm very interested in any input anyone has on this subject.

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

I'll try to see what others did in Battles of Prince of Persia... if I remember correctly there's a collectible card aspect that drives fights in the game. I'll let you know if I can get any more infos.

Alright, on Battles of Prince of Persia (DS game) they simplified the combat to allow only 1 card to be played each turn... I wasn't able to get any infos that could help you solve this kind of problem.

Does the AI in the PC version of Magic the Gathering play well?

Quote: Original post by xEricx
[...]Does the AI in the PC version of Magic the Gathering play well?

Which game are you talking about? The only one I know of is 'Magic Online', which only has human vs human modes.

I "think" I'm talking about this game. I remember hearing about it a _while_ ago... not sure if that's any help... you could still buy a used version on eBay or something and "reverse engineer" the way the AI plays it.

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

Quote: Original post by Timkin
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! ;)[...]

Thanks for your reply, but I wish you had given the longer version!

The problem with a heuristic approach is that it requires a lot of understanding of the game that nobody really has (for my purposes) and part of the reason I'd like to make such an AI is so that it could point to balance problems (it would make balancing much easier if you had a program to find the best combos, rules loopholes, etc in a mostly automatic way).

Also, I've no idea how to make a heuristic system that would include enough to fully play the game (meaning things like build a deck from a large set of cards), and it really seems like such a system would require constant updating as new cards are created and released, whereas a more complete solution would likely only require a list of the new cards and possibly minor adjustments for new abilities, rules changes, etc.

I realize it's a complicated problem and that a good AI might not be any fun to play against, but it'd be much more helpful and a much more interesting project. I'd really appreciate more information about the complicated approach =-)

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.