Automated Testing

Testing is a very important part of software. Automated tests let you know that your code is working. I was reading Wagic’s blog and he mentions how constructs tests. (Wagic lets you play Magic against the computer on PSP or Windows.)

The way Wagic tests Magic cards is very simple and easy to understand. The tests are in plain text which makes the tests probably shorter than if they were coded in C++ which is the language that Wagic uses.

The tests consist of an init section, init is short for initialization or beginning, a do section which plays a card, and the assert section which checks to make sure that the card did what it was supposed to do.

I don’t usually cut and paste anything but the blog does a good job describing the parts of the test.

Wagic Blog
Wagic Card Testing

INIT
When it loads a test file, the Testing Suite initializes the game with the data from the initial state. So for example:

[INIT]
FIRSTMAIN
[PLAYER1]
hand:Ancestor’s Chosen
graveyard:swamp,grizzly bears,dragon engine
manapool:{5}{W}{W}
[PLAYER2]
graveyard:black knight

The above init state is loaded by the testing suite. The Game engine is “forced” to go to the “first main phase” of player 1. Player 1 has {5}{W}{W} in his manapool, Ancestor’s Chosen in his hand, and 3 cards in his graveyard. Player 2 has 1 card in his graveyard. Obviously what we want to test here is Ancestor’s Chosen ability: When Ancestor’s Chosen comes into play, you gain 1 life for each card in your graveyard. The obvious advantage is that I don’t have to create a specific deck with Ancestor’s Chosen to playtest it in order to test its ability.

DO
As I said in my other article, the testing suite is like a CPU player, except it is very dumb: Instead of computing the best moves for its cards, it just takes orders from the test file. This is the second part of the test file for Ancestor’s Chosen:

[DO]
Ancestor’s Chosen

It looks simple? Well it is. What I tell the “dumb AI player” here is: just click on the Ancestor’s Chosen card. And that’s it. Since player 1 has the mana in its mana pool, and it’s his first main phase, clicking on the ancestor’s chosen card will put it into play.

ASSERT
Now that we’ve done the actions needed in the test, what we want is to compare the new state of the Game, with what we expect to happen. We write what we expect to happen in the third part of the test file:

[ASSERT]
FIRSTMAIN
[PLAYER1]
inplay:Ancestor’s Chosen
life:23
graveyard:swamp,grizzly bears,dragon engine
manapool:{0}
[PLAYER2]
graveyard:black knight
[END]

So, if you compare this to the initial state we described above, the differences are the following: Ancestor’s Chosen is in play, player 1 has no more left mana in his manapool, and he has 23 life (initial life of player 1 wasn’t described in the initial state. In that case the game uses the default value of 20).

Now, this is what the test expects to happen. The testing suite will of course compare this to the actual state of the game. If the expected and the actual states are not equivalent, then the test fails and the program lets me know about the error.

Here is the full test file for Ancestor’s Chosen:

#Testing Ancestors chosen
[INIT]
FIRSTMAIN
[PLAYER1]
hand:Ancestor’s Chosen
graveyard:swamp,grizzly bears,dragon engine
manapool:{5}{W}{W}
[PLAYER2]
graveyard:black knight
[DO]
Ancestor’s Chosen
[ASSERT]
FIRSTMAIN
[PLAYER1]
inplay:Ancestor’s Chosen
life:23
graveyard:swamp,grizzly bears,dragon engine
manapool:{0}
[PLAYER2]
graveyard:black knight
[END]

Getting Stuff Done

Today I’m just going to talk about “getting stuff done.” MTG Forge was completed not because it was a work of art but because I was willing to use duct tape and “get it done.”

Magic is a wonderful game that seems to attract its fair share of programmers but very few programs ever get finished enough to be useable. Part of this problem is that people try to add too much stuff and get overwhelmed. I didn’t have this problem with MTG Forge version 1 but I’m definitely having it with version 2. In version 1 I knew that it was going to be not-perfect so I didn’t sweat the details. At first the computer treated all mana costs as colorless. I wasn’t trying to make the computer perfect and later I was able to update the code so the computer would tap the appropriate lands.

I also programmed MTG Forge with only a few of the phases because I didn’t know how to program all of them. While this annoying from the players perspective, it enabled me to work on the rest of the program and get it done. The same thing could be said about the user interface. It isn’t perfect but it has gone through a few upgrades and it looks better. At first the card picture was only displayed on the right and the cards in your hand and on the battlefield were just colored boxes.

Much like writing a paper for school, you just sit done and “get it done” or as we say in the south “git er done.”

p.s. By south I mean the southern USA not South American.

Computer Programming Is Boring

Much of computer programming is as interesting as watching paint dry. Yes, sometimes programming seems like a videogame where you are given constantly evolving challenges and it feels great to conquer them but then programming turns on you and spits out an onslaught of errors.

Last night I changed the zone events. Previously one event handled when a card was added or removed but I split the event into two events, add and remove. This is relatively boring and even last night I wished that I could be programming something fun but the culmination of all of these tiny decisions influences the whole project.

