MINIMAX Procedure Algorithm
MINIMAX PROCEDURE ALGORITHM
Procedure: MINIMAX(node, depth, isMaximizingPlayer)
Step 1:
If the node is a terminal node (i.e., game over) or the specified depth = 0,
Return the heuristic value (evaluation) of that node.
Step 2:
If isMaximizingPlayer = TRUE (MAX's turn), then:
1. Initialize best = -infinity
2. For each child node of the current node:
a. Compute value = MINIMAX(child, depth - 1, FALSE)
b. If value > best, then best = value
3. Return best
Step 3:
Else (isMaximizingPlayer = FALSE, MIN's turn):
1. Initialize best = +infinity
2. For each child node of the current node:
a. Compute value = MINIMAX(child, depth - 1, TRUE)
b. If value < best, then best = value
3. Return best
Step 4:
At the root level, choose the move corresponding to the best value returned.
Explanation Using Tic Tac Toe Example:
Assume:
- Player X = Maximizer (MAX)
- Player O = Minimizer (MIN)
When it's X's turn:
1. Generate all possible moves for X.
2. For each move, recursively call MINIMAX() assuming O plays next.
3. Each terminal board (win/loss/draw) gives a score:
+1 = X wins
-1 = O wins
0 = Draw
4. The algorithm propagates the best score upward:
- MAX selects the maximum value.
- MIN selects the minimum value.
5. Finally, X chooses the move with the highest returned score.
Example Evaluation Table:
| Move (X) | Result (after O plays optimally) | Score |
|-----------|----------------------------------|--------|
| Move 1 | X wins | +1 |
| Move 2 | Draw | 0 |
| Move 3 | O wins | -1 |
Best move = Move 1 (highest score = +1)