Scribd
Upload
8 views2 pages

Minimax Algorithm for Game Strategy

The document outlines the Minimax algorithm, which is used in decision-making for two-player games involving MAX and MIN players. It details the functions Minimax-Decision, Max-Value, and Min-Value, explaining how each function evaluates game states and determines optimal moves based on utility values. The algorithm recursively explores possible game states, propagating values up the tree to identify the best action for the MAX player.

Uploaded by

Vali Bhasha
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
8 views2 pages

Minimax Algorithm for Game Strategy

The document outlines the Minimax algorithm, which is used in decision-making for two-player games involving MAX and MIN players. It details the functions Minimax-Decision, Max-Value, and Min-Value, explaining how each function evaluates game states and determines optimal moves based on utility values. The algorithm recursively explores possible game states, propagating values up the tree to identify the best action for the MAX player.

Uploaded by

Vali Bhasha
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

1.

Minimax-Decision(state)

This is the starting point.

 It looks at the current state of the game.


 Calls Max-Value(state) because the top player is usually the MAX player.
 Finds the action from possible moves (SUCCESSORS(state)) that leads to the
best value for MAX.
 Finally, it returns the best action (the move MAX should take).

So this function decides which move MAX should make.

2. Max-Value(state)

This function is called whenever it’s MAX’s turn to play.

Steps:

1. Check if terminal
o If the state is a terminal node (end of the game), return its utility
value (e.g., payoff score).
2. Initialize v
o Start with v = -∞ (worst case for MAX).
3. Loop over successors
o For each action a and resulting state s in SUCCESSORS(state):
 Call Min-Value(s) (because after MAX moves, it’s MIN’s turn).
 Update v = max(v, Min-Value(s)).
4. Return best value
o After checking all possible moves, return the best value MAX can
guarantee.

This ensures MAX chooses the highest payoff possible, assuming MIN plays
optimally.

3. Min-Value(state)
This function is called whenever it’s MIN’s turn to play.

Steps:

1. Check if terminal
o If the state is terminal, return its utility value.
2. Initialize v
o Start with v = +∞ (worst case for MIN).
3. Loop over successors
o For each action a and resulting state s in SUCCESSORS(state):
 Call Max-Value(s) (because after MIN moves, it’s MAX’s turn).
 Update v = min(v, Max-Value(s)).
4. Return best value
o After checking all possible moves, return the lowest value MIN can
enforce.

This ensures MIN chooses the lowest payoff possible, assuming MAX plays
optimally.

4. Flow of the Algorithm

 Start at the root (current game state).


 MAX calls Max-Value.
 Max-Value checks each move, then calls Min-Value for MIN’s response.
 Min-Value checks its moves, then calls Max-Value again, and so on…
 Eventually, the recursion reaches terminal states (leaf nodes) with fixed
payoffs.
 Those payoffs bubble up the tree:
o MIN nodes pass up the minimum value among their children.
o MAX nodes pass up the maximum value among their children.
 Finally, the root gets the best value, and Minimax-Decision chooses the
best move.

You might also like