Currently MTG Forge stores all of the decks in one file. This makes reading and writing decks very easy. It also makes uploading and downloading decks harder. It also makes it much harder to download a whole bunch of decks at one time. (Currently MTG Forge does support uploading or downloading individual decks, the deck editor menu calls these operations export and import.) It would also be nice if each deck had an optional comment section that describes the deck but I didn't think about this and MTG Forge doesn't support it.

Computer programming is like building a house of cards, it takes a lot of work and patience. Programming takes a ton of boring code in order to do anything interesting. Programming Magic cards is interesting, programming everything else isn't.

More AI Combat

Recently I’ve been tweaking the AI combat. The problem was that the AI would attack with most or all of his guys and then you would attack and win. The computer wasn’t holding back creatures so it could block and stay alive.

While explaining the problem seems simple, changing the code was a little bit more complicated (as always). The code for attacking and blocking are in two different classes so I had to update the attacking code to check if you, the player, were going to win during your next attack phase. The blocking code didn’t need to be changed because it would automatically block in order to stay alive.

While this does improve the AI a little, it still has a long way to go. The AI still doesn’t correctly block creatures with first or double strike. And the AI doesn’t take into account trample damage, so the AI may block but still lose. The AI may also use activated abilities that tap the creature instead of attacking or blocking with them.

Similar to my previous article about two types of AIs, the same thing applies to combat. One, either you tell the AI which creatures should attack or block. Two, you generate lots of combat situations and you try to find the best one.

It is very hard to code for every combat situation which is option one, so my gut feeling is that option two would be better in the long run. Option two would still work good enough even if it didn’t take into account creature activated abilities, which would greatly simplify the coding.

Programming the AI to not look completely stupid is very hard.

Can This Creature Block?

Just answering the question, "Can this creature block that one?" can be complicated. I created a method called CombatUtil.canBlock(Card a, Card b) which returns true if Card a can block Card b. At first this method was simple because it only checked for fear and flying but this method grew longer as MTG Forge added more cards.

As players we know which creatures can block just by glancing at the board but we forget all of the small nuances such as mountainwalk and fear. The canBlock() method is about 100 lines long and has to check for every possible card that could affect combat.

Specific cards like Amrou Seekers, Skirk Shaman, Goldmeadow Dodger, Juggernaut, and Sunweb each have their own specific code that checks to see if they are in play because they modify which creatures can block them. Juggernaut cannot be blocked by walls and Amrou Seekers can only be blocked by white or artifact creatures.

Other keyword abilities that canBlock() supports is reach, shadow, unblockable, "This creature cannot block", protection from a specific color, and "This creature can block only creatures with flying."

Combat also has another useful method called canDestroyAttacker(Card attacker, Card defending) which return true if the defending card can destroy the attacker card. This method is used by the AI when attacking or blocking. This method takes into account flanking, protection from a specific color, Doran the Siege Tower, first strike, double strike, and deathtouch.

CombatUtil.canBlock() is very important because this enables the user interface to only accept legal blockers. The method canDestroyAttacker() is essential to the combat AI because it lets the AI concentrate on the task of finding the best answer when attacking or blocking.

p.s.
When the comprehensive rules were updated last week Wizards quietly slipped in the new keyword "intimidate" which seems to replace fear in the new set after Magic 2010. Both Amrou Seekers and Skirk Shaman have the same ability as intimidate. The word "evergreen" just means that it is a permanent keyword that will be supported like flying.

702.11
This is intimidate, an evergreen keyword that doesn't quite exist yet. A creature with intimidate can't be blocked except by artifact creatures and/or creatures that share a color with it. It's coming soon, so rather than renumber everything in a few months, it was added in early. (It essentially takes the place of fear, which will remain in place but won't appear on new cards.)

p.p.s.
Make sure to check out the new core set Magic 2010.

Visual Spoiler - official Wizards version with large card pictures
Visual Spoiler - one webpage with all of the card pictures

Quest Mode

I can’t think of anything technical to write about so this is just going to be a fluff piece about MTG Forge’s awesome quest mode. I think of the quest mode as a stripped down version of Shandalar, you start with a few cards and you win more by playing against computer opponents.

MTG Forge is “graphical challenged” so it only uses menus instead of full scale animation like Shandalar. To begin with you pick how many games that you have to win in order to finish the quest and quests vary from 10 (easy) to 40 (very hard).

On paper the quest mode seems almost trivial but it adds a lot of replay value to MTG Forge. The cardpool that you have is always different so this challenges you to use different colors and cards than you normally would. If you were using the constructed mode which has all of the cards you would always select Lightning Bolt over Shock since Lightning Bolt does more damage but in quest mode you would might be forced to use Shock or something even worse.

MTG Forge only has so many cards and the quest mode lets the player experience cards that he normally never would. In essence the quest mode is a “flavor” of Magic much like drafting or sealed deck. I also wanted to mention that the AI decks that you play against in the quest mode are divided into three categories of difficultly so after you win a few games the challenge is increased.

