COMP 3200 - Intro to Artificial Intelligence - Lecture 10 - MiniMax Search Enhancements

Overview

Dave Churchill explains how to strengthen minimax and alpha-beta game players through better evaluation, search strategies, and implementation techniques. The lecture distinguishes exact terminal scores from heuristic non-terminal evaluations, then covers tie-breaking, depth parity, move ordering, selective extensions, state undo, bitboards, transposition tables, and Zobrist hashing, including a reported transposition-table result that searched to depth 27 instead of 13 within the same 300,000-node budget.

Key takeaways

Terminal outcomes should use exact scores, while depth-limited non-terminal boards need heuristics; in Connect Four, Churchill's example uses +10,000 for a win, -10,000 for a loss, and 0 for a draw.
Adding the turn number as a tie-break makes a game-playing agent prefer faster wins and later losses, avoiding pointless delays or premature resignation when primary scores are equal.
Connect Four search can replace costly deep copies with do_action/undo_action because each move can be reversed by removing the top piece from its column; Churchill estimates roughly a 50-fold speedup.
Move ordering improves alpha-beta only when promising actions are searched early enough to establish useful bounds, so its actual effect should be tested against a version without ordering.
Transposition tables cache information for repeated board states; in the cited 300,000-node comparison, they increased completed search depth from 13 to 27.
Zobrist hashing supports fast transposition lookup by XORing random piece-square values, with incremental XOR updates when pieces are added, removed, or moved.

Chapters

0:00 Lecture Roadmap, AI Resources, and Actions Versus Moves

Dave Churchill recommends Sebastian Lague's Coding Adventures material and the Chess Programming Wiki as optional resources on game search.
In AI terminology, an action and a move are often interchangeable, but a turn in games such as Magic: The Gathering can contain several ordered actions.

3:17 Exact Terminal Scores Versus Heuristic Evaluations

Terminal states have no legal moves remaining, such as checkmate, a Connect Four win, or a full-board draw, so their outcomes can be scored exactly.
A non-terminal evaluation estimates advantage before the game ends, often because a time or depth limit prevents searching to a terminal state.
A chess material count can be misleading: a player with more piece value may still be checkmated.
Monte Carlo tree search can estimate a position by running random playouts, for example 10,000 games and comparing win rates.

10:16 Connect Four Evaluation and Maximizing-Player Perspective

Evaluation scores should always be calculated from the maximizing player's perspective, so a position scored +100 for one side is -100 for the other.
Connect Four's winner check distinguishes player one, player two, a draw, and player none, where player none means the game is still active.
The assignment evaluation returns a large positive value such as 10,000 for a win, -10,000 for a loss, and 0 for a draw, then calls a heuristic for non-terminal boards.
Alpha-beta search evaluates a state when it is terminal or when the current iterative-deepening depth limit has been reached.

16:22 Implementation Speedups Versus Search Enhancements

Implementation efficiency makes each node cheaper to process, while theoretical enhancements such as alpha-beta reduce how many nodes need searching.
A faster implementation may search deeper in the same time, but a theoretical improvement can deliver much larger savings, including exponential reductions.
Dave Churchill uses Sebastian Lague's chess-engine progression to show how individually modest enhancements can combine into substantial playing-strength gains.

20:23 Tie-Breaking Scores Prefer Faster Wins and Later Losses

When every line appears to win or lose, equal scores can make an agent choose poorly because it sees no difference between outcomes.
Subtract the turn number from a winning score to prefer an earlier win, and add it to a losing score to delay defeat.
A second tie-break field, such as turn number, can be compared only when the primary evaluation scores match.
Churchill recommends tie-breaking for the Connect Four assignment because some provided tests may expose agents that fail to choose an immediate win.

26:12 Search-Depth Parity and Optimistic Horizon Effects

With the maximizing player at depth zero, maximizing moves occur at even depths and minimizing moves at odd depths.
Stopping after a maximizing move can overrate a position because the search has not yet considered the opponent's response.
A depth-12 search can sometimes play worse than depth 11 if the extra ply changes which side made the last move before evaluation.
Churchill suggests experimentally comparing odd-depth searches or increasing iterative-deepening depth by two rather than assuming every additional ply improves results.

30:03 Why Recursive Minimax State Copies Prevent Corruption

