COMP 3200 - Intro to Artificial Intelligence - Lecture 12 - Assignment 3

Overview

Dave Churchill reviews COMP 3200 midterm expectations, then explains Assignment 3, a Connect 4 agent built with minimax, alpha-beta pruning, iterative deepening, time and depth limits, and a student-designed evaluation function. He demonstrates the interface and behavioral tests, then walks through the JavaScript game-state and player code, emphasizing a debugging sequence: make plain minimax pass the tests before adding pruning and heuristic evaluation.

Key takeaways

Debug Assignment 3 in stages: get plain minimax to pass the four depth-one-through-four scenarios before adding alpha-beta pruning or a custom heuristic.
Iterative deepening should retain the best action from the last fully completed depth, because a timeout during a deeper iteration makes that iteration's result incomplete.
A zero depth limit means unlimited search depth, while a zero time limit means unlimited search time; at least one limit must be positive to prevent an impractical full-tree search.
The sample Connect 4 heuristic counts unblocked four-cell lines for each player and subtracts the opponent's count, giving the agent a measure of future winning potential without looking ahead.
The evaluation function must score only the state it receives; future move exploration belongs in minimax with alpha-beta, not inside the heuristic.
The game-state API supports safe search through legal-action lists, reversible moves, winner detection, and deep copies that isolate each branch.

Chapters

0:00 Midterm Scope and Exam Logistics

The midterm is scheduled for Tuesday during the normal class period, with the exam room in the Education Building.
Bring a MUN ID and pencil; calculators, phones, smartwatches, headphones, notes, and other electronic devices are prohibited.
The exam covers lecture videos, slides, and assignments through Assignment 3, but this lecture's assignment demo is not itself midterm material.

4:00 Core Algorithms, Pseudocode, and Exam Question Format

The main algorithms to know are general tree or graph search and minimax with alpha-beta pruning.
Questions can include explanations, definitions, calculations, and pseudocode, but there will be no multiple-choice, true-or-false, or JavaScript-specific questions.
Write pseudocode with clear indentation or braces; example calculations and algorithms from lectures are likely exam-question material.

8:00 Exam Length, Layout, and Missed-Midterm Policy

The exam is four questions across four pages, with two or three parts per page, and is designed to take about 30 to 40 minutes for a prepared student.
Read every page before answering to avoid getting stuck on an early question while later questions may jog your memory.
If a student misses the midterm, its weight moves to the final; a poor result after attending may be discussed with Dave Churchill case by case.

12:00 Studying with Slides, Lecture Videos, and Repetition

Review both lecture slides and videos, because diagrams and sparse slides may be explained in detail verbally.
Practice writing general tree-search pseudocode by hand two or three times to strengthen recall and exam readiness.
Attempt every exam question for possible partial credit, and use Discord, direct messages, or office hours to ask for clarification.

19:00 Connect 4 Rules and Legal Column Actions

Assignment 3 uses a seven-column, six-row Connect 4 board, with yellow as player one and red as player two.
An action is an integer identifying a column from 0 through 6; a piece falls to the lowest available row, and a full column is illegal.
A player wins by making four contiguous pieces horizontally, vertically, or diagonally anywhere on the board.

20:00 Board Size, Game Balance, and Player Options

The interface can change board dimensions, but the default 7-by-6 board has strategic properties, including the importance of the center column.
The class will hold an AI competition, not for grades; the winner receives a certificate, and the final competition may use a larger board.
The interface offers human, student alpha-beta, random, and greedy players, each AI exposing a function that accepts a state and returns a column.

24:00 Random and Greedy Baselines for Testing

The random player chooses uniformly from legal actions; a submitted agent should reliably beat it.
The greedy player takes an immediate winning move if one exists and otherwise chooses the first maximum-valued action.
Greedy's leftmost tie-breaking follows from iterating columns in order and updating only when a value is strictly greater.

28:00 Student Agent Time and Depth Limits

Student alpha-beta settings include a time limit in milliseconds and a maximum search depth.
The search stops when either positive limit is reached; setting depth to zero means no depth cap, while setting time to zero means no time cap.
Both limits at zero effectively request a full game-tree search and may hang the browser, so the assignment tests will use at least one positive limit.

32:00 Behavioral Tests for Minimax Search Depths

The interface provides four tests: depth one must take an immediate win, and depth two must block an opponent's immediate win.
At depth three, yellow should choose column 2 or 5 to create a forced win; a shallower search cannot reliably see the outcome.
At depth four, yellow should block either end of red's bottom-row threat to avoid a forced loss.

37:00 Testing Search Behavior Before Heuristics

The four win-and-block scenarios test search correctness independently of a sophisticated evaluation function.
Start with terminal scores of 10,000 for a win, negative 10,000 for a loss, and 0 for a draw, then get plain minimax passing the tests.
Add alpha-beta pruning only after minimax works, since separating the two makes bugs easier to diagnose.

45:00 Evaluation Button and Possible-Connect-Four Heuristic

The Eval button displays the evaluation of each legal successor state, helping diagnose how an evaluation function ranks candidate moves.
The demo heuristic counts each player's remaining four-cell lines that contain no opposing pieces, then subtracts the opponent's count.
On an empty board the counts are equal; placing in the center can block more opponent lines, illustrating how the heuristic encodes strategic potential.

