AI Evolution

[SoulStorm]

This topic is here to provide a place for people to discuss AI development. Deck builders, programmers, and those who are just interested in the continued evolution of the AI are welcome to post their thoughts here.

[SoulStorm]

I'm not a programmer, but I've recently come to enjoy building decks for the AI. One thing I've learned since I've started is that a good player deck does not necessarily translate into a good AI deck. There are a lot of reasons for this. Whether a player or AI, decisions need to be made concerning what card to play and how to use a card once it is played. The number of possible decisions each turn grows exponentially as more cards enter the battlefield. Given the complexity of Forge, now with over 5,000 cards implemented, one can only be amazed by what the developers have accomplished at this point. Still, the AI is limited and can make a lot of foolish decisions that can be irritating to a would be AI deck builder. I thought a useful exercise would be to post a deck that works very well as a player deck but poorly as an AI deck. I'll then attempt to provide an analysis of what goes wrong and give some lay suggestions of how any problems might be fixed. Remember all, I'm not a programmer, I'm just a fan of the game. I fully expect that any suggestions I have are 10 steps behinds the talented people working on this game every day. Also, talking about how to make a game better is a lot easier than actually writing the code to make it happen.

The Deck: Let's call it... Kiki Gone Wild

4 Academy Rector
4 Archon of Justice
2 Eternal Witness
4 Kiki-Jiki, Mirror Breaker
2 Meadowboon
2 Primeval Titan
2 Rukh Egg
2 Seedborn Muse
4 Seeker of Skybreak

4 Debtors' Knell
4 Doubling Season
2 True Conviction

4 Elspeth, Knight-Errant

4 Plateau
4 Reflecting Pool
4 Rootbound Crag
4 Savannah
4 Sunpetal Grove
4 Taiga
1 Mox Emerald
1 Mox Pearl
1 Mox Ruby

Everybody loves Kiki-Jiki, Mirror Breaker, right? You can make a beater deck with him quite easily, but if you try something more sophisticated like I've done, you're going to be disappointed.

First, why does this deck work well as a player deck?

Lots of synergy if you get Kiki-Jiki, Mirror breaker out:

Kiki-Jiki, Mirror Breaker + Academy Rector = automatically putting enchantments into play, which also thins your deck and increases the probability of drawing useful cards.

Kiki-Jiki, Mirror Breaker + Archon of Justice = exiling a target permanent.

Kiki-Jiki, Mirror Breaker + Eternal Witness = returning a permanent to your hand.

Kiki-Jiki, Mirror Breaker + Meadowboon = counters for all of your creatures.

Kiki-Jiki, Mirror Breaker + Primeval Titan = put any four lands into play, which also thins your deck.

Kiki-Jiki, Mirror Breaker + Rukh Egg = a 4/4 flying token that stays on the battlefield.

Kiki-Jiki, Mirror Breaker + Seedborn Muse = doing any of the above again on your opponents turn.

Kiki-Jiki, Mirror Breaker + Seeker of Skybreak = another Kiki combo.

That's 16 cards that combo with Kiki-Jiki, Mirror Breaker directly and another 6 that let Kiki-Jiki, Mirror Breaker repeat the combo. If Kiki-Jiki, Mirror Breaker hits the battlefield, he's almost guaranteed to have something useful to do.

But what if you never draw Kiki-Jiki, Mirror Breaker?

Only 4 of the 22 cards that combo with Kiki-Jiki, Mirror Breaker have limited usefulness without him, the Seeker of Skybreak, but even that card can be used to untap a creature that has just attacked such as an Archon of Justice or Primeval Titan.

The Debtors' Knell not only can return any creature to the battlefield, it also serves as a back-up Kiki-Jiki, Mirror Breaker. Need a Baneslayer Angel exiled? Just block with your Archon of Justice and bring him back to the battlefield to exile something else next turn.

Doubling Season is just sick in this deck. With the Academy Rector and Kiki-Jiki, Mirror Breaker in the deck, getting out all four copies of Doubling Season is actually quite easy. Ever have 16 copies of Archon of Justice flying at you at the same time? If you happen to survive the initial assault prepare to have 16 permanents exiled!

True Conviction speaks for itself, and is also easy to get into play thanks to the Kiki-Jiki, Mirror Breaker / Academy Rector combo.

Elspeth, Knight-Errant is mostly there for her ultimate which can be used as soon as she hits the battlefield as long as one copy of Doubling Season is out. This stabilizes the battlefield so that Kiki-Jiki, Mirror Breaker can do his thing. Having a bunch of indestructible tokens that can be buffed with Meadowboon doesn't hurt either.

