ToohrVyk: If you just want a basic probability-based deck-design AI, something like a bayesian inference system could easily make a system that can guess the cards likely to be in the deck given enough training on N-card combos likely to show up in decks (ie, use it to predict whether an Nth card is in the deck given that two cards have been seen, and repeat the process with each group of N cards seen so far each time a new card is played).

My problem is that I want to made a "card-based" deck designer that will figure out good card combos on it's own and be able to build a deck without any direct input besides some kind of abstract representation of each card available. I'd love to hear any ideas on algorithms suitable to this kind of thing.

just let it know what is in the opponents deck. Not the best solution but probably the most workable.

Quote: Original post by Glak
just let it know what is in the opponents deck. Not the best solution but probably the most workable.

Also known as "cheating" and generally frowned upon by AI developers.

Quote: Original post by InnocuousFox

Quote: Original post by Glak
just let it know what is in the opponents deck. Not the best solution but probably the most workable.

Also known as "cheating" and generally frowned upon by AI developers.

Perhaps someone knowledgeable in DCI rulings could tell us when decklists are public and when they aren't (I know they aren't in Limited formats, but what about Constructed?)

The "solution" I found to this problem was to let each card have a scripted AI and let it be an adviser to the "master" AI.

This adviser AI would examine the current state of affairs, have the ability to know what is in our deck yet to be played, what went to the graveyard, what cards of the opponent we have seen already, etc, and, from its point of view as a card with certain abilities and objectives it would advise the master AI on a line of play.

Bare in mind that the card can be active, on the table, or inactive, in the player's hand, so its advices could range from "«put me in play now for defense reasons», you have mana" to "«don't attack with me», the opponent has a high attacker only I can defend".

So the cards talk to the master AI in sentences like:
- attack with me (because the opponent cannot stop me, I fly)
- don't attack with me (because only I can block that huge guy without getting murdered)
- use my special ability on target card (I've got a bow and arrow and i can inflict 1dmg anytime, use it on that guy with 1hp)
- etc

There is a certain complexity here, because each card is an adviser, yet, to correctly give any sort of advice about itself and its range of uses, it has to examine the whole play field, so you're struggling to keep something that should be focused from becoming global. Case in point, a certain card might miss the effects of an artifact and advise the master AI to attack with it, but the artifact would turn all damage against the attacker, so we would suffer badly. So it is our role as technical designers to make sure the master AI gets good advices, but it has to be the master AI to see the whole of the playing field and have the last word.

Also, it's a weirdish technical design decision, but it makes sense if you ran the opponent's cards' AI (that you know of, of course), and reversed their suggestions. The AI for that Artifact would advise us to attack (let's not forget it serves the other player), so we would reverse that suggestion, and make a mental note that attacking might be a bad idea because the other guy's cards would harm us in this and this way.

In the game, the AI player does not know all the cards (new cards can be imported into the game many months after the game has launched), so it has to be able to respond to cards it has never seen before. This means that if the game is released on day 1, it has to be able to deal with cards released on day 30, without the dev team constantly patching the core engine.

This "solution" hasn't yet been tested by me, I haven't had the time yet, but if implemented correctly, it could work. The down side is that any minor error in implementation can cause huge play mistakes, and perhaps the biggest down side is that each card may require extensive scripting to be correctly interpreted by the AI, which creates a huge development burden.

Wow... that's an interesting approach. And yes, I can see how it would be a bitch to make sure that the controller AI was tweaked properly to balance all those suggestions. It seems to me that a more mathematical model would add another level of detail to make the comparisons easier - such as attack and defense strengths. Did you do that but leave it out of your post?

(I had a short lunch hour, and the post was already long enough...)

Well, even though each card has its own adviser-script, advising the Master AI, we can tweak or actually program in entirely different ways the Master AI, the AI player itself, so that we can actually mimic different play-personalities, an aggressive player, a defensive player that uses ranged attacks, etc...

How you, in exact terms, would program the Master AI, can vary extensively. There are a number of ways to do it.

You can simulate everything you are aware of, the same way a human player simulates plays in his head not only using his own cards, but also simulating the responses of the opponent's cards (again, that he is aware of).

None the less simulation means little in this context, if you cannot give a score to the outcome of an action. In WotC's MtG, three of the most important aspects of the gameplay are:
- Your Health
- The Health of your Units
- Minimum sum Damage of unblockable Units
- A Low difference in the number of cards left in the Decks

In any simulation, the actions you take have an impact on the above aspects, changing the status quo of the game, and giving you something to measure.

This allows us to have a brute-force search for the best play for a particular spell, for example.

We run our simulated spell attack, and re-score the resulting status. We do this for all legal targets of the spell, and we then real-play the spell on the legal target that resulted in the highest score loss for our opponent.

The amount of cards on the table is always fairly low, so I would say brute-force programming of the Master AI could be the most promising avenue to have a proficient AI player.

One could also suggest Fuzzy Logic as an approach to examining the advices the cards gave, but that is unknown territory for me.

Regarding the play field, it seems to be a simple event/response system. The arbiter fires off game phase events in their usual sequence, pick card, play card, attack, play land, etc. Inside each game phase different events can be triggered by either player.

Finally, I would design the Master AI system in such a way that it would also remember past games, so that it could evolve its play style, and have GA-style variables in the AI script so that they could be micro-tweaked from game to game.

One could also let thousands of iterations of AI players play against each other, and see what type of decks they would evolve, and what play styles would come out of the simulations.

If you could pull this off then gawd blesha! I used to play Magic back in college and had thought about basing a game on the idea. My problem was a lot of cards had arbitrary, specific verbal instructions. Not only would programming the cards be difficult, but the AI to comprehend what each card did seemed virtually impossible.

On another note (and somewhat OT), the game seems to have changed since I was in college. I bought some decks a couple of years ago (just for old times sake) and found the game to be MUCH less strategic and not much more than a monster brawl. The old decks allowed players to get into "cat & mouse" situations where the newer games always seemed to end in "Oh well, I guess your monster is bigger than my monster. In the old days, it wasn't the size of your monster that mattered, it was how you used it. Does this seem to be true for most people or did I just happen upon some shitty decks/expansions? (and please don't answer that if you've never played on the original cards =/) Are the original cards still for sale?

Are there any games out there currently that allow you to match against the computer?

Quote: Original post by coderx75
"Oh well, I guess your monster is bigger than my monster. In the old days, it wasn't the size of your monster that mattered, it was how you used it.

[looksaround] Uh... whoa.

Quote: Are there any games out there currently that allow you to match against the computer?

My step-daughter got an intro set to the game a few years back. It had two very simple decks. It also came with a computer training CD that played against you. However, she (at age 9) could beat the snot out of it. I mean, she would gain points over the game while crushing the opponent. Very disappointing. It also was limited to those two, small decks.

I haven't play magic in years but I remember it being a very strategic game, one that would be difficult to make a good AI for without using scripted strategies.

Even simply strategies like enchanting a basilisk with lure, and regeneration. So that it destroys any monster that it blocks or is blocked by, forces all defending monster to block it, and can regenerate from any damage it receives. Thus effectively eliminate any monster defense that your opponent relies on.

Without scripting strategies I don't see how it could be done effectively.

The real trick with developing an AI for a game like magic is devising an evaluation function. That can decided the best way to use the combination of cards currently available in a given game state.

Do you destroy the artifact that gives your opponent 2 life a turn or the one that deal 2 damage to you? Do you save 4 mana in order to tap all your opponents’ lands on their next turn or use it yourself?

Both of those depend entirely on the current state of the game.