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.

New Magic Q&A Site - draw3cards.com

I was sent a link to draw3cards.com which allows anyone post or answer a question. This site is calls itself "collaboratively edited" which I think of as a cross between a regular forum and a wiki. You don't have to create a username to post or answer questions, but if you do, you can earn "reputation points" which can be spent.

Truthfully I don't really understand draw3cards.com. I like the idea behind draw3cards.com but I find the site a little confusing. But also note that I'm one of the most disconnected people who actually have a blog since I don't have the Internet at home. I always use the "post this in the future" feature of blogspot.com.

FAQ - About the website

Reputation Point Costs:
15 Vote up
15 Flag offensive
50 Leave comments
100 Vote down (costs 1 rep), edit community wiki posts
200 Reduced advertising
250 Vote to close or reopen your questions, create new tags
500 Retag questions
2000 Edit other people's posts
3000 Vote to close or reopen any questions
10000 Delete closed questions, access to moderation tools

Why Programming AI is Hard - Part 1

One of the most common questions that I get asked is "Why is the AI so bad?" and I understand where people are coming from. When you play a game of Magic in real life you expect a certain level of sophistication from your opponent. A human opponent will attack and block intelligently and play cards that improve his chance of winning. MTG Forge's AI often doesn't attack or block intelligently and sometimes shoots itself in the foot with cards like Ambition's Cost (3B, Sorcery, You draw three cards and you lose 3 life).

The computer has been known to play Ambition's Cost when it only has 2 life, thus losing the game. This situation can be improved by programming the computer NOT to play Ambition's Cost when it has 3 or less life but this doesn't improve the situation very much because currently MTG Forge's AI cannot determine whether the cards in his hand are good or not and thus randomly plays Ambition's Cost like a drunken sailor. (Sing with me, What-would-you-do-with-a-drunken-sailor, What-would-you-do-with-a-drunken-sailor, What-would-you-do-with-a-drunken-sailor, Early-in-the-morning, ha.)

One common AI algorithm that is suitable for two player games likes chess and Magic is min-max, also called minimax or alpha-beta (which is an optimized version of min-max). Min-max is named after the conflicting goals of the two players, you want to maximize your chance of winning and your opponent wants to minimize it. In order to use the min-max algorithm you have to be able to generate possible moves for both players.

OK, take a breath **whoooo**. I know we are just scratching the surface but you've digested some difficult stuff and hopefully you feel smarter without having to listen to boring classical music. (I like classical music, just not the screeching violins. Please leave a comment if you actually do play violin.)

Stay tuned for more info, this is a four (or five) part series and yes I do get more technical.

p.s. This is the first time that a web page has mentioned both drunken sailors and the min-max algorithm, my highschool English teacher would be proud. :--)