Monday, November 30, 2009

Shock and Royal Assassin – Part 1

When I first started working on Forge, I could only find two other Magic programs Firemox and Magma. Now there are programs such as Incantus, MagicWars, and Wagic which were inspired by this blog. (On a side note Incantus, MagicWars, and Firemox are like Magic Online and let you play against other people on the Internet with rules enforcement. Wagic and Magma let you play against the computer.)

All of these Magic programs, including my own (Forge), encode cards differently. Today I’m going to show how Forge and Wagic encode two familiar cards: Shock and Royal Assassin. Forge takes the direct route and shoehorns cards into Java while Wagic uses its own scripting language which is very short and concise.

Of the five programs mentioned I believe that Forge’s cards are the longest and Wagic’s are the shortest. Having short cards is a big advantage since it means less code is required for each card and hopefully less debugging. In Forge if you wanted to change the damage code, you would have to update each card that dealt damage, while Wagic would only have to tweak the damage code that is used for all the cards, which is a big improvement.

(This is a contrived example but it is generally true. Cards in Forge always a global static method to deal damage, so the damage code could be updated easily but other aspects of cards such as targeting do not always use a global static method.)

On a side note, usually Forge’s cards are very long but I forgot about the scripting code that people like Rob Cashwalker has been writing. (Since Forge is an open source project, letting other people do some of the “hard stuff” is truly wonderful.) Forge’s Shock is only 5 lines, which is great, and probably wins the title of “shortest Shock code”. So in reality some of Forge’s cards are very long like Royal Assassin and some of the cards are very short like Shock.

Wagic – Royal Assassin
[card]
text={T}: Destroy target tapped creature.
id=129708
auto={T}:destroy target(creature[tapped])
name=Royal Assassin
rarity=R
type=Creature
mana={1}{B}{B}
power=1
subtype=Human Assassin
toughness=1
[/card]

Wagic – Shock
[card]
text=Shock deals 2 damage to target creature or player.
target=creature,player
auto=Damage:2
id=129732
name=Shock
rarity=C
type=Instant
mana={R}
[/card]
Forge - Shock
Shock
R
Instant
no text
spDamageCP:2

