I’m on a roll

I implemented about 70 cards in the last week, which more than doubles the total amount of implemented cards in Mox (which I implemented in a year). Most of these cards use mechanics that were already implemented and hence were easy to add (some more than others!). Here are some statistics about the implemented cards and the complete list is further down.

--- Implemented cards (139/368 - 37.8%) ---
By color:
 None: 29 (20.9%)
 Black: 17 (12.2%)
 Green: 17 (12.2%)
 Blue: 16 (11.5%)
 Red: 29 (20.9%)
 White: 31 (22.3%)
By type:
 Land: 15 (10.8%)
 Instant: 16 (11.5%)
 Creature: 79 (56.8%)
 Sorcery: 12 (8.6%)
 Enchantment: 7 (5%)
 Artifact: 10 (7.2%)

 Adarkar Wastes
 Afflict
 Aggressive Urge
 Air Elemental
 Ambassador Laquatus
 Anaba Bodyguard
 Ancestor's Chosen
 Angel of Mercy
 Angelic Blessing
 Angelic Chorus
 Angelic Wall
 Angel's Feather
 Arcanis the Omnipotent
 Assassinate
 Battlefield Forge
 Beacon of Destruction
 Beacon of Immortality
 Benalish Knight
 Bloodfire Colossus
 Bog Wraith
 Bogardan Firefiend
 Bottle Gnomes
 Brushland
 Canopy Spider
 Caves of Koilos
 Composite Golem
 Condemn
 Counsel of the Soratami
 Craw Wurm
 Demon's Horn
 Dragon's Claw
 Dross Crocodile
 Dusk Imp
 Earth Elemental
 Enormous Baloth
 Forest
 Fugitive Wizard
 Furnace Whelp
 Ghost Warden
 Giant Growth
 Giant Spider
 Goblin Piker
 Goblin Sky Raider
 Grizzly Bears
 Hill Giant
 Holy Strength
 Honor Guard
 Horseshoe Crab
 Icy Manipulator
 Island
 Kamahl, Pit Fighter
 Karplusan Forest
 Kraken's Eye
 Lava Axe
 Lightning Elemental
 Llanowar Elves
 Llanowar Wastes
 Looming Shade
 Loxodon Mystic
 Lumengrid Warden
 Mahamoti Djinn
 Mantis Engine
 Mass of Ghouls
 Megrim
 Might of Oaks
 Millstone
 Mind Stone
 Mirri, Cat Warrior
 Mogg Fanatic
 Mountain
 Nantuko Husk
 Natural Spring
 Naturalize
 Orcish Artillery
 Ornithopter
 Pacifism
 Persuasion
 Phyrexian Vault
 Plague Beetle
 Plains
 Prodigal Pyromancer
 Rage Weaver
 Raging Goblin
 Rain of Tears
 Reviving Dose
 Righteousness
 Rock Badger
 Rod of Ruin
 Rootwater Commando
 Royal Assassin
 Rushwood Dryad
 Scathe Zombies
 Serra Angel
 Serra's Embrace
 Shivan Dragon
 Shivan Hellkite
 Shivan Reef
 Shock
 Sky Weaver
 Skyhunter Patrol
 Skyhunter Prowler
 Skyhunter Skirmisher
 Smash
 Snapping Drake
 Soul Feast
 Soul Warden
 Spined Wurm
 Spineless Thug
 Spirit Weaver
 Spitting Earth
 Starlight Invoker
 Steadfast Guard
 Stronghold Discipline
 Stun
 Sudden Impact
 Sulfurous Springs
 Suntail Hawk
 Swamp
 Tangle Spider
 Tempest of Light
 Threaten
 Thundering Giant
 Tidings
 Traumatize
 Tundra Wolves
 Underground River
 Unholy Strength
 Unsummon
 Venerable Monk
 Viashino Sandscout
 Viridian Shaman
 Wall of Air
 Wall of Fire
 Wall of Swords
 Wall of Wood
 Wild Griffin
 Wurm's Tooth
 Yavimaya Coast
 Youthful Knight

The list doesn’t seem that long when I think about all the time gone since my first card (Shock). I guess I have to tackle the hard cards now! (Global effects, replacement effects, clone effects, reveal effects, modal choices, regeneration, protection… good times)

Advertisements
Posted in Mox | 2 Comments

Mechanics

As I mentioned previously, I’m back to the good stuff: implementing new cards! With every mechanic I implement, I can unlock many new cards. It’s almost like a game with achievements! Here’s the list of new mechanics with some examples, in approximate chronological order of realization:

