Game Tree
Min-Max Algorithm

Game Tree

Suppose we have a two-player game in which each player takes turn making his/her move.   We assume that the game will always terminate in a draw, win, or loss.  We can conceptualize the game as a tree consisting of all the possible "game board" configurations with the initial configuration as a root node.  Each node in the game tree corresponds to a possible configuration of the game.  A leaf node corresponds to an end game configuration: a win, loss, or draw.

For the sake of definiteness, assume the players are John and Mary.  We can imagine when John is to make a move, he will move to a game node that is best for him.   What's best for John is based on some numerical value that he associates with each of next possible moves.  How are the value of each of the game node calculated?   Here is one such possible computation.

Min-Max Algorithm

For each of the leaf node, John can assign a value of 1 if he wins, 0 if he ties, and -1 if he loses.  Conceptually, John defines a "pay-off" function P as follows:

P (leaf) =

• 1 if John wins
• 0 if John ties
• -1 if John loses.

Now, John assigns a value to a non-leaf node X, as follows:

V (X) =

• max {V (c) | c is a child node of X} if John moves next.
• min {V (c) | c is a child node of X} if Mary moves next.

The heuristic here is that John would make a move to a node that has the maximum value for him, and Mary would do her best by going for the node that has the minimum value (from John's perspective).  This game configuration computation is called the min-max strategy.  In general, it is not possible to get to all leaf nodes of a game.   The best one can do is to examine the game tree up to certain depth.  The min-max strategy can be recasted in the form described in the next section.

Modified Min-Max Algorithm

Instead of flip-flopping between max and min as described in the above, we can reformulate the min-max strategy based on the simple mathematical formula

max (a, b) = - min (-a, -b).

Let

• E (n) be a pay-off function that John uses to evaluate a game node n.
• e (n) =
  • E (n) if n is node from which John is to make the next move
  • -E(n) if Mary is to make the next move.
• ModMinMax (x) =
  • e (x), if x is a leaf of  the game subtree generated
  • max (-ModMinMax (c)), if x is not a leaf of  the game subtree generated, and c ranges over all the (immediate) children nodes of x.

Given x, a game node (i.e. board configuration), and d, the number of lookahead moves from x, compute the value of x based on the min-max formula.

int ModMinMax (GameNode x, int d)

{

• if x is leaf node or d == 0, return e (x);
• else
  • ans = -ModMinMax (c[0], d - 1) // c[0] is the first child node of x.
  • for (int i = 1; i < number of children nodes of x; i++)
    • temp = -ModMinMax (c[i], d - 1);
    • if ans < temp then ans = temp;
  • return ans;

}