Evaluating a Game Tree with the Minimax Algorithm

Last updated

Problem Setup

Scenario:MAX must choose between two moves, A and B. After MAX chooses, MIN selects the outcome that gives MAX the lower score.

Given:A game tree with terminal scores at the leaf nodes. The root is a MAX node, A and B are MIN nodes, and C, D, E, and F are MAX nodes. We evaluate the tree from the leaves upward.

Task:Use Minimax to evaluate each branch, pass the resulting values back to the root, and determine which move MAX should choose.

Need a quick refresher? Review Minimax theory

Game Tree

Each leaf shows a possible utility score for MAX. The tree represents the choices available to both players, with higher scores favoring MAX and lower scores favoring MIN.

Root
A
B
C
D
E
F
4
8
2
6
-3
5
9
0
7
3
Want to edit this data in the live solver?

Step-by-Step Resolution

Follow each node's calculation as values are passed back up the tree. The highlighted node shows which result is being evaluated.

1

Evaluating Node: C

Position:Level 2 (Bottom-most evaluating layer)Layer Type:MAX

Initial Value: −∞-\infty
Child Node Evaluations
Evaluated child 4 (returns 4)max(−∞,4)=4max(-\infty, 4) = 4
Evaluated child 8 (returns 8)max(4,8)=8max(4, 8) = 8
Evaluated child 2 (returns 2)max(8,2)=8max(8, 2) = 8
Result: Node C locks in a value of 8.
Global Tree State (Step 1)
Root
A
B
C [8]
D
E
F
4
8
2
6
-3
5
9
0
7
3
2

Evaluating Node: D

Position:Level 2 (Bottom-most evaluating layer)Layer Type:MAX

Initial Value: −∞-\infty
Child Node Evaluations
Evaluated child 6 (returns 6)max(−∞,6)=6max(-\infty, 6) = 6
Evaluated child -3 (returns -3)max(6,−3)=6max(6, -3) = 6
Result: Node D locks in a value of 6.
Global Tree State (Step 2)
Root
A
B
C [8]
D [6]
E
F
4
8
2
6
-3
5
9
0
7
3
3

Evaluating Node: A

Position:Level 1 (Intermediate Layer)Layer Type:MIN

Initial Value: ∞\infty
Child Node Evaluations
Evaluated child C (returns 8)min(∞,8)=8min(\infty, 8) = 8
Evaluated child D (returns 6)min(8,6)=6min(8, 6) = 6
Result: Node A locks in a value of 6.
Global Tree State (Step 3)
Root
A [6]
B
C [8]
D [6]
E
F
4
8
2
6
-3
5
9
0
7
3
4

Evaluating Node: E

Position:Level 2 (Bottom-most evaluating layer)Layer Type:MAX

Initial Value: −∞-\infty
Child Node Evaluations
Evaluated child 5 (returns 5)max(−∞,5)=5max(-\infty, 5) = 5
Evaluated child 9 (returns 9)max(5,9)=9max(5, 9) = 9
Result: Node E locks in a value of 9.
Global Tree State (Step 4)
Root
A [6]
B
C [8]
D [6]
E [9]
F
4
8
2
6
-3
5
9
0
7
3
5

Evaluating Node: F

Position:Level 2 (Bottom-most evaluating layer)Layer Type:MAX

Initial Value: −∞-\infty
Child Node Evaluations
Evaluated child 0 (returns 0)max(−∞,0)=0max(-\infty, 0) = 0
Evaluated child 7 (returns 7)max(0,7)=7max(0, 7) = 7
Evaluated child 3 (returns 3)max(7,3)=7max(7, 3) = 7
Result: Node F locks in a value of 7.
Global Tree State (Step 5)
Root
A [6]
B
C [8]
D [6]
E [9]
F [7]
4
8
2
6
-3
5
9
0
7
3
6

Evaluating Node: B

Position:Level 1 (Intermediate Layer)Layer Type:MIN

Initial Value: ∞\infty
Child Node Evaluations
Evaluated child E (returns 9)min(∞,9)=9min(\infty, 9) = 9
Evaluated child F (returns 7)min(9,7)=7min(9, 7) = 7
Result: Node B locks in a value of 7.
Global Tree State (Step 6)
Root
A [6]
B [7]
C [8]
D [6]
E [9]
F [7]
4
8
2
6
-3
5
9
0
7
3
7

Evaluating Node: Root

Position:Level 0 (Root Node)Layer Type:MAX

Initial Value: −∞-\infty
Child Node Evaluations
Evaluated child A (returns 6)max(−∞,6)=6max(-\infty, 6) = 6
Evaluated child B (returns 7)max(6,7)=7max(6, 7) = 7
Result: Node Root locks in a value of 7.
Global Tree State (Step 7)
Root [7]
A [6]
B [7]
C [8]
D [6]
E [9]
F [7]
4
8
2
6
-3
5
9
0
7
3

Final Answer

The root compares the final values from branches A and B:

max⁡(6,7)=7\max(6, 7) = 7

Optimal move:B

Optimal utility value:7

Choosing B gives MAX a guaranteed utility of 7 under optimal play, even when MIN selects the least favorable outcome. Choosing A would guarantee only 6.

Exam Takeaway

  • Work backward from terminal utilities: Evaluate the deepest internal nodes first, then use their results to calculate the next level. Do not choose a root move simply because one of its leaves has the highest score.
  • Apply the rule of the current node, not its parent: MAX nodes select the highest child value, while MIN nodes select the lowest. A common exam mistake is applying the same operation at every level.
  • The root value assumes optimal play by both players: The final minimax value reflects the outcome MAX can guarantee against an opponent who also chooses optimally. Standard Minimax evaluates every relevant leaf; it does not prune branches.