Auras

The biggest difficulty for this was implementing the whole “attach/unattach” effects. Effects must correctly affect objects and must stop affecting objects when the attachment is removed. Although I only implemented auras with this, the same mechanic will be used for equipments and fortifications. In fact, I already handle the case where the attachment moves from card to card (the effect must stop affecting the first card and begin affecting the second card). For auras to work correctly, I also had to implement subtypes (auras are an enchantment subtype). This mechanic allowed me to implement the two auras from the 10th edition white starter deck:

But before, I had to implement…

Vigilance

This one is pretty straightforward to implement. This one allowed me to get a famous card working:

Also, Serra’s Embrace is giving an ability.. which I did not support. I only supported effects of the type “creature gets +1/+1”. So I had to add…

“Creature gains XYZ”

In the meantime, I started the red starter deck and implemented the cards I could. Here’s a sample:

A lot of red cards have Haste though so I went on to implement a basic rule that I had avoided so far…

Summoning Sickness & Haste

It was not as hard as I would have thought and I had those mechanics working in a couple of hours, unlocking yet again some cards:

Finally, today, I refined the targeting mechanics so I could implement…

There’s still a lot to do, so I’ll stop here! See you around!

Posted in Mox | 4 Comments

Enough AI already!

Hello, everyone!

I’m sure that by now, you’re all fed up with me talking repeatedly about obscure MTG AI programming problems! Well, you’re in it for at least another time!

!Health Warning!

Attempting to program AIs for MTG can be dangerous to your health. If you suffer from any symptom, stop reading immediately. Symptoms may include

  • Extreme fatigue, with insomnia
  • Seeing minmax trees in your cereals
  • Sudden urge to stop programming forever
  • Starting to talk to your AI

AI programming is not recommended for pregnant women and children under 5.

So, I’ve been working these past few weeks on what I call an iterative minmax driver. The minmax driver is the part of the AI that, given starting choices, fills/constructs a minmax tree by trying out all the possible futures of the game. What I had so far is a recursive driver. Although they produce the same tree from the same input game state, the way they do it is very different.

A recursive algorithm usually looks like

void Foo_Recursive(State s)
{
    Pre_Foo(s);

    foreach (State child in s)
    {
        Foo_Recursive(child);
    }

    Post_Foo(s);
}

while an iterative algorithm looks more like

void Foo_Iterative(State s)
{
    Stack<State> statesToTry = new Stack<State>();

    while (!statesToTry.IsEmpty)
    {
        State s = statesToTry.Pop();

        Pre_Foo(s);

        foreach (State child in s)
        {
            statesToTry.Push(child);
        }

        // Can Post_Foo go here?
    }
}

Although the recursive version is clearer to read, the iterative version has a clear advantage: you can stop the algorithm right in the middle very easily by breaking out of the while loop. Much harder to do when you’re 200 function calls deep. Also, it’s possible to run out of stack space in the recursive version (the infamous stack overflow!) but the iterative version always use approximately the same stack space, however deep you are in the minmax tree. Sadly, the iterative version is also much more complex to code. For example, try to figure out where to put the Post_Foo call in the iterative version to get the same behavior as the recursive version. You will find it’s quite tricky!

It took me a few weeks, but now I have an iterative minmax driver that outputs completely identical minmax trees as its recursive counterpart. That allowed me to implement a timeout for the AI very quickly, which gives me a nice failsafe for my other AI woes. If the AI goes on a rampage and starts tearing space time apart because it has too much choices to try, at least it won’t stall eternally and will play something (although probably not the absolute best choice).

I’m very satisfied with the stability of my AI right now. For example, I just ran a quick arena test where I simulate 50 AI vs AI matches. It took 140 seconds (in debug!), i.e. and player 1 won 52% of matches, which makes total sense. I’m a bit tired to work on AI though (as you might be able to tell) so I’ll leave it for now and try to return to implementing more MTG-related features. Last time I talked about this, I proposed to do enchantments & equipments, so I might do that.

Must sleep first though…

Posted in Mox | 3 Comments

MTG: Duel of the planeswalkers on Steam

A quick work to mention that MTG: Duel of the planeswalkers is available for 10$ on Steam. This game was previously only available on Xbox Live Arcade. The game actually comes out June 15th. Happy gaming!

Posted in Uncategorized | Leave a comment

Struggling with combat