Forge – Royal Assassin
if(cardName.equals("Royal Assassin"))
{
final Ability_Tap ability = new Ability_Tap(card)
{

public boolean canPlayAI()
{
CardList human =
CardFactoryUtil.AI_getHumanCreature(card, true);
human = human.filter(new CardListFilter()
{
public boolean addCard(Card c)
{return c.isTapped();}
});

CardListUtil.sortAttack(human);
CardListUtil.sortFlying(human);

if(0 < human.size())
setTargetCard(human.get(0));

return 0 < human.size();
}
public void resolve()
{
Card c = getTargetCard();

if(AllZone.GameAction.isCardInPlay(c) &&
c.isTapped() && CardFactoryUtil.canTarget(card, c) )
{
AllZone.GameAction.destroy(c);
}
}//resolve()
};//SpellAbility

Input target = new Input()
{
public void showMessage()
{
AllZone.Display.showMessage("Select
target tapped creature to destroy");
ButtonUtil.enableOnlyCancel();
}
public void selectButtonCancel() {stop();}
public void selectCard(Card c, PlayerZone zone)
{
if(!CardFactoryUtil.canTarget(card, c)){
AllZone.Display.showMessage(
"Cannot target this card (Shroud? Protection?).");
}
else if(c.isCreature() &&
zone.is(Constant.Zone.Play) && c.isTapped())
{
//tap ability
card.tap();

ability.setTargetCard(c);
AllZone.Stack.add(ability);
stop();
}
}//selectCard()
};//Input

card.addSpellAbility(ability);
ability.setDescription("tap: Destroy target
tapped creature.");
ability.setBeforePayMana(target);
}

Friday, November 27, 2009

Forge is the new official name

The name "MTG Forge" appears to attract Wizard's lawyers like flies to Aunt's Mays apple pie. Having the initials "mtg" seems to be the reason for the cease and desist letter about my original Sourceforge.net site. The name "Forge" sounds a little weird and empty to me but it is good enough. (And everybody by now should know that I am a firm believer in “good enough”.) The official name of this project is "Forge" and my official nickname is "mtgrares".

I tried calling myself forge but it is a little bit confusing having the same name for both a person and a project.

Wednesday, November 25, 2009

Forge's Architecture

The architecture for a computer program is very important since everything else in that program relies on it. Computer architecture is very similar to constructing a physical building. The program's architecture is the concrete foundation that you build on. If the foundation is cracked or broken, then you have a BIG problem. (I hope you understand that a program's architecture is very important even though you cannot see it.)

Forge's architecture restricts which cards are supported. Some cards cannot be added because the architecture isn't flexible enough. Cards like planeswalkers aren't really supported but were added by using elaborate hacks. The same thing applies to cards like Hypnotic Specter and Glorious Anthem. Even activated abilities that tap a card like Royal Assassin have to be "hacked" a little.

All of these "little hacks" add up and causes something later that "should work", not to work. Protection was a major update that required all of the targeting code for all of the cards to be changed. I didn't think about protection when I was creating Forge so all of the cards have to be changed one at a time in order to support protection.

Dennis, Rob, Zerker and others from the forums have donated weeks of their time toward Forge. And although I created Forge, these are the guys that keep it going.

Monday, November 23, 2009

Forge Is Not a One Man Project

Sorry for the long title but I couldn't think of a shorter one. The title is trying to say that many people have contributed to Forge. One person improved the card download and added a cool looking progress bar. Another person compiled a list of cards that could be added to "cards.txt". Someone else coded a few new cards.

This is article is also a big THANK YOU for everyone that has contributed to Forge. Forge really is a group project.

To view a complete list of people and their contributions, see the forum here. Below is a summary.

DennisBergkamp - is currently the lead developer and has the unpleasant job of making sure that everything doesn't fall apart. (Everything will fall apart, it is just a matter of when.) This is the guy that rewrote all of Forge's targeting code in order to support protection.

Rob Cashwalker - has transformed cards.txt from a simple file into keyword madness. He spearheaded the movement to add more and more "keywords" like drawing card and dealing damage to cards.txt. One of his earliest contributions was landwalk.

Thanks to Slightlymagic.net and Huggybaby for providing Forge with its very own forum.

Silly Freak created the "resizable game option" which allows Forge to be resized. He also wrote the "central error code" that shows the nice reports as well as divided up Forge's files into convenient directories.

Zerker has done a great job adding the mana pool and other cards.
Nantuko84 gave me the code that shows the card pictures in play as well as added several cards and added filters to the deck editor.

Mr. Chaos was one of my first, exuberant fans that sent me more than enough error reports.

Apthaven helped to spread the word of Forge far and wide as well as posting bug reports.

Chris. H. has done a fantastic job of keeping up all of the rarities for all of the cards in Forge. He is also responsible for playtesting the quest decks and determining the difficultly of a deck. Currently the decks are only divided up into three categories: easy, medium and hard, but three more "wizard" categories are going to be added soon which should make questing more difficult.

The hard thing is that once you start listing people you inevitably leave someone out, so let me say sorry in advance.

All of these people have helped make Forge the superb program that it is today. (These people also deal with all of Forge's inherent problems that I created. Reading someone else's code is like trying to follow a complicated math problem.)

Friday, November 20, 2009

DCMA Google Notice

I just received a e-mail notification from Google, the owner's of blogspot.com, that one of my posts contained an illegal link. The link was obviously to MTG Forge. I presume that this blog won't be shut down but who really knows.

I'll just post updates on Mediafire.com for awhile. This isn't a great way of doing things because MTG Forge will probably be removed from mediafire.com also.

(This is directed toward Wizards of the Coast. I enjoy Magic and I also understand that you own Magic and can do whatever you want to do with it. I also understand that you have been burnt by other computer programs such as Apprentice and Magic Workstation which makes money off of your work.

MTG Forge has about 2,000 cards and is a casual player's dream. Some of these cards are on your restricted list and will never be printed again like Tithe, Sapphire Mox, Timetwister and Wheel of Fortune. Other cards are out-of-print powerhouses like Flamtongue Kavu and Kiki-Jiki, Mirror Breaker. MTG Forge has a few cards that are in Standard such as Wrath of God, planeswalkers, Lightning Bolt and a variety of creatures with a few "vanilla" abilities.

You are not loosing money when people download this program. I officially want to wave the white flag of peace and would enjoy talking to you on the phone. Anyone from a wizards e-mail address can contact me at (mtgrares yahoo com) and I will give you my phone number.)

Improving Min-Max and Alpha-Beta on Wikipedia

Min-max and alpha-beta are both mentioned on Wikipedia but they have horrible, unusable pseudo-code. The book “Algorithms in a Nutshell” has GREAT pseudo-code so I posted it in both of the discussion sections. (I was too afraid of making the changes myself in the main Wikipedia entry.) Below are links for min-max and alpha-beta pseudo-code.

Min-Max
Alpha-Beta

Wednesday, November 18, 2009

Difficult Cards to Program

Magic is great game full of wonderful, complicated cards. Today I'm going to talk about some of the hardest, thorniest cards to implement.

MTG Forge has 2,100 cards so there are plenty of complicated cards to choose from. The planeswalkers stand out in my mind. I had to add an extra combat phase which wasn't too hard (although MTG Forge still suffers from the flaw that if your opponent has two planeswalkers, you can only attack one of them). The planeswalker's abilities were the hardest part because I had to write the code from scratch which involves some very heavy hacking.

Many planeswalkers have rather common effects but Elspeth, Knight-Errant ultimate ability says "For the rest of the game, artifacts, creatures, enchantments, and lands you control are indestructible" which isn't something easy like dealing damage, it generates an ongoing effect. Each of the planeswalkers took about 220 lines.

Both Adarkar Valkyrie and Kiki-Jiki Mirror Breaker both have abilities that copy creatures and each take up about 100 lines of code. Adarkar Valkyrie lets you "steal" a creature if it is put into the graveyard and Kiki-Jiki lets you copy one of your creatures for one turn, then it is sacrificed. Both cards are extremely fun to use because of the broad variety of creatures that have effects when they enter or leave the battlefield. Flametongue Kavu is a perfect example. He is a 4/2 and does 4 damage to one creature when it enters the battlefield. Combine him with Kiki-Jiki to really turn up the heat.

Incendiary Command was very hard to program but the card isn't that useful. It weighs in at around 200 lines. I coded it after my (failed) phone interview with Wizards. The head guy who called himself Elf or something, asked me how I would implement the 5 card cycle of Commands. I answered him then furiously coded Incendiary Command that night.

I eagerly e-mailed him the next day and ... well nothing happened. For some reason I chose Incendiary Command which is the weakest card in the cycle. When I add cards I usually like to get more bang for my buck, like a super big creature or a devastating spell. I wouldn't even pay 25 cents for Incendiary Command, it is a crap rare indeed. I would rather use the cheaper Pyroclasm which only costs 1R and deals 2 damage to each creature.

p.s.
Kiki-Jiki is unusual because it creates tokens that have a name, typically tokens are nameless.

Monday, November 16, 2009

New Version

I'm always happy to announce a new version of MTG Forge. This version has 268 new cards which brings the grand total up to a whopping 2,149. Well kiss my grits, that's alot of cards, oh my!

MTG Forge finally has Pacifism, which is a classic card. White also gets other new creature enchants like Pillory of the Sleepless, Cessation, Nimbus Wings and Bound in Silence. Two other great classics were added: Giant Strength (enchanted creature gets +2/+2) and Rukh Egg, for those crazy, red mages. Feel free to put it into a red and white deck with Wrath of God for some good old-fashioned fun.

For those Johnnies out there, Sunglasses of Urza is calling your name. Those crazy glasses let you spend white mana as though it were red. Some people would argue that Sunglasses of Urza is worthless but hey, MTG Forge has it now so you can burn any copies that you own. The powerful signets from Ravinca are also included. They let you turn 1 mana into 2, which sounds like a pretty good deal to me.

Some of the Zendikar cards which are included are: all 5 Refuge lands (the lands make 2 colors and give you 1 life but enter the battlefield tapped), Umara Raptor and 6 other new ally creatures which get a +1/+1 counter every time you play another ally creature.

This update was written by the great guys from the forum Rob, Dennis, Zerker, and Silly Freak, Chris and Cyclope. They have kindly donated hours of their time (and sanity). Without those guys, none of the "magic" would happen (pun intended, ha).

p.s. This is the same as the 10-18 version that was posted on the forum. (Yes, the forums get all of the new stuff first.)

p.s.s. I did finally update the set editor which is included in the download below. The set editor lets you change the files that are used to generate the booster packs. Booster packs are used for sealed, drafting, and quest. Basically you can add/remove cards or change the rarity. Also note that the booster pack code doesn't support mythic rares.

Download MTG Forge

Friday, November 13, 2009

Min-Max Evaluation Function For Magic

Below is taken from a private forum about a private Magic program that uses min-max for the computer AI. The AI easily out performs MTG Forge's AI and can play instants and abilities during combat. The author's idea was to use an object with different "layers" for the evaluation function instead just number. (I'm sorry for keeping the name of this program private, but that is the author's wishes, not mine.)

Below is copy and pasted from a private discussion. I did not write it. I'm still working on my own version of min-max and Magic.

I got a lot of requests asking me the AI evaluation function in (private Magic program). I will try to explain a little bit of the function here. You may need to have a basic understanding of how Minimax algorithm works first before you can totally understanding how to apply this to your program.

In the very first engine I have created, my evaluation function is very simple. Basically it counts how many cards in-play for the player and combine that with the player's life. Since life is more important than how many cards a player has put in-play, the life total is multiplied. The result is what I called a score and each area contributing to this score is a component. This calculation is also done for the other player and is subtracted. So for example:

Player 1 - 3 in-play cards - 20 life -> 3 + 20 * 100 = 2003
Player 2 - 10 in-play cards - 18 life -> 10 + 18 * 100 = 1810

Score for player 1 at this stage is 2003 - 1810 = 193 (score for player 2 will be -193)

You will be surprised by how Minimax can perform some amazing things with such a simple evaluation function. There are some special cases in the equation I am not mentioning here. These cases are used to handle losing conditions besides a zero or negative life, e.g. draw with no cards in library, losing condition set by a card, etc. In those cases a lowest possible negative number is used for the player's score regardless of other components.

As a side note, if my computer is infinitely fast and can evaluate the whole game from start to finish in a reasonable time, the evaluation function can be as simple as using just players' life total (plus the win/lose special score.) This is because A.I. can foresee all the consequences of each move and number of in-play cards is not needed to make a sensible decision.

Since our computer can only do a limited amount of calculation and MTG is not a simple game like tic-tac-toe, we need to guide the Minimax/alpha-beta algorithm to an approximated score when an end-game state cannot be achieved. The in-play card scoring part in the above example is one of the approximation. Now you can find many example of winning a game without a single card in-play (e.g. using red.) However in a more general sense the player life part of the equation is kind of balancing this out. So either you are putting cards out or reducing your opponent's life. If you are not doing both, you are not in a good position.

After the first version of the evaluation function, I quickly found out that not all cards are equal and I shouldn't give them equal scores. Ideally, if a card's purpose is to reduce an opponent's life and is effective about it (directly or indirectly), the opponent's life decrease should reflect in the evaluation function and so the merit of one card will be obvious against another card which cannot achieve the same thing. However, when there are too many possibilities and time is limited, Minimax may not be able to reach such a conclusion.

At first I tried to give a card more points when it has more abilities and in case of creatures considering their power and toughness. Later I changed to a more generic 'base' score by just looking at a card's casting cost. The calculation is simple, 150 points for colored cost and 100 points for generic cost. This simple calculation can usually account for how powerful a cards is. However if a card has an unreasonable cost, e.g. Black Lotus, this calculation will not give Minimax a good representation of the card. Hopefully in those case the power of the card (or the lack of) will be reflected in other evaluated parts. Besides the base score, a few bonus points will be added for creatures' power and toughness points.

Besides in-play cards, there are points given to cards in hand and library.

I want to get back to the multiplier given to the life component in the above example. When I add more and more components to the score, it becomes easier for components' scores to 'overlap.' In the above example, using a multipier of 100 will not be enough if all the in-play cards' score total is exceeding 100. Once that is happening, Minimax will behave weird and no longer to preserve a player's life but to put more cards on the table!

To create a solution which is once and for all, I have created a separate score class to deal with scores rather than just use a single integer number. Basically the class has multiple layers of sub-scores. Sub-scores in the upper layer are more important than sub-scores in the lower layers. Each sub-score value is by itself an integer which will allow me to have more precision in tinkering. These are the current list of all the sub-scores:

Limits - represents boundary situations, highest significance
Wins - represents win/lose situations
Creatures - a special sub-score to allow a less conservative play in early game situations
Life - represents play life
Library - represents cards in libraries
InPlay - sub-score for in-play cards
InHand - sub-score for hand cards
Misc - minor scores to prevent indecisive situations, lowest significance

Comparisons of two scores is performed by comparing the highest significant sub-scores against each other first. If they are the same, the next lower significant sub-scores are compared and so on.

Wednesday, November 11, 2009

Evolving a Good Evaluation Function for Min-Max

This is very nerdy so feel free to skip this and watch an episode of The Simpsons or even better The Big Bang Theory. I really do think I'm half-Sheldon and half-Leonard, ha. (I promise to write a normal article about MTG Forge next time.)

For my geeky readers, you might want to checkout this article about evolving a good evaluation function. The name of the article is "Bootstrap Learning of Alpha-Beta Evaluation Functions" which refers to the evaluation function that is used for alpha-beta, an optimized version of min-max. (The article uses the Greek symbols alpha and beta.)

I'll try to summarize the article. The min-max algorithm doesn't involve any learning since it uses a static evaluation function and the article proposes the idea that you save the game state tree that is generated and try to evolve a better evaluation function. The idea is to test the evaluation function with the previously generated game tree to see whether the evaluation function made good choices.

(Remember that the goal of the evaluation function is to determine which player is winning and by how much. Usually the evaluation function generates an integer number to represent how much the AI is winning or losing.)

Saving the whole game state tree that alpha-beta creates is difficult. I understand the alpha-beta algorithm but I don't understand it well enough to code it and the alpha-beta code that I have found is recursive, so I don't know how to save the game state tree that is created.

Basically the article is really interesting and has some really good ideas but I'm not sure how to practically use it. (Thinking about AI hurts my brain.)

p.s.
I got my four year bachelor's degree in Information Science but we didn't touch AI. I really need a Master's degree or PhD in order to really understand AI. Anyone willing to foot the bill? :*)

p.p.s.
I found a nice Java implementation of the alpha-beta algorithm in the download section for the book "Algorithms in a Nutshell". You can read more about the book and download the code from here. (To download the Java source code the link is on the left side in small letters, click on "Examples". Now you should see three directories, click on "Releases".)

Or you can download the 10 MB zip file from here.

Monday, November 9, 2009

Why Programming AI is Hard - Part 4

This is the fourth and final part in this series that explains how the min-max algorithm could improve MTG Forge's AI. I'm going to summarize the previous three articles.

AI programming is hard. Actually any computer programming is hard, but AI programming is even harder. I feel that this is important, so I keep emphasizing this point. It is like saying if you know English then you should be able to write a novel or be able to read a medical dictionary. Writing a novel or reading a medical dictionary is a very specialized form of English.

The min-max algorithm works for two player games like chess and should also work for Magic: The Gathering. Actually using min-max in MTG Forge is very hard because of the programming. You have to copy everything and iterate through the each player's actions. Basically the min-max generates future game states and picks the best one. (Instead of copying the game state it would be better to implement an undo system using Command objects. That way you wouldn't have to copy everything.)

