Monday, November 9, 2009

The Min-Max Algorithm

I like to say "AI is an interesting topic, as long as you don't have to implement it". I think this is very true, because AI is obviously very interesting, but implementing some "intelligent" algorithm may be anything between annoying, boring, monotonic and challenging, hard.

The Min-Max algorithm builds on this though: Every player takes the move that is the most beneficial to him, and every game state is measurable somehow. The easiest move to measure is one that ends the game: The winning player has a "reward" of 1 (maximum) and the losing player has a reward of -1 (minimum).

You see here the end of a tic tac toe game. Green (and the one yellow) are your (circle's) turns, orange is the opponent.

First, you start building the decision tree from the initial state to the final states. Then, you determine the outcomes of the final states. Most of them are draws in this example, meaning no reward for anybody. Two of them are losses and are assigned rewards of -1.

Now, you go back through the tree to the predecessors of the bottommost states. Since you made the move, you maximize your reward. For example, the maximum reward for the yellow node's predecessor is 0, so that node is assigned 0, too.

The next time, it's your opponent's turn. Stepping up one node again, that node has two predecessors, one with 0 and one with -1. Your opponent minimizes your reward, so the node is assigned the minimum of possible child nodes, -1.

We finally reached the original turn where you have three choices, one leading to a draw and two to a loss. You maximize your own reward and choose the option that leads to a draw, which was the final decision made by the min-max algorithm. At this time you know that the game will be a draw if the opponent has the same thoughts as you. It's tic tac toe after all!

that's the basic thought behind min-max, but i guess you see how this is not applicable to Magic. Check back for the details!

1 comment:

nantuko84 said...

started reading your blog (from the begining till up)

>but i guess you see how this is not applicable to Magic. Check back for the details!

unfortunately, yes
as far as I know such games (as tictactoe) are called games with perfect information
strange that wiki says "In game theory, a game is said to have perfect information if all players know all moves that have taken place." - in Magic you also know all moves that have already taken place. In russia, this article sound much beter ;) I will translate: game is with perfect infromation, if
1. a player's turn are discrete and doesn't depend on such parameters as speed, reaction, etc.
2. at any moment you know everything about game state - all positions and all possible moves in future

as you can see, the second is not the case for magic - you have no info about opponent's hand and both decks, may be also morph

I guess this algorithm should be mixed somehow with probabilities, but this "somehow" scares me

waiting for more articles about min-max ;)