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!

Advertisements

About fparadis2

Lead Game programmer
This entry was posted in Mox. Bookmark the permalink.

6 Responses to Struggling with combat

  1. mtgrares says:

    Coding Magic and min-max is hard enough but actually getting it to work in a reasonable amount of time is probably the real challenge. I’ll make a few random suggestions but feel free to ignore them. 🙂

    1. Use min-max only to play cards and abilities. Code a very simple attack and block routine. Like always attack if you would trading creatures, 2/2 would attack into a 2/2.
    2. If the AI is attacking, generate 20 to 100 “good combat scenarios” using some other heuristic code and then use min-max to evaluate the scenarios you generate.

    I don’t know if that really helps or not. It is still a very interesting project. I keep thinking that I’ll try to get Forge 2 working with 10 cards and min-max. I haven’t done it yet since it seems very complicated with data corruption and everything.

    • fparadis2 says:

      Thanks for the input!

      1. That could be interesting 🙂 Maybe one day we can merge AI types or get them to compete against together.
      2. That’s probably what I’m going to end up doing. I’ll basically set a time limit for the AI. When time is up, I’ll use the best scenario found so far.

  2. thealtCaw says:

    Just want to say what a great blog you got here!
    I’ve been around for quite a lot of time, but finally decided to show my appreciation of your work!

    Thumbs up, and keep it going!

    Cheers
    Christian, iwspo.net

  3. neoFred says:

    Hi. I’ve got a question about your code. I downloaded it from your SVN, and noticed your structured it quite well.

    When you create a project at VS what are the first steps you do, so it get organized in folders like Source, Output, etc.

    Hope you understand my question, and by the way, why you don’t follow up the AI at the Xbox game of Magic?

  4. fparadis2 says:

    Hi and welcome!

    I pretty much do it manually (don’t have that many projects). I create the project in the Source folder and I then change the output path in Visual Studio to a relative path so that everything gets output in the Output folder.

    As far as the xbox game goes, I assume you mean the two articles by the lead programmer of the game on wizards.com? Yes, I read those, and indeed our techniques are very similar.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s