Monday, May 17, 2010

Forge's Awesome AI

It's been awhile since I've talked about "Forge's awesome AI". Basically Forge's AI is very simple. Each spell and ability has a method called canPlayAI() which returns true if the AI should play it. Royal Assassin's ability is a good example. The AI for Royal Assassin's activated ability checks to see if you have any tapped creatures and then targets the biggest one. Shock does about the same thing, except that the code tries to kill X/2 flyers and 3/1 creatures and avoids plain 2/2.

The biggest flaw of canPlayAI() is that each card and ability is evaluated separately. The computer will never use two Shocks to kill a 4/4. Since each card is evaluated individually it is hard to create decks that the AI can use effectively. Generally the AI is good with creatures and basic, aggro decks. One of the decks that I submitted as a deck for the quest AI had all vampire creatures, it did not include any sorceries or instants. Some of the vampires had effects that trigger when you play them, which acted like sorceries. The AI could use the deck because it only had to play creatures and then attack.

Combat is handled completely separate. The attacking code tries to be aggressive and will usually attack. Sometimes the AI should attack but is too cautious, thus causing the game to stretch out. (I tried to avoid problem of when the AI would attack with everything and then you would attack and win but I accidentally caused this "stalling" problem.)

The blocking code is also very simple. The AI tries to make decent blocking decisions. The blocking code is more complicated than the attacking code since you can have multiple blockers and generally you don't want flyers to block non-flyers.

The attacking and blocking code does not do anything fancy and just uses a "for" loop to generate which creatures will attack or block. Let me explain the "for" loop for the attacking code. The code looks at each of the computer's creatures individually and asks, "Should this creature attack?" The blocking code does to the same thing, it looks at each attacking creature and asks, "Should this creature be blocked?"

Obviously this isn't how a human player attacks or blocks. Players, like myself, attack or block based on the whole combat situation, all of the creatures. So the AI does very little processing when it comes to combat and that explains why it makes so many mistakes in that area. Ideally the AI would do a CPU intensive search to generate better combat decisions.

Forge's biggest snafu is that the AI doesn't play spells during your turn, except for counterspells, or during combat. This was done to simple the code for canPlayAI(). Coding canPlayAI() for "normal" situations is hard, so coding for unusual situations (like other phases) is out of the question.

The biggest strength of Forge's AI is that it plays by the rules, nothing fancy. On paper it sounds easy until you begin coding and then you start pulling you hair out. Making the AI use the same resolve code as the player is very hard. (Forge's early design dictated that I had to code each card twice. One for the player and one of the computer. I knew this was the wrong way to go.)

For awhile Wagic's AI couldn't use activated abilities and I knew exactly how hard I worked on that. (Unfortunately it is hard to help someone because different projects have different UML designs, how everything fits together.)

By the way, Wagic is a great project. It has more cards than Forge and a nice user interface. Shoutouts to wololo. (The guy who started Wagic.)

And as a side issue, Forge still uses the "old combat" rules.


Forge said...

The title "Forge's Awesome AI" is a bit exaggerated since the AI basically does random legal actions.

DennisBergkamp said...

I've been attempting to add some AI combat improvements... it seems to have helped a little bit but there's still a lot of stupidity going on :)

Hopefully I'll get around to making it more acceptable in the next few versions.

moxdev said...

Funny how I'm currently having problems with combat AI on Mox. Just blogged on that before seeing your post :)

Forge said...

The latest forum release (5/16) greatly improves the attacking and blocking. I've played a few games and the AI was much better.

Greg said...

Rather than trying to improve individual aspects of the AI for particular cards or situations would it be worth implementing a state search type of AI to get the job done?

You'd need three things
(1) A way to represent the state of the game in a single varible. That's probably not too hard, since you can just stick all the variables you already use to store the state of the game into a single AI
(2) A way to generate possible new states from an existing state. Probably a tremdendous amount of work, you'd need to have a function that took a state and worked out what the state would be after each legal play
(3) A way to evaluate how good a particular state is for the computer. It'd be easy to start with something like "computers life + cost of computers cards in play + cards in hand - players life - cost of players cards in play - cards in players hand" and tweak it as needed.

If you had those you could put it all through something like a minimax algorithm (or anything else that good chess programs use).

The advantage is that you wouldn't have to worry about the specifics of any situation. The computer would go through all states and pick the best combination of moves, including attacking, activating creatures, playing cards etc. The disadvantage is that it might be so processor intensive that the AI takes a long time to make decisions. You could limit the depth of the search to one turn for each player though, then it wouldn't be much worse than a standard chess AI.

It'd be a tremendous amount of work, but possibly less than playing whack a mole with AI problems and trying to improve each bit one at a time. Some of the folks I studied with threw together an AI that played 3D noughts and crosses this way in a week, but obviously that's a far simpler game to implement and generate states and movements between them for.

I dunno, just throwing ideas out. This probably isn't a great one since it might be less fun to code (since you don't get that hit off having fixed a particular problem every so often) and ultimately you're doing this for free - so you enjoying doing it is the most important thing.

Good luck with whatever you're doing at the moment, magic related or not :)