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

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

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.

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

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.