Example
Function Definition
function minimax(node, isMaximizing):
• This function decides the best possible value (or move) from the
current game position.
• Parameters:
• node → current state of the game (like a Tic-Tac-Toe board or a point in a
game tree).
• isMaximizing → whose turn it is:
• True → AI’s turn (the MAX player, wants to maximize the score).
• False → opponent’s turn (the MIN player, wants to minimize the score).
12 November 2025 2
Base Case
if node is terminal:
return utility(node)
• Terminal node = end of the game (no more moves).
• Utility(node) = numerical score representing the outcome:
• +1 if AI wins
• 0 if draw
• −1 if AI loses
• When we reach such a state, we simply return the score — no further moves to
explore.
12 November 2025 3
If It’s the MAX Player’s Turn
if isMaximizing:
bestValue = -infinity
for each child in node:
val = minimax(child, False)
bestValue = max(bestValue, val)
return bestValue
• The AI (MAX) is deciding its best move.
• It tries all possible moves (children nodes).
• For each move:
• It simulates the opponent’s response by calling minimax(child, False).
• It keeps track of the best score among all moves using:
• bestValue = max(bestValue, val)
• When all moves are checked, it returns the highest value — the move leading to the best possible outcome for the
AI.
12 November 2025 4
If It’s the MIN Player’s Turn
else:
bestValue = +infinity
for each child in node:
val = minimax(child, True)
bestValue = min(bestValue, val)
return bestValue
• The opponent (MIN) is now playing.
• The opponent also plays optimally — tries to minimize AI’s chances of
winning.I
• t checks all possible moves and picks the lowest value from its child
states (worst for AI, best for itself).
12 November 2025 5
Example Game Tree
• Let’s consider a small game example where:
• The AI is MAX,The opponent is MIN,Leaf nodes show utility values
(the result of the game).
12 November 2025 6
Step 1
• Evaluate Terminal Nodes
• Leaf nodes have fixed utility values:
3, 5, 2, 9, 1, 4
12 November 2025 7
Step 2
• Evaluate MIN Nodes (Opponent’s turn)
• Each MIN node will choose the minimum of its children:
12 November 2025 8
Step 3
• Evaluate MAX Node (AI’s turn)
• Now the MAX node (A) picks the maximum among its children’s values:
12 November 2025 9
Final Result:
• The AI will choose Node B (left branch) because it leads to a
guaranteed value of 3,
which is the best outcome even if the opponent plays perfectly.
12 November 2025 10
12 November 2025 11
Visualizing the Recursion
• Here’s how the recursive calls happen:
So, the recursive evaluation simulates all future moves and
returns the best guaranteed value.
12 November 2025 12
Summary of Each Step
Final result = 3 → means the AI can guarantee a score of 3 no matter what the opponent does.
12 November 2025 13
Key Takeaways
•Minimax is recursive — explores every possible future move.
•MAX = AI → chooses the maximum value.
•MIN = Opponent → chooses the minimum value.
•Base case = leaf node (game end).
•Result = the best guaranteed outcome for the AI if both play optimally.
12 November 2025 14
Prisoner’s Dellima
12 November 2025 15
Nash Equilibrium
• John F. Nash – Nobel Prize in Economics, 1994.
• Beautiful Mind - 2001 Blockbuster movie
• What is the Nash Equilibrium (NE)?
• Captures a notion of stability – stable outcomes. In what sense “stable”?:
• An outcome is a Nash Equilibrium if no player has an incentive to cheat.
• More precisely, an outcome is a Nash Equilibrium if no player can unilaterally deviate
(from it) and be strictly better-off.
11/12/2025 Abhinay Muthoo, University of Warwick 16