MTG Engine compare

[Marek14]

I decided to start this thread as a sort of "quick and dirty" comparison between various Magic AI programs on this board, highlighting their good and bad points. Anyone is welcome to add to it, but no bashing of rival programs For now, these are my personal experiences. I start with four programs I have used the most (arrandeg alphabetically).

Botarena:
Speed: Can be quite slow, but the "time of thinking" can be set. A single game can last for an hour or more.
Number of cards: Large. The "easy" cards are still not all implemented, so I expect the rocket increase in number to last for some time.
Stability: Good. Seems to have an occasional crash, but only rarely.
AI Level: Excellent. Definitely the best Magic AI out of these. I wonder how it compares with the official Duels of the Planeswalkers.
Rules implementation: Excellent. Actually managed to switch to M10 rules. There are some minor kinks.
Updates: Frequent.
Gimmicks: Supports CPU vs CPU play.

MagMa:
Speed: Very fast.
Number of cards: Large. Seems all the "easy" cards are implemented, so it doesn't grow that quickly.
Stability: Good.
AI Level: Not too much of a challenge.
Rules implementation: Pretty fine. Some rules are just rough approximations.
Updates: Very slow.
Gimmicks: Allows for nice random decks.

Manalink:
Speed: Sometimes the thinking is noticeable, but rarely.
Number of cards: Medium. The limit of 2000 cards in total (including tokens) hurts a lot and prevents the implementation of realistic sets. I think the other three have all over 2000 implemented by now.
Stability: Bad. This is caused by the legacy code from previous millenium.
AI Level: Good. I think.
Rules implementation: While the rules are implemented almost perfectly, they are Fourth or Fifth Edition rules. Triggered abilities don't use the stack, for example. However, deserves a props up for having Magical Hack and Sleight of Mind, which are probably some of the hardest effects to do.
Updates: Frequent.
Gimmicks: Challenge Mode.

MTG Forge:
Speed: Great. Ideal for quick games.
Number of cards: Medium. It doesn't grow too fast, but it grows.
Stability: Good.
AI Level: Not very good, I'm afraid. But still manages to win sometimes.
Rules implementation: Worse then MagMa, I think. Improves gradually, so it might surpass it soon.
Updates: Frequent.
Gimmicks: Random decks, Quest Mode.

[juzamjedi]

Thanks for writing this up Marek. I haven't tried all these yet and from your reviews Botarena looks like something that I would enjoy. /download

In my opinion one of the best "gimmicks" for MTGForge is the ability to draft. That is one of my favorite Magic formats and I frequently fire up MTGForge for this reason.

No review of Incantus though?

[Marek14]

Thanks for writing this up Marek. I haven't tried all these yet and from your reviews Botarena looks like something that I would enjoy. /download

In my opinion one of the best "gimmicks" for MTGForge is the ability to draft. That is one of my favorite Magic formats and I frequently fire up MTGForge for this reason.

No review of Incantus though?

Well, I left off Incantus for two reasons. First, I seem to have lost touch with it - I appeared in the IRC channel lately, but haven't seen MageKing or Incantus himself, so I don't have the latest files (I could probably implement some more cards if I had). I wanted to wait until the new M10 rules are implemented, but now I have no idea of what the recent progress is.

The second reason is that I wrote this up as a comparison of Magic AI programs. However good Incantus is in rules implementation, it doesn't have AI, which would harm it in the evaluation (unfairly, I think).

[frwololo]

No love for me ?

[Marek14]

No love for me ?

I said "my personal experiences" If there's someone willing to add pros and cons of Wagic, he's welcome to.

[mtgrares]

MTG Forge:
Speed: Great. Ideal for quick games.
Number of cards: Medium. It doesn't grow too fast, but it grows.
Stability: Good.
AI Level: Not very good, I'm afraid. But still manages to win sometimes.
Rules implementation: Worse then MagMa, I think. Improves gradually, so it might surpass it soon.
Updates: Frequent.
Gimmicks: Random decks, Quest Mode.

My main goal was to make a fun Magic game. The AI is a little random and is like playing your younger brother, sometimes he makes a good play. Hopefully random decks and the quest mode are GREAT gimmicks. Forge also has an integrated deck editor and the ability to upload and download decks.

