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…