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!