ML Extension 🤖

🎯 Learning Objectives

• Describe reinforcement learning as "learning by trial and error"
• Represent the game state as a tuple of observable features
• Explain the Q-table as a lookup table mapping (state, action) → expected reward
• Trace through one Q-learning update
• Run a basic training loop and observe the agent improve over time

💡 The Big Idea — Annotated Code

import random
from collections import defaultdict

# ── State representation ──
# A tuple of 8 binary features the agent can observe:
def get_state(snake, food):
    hx, hy = snake.body[0]
    dx = snake.dx
    dy = snake.dy
    return (
        int((hx + dx) % GRID_COLS == 0 or (hx + dx) < 0),   # danger ahead?
        int((hx - 1, hy) in snake.body[1:]),                  # danger left?
        int((hx + 1, hy) in snake.body[1:]),                  # danger right?
        int(dx == 1), int(dx == -1),                          # moving right/left?
        int(dy == 1), int(dy == -1),                          # moving down/up?
        int(food.x > hx),                                     # food to the right?
    )

# ── Q-table ──
# Maps (state, action) → expected total reward
# defaultdict means missing keys return 0 automatically
Q = defaultdict(float)   # Q[(state, action)] = value

ACTIONS = [(1,0), (-1,0), (0,1), (0,-1)]   # right, left, down, up

# ── Choose action (ε-greedy) ──
EPSILON = 0.1   # 10% chance of random exploration

def choose_action(state):
    if random.random() < EPSILON:
        return random.choice(ACTIONS)       # explore
    # Exploit: pick action with highest Q-value
    return max(ACTIONS, key=lambda a: Q[(state, a)])

# ── Q-learning update ──
ALPHA = 0.1    # learning rate
GAMMA = 0.9    # discount factor (how much future rewards matter)

def update_q(state, action, reward, next_state):
    best_next = max(Q[(next_state, a)] for a in ACTIONS)
    # Bellman equation:
    Q[(state, action)] += ALPHA * (reward + GAMMA * best_next - Q[(state, action)])

# ── Reward function ──
def get_reward(game, ate_food, died):
    if died:   return -10
    if ate_food: return +10
    # Small positive reward for moving toward food:
    hx, hy = game.snake.body[0]
    dist = abs(hx - game.food.x) + abs(hy - game.food.y)
    return 1 / (dist + 1)

Key concept explanations

• State: a compact description of the world the agent can see. We use 8 binary features — dangers in each direction, current movement direction, food location relative to head.
• Q-table: a dictionary mapping (state, action) pairs to expected future rewards. Initially all zeros; updated as the agent plays.
• ε-greedy: with probability ε, take a random action (explore); otherwise take the best-known action (exploit). Balances learning new strategies vs using what works.
• Bellman equation: the update rule. "The value of (state, action) should equal: immediate reward + discounted value of the best next state."
• Learning rate α: how much to update Q on each step. α=1 = replace old value; α=0 = never learn.
• Discount factor γ: how much future rewards matter. γ=0 = only care about now; γ=1 = care equally about all future steps.

🔢 Activity Answers (Conceptual)

Tier 1 — Check Understanding

Tier 2 — Experiment: Modify EPSILON and observe

Change EPSILON = 0.1 to EPSILON = 0.9 (90% exploration). Observe: the agent takes longer to improve because it rarely uses what it learns. Then try EPSILON = 0.01 (1% exploration). Observe: the agent quickly gets stuck in a local strategy and doesn't explore better options.

Tier 3 — Extend: Add a visual training display

episode = 0
scores = []
while True:   # training loop
    game = Game()
    ep_score = 0
    while game.running:
        state = get_state(game.snake, game.food)
        action = choose_action(state)
        # ... apply action, update, get reward ...
        ep_score = game.score
    scores.append(ep_score)
    episode += 1
    if episode % 100 == 0:
        avg = sum(scores[-100:]) / 100
        print(f"Episode {episode}: avg score = {avg:.1f}")

Tier 4 — Research Extension

Read about Deep Q-Networks (DQN). How do they differ from the tabular Q-table approach? What problem do they solve? Answer: state spaces too large for a table — neural networks approximate Q values.

Reflective Journal — Suggested Strong Answers

⚠️ Common Misconceptions & Facilitation Notes

🗣️ Teaching & Facilitation Notes

Opening hook

"You've all learned to ride a bike by falling off and correcting. Nobody taught you the exact muscle movements — you discovered them through trial and error. Q-learning is the same idea: try, observe the outcome, adjust."

Demonstration-first approach

For most classes, showing a trained agent playing Snake (vs a random agent) is more impactful than coding from scratch. Let students observe the difference, then explain the mechanism.

State design discussion

Before showing the state tuple, ask students: "If you were blindfolded and someone told you information about the snake game, what 5 pieces of information would you want?" This surfaces the state design problem collaboratively.

The Q-table as a spreadsheet

Show the Q-table as a grid (state rows × action columns) with values. At the start: all zeros. After 1000 episodes: high values for safe moves, low/negative for moves toward walls. This visual makes the abstract concept concrete.

CT connection — Abstraction at scale

Managing student expectations

Q-learning on a full 20×15 grid takes thousands of episodes. Students may expect "it just works" after 10 games. Explain the training curve: random → slightly better → much better. A graph of average score per 100 episodes makes progress visible even when individual games look chaotic.

Connection to careers

Game AI, robotics path-planning, recommendation systems (YouTube suggesting videos), and stock trading algorithms all use variants of Q-learning. This is not a toy concept.