Skip to content

Adversarial Search

  1. Sequence of moves to play
  2. Rules that specify possible moves
  3. Rules that specify a payment for each move
  4. Objective is to maximise your payment
  • States
  • Initial state
  • Successor function
  • Terminal test
  • Utility function

Pasted image 20260219172824.png

Minimax

Minimax and Alpha-Beta Pruning

Properties

  • Complete (yes, if the tree is finite)
  • Optimal (Yes, against an optimal opponent)
  • O(b^m) - Time Complexity
  • O(bm) - Depth-first exploration

alpha - The highest score that the computer is currently guaranteed to achieve at the current node or any higher level.

beta - The best score that the minimising player is guaranteed to achieve

  • Good Case (Ordered First): If the best move is analyzed first, the "Beta" value drops (or "Alpha" rises) immediately. This creates a very narrow window, causing almost all subsequent moves to be pruned because they are worse than the one already found.

  • Bad Case (Worst Moves First): If you analyze the worst moves first, the window remains wide open. The algorithm must process every single branch to ensure it hasn't missed a better option, effectively turning Alpha-Beta back into standard Minimax.

with perfect ordering - O(b^m/2)

Normal - T(m) = bT(m-1) Perfect - T(m) = T(m-1) + (b-1)T(m-2)

  • Cutoff instead of Terminal
  • Eval instead of Utility

Evaluation Functions in Tic Tac Toe

f(p) =
- Largest positive number if p is a win for computer - smallest negative number if p is a win for opponent - RCDC - RCDO

function evaluateBoard(board) {
    // 1. Identify all 8 winning lines (3 rows, 3 cols, 2 diags)
    const lines = [
        [0,1,2], [3,4,5], [6,7,8], // Rows
        [0,3,6], [1,4,7], [2,5,8], // Cols
        [0,4,8], [2,4,6]           // Diags
    ];

    let rcdc = 0;
    let rcdo = 0;

    lines.forEach(line => {
        const symbols = line.map(index => board[index]);

        // Computer (X) can win if there are no O's in the line
        if (!symbols.includes('O')) rcdc++; [cite: 396]

        // Opponent (O) can win if there are no X's in the line
        if (!symbols.includes('X')) rcdo++; [cite: 396]
    });

    return rcdc - rcdo; // f(p) [cite: 207]
}

Samuel’s Checker-Playing Program

f(n) = w1f1(n) + w2f2(n) + …

  • K = King advantage
  • M = Man advantage
  • U = Undenied Mobility Advantage

In learning mode

  • A adjusts its coefficients after every move
  • B uses the static utility function
  • If A wins, its function is given to B

Horizon Effect

Solutions

  • Do not cut off search at non-quiescent board positions (check until stable nodes) (Quiescence Search)
  • Search further down selected path to ensure this is the best move

Other Solutions

  • Probabilistic cut of branches (assuming that deeper search wont change the outcome)
  • Openings and Endgames
  • Singular Extensions

Other Games

  • Use Expetiminimax, which introduces a change node
  • Time complexity - O(b^mn^m)

Pasted image 20260219190115.png