• Advertisement
Sign in to follow this  

AI for (Collectible) Card Games?

This topic is 4142 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

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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 =-)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
- 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).

Share this post


Link to post
Share on other sites
<< << 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.

Share this post


Link to post
Share on other sites
Extrarius: my apologies, but I don't have a lot of spare time at the moment to dedicate to a thorough exposition of my ideas... my brain is currently wrapped around the problem of extending a proof of the stability of recurrent systems and right now it wants to burst! 8( I'll try and give a brief account of whats going through my mind and you can highlight the bits that sound most interesting to you, which I'll try and expand upon further later.


For games such as M:TG (and here I'm writing as a former national level tournament player and judge), there is a core ruleset governing how cards can be played. However, the actual gameplay mechanics are dictated by the union of the specific cards in a deck and the ruleset. So, as you rightly mentioned in your opening post, very complex gameplay scenarios can arise through the combination of just a few cards. Indeed, the best combo decks in M:TG revolved around 3 to 4 cards and then the rest of the deck was built to support that combination (usually to ensure either speed to set it up, or robustness of the deck until the combo hit the table).

So, with this in mind, I would approach the problem of deck design and play from the perspective of defining the (sequence of) event(s) generated by applying the ruleset to an arbitrary subset of cards. These events will eventually result in a change of state of the game (where state includes all cards in each hand/deck/graveyard/play and life totals). So, any given set of cards defines a set of possible event sequences (or operations on the game state).

What you want to know is which sequence(s) of events are most effective at generating particular state changes (think of these sequences just as you would actions which generate a transition in a state space in any other planning problem). You then want to know which are the most robust given that you have an intelligent opponent trying to disrupt you. Finally, you want to find the minimal set of cards that produces the given set of sequences that you want to use to win the game with the most robustness to opponent strategies.

There are two aspects to your problem here: analysis (modelling of the possible gameplay) and planning (deciding what operators to use and how and when to combine them to maximise performance). These are coupled problems and not trivial, because of your opponent. So, a further extension to this would be to try and recognise your opponents policy and understand their gameplay model (this is known as plan recognition and opponent modelling).

(Sorry to have to cut this short, but I've got a meeting to run to...)

Cheers,

Timkin

Share this post


Link to post
Share on other sites
The original M:TG computer game had a credible AI that could play any deck handed to it (though I don't think it played combo decks well). So it was not using a pre-set per-deck set of rules - I think the heuristics were probably per-card. It was a really fun game and I have several times considered trying to pull together a M:TG AI, but it seems like a huge project and is rather daunting. On the other hand it would be totally sweet to train different AIs/deck combinations against each other - you would probably see some interesting behavior.

Ultimately I was discouraged by the fact that even if I did come up with something cool, I wouldn't be able to distribute it without getting sued :-(

Share this post


Link to post
Share on other sites
Has anyone considered the highly likely possibility that the OP is intending to write (or get someone to write) this program in order to cheat?

I don't think a program would be very applicable to this game, since it won't know the cards the other player has. Some games of imperfect information are played well (perfectly) by computers, but something like this probably wouldn't be.

-Trying to find loopholes- doesn't seem very plausible to me.

Share this post


Link to post
Share on other sites
<< Has anyone considered the highly likely possibility that the OP is intending to write (or get someone to write) this program in order to cheat? >>

I don't see how. I don't see cheating being a huge problem with collectable card games.


<< I don't think a program would be very applicable to this game, since it won't know the cards the other player has >>

Yeah, that's the challenge for humans too. There are thousands of different cards by now. The only way of knowing what's in your opponent's hand is to have a card that lets you look.

Share this post


Link to post
Share on other sites
Quote:
Original post by sharpnova
Has anyone considered the highly likely possibility that the OP is intending to write (or get someone to write) this program in order to cheat?[...]
I'm nearly certain that I could make more money by selling(or leasing/contracting/etc) a superior MtG AI to WotC than I could ever get by winning in tournaments (and cheating elsewhere would just be a waste of time). It'd be far cheaper to run a program over the latest set they're developing than to hire all the testers they normally do, and they could still have a secondary playtest of human players (even human testers vs the AI to see if it's decks/strategies/etc are valid).

Quote:
[...]I don't think a program would be very applicable to this game, since it won't know the cards the other player has. Some games of imperfect information are played well (perfectly) by computers, but something like this probably wouldn't be.[...]
Yes, this is one of the factors that make it an interesting problem IMO. There are many cards that could be used to see the opponents hands, but the main question is "are they worth it?" Could an AI play decently without knowing the opponent's hand, as most decks force the human players to do? I imagine it could, since a large part of playing is guessing what the opponent will do, and an automated player could run easily several complex algorithms in order to accurately guess what the opponent's hand is like.

Quote:
[...]-Trying to find loopholes- doesn't seem very plausible to me.
WotC changes card text and rules quite often, and many cards are banned or restricted in different modes of play in tournaments, so it seems likely there are exploits in the system.
Even though that may be the case, the real value is for designing future cards. Human testers might find better combos, but an automated tester could examine things more completely and could thus probably find more unintended interactions. Even if they're not game-breaking, they might significantly hurt the fun of casual play.
It applies to creating completely new games even more than new cards for existing games, because both rules and cards would be in flux, and that could easily create unintended interactions. Also, with few people working on the game (as there would be anyplace besides WotC), there are fewer minds thinking about combos and thus it's more likely for something to go unnoticed. Then there are problems like 'which types of cards are needed' that the AI could solve during it's deck-building phase - when it finds a card it wants to counter and can't find a simple counter, it could simply produce a diagnostic message that lets designers know there is a hole that needs filling. It could also take information about cards favored by human players and apply the same 'deck plan recognition' capability to guess which new cards will be used most, and designers could use that information to help eliminate 'useless' card and attempt to make everything more balanced.

Share this post


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

  • Advertisement