Lecture 2: Views of AI & Historical Wave Cycles
Science vs. Engineering, The AI Effect, 4 Views, Turing Test, Combinatorial Explosion, and Modern Lessons.
📈 The AI Hierarchy: Nested Subfields
Non-ML AI (Classical Search, Logic, Constraint Satisfaction) forms the foundational bedrock of rational agency.
Search, Logic, Planning, Agents
Statistical learning from data
Multi-layer neural representations
Next-token probability distributions
🎓 The Four Views of AI (Russell & Norvig Matrix)
Click each quadrant to explore the distinction. Modern AI concentrates decisively on Acting Rationally.
✈ The Aeronautics Analogy (Slide 305)
Aircraft do not flap their wings like pigeons, yet both obey the universal laws of aerodynamics. Similarly, AI engineers rational entities that achieve goals without needing to replicate human biological cognition.
🤖 Moravec’s Paradox (Slide 1390)
“High-level cognitive reasoning (chess, logic) requires very little compute; low-level sensorimotor perception and locomotion require massive computational power.” Explains why Deep Blue defeated Kasparov in 1997, yet humanoid RoboCup soccer remains a grand challenge!
💥 Combinatorial Explosion: Why Brute Force Collapses
The mathematical root cause behind both AI Winters (Lighthill 1973 & Collapse of Expert Systems 1987).
📅 Historical Waves & Crucial Milestones 16 Slide-Verified Milestones • Click to Expand
Every wave follows: Toy Success → Overpromising → Combinatorial Explosion → Winter → Technical Innovation.
Lecture 1: Intelligent Agents, PEAS & Task Environments
Perception-Action loops, Agent Functions, 4 Determinants of Rationality, and the 5 Architecture Progress Ladder.
↑ Live Agent-Environment Interaction: Percepts generate internal states which trigger actuators.
Agent Function (The Specification)
$f : \mathcal{P}^* \to \mathcal{A}$
A mathematical mapping from every possible percept sequence to an action. An idealized specification of what an agent does. A lookup table for chess would require $10^{120}$ entries (Shannon Number), far exceeding the $\approx 10^{80}$ atoms in the observable universe.
Agent Program (The Implementation)
$\text{Program}: \mathcal{P} \to \mathcal{A}$
The concrete computational algorithm executing on physical hardware. The art of AI is designing compact programs that produce rational behavior without massive tables.
🎯 Rationality & The 4 Determinants (Russell & Norvig)
A rational agent selects an action that maximizes expected performance given the evidence of its percept sequence and built-in knowledge.
The success metric chosen by us
Built-in rules of the world
All available actuators
Full sensory history to date
🔎 Task Environment Specifications (PEAS Framework)
📈 The 7 Environment Dimensions
These dimensions determine the algorithm design. The hardest case is driving a taxi.
🗸 The 5 Agent Architectures (Progress Ladder)
Each step is forced by an inescapable limitation of the tier below. Click each step to inspect:
⚡ Lecture 1 Spotlight: The Modern LLM Coding Assistant as a Rational Agent
Prof. Wolter demonstrates how modern 2026 AI coding agents fit precisely into Russell & Norvig’s 1995 framework:
User prompts + tool execution outputs + error logs
Epistemic (read file, run tests) vs. Ontic (edit code, commit)
Context window tokens (explains why it forgets long history!)
Code correctness, test pass rates, user satisfaction
Lecture 3: Uninformed Tree Search — BFS vs. DFS
Search Problem 5-Tuple, Dual-Pane Tree Visualizer, Physical Conveyor Queue, and the DFS Spine Space Proof.
📜 Formal Search Problem Formulation
A search problem is formally defined by the 5-tuple:
State Space
Initial State
Goal State(s)
Actions / Succs
Step Cost
🏆 Optimal Path Found!
📜 Mathematical Proof: Why DFS Space is $O(b \cdot m)$ (Slides 2133–2302)
Prof. Wolter’s 9-slide step-by-step spine-and-stubs derivation.
Consider a search tree of branching factor $b$ and maximum depth $m$:
Footnote on parent pointers: Storing full path lists requires $O(b m^2)$ memory. Using parent back-pointers reduces each frontier entry to $O(1)$, strictly guaranteeing $O(bm)$ linear space!
Lecture 4: Depth-Limited, Iterative Deepening & Bi-directional Search
DLS Cutoffs, The IDS “Sweet Spot”, Regeneration Overhead Math, 3 Levels of Repeated State Avoidance.
⚡ Interactive Depth-Limited Search (DLS) Cutoff Simulator
Adjust the depth limit $\ell$ to see how DLS stamps nodes with a cutoff line.
⭐ Iterative Deepening Search (IDS): The Undisputed Sweet Spot
Runs $\text{DLS}(\ell)$ for $\ell = 0, 1, 2, \dots$ combining BFS optimality & completeness with DFS linear memory $O(bd)$.
Total nodes generated across all DLS runs up to depth $d$:
For $b = 10, d = 5$:
• BFS: Expands $111,111$ paths — Stores $100,000$ in RAM!
• IDS: Expands $123,456$ paths (+11.1%) — Stores only $b \cdot d = 50$ in RAM!
🔄 The 3 Levels of Avoiding Repeated States (Slides 549–596)
Why practical DFS and IDS use Level 2, while BFS uses Level 3.
Do not return to immediate parent. Extremely cheap ($O(1)$ check), but fails to prevent larger cycles.
Reject child if it already exists along the current active branch. Cost: $O(d)$. Preserves linear memory $O(bm)$!
Store all reached states in a hash set. Reduces exponential paths to polynomial, but destroys linear space!
🔀 Bi-directional Search & The First-Meeting Trap
Searches forward from $s_{\text{start}}$ and backward from $s_{\text{goal}}$ until frontiers intersect at depth $d/2$.
The first state encountered in the intersection of forward and backward frontiers is not guaranteed to lie on the optimal path! A correct optimal implementation must finish expanding the current depth layer and test all candidate crossing edges.
• Actions must be dynamically reversible ($\text{pred}(s)$ computable).
• Goal set must be small and explicit (cannot search backward from vague condition like “any checkmate”).
🤖 Interactive Complexity & RAM Calculator
Input parameters to compute exact expansions and RAM requirements across all 5 uninformed algorithms:
| Algorithm | Nodes Generated | Max Frontier Size | RAM (@ 1KB/node) | Complete? | Optimal? |
|---|
Canonical Search Formulations: Benchmark Problem Lab
In AI, a well-formulated search problem consists of 5 mathematical components: Initial State ($s_0$), Actions ($ ext{Actions}(s)$), Transition Model ($ ext{Result}(s,a)$), Goal Test ($ ext{IsGoal}(s)$), and Path Cost ($c(s, a, s')$). Explore the 4 canonical problems that anchor the COMP111 curriculum.
🧹 The 8-State Vacuum Cleaner World & Agent Dynamics
Why does this simple 2-room world form the cornerstone of AI theory? It exposes the sharp boundaries between Physical States vs. Belief States, reveals the fatal Pacing Pathology of Reflex Agents, and proves why Tree Search creates infinite loops ($m = \infty$) without cycle checking.
♕ 8-Queens Problem Formulation: Naive vs. Column-wise Search
Place 8 queens on an $8 \times 8$ chessboard such that no two queens attack each other (same row, column, or diagonal). How a problem is formulated completely dictates whether its search space is computationally tractable or completely explodes!
States: Any arrangement of 0 to 8 queens anywhere on the 64 squares.
Actions: Add a queen to any unfilled square on the board.
State Space Size:
$\prod_{i=0}^7 (64 - i) = \frac{64!}{56!} \approx 1.78 \times 10^{14}$ states!
States: Arrangements of $k$ queens ($0 \le k \le 8$) in columns $0 \dots k-1$, with no two queens attacking.
Actions: Add a queen to any unattacked square in column $k$.
State Space Size: At most $8^8 = 16,777,216$ states. With unattacked pruning, the entire tree contains only 2,057 nodes!
- Strict Depth Limit: Every path from root terminates at depth $d = 8$ ($m = 8$).
- Zero Cycles: Each step advances strictly to the next column ⇒ impossible to revisit a state!
- Finite Tree: Because the tree is finite and acyclic, even basic Tree Search (DFS) is guaranteed to terminate!
🗺️ Holiday in Romania: Path Cost & Heuristic Formulation
Admissibility: Because a straight line is the shortest possible path between two Euclidean points, $h_{SLD}(n) \le h^*(n)$ guaranteed!
🚣 Missionaries & Cannibals Formulation
📑 Comparison Matrix: The 4 Canonical Search Problems
COMP111 Exam Reference| Problem | State Tuple | Physical States | Branching ($b$) | Goal Depth ($d$) | Max Tree Depth ($m$) | Reversible? | Finite Tree? |
|---|---|---|---|---|---|---|---|
| Vacuum World | [Loc, DirtA, DirtB] | 8 | $b \le 3$ | $d \le 3$ | $m = \infty$ (cycles) | ✓ Yes | ✗ No (Infinite) |
| 8-Queens (Col-wise) | Queen rows per col $[r_0 \dots r_k]$ | 2,057 (pruned) | $b \le 8$ | $d = 8$ | $m = 8$ strictly | ✗ No | ✓ Yes (Finite!) |
| Holiday in Romania | $\text{In}(\text{City})$ | 20 cities | $b \le 4$ | $d = 3$ to 4 hops | $m = \infty$ (cycles) | ✓ Yes | ✗ No (Infinite) |
| Missionaries & Cannibals | $(M_L, C_L, B)$ | 32 valid states | $b \le 5$ | $d = 11$ | $m = \infty$ (cycles) | ✓ Yes | ✗ No (Infinite) |
| 8-Puzzle | Permutation of $(0 \dots 8)$ | 181,440 | $b \le 4$ | $d \le 31$ | $m = \infty$ (cycles) | ✓ Yes | ✗ No (Infinite) |
Practice Lab: 8-Puzzle State Space Explorer & Decision Engine
Visual step-by-step heuristic solver, live successor branch evaluator ($f = g + h$), displacement heatmap, heuristic shootout, and inversion parity validator.
A* never guesses — it guarantees the optimal (shortest) solution by scoring every candidate move with $f(n) = g(n) + h_2(n)$. The bar below shows these live values as you step through the solution. $g$ = moves already made · $h_2$ = Manhattan distance still to go · $f$ = total priority (lowest wins).
🎮 Try it: Scramble the board, click ⚡ Solve with A*, then use the step controls to walk through every single decision, one tile slide at a time.
Most search visualisers just play an animation. Here, each step of the scrubber reflects the exact internal decision A* made — which node it popped from its priority queue and why. The narration banner below the controls tells you which tile moved and in which direction.
Notice that A* doesn't just rush toward the goal. It also accounts for detours already taken. A move that looks closer to the goal might still have a higher $f$ if you've already taken a long path to get here — that's what separates A* from a simple Greedy search.
Evaluation & Successor Branch Analyzer
Every time A* makes a move, it looks at all legal tile slides from the blank's current position and scores each one. The card marked ★ CHOSEN (Lowest f) is the actual move A* takes — it has the smallest total estimated cost to the goal.
The other cards are real alternatives that A* considered but rejected. They stay on the open list (priority queue) and may be revisited if the chosen path later turns out to be a dead end — that's A*'s guarantee of completeness and optimality.
$h_2$ is calculated tile by tile: for each tile not yet home, count how many squares it must travel horizontally plus vertically to reach its goal position. Add them all up — that's the Manhattan sum. The table below shows this live for every tile in the current state.
This can never overestimate the true cost (it's admissible) because tiles cannot jump over each other. Every tile must actually travel at least that many squares — often more. An admissible heuristic guarantees A* always finds the optimal solution.
| Tile | Current $(r, c)$ | Goal $(r^*, c^*)$ | $|\Delta r| + |\Delta c|$ | Status |
|---|
🚀 Heuristic Comparison Shootout: $h_2$ vs. $h_1$ vs. Greedy vs. BFS
Observe firsthand why Manhattan Distance strictly dominates Misplaced Tiles without losing optimality, and how ignoring path cost $g(n)$ causes Greedy Best-First to return suboptimal paths.
All 4 algorithms below solve the exact same board. The only difference is how they estimate the remaining cost. Watch how A* with Manhattan expands far fewer nodes than A* with Misplaced Tiles, yet always finds the same optimal solution. This is heuristic dominance — a sharper lower bound means less wasted searching.
Greedy Best-First uses only $h_2$ (no $g$ at all), so it may find a path fast but it's often suboptimal — it rushes toward the goal without caring how many moves it wasted getting here. BFS has no heuristic at all, so it expands nodes in waves and can become enormous for hard states.
If $h_2(n) \ge h_1(n)$ for all states $n$, and both are admissible heuristics, then $h_2$ dominates $h_1$. Mathematically, this guarantees:
$A^*$ using $h_2$ will never expand any node that $A^*$ using $h_1$ does not expand (except possibly on the tie-breaker contour where $f(n) = C^*$). Because Manhattan distance sums the true minimum rectilinear distance for each tile, whereas Misplaced tiles only scores 1 regardless of whether a tile is 1 step or 4 steps away, $h_2$ provides strictly sharper lower bounds!
🧩 Solvability Engine: Why Exactly $\frac{9!}{2} = 181,440$ States Exist
Flatten the 8-puzzle into a 1D list (ignoring the blank). An inversion is any pair of tiles where a larger number appears before a smaller one — e.g. (5, 3) is an inversion because 5 > 3 but 5 comes first. Every legal tile slide either preserves the inversion count's parity or changes it by ±2 (keeping it even or odd).
The goal state has 0 inversions (even). Therefore: only states with an even inversion count can ever reach the goal. If a state has an odd number of inversions, no sequence of legal slides can fix it — it's mathematically impossible. That's why exactly $ rac{9!}{2} = 181{,}440$ of the 362,880 possible arrangements are solvable.
🔬 Try it: Click ⚠ Swap Tiles 7 & 8 to flip the parity of the current state and watch the verdict change instantly.
Total permutations of 9 tiles is $9! = 362,880$. However, the state space is partitioned into two disjoint reachability components of size $\frac{9!}{2} = 181,440$ each!
- Horizontal Blank Move: The blank shifts left/right within the same row. The relative order of all numbered tiles remains completely identical ⇒ $\Delta I = 0$.
- Vertical Blank Move: Moving the blank up/down changes the 1D position of the moved tile by exactly 2 positions (it jumps over 2 other tiles). The number of inversions changes by either $+2, 0,$ or $-2$ ⇒ $\Delta I \equiv 0 \pmod 2$.
🎓 COMP111 Comprehensive University Exam Suite
25 Analytical, Mathematical & Conceptual Questions Covering Lectures 1–4 with KaTeX Formatted Math.