On my blog I keep talking about improving Forge's AI but I haven't really coded anything. It is really hard to start "Forge version 2" because I'm starting from scratch which will be good for the rules engine and bad because each card will have to be re-programmed. If the rules engine is sophisticated enough with events and triggers, coding the cards won't be so difficult. Instead of hardcoding the card in Java, I'm planning on creating a very simple text language that will work for 99% of the cards.

Hopefully I'll get inspired to code.

[Marek14]

MTG Forge:
Speed: Great. Ideal for quick games.
Number of cards: Medium. It doesn't grow too fast, but it grows.
Stability: Good.
AI Level: Not very good, I'm afraid. But still manages to win sometimes.
Rules implementation: Worse then MagMa, I think. Improves gradually, so it might surpass it soon.
Updates: Frequent.
Gimmicks: Random decks, Quest Mode.

My main goal was to make a fun Magic game. The AI is a little random and is like playing your younger brother, sometimes he makes a good play. Hopefully random decks and the quest mode are GREAT gimmicks. Forge also has an integrated deck editor and the ability to upload and download decks.

On my blog I keep talking about improving Forge's AI but I haven't really coded anything. It is really hard to start "Forge version 2" because I'm starting from scratch which will be good for the rules engine and bad because each card will have to be re-programmed. If the rules engine is sophisticated enough with events and triggers, coding the cards won't be so difficult. Instead of hardcoding the card in Java, I'm planning on creating a very simple text language that will work for 99% of the cards.

Hopefully I'll get inspired to code.

If you do, I can write the cards. I can be productive in that

But seriously, if you plan to redo the Forge, keep us posted. I am a stickler for exact rules implementations, and it would be great to have a project which would be done with, say, Artificial Evolution, Sorin Markov and Primal Beyond in mind (All of which are a bit troublesome to insert into a framework that didn't count with such possibilities.)

[Incantus]

I can definitely attest that without Marek's help understanding obscure rules corner cases (and also implementing more than half of Incantus's cards - 3221 according to the editor) he was a great help to the project!

Anyway, here is probably the order of difficulty in implementing the cards that Marek listed (from easiest to hardest):
1. Primal Beyond - just requires generalizing the mana framework to handle tagged mana (ie mana that can only be used for a certain purpose)
3. Sorin Markov - One way I've thought about implementing controlling another player's turn is to basically accept input from the controlling player instead of the actual player, and overriding some of the rules that go into effect (well, the main one was manaburn, but they removed it)
2. Artificial Evolution - this depends on how you've implemented your cards. If you have a simple text description (actually, this would work for scripting language implementations as well), it's probably sufficient to reevaluate it with the changed characteristics. However, the difficult part is replacing the original card (and all references to it by other parts of the code) with this new card object.

[Marek14]

I can definitely attest that without Marek's help understanding obscure rules corner cases (and also implementing more than half of Incantus's cards - 3221 according to the editor) he was a great help to the project!
[\quote]

I can still be, I think, I just decided I will come back to Incantus after the M10 rules will be implemented How is that going?

Anyway, here is probably the order of difficulty in implementing the cards that Marek listed (from easiest to hardest):
1. Primal Beyond - just requires generalizing the mana framework to handle tagged mana (ie mana that can only be used for a certain purpose)
3. Sorin Markov - One way I've thought about implementing controlling another player's turn is to basically accept input from the controlling player instead of the actual player, and overriding some of the rules that go into effect (well, the main one was manaburn, but they removed it)
2. Artificial Evolution - this depends on how you've implemented your cards. If you have a simple text description (actually, this would work for scripting language implementations as well), it's probably sufficient to reevaluate it with the changed characteristics. However, the difficult part is replacing the original card (and all references to it by other parts of the code) with this new card object.

If I go with what Incantus had problems with last time I saw it, it was nontraditional ways of playing spells (like Cascade). MageKing was working on new spell framework last I talked with him - that was about six months ago, though...

Reflecting Pool, Exotic Orchard, and their kin are also not too easy, I think. From the beginning, you should realize that anything that produces mana can be suddenly asked "and what types of mana can you produce, anyway?" And there can be nested examples, like sacrificing Reflecting Pool to Squandered Resources. See my post viewtopic.php?f=27&t=1515#p18704

Also, I chose Sorin Markov for my "triplet" instead of Mindslaver because Sorin is a planeswalker and planeswalkers are another thing that is not easy to add after the project starts. Lots of projects did it, but Forge for example still has them quite hacky (for example it lets you target planeswalkers with direct damage spells instead of implementing the planeswalker redirection rule).

