The Minmax Procedure
The minmax procedure is a recursive procedure that finds an optimal strategy which leads to win state in a given game tree. The minmax procedure takes three parameters, a board position 'Pos' the current depth of the search 'Depth' and the player to move 'P name'. The return value of minimax procedure is a structure containing two components, one the backup value of the path that minimax chooses and the other the path itself. We use two functions VAL( ) and PATH( ) to separate these two components from the return value.
Additionally, the minimax procedure uses the following functions. >
- GENERATOR(Pos, P_name): It is the move generator function that generates all possible moves that player `P_name' can perform from the position 'Pos'. It returns a list of nodes representing the possible moves. .
- EVAL-FUNC(Pos, P_name) : It is the static evaluation function that determines how promising a position 'Pos' is for the player 'P_name'. It returns a number that represents the promising value.
- SUFFICIENT-DEPTH(Pos, Depth): This function determines whether the recursion should be stopped at the position 'Pos' given the depth limit `Depth'..(Since, minimax procedure is a recursive procedure, it should have a mechanism that determines when it should stop the recursion).
This function takes into consideration the following factors to take this decision.
- Has any one player won the game.
- The number of ply that have been explored.
- The promising value of the path.
- The time that is left to complete the game.
- The stability of configuration.
The function SUFFICIENT-DEPTH returns TRUE if recursive search has to be stopped otherwise a FALSE.
Algorithm: Minimax procedure (Pos, Depth, P_name)
STEP 1: If SUFFICIENT-DEPTH (Pos, Depth) is TRUE, then return the structure with its,
Value = EVAL-FUNC (Pos, P_name)
Path = Null.
In other words, in this step, we verify whether we have explored sufficient number of players of the game tree and if so, we call static evaluation function EVAL-FUNC() to calculate the promising value at the position 'Pos'. The variable path is initialized to null.
STEP 2: If SUFFICIENT-DEPTH (Pos, Depth) is FALSE then we call function GENERATOR (Pos, P_name) to generate one more ply of the game tree. The GENERATOR() function returns a list of nodes, we assign this list to a set named SUCCESSORS.
i.e., SUCCESSORS = GENERATOR (Pos, P-name).
STEP 3: If SUCCESSORS is an empty set, then it means there are no more moves. Therefore, we return the same structure as in step 1.
STEP 4: If SUCCESSORS set contains nodes, then we examine each node and keep track of the most promising one, which can be done as follows,
- Initialize the variable 'Promising score' to minimum value that function EVAL-FUNC() can return. This variable will be updated in the later steps.
- For each node 'N' present in SUCCESSORS set, perform the steps (i) through (iii)
- RES-SUCCESSOR = Minimax_Procedure (N, Depth + 1, opposite player's name). This is a recursive call that will perform the further exploration of successor node N.
- Assign, New_Value = VALUE(RES-SUCCESSOR)
- The variable 'New_value' will .now contain the advantage (or merit) of position from the perspective of opposite player for the next lower level.
- New_Value > Promising_score, then it means that we have discovered a successor node (or position) that is better than the nodes examined till now. This successor node is examined as follows,
Promising_score = New_Value
Promising_Path = PATH (RES-SUCCESSOR) + Node 'N'
STEP 5: At this point we have examined all the successor nodes of the game tree.
Therefore, we will return the structure with its components as,
Value = Promising_score.
Path = Promising_Path.
Solving Tic-tac-toe Using Minimax Search: Drawing and analyzing the complete game tree of Tic-tac-toe game is quite complex. Therefore, we will consider a trivial game tree as shown in below Fig
Fig: A trivial Two-ply Game Tree for Tic-tac-toe
In the came tree shown above, the nodes represented by the symbol ⇧ are called as "max nodes", in which it is player Max's turn to move. In the same way, nodes represented by ⇩ symbol are "min nodes", in which player. Min will play. The terminates(leaf) nodes are labeled with utility value (i.e., the final outcome of game that determines win or loss). The other nodes are labeled with their respective minimax values.
The optimal playing strategy can be found by examining the minimax values of each node in the game tree. It is obvious that player max will always prefer to move to a node with maximum value. And on the other hand, player min will try to move to a node having minimum value. Therefore, minimax value of a node 'N' can be defined as,
Minimax-value (N) = Maximum (Successors (N)) if 'N' is a Max node.
= Minimum (Successors (N)) if 'N' is a Min node.
= UTILITY (N) if 'N' is a terminal node.
Node 'Ml' in above figure, has three successors with values 5, 18 and 11. Since, M1 is a min node, it will choose the minimum value i.e., 5 as its minimax value. Similarly, the minimax values of other two nodes i.e., 'M2' and 'M3' will become 5 and 8 respectively.
The root node 'S' has three successors Ml, M2 and M3 with minimax values 5, 5 and 8 respectively. Since, 'S' is a max node it will choose node 'M3' with value 8. Therefore, the minimax value of node 'S' will be '8'.
It is the responsibility of the player to search and examine the game tree and determine the best move.