Previously on this blog: I’m trying to get AI vs AI games to work so that I can do tests that cover random situations. Also, it gives me an opportunity to solve all the little problems that are bound to happen.

One of these problem is performance. I can hardly get a single game to finish. Some games do finish quick enough (couple of seconds), but others I can let run for an hour and still not have a result. This is obviously not good. I realized that the main problem is combat, or rather, the number of combinations involved in attacker/blocker declarations. The huge number of combinations result in many, many “possible futures” to try out for the AI. In other words, the minmax tree explodes.

As an example, consider this ‘simple’ situation: 5 creatures in play for each player. AI for player A must declare attackers. There are 32 different ways to declare attackers with 5 creatures. Now, imagine the AI trying out one of these 32 combinations. Let’s say the one where the player attacks with all five creatures. In order to evaluate if this move is good or not, the AI must then try out all the different blocking positions for player B. Let’s say player B decides to block with all of its 5 creatures. There are 3125 (5^5) distinct ways to block 5 creatures with 5 other creatures. That’s a lot. The AI must also try out blocking with only 4 of the 5 creatures, 3 of the 5, up to no blocker at all. I’ll leave the math to you, but there are 7776 distinct ways to block 5 attackers with up to 5 blockers. Now, remember that these are only for the 1 combination out of 32 where player A attacks with all 5 creatures. It still has to try the 31 other combinations. Since combinations are multiplicative, it makes a huge amount of possibilities to try. I didn’t actually compute the total number of possibilities for this case, but I imagine it must be greater than 100,000. Even if your object model is very fast and all, you can still expect your AI to take a lot of time to try these out.

This is for 5 vs 5, a situation that can realistically happen in casual games. Now for the worse part: it’s exponentially worse as you add creatures to the mix (6 vs 6, 7 vs 7). In my case, the situation is made worse by the heuristic my AI uses. It tends to value creatures too much, especially at high life (20 is high). Because of that, it’s very conservative when it comes to risking its creatures in combat. If both players are like that, you soon end up with massive amounts of creatures in play on each side. I think that this is what happens in most of my arena runs.

Now, there’s a special case where the number is reduced considerably and that is when there are equivalent creatures in play. For example, for 5 identical creatures versus 5 identical creatures, there’s only 6 distinct ways to attack and given 5 attackers, only 1 (!) way to block with 5 creatures. I’ll probably implement this optimization, but it doesn’t help me at all when the creatures are unique. I feel that in real games, the case where creatures are different is more frequent than the alternative.