As one can tell, I love this deck, which is why I wanted to share it with the community as an AI deck, but it just doesn't work as an AI deck. Let's examine some of the reasons why.

Often the AI will only block creatures when not blocking creatures means death. Many times have I seen the AI let creatures deal damage to it even if the AI's creatures could have killed the attacking creatures without suffering any losses. This often leaves the AI with little life to deal with threats in subsequent turns. This also means that planeswalkers have a more difficult time getting their ultimate abilities to go off. Admittedly, this is a problem that applies to every AI deck.

Solution: Have the AI attack by default only when it can block all possible counter attackers or when the damage output vs. expected damage taken exceeds some specified ratio. This isn't a perfect solution, but it should be better.

The AI doesn't know how to use permanents that have abilities that trigger when they go to the graveyard. Creatures like the Archon of Justice, Academy Rector, Meadowboon, and Rukh Egg are meant to take one for the team. As a player you might sometimes recognize that sacrificing them later rather than sooner is the appropriate tactic, but as a general rule, you want them to always block, regardless of resulting death.

Solution: Have creatures with abilities that trigger upon entering the graveyard behave as explained above.

The AI doesn't know how to handle permanents that put other creatures into play such as Kiki-Jiki, Mirror Breaker and Debtors' Knell. One game the AI had three permanents in the graveyard (Archon of Justice, Seeker of Skybreak, Eternal Witness) and two copies of Debtors' Knell on the battlefield. The AI brought back the Seeker of Skybreak and the Eternal Witness. I can't even begin to fathom how that decision was made. I at least expected the AI to bring back the most beefy creature.

Another game had Kiki-Jiki, Mirror Breaker on the battlefield with a Seeker of Skybreak and an Academy Rector. Kiki-Jiki, Mirror Breaker copied the Seeker of Skybreak. The copied Seeker of Skybreak then untapped the original Seeker of Skybreak which had untapped one of the opponents creatures. Once untapped, the original Seeker of Skybreak then untapped another of the opponents creatures. Needless to say, that was nothing like how I had envisioned that scenario playing out.

Solution: Let's first examine why a deck builder puts cards into a deck that brings creatures into play. The builder may just want to put more creatures into play or the builder might be expecting or even wanting the creatures to go to the graveyard and be recycled. Priority targeting should be given to cards that have effects upon entering the battlefield or going to the graveyard. Priority should then be given to the most beefy creatures or those creatures with the highest converted mana cost. Not a perfect solution, but the results would probably be better.

Planeswalkers perhaps love staying on the battlefield a little too much. They like to have that one loyalty cushion before setting off their ultimate abilities and sometimes don't even use them then. This often leads to them getting attacked and killed when they already had an opportunity to get that ultimate off.

Solution: As a default, planeswalkers should be getting their ultimates off as soon as possible. However, they should be checking to see if their emblem is already on the battlefield if the effects of the emblem don't stack (as is the case with Elspeth, Knight-Errant). This isn't a perfect solution, but more often than not it is probably better to get the ultimate off than to risk losing the planeswalker before using the ultimate.

These are the primary issues I encountered when trying to build this deck.

Before I end this post, I do want to point out one other problem with the AI that I've encountered when trying to build other decks. When the AI controls creatures on the battlefield that use mana to create tokens, the AI will just continue to pump out tokens and not play anything from their hands. Though this sometimes works as a strategy, more often than not it would be better to play cards first and then use any remaining mana to make tokens. The main culprits I'm referring to are Rhys the Redeemed and Sliver Queen.

If you've read this entire post, congratulations on you remarkable patience.

[lazylockie]

I'm gonna send a sketch of an article I'm writing to rares blog asap. Most of the stuff is general consensus (I guess), but could be a starting point into the discussion.

[mtgrares]

One thing I've learned since I've started is that a good player deck does not necessarily translate into a good AI deck.

Yeah, the AI is best with cards that are "always good" like Shock. The AI is horrible with situational cards (and abilities) like Kiki-Jiki, Mirror Breaker or Wrath of God. In general the AI is pretty bad with activated abilities. Cards like Glorious Anthem are pretty good for the AI. Sometimes the AI is bad with removal like Shock or Dark Banishing since it the AI has a hard time deciding which creature to destroy since the answer depends on the specific situation.

Also what makes a good AI deck is how the AI handles each individual card, which is an unknown quality. (Even when looking at the code it is not always easy to understand how the AI will use a card.)

I programmed the AI for Wrath of God and the AI will play it if you (the opponent) have two more creatures in play versus the number of creatures the AI has in play. (If the AI has N creatures in play, the AI will play Wrath of God if you have N+2 or more creatures in play.)

