MINIMAX Tree

Game playing has been a major topic of AI since the very beginning. Beside the attraction of the topic to people, it is also because its close relation to "intelligence", and its well-defined states and rules.

The most common used AI technique in game is search. In some other problem-solving activities, state change is solely caused by the action of the system itself. However, in multi-player games, states also depend on the actions of other players (systems) who usually have different goals.

A special situation that has been studied most is two-person zero-sum game, where the two players have exactly opposite goals, that is, each state can be evaluated by a score from one player's viewpoint, and the other's viewpoint is exactly the opposite. This type of game is common, and easy to analyze, though not all competitions are zero-sum!

There are perfect information games (such as Chess and Go) and imperfect information games (such as Bridge and games where dice are used). Given sufficient time and space, usually an optimum solution can be obtained for the former by exhaustive search, though not for the latter. However, for most interesting games, such a solution is usually too inefficient to be practically used.

MINIMAX TREE:

            The minimax search procedureis a depth-first, depth-limited search procedure. The idea is to start at the current position and use the plausible-move generator to generate the set of possible successor positions. Now we can apply the static evaluation function to those positions and simply choose the best one. After doing so, we can back that value up to the starting position to represent our evaluation of it. The starting position is exactly as good for us as the position generated by the best move we can make next. Here we assume that the static evaluation function returns large values to indicate good situations for us, so our goal is to maximize the value of the static evaluation function of the next board position.

ALGORITHM: MINIMAX(Position, Depth, player)

1.       If DEEP-ENOUGH(Position, Depth), then return the structure

         VALUE=STATIC (Position, Player);

          PATH=nil

This indicates that there is no path from this node and that its value is that determined by the static evaluation function.

2.       Otherwise, generate one more play of the tree by calling the function MOVE-GEN (Position, Player) and setting SUCCESSORS to the list it returns.

3.       If SUCCESSORS is empty, then there are no moves to be made, so return the same structure that would have been returned if DEEP-ENOUGH had returned true.

4.       If SUCCESSORS is not empty, then examine each element in turn and keep track of the best one. This is done as follows;

Initialize BEST-SCORE to the minimum value that STATIC can return. It will be updated to reflect the best score that can be achieved by an element of SUCCESSORS.

For each element SUCC of SUCCESSORS, do the following:

a)      Set RESULT-SUCC to

     MINIMAX(SUCC, Depth+1, OPPOSITE(Player))ᶟ

 This recursive call to MINIMAX will actually carry out the exploration of SUCC.

b)      Set NEW-VALUE to –VALUE (RESULT-SUCC). This will cause it to reflect the merits of the position from the opposite perspective from that of the next lower level.

c)       If NEW-VALUE>BEST-SCORE, then we have found a successor that is better than any that have been examined so far. Record this by doing the following:

                                                              i.            Set BEST-SCORE to NEW-VALUE.

                                                            ii.            The best known path is now from CURRENT to SUCC and then on to the appropriate path down from SUCC as determined by the recursive call to MINIMAX. So set BEST-PATH to the result of attaching SUCC to the front of PATH(RESULT-SUCC).

5.       Now that all the successors have been examined, we know the value of Position as well as which path to take from it. So return the structure

     VALUE=BEST-SCORE

PATH=BEST-PATH

When the initial call to MINIMAX returns, the best move from CURRENT is the first element on PATH.

EXAMPLE:

                      It assumes a static evaluation function that returns values ranging from -10 to 10, with 10 indicating a win for us, -10 a win for the opponent and 0 an even match. Since our goal is to maximize the value of the heuristic function, we choose to move to B. Backing B’s value up to A, we can conclude that A’.

 

 

STEP 2:

 

STEP 3:

STEP 4:

 

Likewise

STEP 5:

The best path is