Wednesday, April 9, 2008

AI Tricks

I wanted to go over same of the tricks that the AI uses in order to seem smart. Admittedly, the AI is a basic opponent and is hopefully a little smarter than your little brother. (link to AI Good Enough?)

If you are a frequent reader, you will already know the computer’s land is smoothed, to read more see my previous column. The computer’s AI is divided up into three main parts. The general “brain” that pays for card costs, plays a land, and calls all the other routines. Then there is the combat code that handles when to attack and block. Finally, some code is added to each card that tells the computer when it can be played. The AI code in each card also sets the targets.

The AI built into each card accounts for most of the computer’s intelligence. The computer is only as smart as the few lines of code that are added to each card. A card like Shock is difficult for the computer to play effectively because of the wide variety of game situations. The AI for Shock basically targets a 2/2 flyer or the human player if it would kill him. If the computer’s life is under 7 (an arbitrary number), the computer will target a random creature that it can kill. A card like Ancestral Recall (draw three cards) is much easier for the computer to use well.

Wrath of God is a very situational card that the computer has a hard time evaluating. The AI code will play Wrath of God if he would destroy 2 more human creatures than computer creatures, or if the computer is under 7 life. The AI won’t play Wrath if you, the human player, do not have any creatures in play. The computer can win more easily with straightforward cards like Epic Proportions (enchantment, target creature gets +5/+5 and trample.)

Previously, I have also talked about how playing cards during the Main1 or Main2 phase helps the AI. (link to AI and Phases)

I’m not sure if anyone is really interested, but the “brain” is the Java class ComputerAI_General. ComputerUtil_Attack2 and ComputerUtil_Block2 handle combat. The reason the “2” is there is because they are the second version. The AI card code is handled by the methods canPlayAI() and chooseTargetAI(). Every spell and ability is represented by the class SpellAbility. Each SpellAbility class has the methods canPlayAI() and chooseTargetAI(). Wrath of God doesn’t have any targets, so chooseTargetAI() is not needed.

//Wrath of God, taken from CardFactory
public boolean canPlayAI()
CardList human = new CardList

CardList computer = new CardList

human = human.getType("Creature");
computer = computer.getType("Creature");

/*the computer will at least destroy 2 more human creatures*/

return computer.size() < human.size()-1 ||

(AllZone.Computer_Life.getLife() < 7
&& !human.isEmpty());

}//end canPlayAI()


Unknown said...

Have you considered trying a minmax or expectimax algorithm w/ pruning?

I'm currently working on an AI player for Dreamblade (as well as rules enforcement etc). It's in python currently and might be a wee bit too slow when the search tree expands and when that happens I'll probably move parts to C/C++.

Great blog BTW!

Forge said...

I actually have a min-max algorithm in Java that I wrote. (I hate writing algorithms because they are so hard to get exactly right.) But I have a hard time coping all of the game data. And I have experimented with simple searches, do 10 actions and return the best one, and finding the right evaluation function is hard. How do you evaluate a whole game of Magic? I wrote some simple evaluations, but it still didn't work correctly, so I gave up and use my easy AI implementation.

Dreamblade is cool, I hope you get something working. Glad you like the blog.

Forge said...

Also, the algorithms look great on paper but are usually pretty hard to use in an actual computer program. I've tried applying min-max to creature combat, but my head explodes, because it is hard to generate all combat situations.

I tend to like Random Hill Climbing (RHC). You just generate a bunch of random test cases and choose the best one. The more powerful your computer is the more test cases you get. Hopefully RHC will find a pretty good solution to the problem, but again you have to evaluate each test case which is difficult.

Unknown said...

I agree with forge - the main difficulty in doing an AI is designing a metric to evaluate the game. This is much more difficult than a game of chess, since you are dealing with unknown information (what kind of deck is the opponent playing?), and also likely depends on the particular deck the AI is playing. Probably the easiest AI to do would be simple aggro decks, while blue control decks would probably be the most difficult to implement.

Unknown said...

Good point Incantus, I guess I'm looking at it from my project's perspective (while although similar to MtG, MtG it is not).

Dreamblade is game of perfect information. The only part that is kinda wonky is the dice rolling. What do you do? Assume an average roll (does that even make sense)? A good roll? Go down every tree for each possible roll outcome? I guess I have issues too. :)

I do know of one MtG AI project though that does uses minmax with pruning (with special heuristics for MtG). I've only seen some of the code so I can't comment on just how the evaulation functions etc are done.

I'm very impressed with your program Incantus. Enforcing the rules is *extremely* challenging although python makes it a wee bit easier than something like C.

Are you using pygame or pyglet? Is it open source? I'd like to check out the code. I'm going to put my project up soon once I have something somewhat functional (either sourceforge or google code, not sure). I stink at graphics and although I know pygame pretty well my interface is currently using ncurses (ugh). But it makes it easy to test over ssh. ;)


Unknown said...

Oh, and I forgot to mention one other MtG-esque card game that recently an AI was written for. Blue Moon.

This guy used neural nets but fixed decks. I know very little about neural nets but the code was very interesting.

I have no idea if something like that would work for arbitrary decks. Given how long he said it takes to generate the data for fixed decks, I imagine it's not that easy.


Forge said...

I downloaded Blue Moon and I'll see how it is.

In case Incantus didn't see your question, he is using pyglet I believe and it will be open source.

"Dreamblade is game of perfect information. The only part that is kinda wonky is the dice rolling. What do you do? Assume an average roll (does that even make sense)? A good roll? Go down every tree for each possible roll outcome? I guess I have issues too. :)"

Only small projects don't have any issues.

Dice rolls seem very hard of course. You can cheat and have the AI know the dice rolls in advance. The dice rolls are random, it is just that the AI knows what the future dice rolls will be.

My theory is that you probably can't make the AI too hard. Theoretically the AI could be so good that it wasn't very fun, but making the AI anything but an idiot is very difficult.

Forge said...

I still think about setting up a forum somewhere because it would make discussions like this easier.