Some cards like Hex, the AI can't use at all. (I programmed Hex a long time ago and had to hack it to get it working.) And I've mentioned this a few times but the computer will not destroy a 4/4 creature with two Shocks since each card is evaluated individually. I think the computer will combo a few cards that have alternate winning conditions but I'm not sure what are the specific cards. Like if you have these 2 cards in play, the AI would win.

I know that this is a bunch of random info but hopefully it helps explain the situation a little.

[SoulStorm]

Rares, interesting that you mention Wrath of God specifically as an example of AI programming. My understanding is that originally AI routines were written for each card, like your example with Wrath of God. Doesn't the use of Ability Factory (AF) mean that coding the AI for each card is not necessary in most cases? So for instance, you would have AF Destroy All Creatures, and then every card that destroys all creatures (Wrath of God, Damnation, etc.) would use the AF code destroy all creatures, which would include the way the AI handles the card. Please correct me if my understanding of how AF works is wrong.

Also, you mention the inability of two shocks being used to kill a 4/4 creature because, "each card is evaluated individually". Would it be possible to move to hand based evaluation instead of card based? So for instance, if the AI had two shocks in hand it would know that it can deal 4 damage. The AI would then evaluate if the mana was available and play both shocks if true, but neither if false, because then it would no longer be able to deal enough damage to kill the creature.

It would seem that if you have an AF Damage Target Creature, the AI could be programmed to evaluate all cards in hand with that property, tally them, and then determine actions.

It would also seem that one could evaluate the battlefield, so that if you have two Prodigal Pyromancer cards in play the AI knows it can deal 2 damage to a target creature.

What would seem more difficult is having one card in hand that damages a target creature and another card that gives -1/-1 counters. Combining damage from the AI's hand and the battlefield also seems problematic. Perhaps instead of hand based and battlefield based, both should be evaluated together?

Of course, it may be possible that performing such evaluations would require too many processor cycles and make the game unbearably slow.

[Chris H.]

The new AbilityFactory is an improvement to the older scripted keywords. AbilityFactory_DestroyAll would take an input parameter that would determine the type of card(s) that are destroyed. This would allow a single block of code to not only handle Wrath of God but also Flashfires.

The AI code can get very tricky. Every block of code that handles a single card or a group of cards has it's own section of code for the AI. I recently added some AI code to AbilityFactory_Draw. At first, the computer would draw cards past the maximum hand size and it would then be forced to discard at end of turn.

The computer will now determine if casting the spell will cause the computerHandSize + numberOfCardsDrawn to be greater than computerMaximumHandSize. This calculation is now used to determine if the computer should cast the spell.

[SoulStorm]

I noticed the changes to computerMaximumHandSize on the SVN. That's a helpful change, makes AI decks that use cards that increase maximum hand size and card draw more playable.

Writing AI at this level makes perfect sense for the current state of the game considering that there are about 5000 more cards to be added. Are there any plans to create a more context sensitive AI once all the core work is completed on the game?

Let's take card draw for example. The AI has cards in the deck that increase draw, but none that increase hand size. However, the deck also has cards that cheat other cards into play using the graveyard. Presumably the person designing the deck planned to use card draw to fuel graveyard shenanigans. With the changes you made, one type of AI deck becomes more usable (the most probable use of card draw), while the other (admittedly fringe) would no longer work at all. Are there plans to ever have the AI be robust enough to examine the deck and make context sensitive choices so that both deck types can be played by the AI? Is such a level of sophistication even (reasonably) possible for a game of this magnitude?

I ask this not only because I'm curious as to where Forge is headed, but I'm also watching an engine being built (especially with the upcoming Shandalar features) that could be used to create a new IP.

Imagine end users being able to create complex AI decks that get sent to a central server where they are repeatedly tested against one another. Decks that perform within set parameters can then be downloaded by end users. Depending upon the difficulty level being played, campaign progression, and opponent type, a random deck that falls within the appropriate parameters is chosen as the AI deck.

Sorry, that was a bit of a rant. Playing this game makes me think of such possibilities. Anyway, keep up the great work!

[Chris H.]

It is fun and intellectually stimulating to discuss AI improvements. I enjoy participating in these discussions even when I do not have much to contribute.

The AI code can be tricky. At first, people tend to add AI code that covers situations that come up frequently. As time passes, people will notice odd AI behavior. And someone might then add some AI code to handle a situation that comes up on a less frequent basis.

You mention the changes to computerMaximumHandSize on the SVN and cards which use AbilityFactory_Draw. And as you state, these changes can help in one type of AI deck while making others problematic.

