Game Trees

In games of mental skill, like checkers or chess, the computer needs to use certain strategy to make a move. Like a human, the program tries to anticipate what will happen several steps in advance. Such an algorithm is most naturally described in terms of a tree.
1. Game Tree Concept

We can abstract the sequences of possible moves by means of a game tree, where the root denotes the initial state and its branches denote the legal moves the first player can make. At the next level, the nodes signify the second player, and the branches of each node denote the legal moves the second player can make at that situation. The next level nodes signify the first player again and so on. Thus, branches from nodes at even levels ( root is at level 0 ) denote legal moves of the first player and branches from nodes at odd levels denote legal moves of the second player. ( Note that in reality, no tree is actually constructed by the algorithm. The game tree is just an abstract concept. ) A level of the tree is the number of look-ahead moves that the program would make and is sometimes referred to as ply.

The following figure shows the complete game tree for the trivial game of Eight, where the first player chooses a number from the set N = ( 1, 2, 3 ). At next turn the second player chooses another number from N but his number must not be the same as the previous number the first player has chosen and so on. A running sum of the numbers chosen is kept, and whoever first brings the sum to 8 wins the game. If the player takes the sum over 8, then the other player wins. No draws are possible. In the figure, F denotes a win by First Player, and S denotes a win by Second Player.


Figure 1 Game tree of Eight

Even a trivial game like Eight generates a game tree of significant size. Games of real interest like chess and checkers have trees so huge that it is impossible to search all the way to the terminal nodes; a program running in a reasonable time frame can only examine a few levels below the current node of the tree. Humans playing such games are also unable to foresee every possible move to the end of the game. However, they can make intelligent choices based on experiences, recognizing that some situations in a game are much better than others, even if they do not guarantee a win. Therefore, in developing a mental game program, we need some kind of evaluation function that will examine the current situation and return a score that accesses its benefits. In practice, from the point of view of First Player ( assume a female ) we can use a high score to signify favorable conditions for her and a low score ( or more negative ) shows an advantage for Second Player ( male ). In making a decision, while she intends to make a move of highest score, she must assume that her opponent shall make a best subsequent move, i.e. a move that generates the lowest score. This intuition leads to the development of the minimax strategy.

2. Minimax Procedure

Figure 2 shows a hypothetical game tree with scores assigned at leaves ( terminal nodes ). As we are looking ahead, we need the evaluation function only at the leaves of the tree, and the program will make a move based on these values. We start with First Player at the root and examine the whole situation in her perspective. The move the program chooses is a branch coming from the root and the program picks a move to maximize the score in order to minimize mistakes. She also assumes her opponent is as good as her. At the next level down, her opponent selects a move to minimize her score, and so on.


Figure 2 A Game tree with values assigned at leaves

By working up from the bottom of the tree, the program can assign backed-up values to all the nodes. For example, at the right side of Figure 2, the parent of the leaves with score 3 and 8 is at level 3, corresponding to Second Player who moves to minimize the score; so he chooses 3, the minimum of ( 3, 8 ) and we assign score 3 to the node. Its parent, at level 2, corresponding to First Player will choose from ( 3, 12 ) to maximize the score; so she chooses 12 and the program assigns score 12 to the node; the parent of this node again corresponds to Second Player who then chooses 6 from ( 6, 12 ) to minimize the score and so on. The resulted tree is shown in Figure 3


Figure 3 Minimax evaluation of a game tree.

Since we alternately take minima and maxima, this process is called a minimax procedure. In a minimax tree, one can view in its entire form, the score values at each each level of the tree at any instant of the game. A player can find out from the tree which moves are the best. In our example, the current situation has a score of 7. So First Player should choose the leftmost branch which leads to the child with the maximum score.

The minimax procedure can be described by a simple recursive algorithm as shown below.

//node n is the node you want to score int minmax ( Node n ) { if ( n_is_a_leaf ) return score_of_n; else if ( n_is_a_min_node ) { for all children of n: v[0], v[1], ..., v[m-1] return min ( minmax(v[0]), minmax(v[1], ..., minmax(v[m-1]) ); else for all children of n: v[0], v[1], ..., v[m-1] return max ( minmax(v[0]), minmax(v[1], ..., minmax(v[m-1]) ); } }

Unfortunately, the complexity of minimax's is O(bⁿ), where b, the "branching factor" is the degree of the tree, representing the number of legal moves available on average at any instant and n is the tree level representing the number of "plies" you look ahead, where one ply is one move by one side. As such a complexity grows exponentially, it is impractical in most cases to use minmax tree directly to search for a best move in a game of real interest like chess play. Numerous research has been done to make improvement on the searching method. Iterative-deepening Alphabeta, NegaScout and MTD(f) are some of the most successful of these algorithms.

