COMP 3200 - Intro to Artificial Intelligence - Lecture 04 - Assignment 1

Overview

Dave Churchill explains COMP 3200 Assignment 1: implement breadth-first search (BFS) and depth-first search (DFS) for pathfinding on a JavaScript grid, while learning the HTML-based assignment framework used throughout the term. He details the grid and node representations, search functions, debugging tools, interface visualizations, test expectations, and submission rules; COMP 6980 and IDFS material is explicitly out of scope for undergraduates.

Key takeaways

For Assignment 1, BFS produces optimal paths because every legal move costs 100; DFS only needs to find a route and is not expected to match optimal-cost tests.
Represent states and actions as coordinate pairs, but keep their meanings distinct: states are `[x, y]` locations, while actions are `[dx, dy]` changes.
JavaScript array equality checks whether two variables refer to the same array, not whether their coordinates match; compare state elements individually when searching a closed list.
Build and test the implementation incrementally, and keep the browser console free of red errors; `try...catch` can conceal failures rather than fix them.
The assignment interface separates setup from iteration: `start_search` initializes state, while `search_iteration` performs each step and updates shared result fields.
Use the provided timing tests as a correctness and performance check: BFS should match optimal costs, DFS need only find a path, and every individual search should complete in under one second.

Chapters

0:00 Assignment 1 Scope: BFS, DFS, and Ignoring IDFS

COMP 3200 students implement four-direction grid pathfinding with BFS and DFS; the assignment is conceptually simpler than later work.
References to COMP 6980 and IDFS belong to the graduate assignment and should be ignored by undergraduates.
The lecture introduces the shared HTML and JavaScript framework that will also support Assignment 2.

3:03 Partner Work, Deadlines, and Optional Speed Certificates

Assignments may be completed in groups of up to two; one partner submits and lists the other partner in a comment at the top of the JavaScript file.
Dave Churchill recommends even contributions and real-time pair programming, such as working together in person or on Discord voice chat.
Late work loses 5% per hour, rounded up, and students have one 48-hour extension; Churchill advises saving it for a higher-value assignment.
Fastest BFS implementations may earn a certificate, but runtime competitions do not affect course grades.

6:48 JavaScript Basics and Building Code Incrementally

The required JavaScript is limited to variables, objects, loops, conditionals, 2D arrays, functions, and classes; HTML and CSS knowledge is unnecessary.
JavaScript and HTML let students open the assignment directly in a browser and inspect an algorithm through a graphical interface.
Churchill advises testing one function at a time: verify action legality before writing search code that depends on it.
Writing a large block of code before the first run makes bugs harder to isolate; use the browser interface and console while building incrementally.

9:35 JavaScript Scope, Array Equality, and Debugging Pitfalls

Use `let` rather than `var` to avoid unexpected variable-scope behavior and accidental overwrites.
JavaScript arrays compare by object identity, not contents; compare state coordinates element by element when checking a closed list.
Prefer `===` to `==` when data types matter, since `==` can coerce values such as the number 5 and the string "5".
Open the browser debug console while testing, and avoid `try...catch` in assignment code because it can hide errors and stop execution prematurely.

15:27 Console Logging and Inspecting the Grid Interface

`console.log` can display arrays and objects in the browser console, but logged objects are references; later mutations can make earlier entries appear changed.
Red console messages indicate errors that can cost marks, even if the tested examples seem to work.
The interface lets students select a start cell and a goal cell, then displays the path returned by their search algorithm.

19:21 Grid States, Coordinates, and Color-Based Movement Rules

The environment is a 2D array of integer values; colors such as blue and green visualize different values rather than representing literal terrain.
Each cell is a state stored as an `[x, y]` pair, with `(0, 0)` at the top left; x increases to the right and y increases downward.
The default grid is 64 by 64, so its bottom-right cell is `(63, 63)`.
Movement is allowed only between cells with the same underlying value, which makes differently colored regions function as obstacles.

23:18 Action Vectors, Legal Moves, and Assignment 1 Costs

Actions are `[dx, dy]` vectors: up `(0, -1)`, left `(-1, 0)`, right `(1, 0)`, and down `(0, 1)`.
A move is illegal if it leaves the map or enters a cell whose value differs from the current cell.
Each cardinal action costs 100; integer-scaled costs prepare the framework for Assignment 2, where diagonal moves cost 141.
In Assignment 1, a path's cost is its number of actions multiplied by 100.