At some point, the AbilityFactory_Draw AI code could be changed to look for cards in it's deck which could be used to cheat a card from the graveyard onto the battlefield. Granted, this may also require a change to the code which is used to determine which cards the AI would discard at end of turn.

And then there is also an issue on whether we should allow the computer to cheat by looking at the cards in it's or the human's library. Some people object to this type of cheating. They want an AI that is as smart as a human being and they want the computer to use only the limited info that we humans would have under the same circumstances.

So there are also some moral type issues that have to be considered. I do not mind if we sometimes give the computer a look at either library. If this makes the computer a wee bit better at playing a few more decks or cards, great! I do not mind one bit. But I can only speak for myself.

I am not sure what sort of AI plans that other people may have. I could only guess. These new AbilityFactories require us to convert over a huge number of cards. Most have been converted but there are still some cards left to convert. I suspect that we may then want to move over some of the AI code from the old style of scripted keyword to the newer AbilityFactories.

Sol and I noticed recently that the AbilityFactories AI code that would handle X costs can be very tricky to write and this part of the project may come at a later time.

I think that we could honestly state that this is a work in progress. We build this building one brick at a time. I can remember the old forge back before it became open source. We have come a long way since then.


BTW, I made this topic a sticky.

[friarsol]

And then there is also an issue on whether we should allow the computer to cheat by looking at the cards in it's or the human's library. Some people object to this type of cheating. They want an AI that is as smart as a human being and they want the computer to use only the limited info that we humans would have under the same circumstances.

So there are also some moral type issues that have to be considered. I do not mind if we sometimes give the computer a look at either library. If this makes the computer a wee bit better at playing a few more decks or cards, great! I do not mind one bit. But I can only speak for myself.

.
I would say the AI could examine anything that appears face up (battlefield, graveyard, certain exile cards) that the Human controls. One way to make this more realistic is to create a "known deck list" for the Human each match. That way any time something is revealed the AI records it in its superior knowledge base. This way the AI wouldn't play Engineered Plague until he sees a creature type, but in game 2, if you know the Human has a bunch of Elves (or whatever) from the previous game he could target that type.

But "looking" through his own deck shouldn't be an issue. This would be equivalent to a Smart player being highly familiar with the contents of his own deck.

If for some reason there are face down cards (that the AI cannot look at and doesn't know what they were originally), then we could always take the original decklist remove all of the cards that the AI knows about, and use that remaining list as "possible cards left in library" when determining such things.

[timmermac]

It sounds like we're getting close to a combo that I used to love playing paper magic and Shandalar. Library of Leng and its relatives with Ivory Tower. And if the computer can use it too, then all the better.

[mtgrares]

Would it be possible to move to hand based evaluation instead of card based? So for instance, if the AI had two shocks in hand it would know that it can deal 4 damage.

Not without major changes. Just making the AI not stupid is hard and Forge is still working on making sure the AI doesn't kill himself with cards like Char. And when you add it combat, the AI is very, very basic versus a regular player.

[SoulStorm]

These new AbilityFactories require us to convert over a huge number of cards.

Yes, I follow the SVN regularly and noticed how much work was being done to convert all the cards. I've watched a lot of open source games develop (or more often collapse) over the years, but I've never seen a team as dedicated as this one.

BTW, I made this topic a sticky.

Thanks!

[SoulStorm]

This question is for all of the developers who have contributed to forge. Taking into account what you have learned since starting work on forge, are there any fundamental changes you would make if you were designing the game from scratch?

[DennisBergkamp]

The main thing would obviously be to have a real Game State, since this would allow for cool things such as:

- Min Max AI.
- Saving/loading anytime during a match.
- Saving/viewing replays of a match.
- A generic test "suite" with a lot of test cases, which can be run in a matter of seconds before releasing a new build.
- AI vs AI matches should be easier to implement.

[mtgrares]

The cool thing about AI vs AI is that it could test for errors that occur during the game. The AI could play itself for days and find a bunch errors.

A testing framework that would let you test cards individually and would also let you test the effects of multiple card interactions. Cards need to be tested individually to make sure that they work correct and cards need to be tested with other cards because the number of card interactions growths exponentially.

And since there are a huge number of possible errors because of card interactions, users should be able to send errors over the Internet. Once an error happens, like a card not working, the user clicks a button which sends the game information directly to the developers. Obviously we would get a few false positives but it would really help to improve the quality of the software. You can only fix something IF you know a problem exists.

Currently Forge is sort of a bug factory. I don't mean this badly and the problem stems from my original hacked, duct-taped, ad hoc architecture which worked but not well. The architecture should eloquently solve the problem.