In JavaScript, game-state objects are passed by reference, so applying a child action can also alter the parent state.
Without isolation, recursive search may return to a loop whose next action is applied to a board already changed by a previous branch.
A deep copy of the state before each action preserves the parent board, but copying large arrays and heap-allocated data can be expensive.

34:30 Connect Four Undo Moves to Avoid Expensive Copies

Connect Four can avoid child-state copies because undoing a move means removing the top piece from the selected column.
Search can apply an action, recurse on the same board, and call undo_action before trying the next legal action.
Churchill estimates undo-based search can run about 50 times faster than copying states in this assignment.
Undo is harder in chess because reversing a move may require restoring a captured piece and other prior state.

38:03 Move Ordering Gives Alpha-Beta Better Pruning Opportunities

Minimax considers every legal action, but alpha-beta can prune branches once bounds show they cannot affect the result.
Searching promising moves first can establish stronger alpha or beta bounds sooner and trigger more cutoffs.
Move ordering is heuristic rather than guaranteed, so Churchill recommends keeping versions with the feature on and off and comparing them experimentally.

40:17 Selective Search Extensions for Critical Moves

Ordinary minimax searches every action to the same depth, although some positions are more strategically significant than others.
A chess engine can extend the search after a checking move, while a Connect Four engine might extend lines that create or face three-in-a-row threats.
Adding depth selectively can reveal tactical consequences, but extensions are a possible enhancement rather than a guaranteed improvement.

42:15 Bitwise AND, OR, XOR, Shifts, and Negation

Bitwise AND, OR, and XOR operate on corresponding bits of integer values, and processors perform these operations very quickly.
XOR returns 1 when two bits differ and 0 when they match; bit shifts move bits left or right, while negation flips each bit.
The lecture presents bit operations as optional low-level optimization material, not a requirement for the Connect Four assignment.

46:21 Bit Sets Encode Collections in a Single Integer

A bit set uses each bit as a Boolean membership flag, allowing a set such as {1, 4, 6, 7, 8, 12, 14} to fit in one integer.
Bitwise AND tests membership or computes an intersection, OR computes a union or adds elements, and AND with a negated mask removes an element.
Bit sets are compact and fast, but their finite number of bits limits which element indices they can represent.

52:21 XOR Reversibility and Single-Drive RAID Parity

XOR with zero leaves a value unchanged, and XORing a value with itself produces zero, so repeated matching values cancel.
A parity drive can store the XOR of corresponding bits across data drives, allowing the contents of any one failed drive to be reconstructed.
The single-XOR-disk method illustrates one-drive redundancy; supporting two failed drives requires more than simply adding a second XOR copy.

57:42 Chess Bitboards Turn Board Operations into Bitwise Masks

An 8 by 8 chessboard has 64 squares, so a 64-bit integer can encode square occupancy as one bit per square.
A full chess position can use 12 bitboards, one for each piece type and color, with OR combining them into occupancy masks.
A queen's attack mask can be intersected with an opponent's occupancy bitboard to find attacked pieces without scanning board cells in multiple directions.
Bitboards can make chess operations thousands of times faster than iterating over array cells, though Churchill does not recommend implementing them for the JavaScript assignment.

1:03:34 Transposition Tables Reuse Search Results Across Paths

A transposition occurs when different move sequences reach the same game state, causing ordinary search to recompute the same subtree.
Iterative deepening also revisits states at successive depths, creating opportunities for a table to reuse evaluations, best moves, depth information, and alpha-beta bounds.
In a cited experiment capped at about 300,000 nodes, a search without transpositions reached depth 13, while one with a transposition table reached depth 27.
Churchill identifies alpha-beta and transposition tables as especially valuable minimax enhancements, with tables potentially saving an exponential amount of computation.

1:12:18 Zobrist Hashing Builds Incremental Game-State Keys

A transposition table needs a hash key that maps each board configuration to an integer index.
Zobrist hashing assigns random values to each possible piece, color, and square, then XORs the values for pieces currently on the board.
Because XOR is reversible, adding or removing a piece updates the hash with one XOR, and moving a piece removes its old-square value and adds its new-square value.
A 64-bit hash can collide because there may be more possible board states than hash values, but collisions are unlikely in practice with suitable random values.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Dave Churchill.