Game Playing and Constraint Satisfaction Problems

Game theory is the mathematical study of strategic interaction between multiple rational decision-makers, where each agent's outcome depends not just on its own action but on the actions of others. This is fundamentally different from single-agent search - there is no single "optimal path," only optimal strategies in light of an opponent's strategy.

Classifying Games

Nash Equilibrium

Worked Example - Prisoner's Dilemma

(Defect, Defect) is the unique Nash equilibrium: given that B defects, A's best response is to also defect (−2 beats −3); symmetric for B. Notably, (Cooperate, Cooperate) would give both players a better outcome (−1,−1) - but it isn't stable, since either player could unilaterally improve by switching to Defect. This famous tension (individually rational ≠ collectively optimal) is a cornerstone result of game theory.

Pure vs. Mixed Strategy Equilibria

Game Theory vs. Classical Adversarial Search

This course's later topics (Minimax, Alpha-Beta) focus specifically on zero-sum, two-player, perfect-information, deterministic games - the simplest, most tractable game-theoretic setting, where Nash equilibrium for one player reduces exactly to the Minimax strategy.

Interview Questions

Minimax is the foundational algorithm for two-player, zero-sum, deterministic, perfect-information games (e.g., Tic-Tac-Toe, Chess, Checkers). It's also implemented in this course's Lab Experiment 7.

Worked Example - Small Game Tree

def minimax(state, depth, maximizing_player):
    if depth == 0 or is_terminal(state):
        return utility(state)

    if maximizing_player:
        best = float('-inf')
        for action in actions(state):
            value = minimax(result(state, action), depth - 1, False)
            best = max(best, value)
        return best
    else:
        best = float('inf')
        for action in actions(state):
            value = minimax(result(state, action), depth - 1, True)
            best = min(best, value)
        return best

def best_move(state):
    return max(actions(state),
               key=lambda a: minimax(result(state, a), depth - 1, False))

Properties

Applications

• Tic-Tac-Toe, Checkers, Chess engines (Lab Experiment 7)
• Any two-player, zero-sum, perfect-information game AI
• Adversarial decision-making in security/game-theoretic simulations

Interview & Exam Questions

Alpha-Beta Pruning computes the exact same result as Minimax, but prunes away branches that provably cannot affect the final decision - dramatically reducing the number of nodes explored without sacrificing optimality.

Step-by-Step Working

