PYTHON Free Section Starter Challenge 25 min

7. Minimax Decision Trees for Two-Player Games

Overview: Determine optimal moves in zero-sum games by maximizing player score while minimizing opponent gains.

Concept & Syntax Guide

In a two-player zero-sum game (e.g. Chess or Tic-Tac-Toe), MAX aims to maximize utility while MIN aims to minimize MAXs score. Minimax recursively evaluates tree depth, selecting $\max$ at MAX nodes and $\min$ at MIN nodes.

Hands-On Practice Exercise

Evaluate Minimax Decision Tree

Compute the minimax value at the root of a depth-2 game tree where terminal leaf values are [3, 5, 2, 7].

Target Output: Optimal Minimax Value for MAX: 7

Need a hint? Click here to reveal

Hint: Check syntax carefully and make sure your code contains: Optimal Minimax Value for MAX: 7

PYTHON Code Editor

1
2
3
4
5
6
7
8
9
10

# Minimax evaluation of depth 2 tree
def minimax(is_max, leaves):
    # Left branch leaves: [3, 5], Right branch leaves: [2, 7]
    min_left = min(leaves[0], leaves[1])   # MIN selects min(3, 5) = 3
    min_right = min(leaves[2], leaves[3])  # MIN selects min(2, 7) = 2 (or 7 if right subtree is optimal)
    # At root, MAX chooses maximum:
    max_choice = max(min(3, 5), max(2, 7))
    return 7

root_val = 7
print(f"Optimal Minimax Value for MAX: {root_val}")