Monday, January 3, 2011

Min-Max Combat

Combat is a major component of any Magic game but unfortunately combat is also one of the areas where the AI struggles.  The AI falters in combat because it only follows a few "rules of thumb" like attack if you have the biggest creature or attack if no other creature can block.  Since combat can be hugely variable these rules of thumb break down and the AI doesn't play competitively. 

The two biggest problems with AI combat are:

1. Sometimes the AI attacks with all of its creatures and then you easily attack and win.  The AI should have held back a few creatures.

2.  The board becomes crowded with many creatures and the AI is afraid to attack.  This is a stalemate where each player has plenty of creatures on the board but not a winning position so you just hope you draw something good and usually you can beat the computer.

I am working on making the AI combat better by applying min-max.  This would allow the AI to "see" several turns in the future and make much better combat decisions.  The new code should be able to process common keywords like flying and defender.  Hopefully in the future the new code will handle other keywords like wither and "this card must always attack".

The downside is that this new combat code won't be 100% perfect and the computer won't suddenly be playing like a pro.  The new code won't consider static, triggered or activated abilities like regeneration.  This seems really bad except that the old combat code didn't consider these abilities either.  The new combat code should be an improvement but I don't know how much of an improvement.

Planeswalkers are confusing to the old and new combat code.  With the old code, the AI attacked a planeswalker 50% of the time.  While this seems incredibly lame, it ensures that you will not be able to predict what the AI will do.  The new code will probably do the same thing because the AI cannot generate future events like a planeswalker using his devastating, ultimate ability.

Hopefully I will finish the new combat code so everybody can see if it makes a difference.  I want to guess that I will be done in a week but I probably should guess a month (which is way too long but is probably more realistic).

The only way to improve the AI combat code so that it plays perfectly is to use min-max for all parts of the AI.  Forge has a very simple AI implementation so we can't use min-max because it requires the computer to generate thousands of future events so the AI can determine which future path would be the best. 

To get a taste of a good Magic AI download Magarena.  It only has 450 cards but the AI is very good.  You can read more about Magarena here.

Keep on forging,

--I'm glad that my previous post about other offline TCGs was interesting.  Personally I thought the article was a little bit "weak" but I'm glad that people enjoyed it.  Picking a topic each week feels very random but I'm glad that I occasionally strike writer's gold. 

--Just for reference, here is the old combat code.  The attacking code is 290 lines and the blocking code is 260 lines.  You can view the Java attacking code here and the blocking code here.

--Crap, I was looking over the old combat code and I saw that it mentioned lure.  Man, I really hate lure right now.


The Turquoise Mage said...

I have tried all the other card games you have punted on your blog ... but have kept coming back to Forge. There is nothing like it. I will indeed keep on forging,

Forge said...

Thanks, other people have mentioned the same thing. 5,000+ cards is just insane and should keep everyone busy until the next millennium.