1. Initialize α = −∞, β = +∞ at the root.
2. At a MAX node: update α = max(α, child's value) after evaluating each child. If α ≥ β, prune remaining children (β-cutoff).
3. At a MIN node: update β = min(β, child's value) after evaluating each child. If β ≤ α, prune remaining children (α-cutoff).
4. Pass the current (α, β) values down to recursive calls - pruning information flows from ancestors to descendants.
5. Return the same minimax value Minimax would have computed, having explored fewer nodes.

def alphabeta(state, depth, alpha, beta, maximizing_player):
    if depth == 0 or is_terminal(state):
        return utility(state)

    if maximizing_player:
        value = float('-inf')
        for action in actions(state):
            value = max(value, alphabeta(result(state, action), depth-1, alpha, beta, False))
            alpha = max(alpha, value)
            if alpha >= beta:
                break          # β cutoff - prune remaining siblings
        return value
    else:
        value = float('inf')
        for action in actions(state):
            value = min(value, alphabeta(result(state, action), depth-1, alpha, beta, True))
            beta = min(beta, value)
            if beta <= alpha:
                break          # α cutoff - prune remaining siblings
        return value

# initial call: alphabeta(root, max_depth, float('-inf'), float('inf'), True)

Worked Example with Pruning Shown

Move Ordering - Critical for Pruning Efficiency

Best-Case vs Worst-Case Complexity

Properties

Applications

• Chess engines (historically including early IBM Deep Blue) - Lab Experiment 7 of this course
• Any deep adversarial game-tree search where plain Minimax is too slow
• General two-player game AI in commercial games

Interview & Exam Questions

Minimax and Alpha-Beta need a hand-crafted evaluation function and struggle with enormous branching factors (e.g., Go's b≈250). Monte Carlo Tree Search (MCTS) instead estimates the value of moves via repeated random simulation (playouts), requiring no domain-specific evaluation function - this is the technique behind AlphaGo's historic 2016 victory.

The Four Phases of MCTS (repeated every iteration)

1. Selection - starting at the root, recursively select child nodes using a selection policy (typically UCB1/UCT) until a node with unexplored children (or a terminal state) is reached.
2. Expansion - if the selected node is non-terminal and has unexplored actions, add one (or more) new child node(s) to the tree.
3. Simulation (Rollout) - from the newly expanded node, play out the rest of the game using a fast, simple policy (often random moves) until reaching a terminal state.
4. Backpropagation - propagate the simulation's result (win/loss/score) back up through every node visited in this iteration, updating visit counts and win statistics.

UCB1 / UCT - The Selection Formula

w_i/n_i = win ratio (exploitation)  |  N = parent visit count, n_i = child visit count (exploration bonus)  |  C = exploration constant (commonly √2)

function MCTS(root_state, iterations):
    root ← Node(root_state)
    for i in range(iterations):
        node ← root
        # 1. Selection
        while node is fully expanded and not terminal:
            node ← SELECT-UCB1-CHILD(node)
        # 2. Expansion
        if node is not terminal:
            node ← EXPAND(node)               # add one new child
        # 3. Simulation
        result ← RANDOM-ROLLOUT(node.state)
        # 4. Backpropagation
        while node is not null:
            node.visits += 1
            node.wins += result
            node ← node.parent
    return BEST-CHILD(root, criterion="most visited")   # robust choice

Why MCTS Beats Minimax in Large/Complex Games

Properties

Applications

• Go-playing AI (AlphaGo, AlphaZero)
• General game playing competitions
• Real-time strategy game AI
• Resource scheduling and planning under uncertainty

Interview Questions

Minimax and Alpha-Beta assumed deterministic, perfect-information games. Many real games involve chance elements (dice, card draws) or hidden information (opponent's hand) - this topic extends game-tree search to handle both.

Part A: Stochastic Games - Expectimax

Part B: Partially Observable Games

Key Concepts in Imperfect-Information Games

• Information sets - the set of game states a player cannot distinguish between, given what they've observed so far.
• Bluffing - a rational strategy in games like Poker precisely because of hidden information: deliberately misrepresenting one's true state (hand strength) to manipulate the opponent's beliefs.
• Mixed strategies are essential - a deterministic (pure) strategy in an imperfect-information game can often be exploited once the opponent learns the pattern, whereas a well-calibrated randomized strategy cannot.

Comparison Summary

Interview Questions

CSPs are a different - and very powerful - way to frame a search problem: instead of finding a path through a state space, the goal is to find an assignment of values to variables that satisfies all problem-specific constraints.

Classic Example - Map Coloring

Color a map's regions so that no two adjacent regions share a color, using the fewest possible colors. Variables = regions; Domain = {Red, Green, Blue}; Constraints = "adjacent regions must differ."

Types of Constraints

Constraint Graph & Structure

Real-World CSP Examples

• Sudoku - 81 variables (cells), domain {1..9}, ALL-DIFFERENT constraints per row/column/box.
• N-Queens - n variables (one per column, value = row), constraints: no two queens share a row, column, or diagonal.
• Class/Exam Scheduling - variables = courses, domains = time slots, constraints = no professor/room double-booked.
• Cryptarithmetic (e.g., SEND+MORE=MONEY) - variables = letters, domain = digits 0-9, constraints = all-different + arithmetic column sums.

Why CSP Formulation Helps

Unlike general state-space search, CSPs expose problem structure explicitly (which variables interact, and how), enabling powerful domain-independent techniques: constraint propagation (inferring additional restrictions before search even begins), heuristics like Most-Constrained-Variable and Least-Constraining-Value, and graph-structure exploitation (e.g., tree decomposition).

Step-by-Step Working

1. If all variables are assigned consistently, return the assignment as a solution.
2. Select an unassigned variable (using a selection heuristic - see below).
3. For each value in that variable's domain (ordered by a value heuristic):
4. Check if assigning this value is consistent with all constraints involving already-assigned variables.
5. If consistent, assign it and recursively continue to the next variable.
6. If the recursive call fails, undo this assignment ("backtrack") and try the next value.
7. If no value works for this variable, return failure (forcing the parent call to backtrack further).

function BACKTRACKING-SEARCH(csp):
    return BACKTRACK({}, csp)

function BACKTRACK(assignment, csp):
    if assignment is complete: return assignment
    var ← SELECT-UNASSIGNED-VARIABLE(csp, assignment)
    for each value in ORDER-DOMAIN-VALUES(var, assignment, csp):
        if value is consistent with assignment (per csp.CONSTRAINTS):
            add {var = value} to assignment
            inferences ← INFERENCE(csp, var, value)        # e.g., forward checking
            if inferences ≠ failure:
                add inferences to assignment
                result ← BACKTRACK(assignment, csp)
                if result ≠ failure: return result
            remove {var = value} and inferences from assignment   # undo / backtrack
    return failure

Variable & Value Ordering Heuristics

Constraint Propagation: Forward Checking & Arc Consistency

Plain backtracking only checks constraints involving already-assigned variables - it can waste time exploring branches doomed to fail much later. Constraint propagation proactively detects such failures earlier:

• Forward Checking - whenever a variable is assigned, immediately remove inconsistent values from the domains of its unassigned neighbors; if any neighbor's domain becomes empty, backtrack immediately rather than waiting to reach that variable.
• Arc Consistency (AC-3) - a stronger form of propagation: an arc X→Y is consistent if, for every value in X's domain, there exists some compatible value in Y's domain; AC-3 repeatedly enforces this across all arcs until no further domain values can be removed, often dramatically shrinking the search space before any guessing occurs.

Properties

Applications

• Sudoku solvers, N-Queens - common CSP teaching examples
• Class/exam timetabling and resource scheduling
• Compiler register allocation
• Configuration problems (e.g., product/component compatibility)

Interview & Exam Questions

Backtracking builds a solution incrementally, variable by variable. Min-Conflicts takes a completely different approach inspired by Module 2's local search: start with a complete (but possibly invalid) assignment of all variables, then iteratively repair conflicts.

Step-by-Step Working

1. Generate an initial complete assignment (often randomly, or using a greedy heuristic).
2. If the assignment satisfies all constraints, return it as the solution.
3. Otherwise, randomly select any variable involved in a constraint violation.
4. Reassign that variable to the value minimizing the total number of conflicts (ties broken randomly).
5. Repeat from step 2, up to a maximum number of steps.

import random

def min_conflicts(csp, max_steps=10000):
    assignment = {var: random.choice(csp.domains[var]) for var in csp.variables}
    for step in range(max_steps):
        conflicted = [v for v in csp.variables if csp.conflicts(v, assignment) > 0]
        if not conflicted:
            return assignment                       # solution found
        var = random.choice(conflicted)
        # choose value minimizing conflicts for this variable
        best_value = min(csp.domains[var],
                          key=lambda val: csp.conflicts_if(var, val, assignment))
        assignment[var] = best_value
    return None    # failure within step budget

Worked Example - N-Queens with Min-Conflicts

Min-Conflicts is famously effective on N-Queens: starting from a random placement of N queens (one per column), it repeatedly picks a queen under attack and moves it to the row minimizing the number of attacking queens. Remarkably, this solves even the million-queens problem in roughly constant time per queen - a striking contrast to backtracking, which scales poorly for very large N.

Min-Conflicts vs. Backtracking - Comparison

Properties

Applications

• Large-scale scheduling problems (e.g., the Hubble Space Telescope's observation scheduler famously used Min-Conflicts)
• N-Queens and similar large constraint puzzles
• Real-time resource allocation where a fast, "good enough" repair beats slow, perfect search

Interview & Exam Questions