When you start the quest mode you are given 75 cards. At first I wanted to only give the player a smaller cardpool of 50 cards but that seemed a little too restrictive, so I chose 75 because it is the same as sealed deck tournaments. And when you win more cards you only get 12 because I didn’t want to make it too easy.

New Rules

The updated version of the comprehensive rules has been released as well as the faq for Magic 2010.

Article - Mark Gottlieb explains the comprehensive rule changes

Comprehensive Rules - with new rule updates about combat damage and battlefield

Magic 2010 Faq - this is a link to the individual faqs for each Magic set

AI Blocking

Knowing when to block is almost a science and trying to distill those nuggets of knowledge into hard, inflexible code is challenging. The computer will block each attacking creature 50% of the time. (If you have four attacking creatures the computer will usually block two of them.) While this might seem arbitrary it also makes the computer less predictable. (Maybe 50% should be something else like 30% but I really don’t know.)

And finally the bad news, the computer still does a few stupid things. The AI doesn’t take into account activated abilities or a creatures “worth”. The AI sees Royal Assassin, Soul Warden, and Eager Cadet as all the same, just a 1/1 creature. On the bright side the AI does take into account first strike, double strike, deathtouch, and flying. Occasionally, 20% of the time, the computer will block a non-flyer with a flyer or not attack with a creature just to surprise you.

The computer also checks to see if it can win the game by attacking with all of its creatures. I nicknamed this “assault attacking” in my code. The programming is a little tricky because it presumes that the biggest attacking creatures will be chump blocked.

AI Attacking

Combat is at the very center of Magic. Knowing when to attack and block is crucial to every game. Trying to program the AI to intelligently attack and block is very complicated. I have already rewritten the AI combat code once and I spent a few hours last night updating it.

The good news is that the computer now handles combat better. The computer is very aggressive when attacking. The AI code used to never attack with a 2/2 into a 1/4 and now it will. While attacking with just one 2/2 into a 1/4 is still a little stupid, the computer will attack with ALL of its 2/2 creatures if you have a 1/4. The idea is that the computer will still look stupid some of the time but it will improve the computer’s performance most of the time.

The attacking code is simpler than the blocking code because there are a variety of reasons to block: chump block to stay alive, trade creatures, bigger – block a 2/2 with a 3/3, shield – block a 2/2 with a 1/4, or have multiple blocker destroy a big creature.

I’ll talk about blocking next time.

p.s.
This post is comments on my post, "Two Kinds of AI" which is written by somebody who has more experience programming AIs than I do.

Videogame - Plants vs Zombies

I have to tell you about this casual, strategy videogame that enthralled me for six hours this week. PopCap’s Plants vs. Zombies pits you against a horde of zombies that are trying to reach your house and eat your brain. Your goal is to use a variety of plants, aka cannons, to destroy the zombies. There are a variety of plants that you can use with a total of 49.

The zombies also come in 26 different varieties such as zombie quarterback, cone on head (tougher than your average zombie), or my favorite the Michael Jackson, thriller zombie that sports a flashy red jacket and summons backup dancers. The difficulty starts easy and then slowly keeps pushing you. Each level is beautifully designed. As a fellow programmer I can tell the A LOT of time went into this videogame.

Plants vs Zombies Homepage

Two Kinds of AI

Let me briefly describe two different ways to program a Magic AI.

One, the programmer specifies all of the scenarios in which the computer would play Giant Growth. Two, the programmer lets the computer evaluate the outcome of using various cards, this is very flexible when compared to option one. Option one is hard to implement because each scenario has to be specified while option two requires more planning and coding. (Option two would use an algorithm like min-max or alpha-beta.)

MTG Forge uses option one and Wizard’s new Xbox game uses option two. In MTG Forge each card has around 4-10 lines of code that tells the computer if the card should be played. Below is an example of the code from Shatter. The computer will only play it if you, the opponent, have an artifact and it is turn 5 or latter. The idea behind playing Shatter after turn 5 is that hopefully it will destroy something really good instead of a cheap artifact.

public boolean canPlayAI()
{
  return (getArtifact().size() != 0) && (AllZone.Phase.getTurn() > 4);
}

The code for Dark Banishing just verifies that you have a non-black creature in play. The method getNonBlackCreature() returns the biggest non-black creature.

public boolean canPlayAI()
{
  check = getNonBlackCreature();
  return check != null;
}

So you see that in MTG Forge each card has a little bit of AI logic programmed into every card. The AI can't use card combinations effectively because each card is programmed separately. Likewise the computer doesn't know that it should use both of its Shocks to win the game if you at are 4 life, because each the AI isn't that smart.

And while MTG Forge's AI is very basic, I still attest to the fact that it is very fun.

p.s.
The lines between the two types of AI's can be blurred. I can envision an AI that could be optimized for a specific deck such as white weenie. The AI would be hardcoded to play cards in a certain order but would also be able to "look ahead". The evaluation function for the look ahead code could be optimized especially for white weenie. This same idea could also be applied to combo decks.