27:52 Failure Costs and Reconstructing Paths from Parent Pointers

If no route exists, represent failure with a cost of `-1` and an empty path rather than returning a special failure object.
The final path must be an ordered sequence of actions, not a list of visited states, because the interface draws the route by applying each action.
Reconstruct the route by following parent pointers from the goal node to the root, collecting each node's action, then reversing the collected actions.
Churchill provides pseudocode for a `compute_path` function that can be translated into JavaScript.

32:45 Node Data and the Interface's Search Loop

Each search node stores its state coordinates, the action that reached it, and a parent pointer; Assignment 1 does not require depth information.
The interface handles initialization through `start_search` and repeatedly calls `search_iteration` for the algorithm's loop body.
The interface redraws and processes input at roughly 60 frames per second, enabling instant, animated, and step-by-step search modes.
When a search succeeds or fails, the implementation updates fields such as path, cost, and in-progress status rather than returning from the UI loop.

37:09 BFS and DFS: Queue-versus-Stack Selection

Both algorithms add nodes to the end of a JavaScript array; BFS removes the first node with `shift()`, while DFS removes the last with `pop()`.
BFS is optimal here because all actions cost 100, so the path with the fewest actions also has the lowest cost.
DFS is not optimal: its required outcome is to find a path, not to match the solution path or pass the optimal-cost tests.
A closed-list check can avoid adding nodes that have already been visited, reducing redundant work and memory use.

43:36 Choosing Maps and Algorithms in the Assignment Interface

The interface offers several hard-coded maps, including the default environment, a small map, a blank map, an L-shaped wall, and dense caves.
The default map is used for the provided tests; students can switch environments to probe their implementations.
The student BFS and DFS options initially use sample code that can draw an illegal route, while the solution options demonstrate completed searches.
Undergraduate students should ignore the IDFS option in the algorithm selector.

47:43 Single-Step Search, Animation, and DFS Backtracking

The visualization colors the final path white, closed-list states red, and open-list states yellow; gray marks the current node and its parent chain.
Single-step mode advances one search iteration at a time, helping students inspect node expansion and debug list behavior.
Animated search runs iterations over time, with a speed control that can increase playback to eight times speed.
DFS can follow one direction deeply and backtrack before finding a route, illustrating why it may return a longer path than BFS.

51:47 Test Tables, Runtime Measurements, and Performance Expectations

The test suite compares student results with solution results across 20 handpicked start-and-goal pairs, reporting path costs, correctness, and runtime.
Only BFS is expected to pass the optimal-path tests; DFS is checked visually by a TA for whether it finds a path.
Each individual search should finish in under one second for full marks; straightforward array-based implementations should meet that threshold.
Repeated test runs may get faster because of JavaScript caching, and Churchill recommends using the lowest result across roughly 10 runs for speed comparisons.
The obfuscated solution code runs about 10–20 times slower than unobfuscated code, so student code can legitimately outperform its displayed runtime.

58:09 Assignment Files and the Environment Helper

`search_student.js` is the only file students edit and submit; `A1_GUI.js` and `gui.js` implement the interface and should be left alone.
`environment.js` stores grid data, dimensions, and predefined test locations; its `get(x, y)` method returns the integer value at a cell.
The environment's `is_out_of_bounds(x, y)` helper checks whether a coordinate lies outside the map.
`index.html` sets up the page, while the supplied solution file is intentionally obfuscated.

1:03:48 Student Search Class and Separating Data Storage from Logic

Students may add member variables and helper functions in `search_student.js`, but must preserve the existing class and function names called by the interface.
Open-list and closed-list classes hide storage details behind operations such as adding a node, retrieving an item, and checking list size.
Separating data storage from search logic makes it easier to change the underlying structure without rewriting the algorithm.
The same abstraction becomes more important in Assignment 2, which uses a priority queue rather than a basic array for the open list.

1:10:12 Implementing Search Functions and Interface State Reporting

`config.actions`, `config.action_cost`, and `config.strategy` provide legal action vectors, costs, and the selected BFS or DFS strategy.
`start_search` initializes coordinates, lists, the root node, and search status; `is_legal_action` checks map bounds and matching cell values.
In `search_iteration`, replace the demonstration path with the search algorithm, set failure to cost `-1` and an empty path, or reconstruct the successful path and set its cost to `path.length * 100`.
Implement `get_states` for both open and closed lists by converting stored nodes into coordinate pairs, allowing the interface to color yellow and red cells correctly.

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.