3. NegaMax Search

NegaMax exploits the fact some games like Tic-tac-toe or chess are symmetric between the two players, and therefore the analysis function must give symmetric scoring. The difference between the min and max player mainly consists of the treatment of comparisons. We can start with the max routine, and then switch the evaluation function from one player to the other to reverse the sign of the result obtained from the next lower level. So while your own best move gives you the most positive score, your opponent's best move should give you the most negative score. At any point, First Player score is exactly the negative of the Second Player score ( i.e.the sum of the two scores always equals zero ). For example, in a chess game, if you win a pawn, your opponent loses a pawn. Basically, this algorithm merges the min() and max() functions of minimax into one function. This concept is illustrated in Figure 4. The resulting scores are as they would be if we were to evaluate node values using the minimax algorithm above, and then multiply blue rows by -1.


Figure 4. NegaMax Search Tree

This algorithm can be summarized as follows.

int negaMax ( int player ) { if ( atLeaf ) { //leaf position best_move_score = evaluate ( player ); //static evaluation from // current player's side return best_move_score; //exit condition of algorithm } else { generate ( moves, nMoves ); //generate successor moves best_move_score = -infinity; //preset return value for ( i = 0; i < nMoves; ++i ) { //loop through all moves doMove ( moves[i] ); //execute move move_score = -negaMax ( other(player) ); //set to negative of Opponent's best move score if ( move_score > best_move_score ){ //update best move best_move = moves[i]; best_move_score = move_score; } undoMove ( moves[i] ); //undo move before continuing } return best_move_score; } }

As you can see, the algorithm is recursive. To calculate the score for the current player, you have to first calculate the best score of her opponent's moves. For each of her opponent's moves, you must calculate the best score for the replies to those moves, and so on until the 'leaf' position is reached. To check if 'leaf' has been reached, you can maintain a variable depth, which is set to an initially required value; each time negaMax () is called, depth is decreased by 1; when depth == 0, a leaf position is reached.

The evaluate() function simply returns a score for the current position based on various considerations. For example, in a chess game we can add up the points values for all the current side's pieces, and subtract the points values for the opponent's pieces. This would be a very fast evaluation function, but will play very bad chess as the positions of the pieces have not been considered.

An Example: Tic-tac-toe

We use a simple example, the game of Tic-tac-toe to further illustrate the minimax method. Actually, we'll use the negamax search in our implementation as this game has symmetry between the two players. In Tic-tac-toe, players alternatively put marks in a 3 x 3 array. One marks crosses ( X ), and the other marks circles ( O ). Whoever first fills a row, column or diagonal with her marks wins the game.

Tic-tac-toe is a draw if both sides play optimally. It is not too difficult to analyze all the possible positions, win-lose situations, and save them in a lookup table. We can then write an algorithm to choose a move based on the current position by looking up the table. If this strategy is used, then we require the programmer, rather than the computer to do most of the work and thinking. On the other hand, when we use the minimax strategy to search for the best move, the work is done by the computer. In this example, the static evaluation function that assigns score at the terminal positions ( leaves ) might assign a value of +1 if the computer wins at that position; 0 for a draw; and -1 for losing. As discussed above, a node calculates its score by recursively probing its children until the leaves are reached where the evaluation function can assess a score; the process then reverses and scores are propagating upwards, from children to parents. The following function ticBestMove() shows the computer's strategy. It is a special ( and simple ) implementation of the above negamax search for this particular game. The function is recursive. It exits when the terminal position has been reached. Each successor position is evaluated in turn. If the opponent's response to a move leaves the computer with a more favorable position than that obtained with the previously best computer move, then the bestScore and bestMove are updated. For your convenience, a complete program that makes use of this function to play the game is also shown.

/* tictac.cpp compile: g++ -o tictac tictac.cpp execute: ./tictac player can be 0 or 1, representing the two players. bestMove ranges from 0 to 8, representing the square to be marked */ #include <stdio.h> #define LOSS -1 #define DRAW 0 #define WIN 1 int square[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 }; //the tic-tac-toe board bool isEmpty( int i ); bool mark ( int i, int p ); void unmark ( int i ); bool marked3( int p ); bool fullBoard(); int ticBestMove ( int player, int &bestMove ) { int bestScore, score; if ( fullBoard() ) //terminal position ( full board or 3 marked ) return DRAW; //static evaluation else if ( marked3 ( player )) //row, col or diagonal marked return WIN; //static evaluation else if ( marked3 ( 1 - player )) //row, col or diagonal marked by opponent return LOSS; else { //need to go further down bestScore = LOSS; int not_used; for ( int i = 0; i < 9; i++ ) { //try each square if ( isEmpty ( i ) ) { mark ( i, player ); //execute move /* set to negative of opponent's best move; we only need the returned score; the returned move is irrelevant. */ score = -ticBestMove (1-player, not_used ); if ( score > bestScore ) { bestMove = i; //update best move bestScore = score; //and score } unmark ( i ); //undo the move ( restore board ) } } } return bestScore; } //ticBestMove() bool isEmpty( int i ) { if ( square[i] ) return false; else return true; } bool mark ( int i, int p ) { square[i] = 1 + p * 4; return true; } void unmark ( int i ) { square[i] = 0; } bool fullBoard() { for ( int i = 0; i < 9; ++i ) if ( !square[i] ) return false; return true; } bool marked3( int p ) { int sum = 0, expectedSum, i, j, k; if ( p == 0 ) //player 0 expectedSum = 3; else //player 1 expectedSum = 15; //check row sums for ( i = 0; i < 3; ++i ) { k = i * 3; sum = 0; for ( j = 0; j < 3; ++j ) { sum += square[k]; k++; } if ( sum == expectedSum ) return true; } //check col sums for ( i = 0; i < 3; ++i ) { k = i; sum = 0; for ( j = 0; j < 3; ++j) { sum += square[k]; k += 3; } if ( sum == expectedSum ) return true; } //check diagonal if ( square[0] + square[4] + square[8] == expectedSum ) return true; if ( square[2] + square[4] + square[6] == expectedSum ) return true; return false; } void print_board() { printf("\n"); int k = 0; for ( int i = 0; i < 3; ++i ) { for ( int j = 0; j < 3; ++j ) { if ( square[k] == 1 ) printf( "O\t" ); else if ( square[k] == 5 ) printf( "X\t" ); else printf("\t"); k++; } printf("\n"); } } /* An example of using ticBestMove. The computer is the first player and is player 0. Human is player 1. */ int main() { int move; while ( 1 ) { ticBestMove ( 0, move ); printf("Computer's move: %d\n", move ); mark ( move, 0 ); print_board(); if ( marked3 ( 0 ) ) { printf("\nComputer has won!\n"); return 1; } if ( fullBoard() ){ printf("\nIts a tie\n"); print_board(); return 1; } do { printf("Enter your move ( 0 - 8 ): " ); scanf ( "%d", &move ); if ( move < 0 || move > 8 ) continue; if ( isEmpty( move ) ) { mark ( move, 1 ); print_board(); if ( marked3 ( 1 ) ) { printf("\nYou have won!\n"); return 1; } break; } } while ( 1 ); if ( fullBoard() ){ printf("\nIts a tie\n"); print_board(); return 1; } } }

4. Alpha-Beta Pruning

Minimax or NegaMax searches every reply to every move in the tree. In a game of real interest like chess, an average position consists of about 30 moves. If we search for every move, we could not go too deep. Knuth introduced a technique called alpha-beta pruning to reduce the search tree size by transferring backed-up values from nodes to their successors. The basic idea is "Don't check moves which cannot possibly have an effect on the outcome of your search." The technique is quite easy to understand.

If you have worked your way through the game tree shown in Figure 2 in enough detail, you may have noticed that it is not necessary to obtain the values for all the nodes while making the minimax search as there are some parts of the tree that the best strategy certainly will not consider. Recalling that in the figure, the root and even levels are for MAX and odd levels are for MIN, let us consider an example in which we work our way through the tree starting at our lower left, and filling in the score for a parent node as soon as we have the scores for all its children. After we have done all the nodes in the two main branches on the left, we obtain scores of 7 and 5. As we shall take the max score from all the children, we know that the maximum score will be at least 7. Anything that's smaller than 7 will be discarded. When we go to the next node on level 1 ( the MIN level ) and its left child, we find that the score of this child is 3; at this level, we are taking the minima, so the score of this node ( at level 1 ) cannot be more than 3. Since 3 is less than 7, its parent, the MAX player ( root ) will not consider the score of this node regardless of the score of its right child. Therefore, the subtree shown within the dotted line of Figure 3 need never be evaluated. For the same reason, the other subtree circulated by dotted lines at the right side of the figure do not need to be evaluated either. The process of eliminating branches in this way is generally called alpha-beta pruning. The letters α ( alpha ) and β ( beta ) are in general used to denote cutoff points. The reduction in search effort is achieved by keeping track of bounds on backed-up scores ( scores obtained from children ). In general, as a node's successors are assigned backed-up scores, the alpha/beta bounds can be revised. Note that

1. The alpha values of MAX nodes, including the root, can never decrease.
2. The beta values of MIN nodes can never increase.

Under these constraints, we can discontinue searching the nodes under one of the following conditions.

1. The nodes are successors of any MIN node having a value less than or equal to the alpha value of any of its MAX node ancestors. The final backed-up score of this MIN node can then be set to its beta value. This value may not be the same as that obtained by minimax search, but the final selected results are the same.
2. The nodes are successors of any MAX node having an alpha value greater than or equal to the beta value of any of its MIN node ancestors. The final backed-up score of this MAX node can then be set to its alpha value.

From the nature of the pruning method, we see that the tree is not evolved evenly downward. Instead, the algorithm pursues one branch all the way to the bottom, gets a 'score to beat' (the alpha-beta bounds), and then sweeps across the tree sideways. How well the pruning works depends crucially on move ordering. If the best line of play is searched first, then all other branches will be pruned rapidly. The minimax search with alpha-beta pruning can be summarized as follows.

int alpha = -infinity, beta=infinity; int AlphaBetaMiniMax ( Node node, int depth, int alpha, int beta ) { if ( depth == 0 ) { //leaf position best_score = static_score ( node ); //evaluate current player return best_score; //exit condition of algorithm } else { if ( node == max_node ) { //MAX node for ( i = 0; i < nChildren; ++i ) { //scan all children alpha = max ( alpha, AlphaBetaMiniMax ( child[i], depth-1, alpha, beta ) ); if ( alpha >= beta ) return beta; } return alpha; } else { //MIN node for ( i = 0; i < nChildren; ++i ) { //scan all children beta = min ( beta, AlphaBetaMiniMax ( child[i], depth-1, alpha, beta ) ); if ( alpha >= beta ) return alpha; } return beta; } } }

The corresponding pruning algorithm for negamax search is shown below with more details.

int alpha = -infinity, beta=infinity; int AlphaBetaNega( int position, int player, int depth, int alpha, int beta) { if ( depth == 0 ) { //leaf position best_score = static_score ( position, player );//evaluate current player return best_score; //exit condition of algorithm } else { generate ( moves, nMoves ); //generate successor moves i = 1; while ( i <= nMove && alpha < beta ){ //loop through each move do_move(position, moves[i] ); //execute move //check other player, note alpha, beta positions switched move_score = - AphaBetaNega(position, other ( player ), depth-1, -beta, -alpha) undo_move(position,moves[i]); //undo move before continuing if ( move_score > alpha ) { //compare return value, update if necessary alpha = move_score; //its also the best score so far best_move = moves[i]; } best_score = alpha; ++i; } return best_score; }

The following shows the corresponding α-β pruning implementation of the tic-tac-toe game.

/* Similar to ticBestMove() but performs alpha-beta pruning. Initially, the calling routine should call with parameters alpha = WIN, beta = LOSS */ int ticBestMoveAlphaBeta ( int player, int &bestMove, int alpha, int beta ) { int bestScore, score; if ( fullBoard() ) return DRAW; //static evaluation else if ( marked3 ( player )) //row, col or diagonal marked return WIN; //static evaluation else if ( marked3 ( 1 - player )) return LOSS; else { bestScore = alpha; int not_used; for ( int i = 0; i < 9 && bestScore < beta; i++ ) { //try each square if ( isEmpty ( i ) ) { mark ( i, player ); //execute move /* set to negative of opponent's best move, we only need the returned score, the returned move is irrelevant. */ score = -ticBestMoveAlphaBeta (1-player, not_used, -beta, -alpha ); if ( score > bestScore ) { bestMove = i; //update best move bestScore = score; //and score } unmark ( i ); //undo the move ( restore board ) } } } return bestScore; }

In more complicated games, programs may try to apply the evaluation function to nonterminal nodes in an attempt to place the best moves early in the search in order to take full advantage of α-β pruning. This could result in more pruning than from a random ordering of the nodes.

The complexity of α-β pruning search is O( N^1/2 ), where N is the size of the full game tree. This is a huge savings and means that searches using α-β can go twice as deep as compared to unpruned tree. This is because the depth of the pruned tree is ~ log ( N^1/2 ) = ( log N ) / 2 as compared to an unpruned tree having depth ~ log N.

In later chapters, we shall discuss employing these techniques to develop a chess program.