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

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.

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.

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)

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.

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.

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.