I thought up a fun thing to do for Forge - try implementing all cards in Magic with Forge in their name:

Battlefield Forge
Burrenton Forge-Tender
Darksteel Forge
Forge Armor
Forget
Greater Forgeling
Manaforge Cinder
Pulse of the Forge
Rage Forger
Sunforger
Thran Forge
Unforge
Wurmskin Forger

This set does actually cover many basic things - Manaforge Cinder means you have to implement hybrid, Sunforger forces you to implement playing spells for free, Wurmskin Forger means distribution targeting, Burrenton Forge-Tender means damage source selection... try it!

[mtgrares]

But seriously, if you plan to redo the Forge, keep us posted. I am a stickler for exact rules implementations, and it would be great to have a project which would be done with, say, Artificial Evolution, Sorin Markov and Primal Beyond in mind (All of which are a bit troublesome to insert into a framework that didn't count with such possibilities.)

Well I keep thinking about Forge 2 everyday, so eventually I'm going to do some actual work on it.

I want to try out a more sophisticated AI algorithm like alpha-beta and my initial goal is 10 cards like Royal Assassin, Wrath of God, Giant Growth, Counterspell and Shock which are tricky cards for the AI to handle. That way I can test the AI under "real conditions". My goal is for the AI to respond to spells and to play spells at EOT.

Since you are a rules lawyer Marek14, I'll probably need your help to test the new combat rules which I don't fully understand. I haven't written the code for the new combat system yet, but when I do I'll need your help. The only thing that I have completed for Forge 2 is the user interface which uses abstract components so I (or someone else) should be able to write a new user interface for Forge 2 by just implementing the code which shows the cards and not having to worry about the other stuff.

I'm also planning on making an object called "RulesEngine" which handles all of the rules such as drawing cards, untapping, who wins, whose turn it is, etc... It will be a big object but it will have just one purpose, to implement the rules of Magic (which is a big enough goal). Currently I have the rules spread out all over the place which is very, very messy and impossible to update. This way I'll have ONE method that moves cards, moveCard(Card, Zone to, Zone from) and ONE method that does damage, damage(Object playerOrCard, int damage, SpellAbility damageFrom, Card damageFromCard).

[Marek14]

Well I keep thinking about Forge 2 everyday, so eventually I'm going to do some actual work on it.

I want to try out a more sophisticated AI algorithm like alpha-beta and my initial goal is 10 cards like Royal Assassin, Wrath of God, Giant Growth, Counterspell and Shock which are tricky cards for the AI to handle. That way I can test the AI under "real conditions". My goal is for the AI to respond to spells and to play spells at EOT.

Since you are a rules lawyer Marek14, I'll probably need your help to test the new combat rules which I don't fully understand. I haven't written the code for the new combat system yet, but when I do I'll need your help. The only thing that I have completed for Forge 2 is the user interface which uses abstract components so I (or someone else) should be able to write a new user interface for Forge 2 by just implementing the code which shows the cards and not having to worry about the other stuff.

I'm also planning on making an object called "RulesEngine" which handles all of the rules such as drawing cards, untapping, who wins, whose turn it is, etc... It will be a big object but it will have just one purpose, to implement the rules of Magic (which is a big enough goal). Currently I have the rules spread out all over the place which is very, very messy and impossible to update. This way I'll have ONE method that moves cards, moveCard(Card, Zone to, Zone from) and ONE method that does damage, damage(Object playerOrCard, int damage, SpellAbility damageFrom, Card damageFromCard).

I can do it, although I tested only Incantus... it gets more tricky when AI is involved.

Do you plan to have players as things that "plug in" the rules engine so there would be no difference between AI and human, as far as the engine is concerned? I.e. both would send the same sort of inputs?

[frwololo]

I.e. both would send the same sort of inputs?

At some level that's how any game involving an AI should work, otherwise maintenance becomes a nightmare

[Marek14]

I wonder what could be the "hook" for new Forge Planechase? Two-Headed Giant?

[mtgrares]

I wonder what could be the "hook" for new Forge Planechase? Two-Headed Giant?

Hm..just better AI at first. Two-Headed Giant seems impossible since it changes too many of the cards. Maybe Planechase since it doesn't seem too different. Doing something like Momir Basic would be fun, since the games would be very wild.

Do you plan to have players as things that "plug in" the rules engine so there would be no difference between AI and human, as far as the engine is concerned? I.e. both would send the same sort of inputs?

Yeah, because you can go crazy trying to program two different versions of each card: one for the player and one for the AI. When I first started Forge the easiest I experimented by coding two different versions but I quickly abandoned the idea since it multiplies your code by 2.

Forge uses the same "resolve" code for both human players and the AI. Typically the resolve part of the card is the hardest to program. The AI chooses targets differently than human players, so stuff like protection has to be duplicated for both the human and AI targeting code. Both the AI and human players choose a spell's targets and call Card.setTarget(...). The resolve code gets the target from the targeting code and then does damage or whatever.

Currently the AI won't use 2 Shocks to kill a 4/4 creature and I want the AI to be able to do that. Forge's current AI isn't good with activated abilities or instants either. I want the AI to use Giant Growth during combat in order to make the player a little nervous. I hope people will actually fear the AI but we'll see.

I laugh when I see "evil AI" movies on TV because AI is so hard. Computers will never be smart, just really fast calculators. AI is just a special effect that makes computers appear to be smarter than they really are. (On the most basic level a computer can only add 2 numbers and compare 2 numbers.)

[Marek14]

I wonder what could be the "hook" for new Forge Planechase? Two-Headed Giant?

Hm..just better AI at first. Two-Headed Giant seems impossible since it changes too many of the cards. Maybe Planechase since it doesn't seem too different. Doing something like Momir Basic would be fun, since the games would be very wild.

Vanguard, then? There's 106 of them right now, and many of them are pretty fun...

Do you plan to have players as things that "plug in" the rules engine so there would be no difference between AI and human, as far as the engine is concerned? I.e. both would send the same sort of inputs?

Yeah, because you can go crazy trying to program two different versions of each card: one for the player and one for the AI. When I first started Forge the easiest I experimented by coding two different versions but I quickly abandoned the idea since it multiplies your code by 2.

Forge uses the same "resolve" code for both human players and the AI. Typically the resolve part of the card is the hardest to program. The AI chooses targets differently than human players, so stuff like protection has to be duplicated for both the human and AI targeting code. Both the AI and human players choose a spell's targets and call Card.setTarget(...). The resolve code gets the target from the targeting code and then does damage or whatever.

Currently the AI won't use 2 Shocks to kill a 4/4 creature and I want the AI to be able to do that. Forge's current AI isn't good with activated abilities or instants either. I want the AI to use Giant Growth during combat in order to make the player a little nervous. I hope people will actually fear the AI but we'll see.

I laugh when I see "evil AI" movies on TV because AI is so hard. Computers will never be smart, just really fast calculators. AI is just a special effect that makes computers appear to be smarter than they really are. (On the most basic level a computer can only add 2 numbers and compare 2 numbers.)

Well, I dislike the word "never" - after all, how do we know our own intelligence isn't just a "special effect" as well?

If I understand it correctly, one way would be to have an evaluation function that would assign a number to a game state, and then lookahead that tries to maximize that number. Two basic problems are how to construct the function, and how to search the state space in game with incomplete information and random moves like shuffling.

The evaluation function would take into account life totals, I presume (someone somewhere tossed the idea of making it a logarithmic function, so 20 life vs 10 life would be the same difference as 10 vs 5). Taking into account the board, that's the hard thing since there's uncountable number of variants. I had an idea of making the card values dynamic... For example, the value of Gaea's Anthem would grow with number of your creatures (the more creatures you have, the more is enhanced, and the more valuable is the Anthem). A value of landwalker would be increased if its landwalk is active.

As for random look-ahead, I was wondering about a kind of Monte Carlo method. Before the computer takes action, some number of possible "worlds" is generated, and each of them has the "unknown elements" randomly shuffled - different order of cards in libraries, different cards in opponent's hand, different morphs hiding under face-down creatures (but cards KNOWN to AI are left alone - if it returned a creature to your hand, it will know it's there). In each of these worlds, the random seed is set, so it's deterministic. Then, after determining the values of various moves in various worlds, computer will choose, for the real game, the one with highest average value in all worlds. With less worlds, the AI play would get more random and surprising, with more worlds, it would get overall stronger.

This approach requires AI to have access to the contents of player's deck - which I consider acceptable. In real world, the deck contents are shaped by tournament rules and metagame, so you can know what to expect. In computer Magic, there are no guarantees, so knowing the contents of deck is not too big a problem.