50:00 Assignment Testing and Heuristic Requirements

Test the completed agent against random with a short time limit, such as 300 milliseconds, and a depth limit of zero.
First make the four depth tests pass; only then improve the heuristic, since a strong evaluation cannot compensate for a broken search.
The submitted evaluation function needs an English comment describing its logic and must be more thoughtful than simply counting pieces or copying the baseline.

53:00 Assignment Files and GameState Representation

The assignment includes GameState, PlayerStudent, players.js, interface files, and marking-related files; most student implementation work is in PlayerStudent.
GameState stores board dimensions, a two-dimensional board array, piece counts per column, the total piece count, and the current player.
Player values represent yellow, red, empty cells, and draws; board coordinates use x from left to right and y from the bottom upward.

58:00 GameState Actions, Undo, and Legal Moves

doAction places the current player's piece at the next open row in the chosen column, increments column and board counts, and switches turns.
undoAction reverses those updates and warns if asked to undo an empty column.
getLegalActions checks each column against the board width and returns only columns that are not full.

1:04:00 Win Detection and Deep Copies

GameState checks for a win across horizontal, vertical, and two diagonal directions, returning player one, player two, draw, or player none.
The winner method checks board positions and directions; player none signals that the game is still ongoing.
GameState.copy makes a deep copy, duplicating the arrays so search branches can modify successor states without altering their parent.

1:10:00 Random and Greedy Player Implementations

Each player implements getAction(state) and returns a legal column for the current position.
The random player selects an index into getLegalActions, then returns the action at that index.
The greedy player copies the state for each candidate, applies the actual legal action, evaluates the child, and retains the first action with the highest score.

1:19:00 PlayerStudent State and Search Setup

PlayerStudent tracks searchStartTime, the best action from completed depths, the current iteration's best action, the current depth, and whether the time limit was reached.
getAction records performance.now(), resets persistent search variables, sets the maximizing player, and calls iterative deepening alpha-beta.
The separation between current and completed best actions prevents an interrupted search from replacing a result from a fully completed depth.

1:25:00 Iterative Deepening and Search Limits

Iterative deepening calls alpha-beta at depths 1, 2, 3, and onward, retaining the best action only after each full iteration completes.
A positive maxDepth caps the iterations; maxDepth equal to zero should be converted to an effectively unlimited depth.
The search respects whichever positive constraint arrives first, elapsed time or maximum depth, and the interface can test timing by playing the agent against itself.

1:32:00 Timeout Handling Without Recursive Exceptions

The revised assignment avoids the try/catch approach shown in older slides and instead uses a timeLimitReached boolean.
hasTimeLimitReached returns true once the flag is set, returns false when the configured time limit is zero, and otherwise compares performance.now() minus searchStartTime with the limit.
When a timeout is detected, recursive calls return quickly and iterative deepening exits without trusting the incomplete depth.

1:38:00 Alpha-Beta Terminal Checks and Minimax Recursion

At each node, alpha-beta first handles terminal states and the maximum-depth cutoff by evaluating the current state.
A state is terminal when winner returns anything other than player none; otherwise the search generates legal actions and recurses over copied child states.
Implement plain minimax first, then add alpha and beta updates and pruning using the pseudocode from the earlier lecture slides.

1:44:00 Custom Heuristic Rules and Lookahead Boundaries

For nonterminal states, the evaluation should compare the position for the maximizing player with the position for the opponent; wins, losses, and draws remain positive, negative, and zero.
Do not perform lookahead or apply actions inside the evaluation function; minimax and alpha-beta are responsible for searching future moves.
Helper functions for counting possible connections are encouraged, but existing interface function names should remain unchanged.

1:50:00 Submission Guidance and Assignment Support

Zobrist hashing is for the COMP 6980 graduate version and is not required for COMP 3200; it earns no bonus marks.
Dave Churchill says the assignment due date may be extended because the lecture release is late, with an update expected on Brightspace.
Students can ask questions through Discord, email, or office hours.

Transcript excerpt

0:00 So today's lecture is number 12 and we'll be talking about assignment three. But what I'm going to do is first go over um that post I made about the midterm because the assignment 3 demo is not going to take much time. Um I'm going to go over the midterm stuff. Then I'll give the assignment three demo and what you have to do. And then later on I'll do what I did before and put the live coding part at the end of the lecture so I can spend more time at it um rather than rushing through it here. So as you can see uh so it is October 22nd. We're doing uh this lecture which is the lecture before the midterm. I said that the midterm would cover all the lectures up to and including this one, but really um there's not a lot of stuff that I could ask about assignment

0:49 three that wasn't in the lectures before. And so really the only things that I could ask about this lecture are algorithmic and they've already been in the previous slides. So I guess to be more accurate, you could not study today's lecture and be fine for the midterm. It's just the assignment three information. Um, keep in mind that there can be um, so this we weren't in class for this one. So I just want to make I'll color this one just to indicate that we weren't live um, in class for that one, but I gave a video for that. So make sure you do look over the slides and the video for the um, voting algorithms because there can be a question about that on the exam, but we didn't do it like in class. it was just a video

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

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.