The min-max algorithm has to figure out who is winning. The min-max algorithm might generate 1 or 2 moves ahead and then try to determine which player is winning. Determining which player is winning is very complicated and will require much tweaking. Most of the time the min-max algorithm will not be able to generate all future game states because the number of possibilities is astronomical.

Well this ends this series of four articles that examines the question, "Why programming AI is hard?" The min-max algorithm is very important and I'll bore you with more details later. (joke)

Friday, November 6, 2009

Response to Comments

My last post generated a lot of comments and I wanted to address a few of them. Much of MTG Forge contains my “philosophy” of computer programming and Magic. My philosophy is often “if it is good enough, then stop.” Different people have different ideas about what is “good enough” and usually for me “good enough” means what is easiest for me to program. (I always knew that the user interface was going to be very plain at best.)

Many people don’t like the idea that the AI cheats. Of course most of the time people don’t know that the AI really does cheat. If I write and say that MTG Forge’s AI looks at your hand, people would get upset. But if I never tell people, they wouldn’t ever know, so they couldn’t get upset. (And please note that MTG Forge’s AI does not look at your hand because it wouldn’t be helpful.) I try to give users as many options as possible and MTG Forge has the option to smooth the AI’s land but you can also turn that option off.

MTG Forge is really just thousands of little decisions that I and other people had to make. Much like movie reviews where a person watches a movie for two hours and then criticizes it, I (and others) have spent hundreds of hours working on MTG Forge. If something works, like the deck editor, I receive no comments about it but if something is broken, I receive tons. Often I receive more criticism than praise and it doesn’t bother me. People are using MTG Forge and are enjoying a good game of Magic and that was my goal. (Ok, really my goal was for me to enjoy a good game of Magic but I don’t mind sharing.)

