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.