Monday, March 1, 2010

Combat is Hard

Forge is sometimes really stupid when it comes to combat. Deciding when to attack or block is a very thorny issue. (Well…most things in Magic are thorny aren’t they?) I wrote the AI combat code and although I’ve rewritten it once, it still has some major flaws.

First let me state that the code works well but is restricted by the overall combat architecture, which I did designed. The code answers the question, “Should this one creature attack?” While this question is important, it leads the AI down the wrong path and makes it look stupid. The correct question would be “What is the best way that all of the creatures should attack?”

So now we know that the AI makes attacking and blocking decisions by only looking at each individual creature but that doesn’t approach the intellect of playing against a real human opponent. A better AI would have to do an actual search and try to find good combat scenarios. (Doing an actual search may take 5-30 seconds but this is just a guess.)

Right now the alpha-beta search algorithm could be applied to Forge but it wouldn’t take into account activated or triggered abilities. Each ability is hardcoded and tries to find a good target, the AI doesn’t have a way to make an ability try different targets. The AI code would only see regular creatures with a few simple abilities like flying, vigilance, and trample. Also the code might not work with the rest of the program because of the overall architecture, which I designed on-the-fly.

So butter by backside and call me a biscuit, I think that’s all I have to say. Hopefully the computer occasionally surprises you with a good play.

The blocking code is more complicated that the attacking code because you can have multiple blockers. And the attacking code does look to see should it attack with all of its attackers in order to win.

The blocking code tries to see the situation when the AI might attack with everything and then you attack with everything and easily win. Unfortunately I messed up the logic so even that doesn’t work sometimes and it actually makes the AI seem more stupid since it doesn’t race. (Racing is when you attack with everything and then your opponent attacks with everything.)

If the AI could figure out should it race or not, that information would really improve the AI’s performance. (If the computer shouldn’t race, it would attack less and block more, thus making the game go longer because the AI would be trying to topdeck something good.)


Huggybaby said...

Can you put the blocking code in a separate file? Then it could be adjusted as time goes by.

AI should always block the largest creature it can without dying. So if AI has 4 defense, block a creature with 3 attack. If human pumps attacker, so be it, we can worry about that later. It's better than sitting there taking attack after attack and doing nothing about it.

DennisBergkamp said...

I'll make some changes so the AI should block a lot more often.

Forge said...

It would also be nice if somehow the AI has "personalities" to go with the deck, like aggro.

One of the hardest questions for the AI to decide is when to trade creatures when attacking or blocking.

(By trade creatures I mean that both creatures are destroyed.)

Anonymous said...

Hi, just a quick 2c without really knowing your issue. Instead of the minimax search only exploring attack-or-block options, you could include activation of abilities, and paths for groups rather than individuals.

If you can take a hand, you should be able to enumerate every possible future state of that hand which is reachable in the current phase, then regard each future state as an option to be put into the search tree.

In that mode, one possible "choice" would be that card A activates an ability while card B attacks, another would be A attacks, another that B attacks, another that A and B both attack. So instead of searching for the best choice for each creature, or even for a group of creatures, you could examine the best choice for the whole hand.

The branching factor would be pretty high though, because of the number of combinations that a hand can be used in.

So I don't have any suggestions for good heuristics, short-cuts etc, but if the action is made by the hand rather than a card, then might that be a way forwards?

Also, is the AI only considering the combat (i.e. figuring out the best outcome for the combat at hand and what is left), or looking ahead to future turns also?

Thank you very much for keeping your blog and for making the software available.


Forge said...

Thanks for your comment. The main issue is that I haven't worked on version 2 that implements "undo" so I can't use alpha-beta or any of the stuff that I have been talking about.

"Thank you very much for keeping your blog and for making the software available."

Well I enjoy Magic and other people do to, so it win-win and everyone is happy. I'm just happy that something that I've helped to create is fun. (Fun is a very tricky word to actually achieve.)