All of MTG Forge’s major flaws are a result of decisions that I made, such as the AI isn’t great, you can’t sideboard, and not all of the phases are implemented and I understand how these omissions could be frustrating for other people to understand.

I didn’t want MTG Forge to be a half-written program that never really did anything. Sourceforge.net and other sites have a TON of half-written programs which no one uses. MTG Forge is useable and despite some horrible coding practices like 10,000 line methods and global variables, it is very playable. (I just enjoyed a great 10 game quest last night. Ok, you got me, it was really a 16 game quest because I lost 6 times, ha.)

And to quote myself, MTG Forge is a collection of bugs that happens to play Magic.

p.s. I love the new Zendikar basic lands, they look great.

p.p.s.
Truthfully, I'm a perfectionist and I want everything to be 100% perfect but then I would have never completed MTG Forge. Computer programming (and life) often involve compromises.

Wednesday, November 4, 2009

Why Programming AI is Hard - Part 3

Hopefully you read (or at least glanced) through parts 1 and 2 that talk about how the min-max algorithm can be used to simulate an AI opponent. This article describes some of the problems when using min-max.

In theory min-max can only be used for games that don't have any "hidden information" and in Magic, the cards in your hand and deck are "hidden information". I have no problem with the idea of allowing the min-max algorithm to see all of the cards in you hand and deck. The only possible "problem" that I see is that this might create an AI that is "too good". I seriously doubt this situation would occur because of the complexities of the actual programming.