Now, I’m turning to you: do you see any other way that would reduce considerably the number of situations to evaluate in combat? Right now, the only way out I see is to simply discard combinations randomly and only consider a fraction of them. I can probably pre-sort the possible situations in order to evaluate the ones with most potential damage. Still, I would have to evaluate situations that don’t look that good but can turn the tides with special abilities (imagine a small creature with “When this creature attacks alone, you win” (a bit far-fetched, but you get the idea).

See you around!

Posted in Mox | 6 Comments

New theme

I thought this theme was pretty nice so here it is 🙂 I have made several improvements in Mox but I’ll leave that for the next post. I also added a link to the sourceforge project page for people wanting to download/try Mox (no binary included, you’ll need to compile it yourself).

Have a nice day!

Posted in Mox | Leave a comment

Introducing Arenas

Mox is still not quite stable. Even with my work in the previous weeks, the AI (it’s always the AI…) can still lead to one of these disasters:

  • Stack overflow: This usually means that the AI is stuck in a infinite recursion. For example, playing repeatedly an ability costs no mana and doesn’t require tapping. This is not the actual situation here, but it shows the point.
  • Infinite loop: Similar to infinite recursion, but the AI is stuck in the same loop over and over. For example, trying to play a card, realizing it’s not possible (not enough mana), and then trying to play the same card, over and over. That would be a bug, of course.
  • Data inconsistencies: Yes, it’s back. The problem with data consistency across AI tries that I took so long to fix this spring still happens (or the same symptoms anway), although much less often.

The nasty thing about card game AI is that there’s a lot of randomness involved (many starting positions possible given a deck). So it’s a pain to reproduce these bugs through normal playing, and even more difficult to debug. To help me, I started to write tests that use arenas (Another Radical Education Network for AI). Seriously, arenas are just tests where I pitch two AIs against each other with some given decks. The nice thing is that if I need to reproduce a bug that happened during a particular run, I can re-run the same game by feeding another arena with the same parameters (including random seed). Tadam! Can debug those nasty issues. Another nice advantage to arenas is that I can run many, many different games and find problems faster (about 1-2 seconds per game right now). Testing manually would take much longer!

By the way, I tried the optimization technique that I discussed in my last post, where the AI doesn’t try equivalent cards (4 mountains are equivalent). It worked majestically! A single AI choice that took about 30s now takes 1 second! Schwing!

So, now I’ve only got to fix those disasters!

Posted in Mox | 1 Comment

Spring news

Hey everyone, it’s been a while since I wrote!

Since my last post, I’ve been working on solving the second problem I discovered a few months back: having the minmax algorithm ‘seeing’ exactly the same game state when trying different choices. This is essential to the algorithm working alright and was due to a skew between my sequencing module and my minmax module. They were not being on the same page. The sequencing module would start trying a choice from a given point while the minmax module would start from a slightly later point. I solved this by moving all the “replay” glue code in the sequencing module, so that the minmax module can concentrate on the minmax algorithm. This way, replaying parts of the game is always consistent.

After that, I kinda came to realize that the performance of the minmax algorithm is not so great, even with pretty intense multi-threading. It can really only check one or two ‘plies’ ahead (a ply can thought of as another step in the future the AI is trying). I’ve read more about minmax since then (thanks for mtgrares for this link) and I’d like to implement iterative deepening sometime in the future. Iterative deepening consists of applying the minmax algorithm to only 1 ply, then using the result of this pass for a 2-plies pass, and so on, until satisfied with the result. This technique can be used to give the AI a given amount of time to think instead of a given amount of plies. Also, it can actually make the algorithm go faster (which is a bit counter-intuitive) due to the pruning nature of the alpha-beta technique.

For that, I still need to be able to squeeze in a few more plies, so I’ll turn around to more down-to-earth optimisations. Especially, treating all cards of the same type the same would help me a lot. For example, when you have 4 shocks in your hand at a given time, it’s useless for the AI to try them all out, they are exactly the same and will have the same effect. Doing this optimisation in your hand is easy, but not so trivial in the battlefield, where effects can introduce variations in cards otherwise identical.

If anyone has experience in applying min-max algorithms to complex card games, please contact me, I’m interested in your advice or your code 🙂

Posted in Mox | 7 Comments

Good news everyone!

I have invented a device that which makes you read this in my voice in your head!

Good news everyone!

I started working again this weekend on one of the two “elephant in the room” problems: minmax driving of multichoice parts (that’s a mouthful)! Tonight, I committed what I think is a robust solution, with a ton of new unit tests to make sure those new limit cases are taken care of forever.

Recap: About a month ago (or has it been two already?), I discovered two major flaws in the mechanism that drives AI in Mox: what I call the “min-max” driver. This piece of software is responsible for trying the choices available and evaluating the game state’s value every now and then. It’s basically the centerpiece of the minmax AI module.

Both flaws are related to multichoice parts. Parts are the individual (atomic) game flow pieces that make up the whole game. The driver works on the part level, meaning that when confronted with a choice, it has to retry that last part. A part can contain 0..N choices, meaning that it can contain more than one choice to be decided by the AI module. For example, playing a spell might require to choose a target AND tap a card. This is what I call multichoice parts.

The first flaw involves the state of the game when retrying multi-choice parts. I realized that when the AI was trying out the possibilities for a multi-choice part, there was a possibility that the game state was not quite the same as when the choice has to be made originally. This is not due to a problem in the transactional object model, so the solution is not straightforward. Although I have some ideas in mind for this problem, I chose to attack the second problem first.

The second flaw was that I realized, when investigating for a solution to the first problem, that the minmax driver was plain broken for multichoice parts! Basically, it would spew out random results on the second decisions of a part and later decisions (first decision was ok). Turns out this bug didn’t really appear in the game because most parts are not multichoice parts. This is the bug I fixed this week.

I can now get working on the first bug! Hopefully I can get back to doing funnier things (like adding cards) soon.
See you around!

Posted in Mox | 3 Comments

Midlife crisis

Hi everyone, just wanted to post a quick update. Life has been crazy lately and I didn’t have time to work on Mox for the last few weeks. Between the crazy hours at work, watching the olympics, getting my bathroom redone and going on long weekends outdoors, it just wasn’t possible. Doesn’t mean I’m not thinking about it anymore or that I will stop (Visual Studio is still open in background 24/7), but I definitely don’t have the momentum I had a couple of months ago. Can’t promise anything, but I hope I can put some time into the project soon.

See you around!

Posted in Mox | Leave a comment