(Programming is very hard in case you forgot, ha, but you probably didn't forget because you might be a programmer yourself. Programmers have to interface directly with the computer, so technically, programmers aren't human.)

p.s.
In order to use the min-max algorithm you have to be able to generate all possible moves for both players. I could have also said, "In order to use the min-max algorithm you have to generate all possible game states." I didn't use the term "game state" because I didn't want people to geek out and quit reading my blog. :--)

p.p.s.
On a side note, according to Wikipedia there is a variation of min-max that can use probabilities. You could use probabilities instead of taking my suggestion of revealing the hidden information; there is a 20% probability that your opponent is holding Wrath of God in his hand.

Monday, November 2, 2009

Why Programming AI is Hard - Part 2

I'm going to continue my thoughts about the AI algorithm min-max. Previously I said, "In order to use the min-max algorithm you have to be able to generate possible moves for both players."

Ideally you would generate all possible moves for both players until the game ends. Usually generating all possible moves is impossible even for simple games like checkers, so the trick is to use an "evaluation" function that evaluates the game. The evaluation function basically determines which player is winning.

A rough analogy would be a person's life points as a very simple evaluation function. Usually the person with the highest life points is winning, notice that I said "usually". A good evaluation function for Magic would look at both players' life totals, cards in hand and creatures in play to determine which player has the best chance of winning. Needless to say that the evaluation function for Magic would be very complicated considering creatures like Keiga, the Tide Star and Royal Assassin which can win games by themselves.

Creating a good evaluation function is very important. If your evaluation function is lousy, then your AI will be lousy. (There is probably a better word than "lousy" but it conveys the right idea.)

As you may or not remember, the XBox 360 game Duels of the Planeswalkers used min-max. You can read about the AI engine that the game uses here.

p.s.
Technically min-max can only be used for games that don't have any "hidden information" and in Magic, the cards in your hand and deck are "hidden information". Read my *astonishing*, earth-shattering post on Wednesday that solves the hidden information problem.

p.p.s. I just picked Phelddagrif because it had a weird picture.