Unit I: Foundations of Artificial Intelligence

Section 01

Introduction to Artificial Intelligence

What separates a pocket calculator from a chess-playing computer? Both process instructions — but only one can adapt, reason, and learn. That gap is what Artificial Intelligence tries to close. Since Alan Turing asked "Can machines think?" in 1950, AI has evolved from a philosophical curiosity into a field that powers recommendation engines, autonomous vehicles, medical diagnosis, and language translation used by billions every day.

Formally, AI is the study of agents that receive percepts from the environment and perform actions. The field draws from mathematics, psychology, linguistics, neuroscience, and computer science to build systems that exhibit behaviours we would call intelligent if a human performed them.

Before we can build intelligent systems, however, we need to understand the problems AI tries to solve, the techniques it employs, and why even a simple game like Tic-Tac-Toe turns out to be a surprisingly rich AI training ground.

What is Artificial Intelligence?

There is no single universally accepted definition. Researchers have historically proposed four categories of definition, arranged in a 2×2 grid based on two axes: human-like vs. rational and thinking vs. acting.

Figure 1.1 — Four definitions of AI arranged by (Think vs. Act) × (Human-like vs. Rational). Modern AI favours the rational agent approach (bottom-right).

Exam Tip

Examiners frequently ask: "What are the four definitions of AI?" Memorise the 2×2 grid. The rational agent approach is the dominant framework in the Russell & Norvig textbook and in modern AI systems.

Problems of Artificial Intelligence

AI does not tackle all computational problems — it focuses on a specific class where the solution requires intelligence. These problems share two key characteristics: they are typically too complex for direct algorithmic solutions, and their solutions benefit from heuristic or learned knowledge.

Problem Class	Example	Why It Needs AI	Difficulty
Game Playing	Chess, Go, Tic-Tac-Toe	Combinatorial explosion of possible states	Medium–Hard
Natural Language Processing	Machine translation, QA	Ambiguity, context, pragmatics	Hard
Computer Vision	Face recognition, object detection	Variation in lighting, angle, occlusion	Hard
Planning & Scheduling	Robot navigation, logistics	Large state/action spaces, constraints	Medium–Hard
Expert Reasoning	Medical diagnosis, legal advice	Uncertain, incomplete information	Hard
Learning	Image classification, GPT	Generalisation from examples	Very Hard

The AI Technique

How does AI actually solve these hard problems? Russell & Norvig describe an AI technique as a method that exploits knowledge in a form that:

AI Technique (Russell & Norvig)

An AI technique is a method by which AI programs represent, manipulate, and use knowledge about the world — such that:

The knowledge captures generalisations — it is not a mere list of cases.
It can be understood and verified by humans who provide it.
It can be modified to correct errors or reflect changes in the world.
It can be used even when it is incomplete or inaccurate.
It helps overcome its own combinatorial explosion.

This contrasts with brute-force approaches that enumerate all possibilities. A chess program that evaluates every possible game tree (approximately 10¹²⁰ leaf nodes) is not using an AI technique — it is merely computing. A program that uses heuristics like "control the centre" or "protect the king" is using an AI technique.

BFS, DFS, A*, Hill Climb

Explores a space of possible solutions systematically or heuristically to find a goal state.

Knowledge Representation

Logic, Frames, Ontologies

Encodes world knowledge in a structured, queryable form for reasoning and inference.

Planning

STRIPS, HTN, PDDL

Constructs sequences of actions to achieve a goal from a given initial state.

Machine Learning

Gradient Descent, Backprop

Learns patterns and generalisations from data rather than relying on hand-coded rules.

The Tic-Tac-Toe Problem — A Classic AI Testbed

Tic-Tac-Toe (also called Noughts & Crosses) is a 3×3 grid game where two players, X and O, alternate placing their mark. The player who first aligns three marks in a row, column, or diagonal wins. If the board fills up without a winner, the game is a draw.

Despite its simplicity, Tic-Tac-Toe is a canonical AI problem because it encapsulates the core challenge: how do we choose the best action among many possible future sequences? It is also a two-player, zero-sum, perfect-information game — all properties that make it mathematically tractable.

Classic Example Tic-Tac-Toe: State Space and Game Tree

The State Space

A state in Tic-Tac-Toe is any configuration of the 3×3 board. The total number of board configurations is at most 3⁹ = 19,683 (each cell can be X, O, or empty). After eliminating illegal boards (e.g. X moved twice in a row), about 5,478 valid states remain, with 255,168 possible game sequences.

The Game Tree (Partial)

The game tree shows all possible moves from the current state. At the root, X can place in any of 9 cells. At depth 2, O can respond in 8 remaining cells, and so on. The branching factor decreases as the board fills.

Figure 1.2 — Partial game tree for Tic-Tac-Toe. X playing centre (highlighted blue) is the strongest opening move — it offers the most paths to a win.

Minimax Strategy

AI solves Tic-Tac-Toe using the Minimax algorithm. X is the maximising player (wants highest score), and O is the minimising player (wants lowest score). At terminal nodes: Win = +1, Draw = 0, Loss = −1. The AI propagates values upwards, always choosing the best move at each level.

Minimax Value MINIMAX(state) = UTILITY(state) if TERMINAL(state) max over a of MINIMAX(RESULT(state, a)) if MAX to move min over a of MINIMAX(RESULT(state, a)) if MIN to move

With perfect play from both sides, Tic-Tac-Toe is always a draw. This is provable by exhaustive minimax search — and was one of the first results in AI game theory.

Key Insight

Tic-Tac-Toe is important not because it is hard, but because it illustrates the core ideas of AI problem solving in a compact, verifiable form: state representation, search, terminal evaluation, and adversarial reasoning. Every harder AI game (chess, Go) uses the same framework.

🎯 Quick Check: Which of the four AI definitions forms the basis of modern AI systems according to Russell & Norvig?

✅ Correct! Russell & Norvig advocate the rational agent approach. A rational agent acts to achieve the best expected outcome given its percepts and knowledge. Unlike the "Act Humanly" approach, it doesn't require mimicking human behaviour — only achieving optimal results. This is the most robust and widely adopted framework in modern AI.

Section 02

Intelligent Agents

Now that we understand what AI is, we need a framework for building AI systems. The dominant framework is the agent paradigm. Think of any intelligent entity — a thermostat, a chess program, or a self-driving car. Each one perceives its environment and takes actions. The agent abstraction lets us analyse and design all of these using the same vocabulary.

Building on the rational agent definition from Section 1, we now ask: what is the structure of such an agent? What types of environments can it live in? And how does the structure of the agent match the nature of its environment? These are the core questions of this section.

Agents and the Environment

Agent

An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.

Examples: A human (sensors = eyes, ears; actuators = hands, mouth), a software agent (sensors = keyboard input, file reads; actuators = screen output, API calls), a robot (sensors = cameras, LIDAR; actuators = motors, grippers).

Percept & Percept Sequence

A percept is the agent's perceptual input at any given instant. The complete history of everything the agent has perceived is the percept sequence. An agent's behaviour is described by its agent function, which maps every percept sequence to an action.

Agent Function f : P* \to A where P* = set of all possible percept sequences A = set of all possible actions

Rational Agent

A rational agent is one that, for each possible percept sequence, selects an action expected to maximise its performance measure, given the evidence provided by the percept sequence and any built-in prior knowledge.

Rationality ≠ omniscience. A rational agent makes the best decision with available information. This is a commonly tested distinction.

Figure 2.1 — The agent–environment interaction loop. Sensors feed percepts into the agent; the agent's brain produces actions executed by actuators on the environment.

Nature of the Environment — PEAS Description

Before designing an agent, we must specify its task environment using the PEAS framework. This is one of the most commonly tested items in exams.

PEAS Framework

Performance measure — How do we evaluate success? (e.g., score, time, accuracy)
Environment — What does the agent perceive? (e.g., road, chess board, medical records)
Actuators — How does the agent act? (e.g., steering wheel, chess move, prescription)
Sensors — How does the agent perceive? (e.g., cameras, keyboard, test results)

Worked Example PEAS Description for Three Agents

Agent Type	Performance Measure	Environment	Actuators	Sensors
Autonomous Car	Safety, speed, comfort, legality	Roads, traffic, pedestrians, weather	Steering, accelerator, brakes, signals	Cameras, LIDAR, GPS, speedometer
Medical Diagnosis	Correct diagnosis, patient health	Patient symptoms, test results, history	Prescriptions, referrals, test orders	Keyboard input, lab data feeds
Tic-Tac-Toe Agent	Win / Draw / Lose (+1/0/−1)	3×3 board, opponent's moves	Board position selection	Current board state display

Properties of Environments

Different environments demand different agent strategies. There are seven key properties by which environments are classified. This table is a very common exam question — memorise all seven dimensions.

Property	Values	Description	Example
Observability	Fully / Partially / Non-observable	Can the agent access the complete state?	Chess = Full; Poker = Partial
Number of Agents	Single / Multi-agent	Is the agent alone or competing/cooperating?	Crossword = Single; Chess = Multi
Determinism	Deterministic / Stochastic	Is the next state fully determined by action?	Chess = Det; Taxi driving = Stoch
Episodicity	Episodic / Sequential	Does current decision affect future decisions?	Image classification = Epi; Chess = Seq
Dynamics	Static / Dynamic / Semi-dynamic	Does the environment change while agent thinks?	Crossword = Static; Taxi = Dynamic
Continuity	Discrete / Continuous	Finite or infinite percepts/actions?	Chess = Discrete; Robot arm = Continuous
Knowledge	Known / Unknown	Does the agent know the outcome of its actions?	Chess rules = Known; New game = Unknown

Key Insight

The hardest environments combine partial observability, multiple agents, stochastic dynamics, sequential decisions, and continuous state/action spaces — like real-world robotics or stock trading. Tic-Tac-Toe is fully observable, deterministic, discrete, and sequential — which is why it is tractable.

Structure of Agents — The Agent Program

The agent function is an abstract description. The agent program is its concrete implementation. It runs on an agent architecture (the computational device + sensors + actuators). There are four basic agent program types, each more sophisticated than the last.

Figure 2.2 — Five types of agent programs in order of sophistication. A learning agent wraps any architecture and adds the ability to improve from experience.

Goal-Based Agents

Goal-Based Agent

A goal-based agent maintains a description of desirable situations — the goal — and chooses actions that lead toward that goal. It requires both a model of the world (how actions change the state) and a search/planning mechanism to find action sequences that achieve the goal.

Unlike a simple reflex agent, a goal-based agent can handle situations where multiple actions are possible and the current state does not directly trigger a rule. It is more flexible but computationally more expensive.

Utility-Based Agents

Utility-Based Agent

Goals alone cannot distinguish between achieving a goal and achieving it well. A utility-based agent uses a utility function — mapping states to real numbers — to measure how "happy" the agent would be in each state. It then chooses actions that maximise expected utility.

Expected Utility EU(a | e) = Σ_s P(RESULT(s,a) | e) \times U(RESULT(s,a)) where: a = action, e = evidence (percepts), s = possible outcome states P = probability, U = utility of state

Utility-based agents can handle conflicting goals (e.g., reaching a destination fast vs. safely), partial observability (via expected utility), and continuous state spaces.

Learning Agents

All agent types above rely on pre-programmed knowledge. A learning agent can improve its own performance over time by modifying its components based on feedback. It has four sub-components:

ARCHITECTURE: Learning Agent Components (Russell & Norvig, 2020)

Performance Element: Selects actions based on percepts — this is the "core" agent program (reflex, goal-based, or utility-based).

Learning Element: Modifies the performance element based on feedback from the critic. It uses machine learning algorithms (e.g., neural networks, reinforcement learning).

Critic: Evaluates how well the agent is doing with respect to a fixed performance standard and provides feedback to the learning element.

Problem Generator: Suggests actions that may be suboptimal in the short run but will lead to new experiences — enabling exploration vs. exploitation.

Note — Rationality vs. Omniscience

A common exam trap: rationality ≠ omniscience. A rational agent maximises expected utility based on what it knows — not actual utility. A rational agent crossing a road checks for traffic and crosses when safe. An omniscient agent would know the future and never be hit. We cannot build omniscient agents. We can build rational ones.

🎯 Quick Check: Which component of a learning agent evaluates how well the agent is performing and provides feedback to the learning element?

✅ Correct! The Critic evaluates the agent's behaviour against a fixed performance standard and sends feedback to the learning element. The distinction between the Critic (evaluator) and the Learning Element (modifier) is frequently tested. The Performance Element acts; the Critic judges; the Learning Element improves.

Section 03

Problem Solving & State Space Search

Building on the agent framework, we now ask: how does a goal-based agent actually decide what to do? The answer is problem-solving via search. The agent explores a space of possible states to find a sequence of actions — a plan — that leads from the initial state to a goal state.

This section introduces the formal machinery: how to define a problem, what makes a problem hard, and how production systems encode the rules of state transitions. These concepts underpin every search algorithm you will study — BFS, DFS, A*, and beyond.

Defining a Problem as State Space Search

Problem Formulation

A problem is formally defined by five components:

Initial State: The state in which the agent starts. e.g., In(Arad)
Actions: The set of possible actions available in a given state. ACTIONS(s)
Transition Model: The result of taking action a in state s. RESULT(s, a)
Goal Test: A function that determines whether a given state is a goal. GOAL-TEST(s)
Path Cost: A numeric cost assigned to each path (sequence of actions). An agent wants to minimise path cost.

The state space is the set of all states reachable from the initial state by any sequence of actions. It forms a graph (or tree) that the agent searches.

Classic Example The 8-Puzzle — A Complete Problem Formulation

The 8-puzzle has a 3×3 grid with 8 numbered tiles and one blank. The agent slides tiles to reach a goal configuration. This is the canonical search problem in AI courses.

Component	8-Puzzle Specification
Initial State	Any arrangement of 8 tiles + 1 blank, e.g. `[1,2,3,4,_,5,6,7,8]`
Actions	Slide blank Left, Right, Up, Down (depending on blank position)
Transition Model	RESULT(s, Slide-Right) = new arrangement after moving blank right
Goal Test	`[1,2,3,4,5,6,7,8,_]` — tiles in order, blank at bottom-right
Path Cost	Each move costs 1; total cost = number of moves to reach goal
State Space Size	9! / 2 = 181,440 reachable states (half of 9! are unreachable)
Solution	Sequence of Slide moves; optimal solution uses A* with Manhattan distance heuristic

Figure 3.1 — State transitions in the 8-puzzle. Moving the blank tile transforms one state to another. The agent searches for the shortest path from the initial state to the goal.

Production Systems

A production system is one of the earliest and most important AI architectures for implementing state space search. Introduced by Allen Newell and Herbert Simon, it provides a formal way to represent knowledge as condition–action rules and a control mechanism to apply them.

Production System

A production system consists of three components:

Production Rules (Knowledge Base): A set of IF–THEN rules of the form IF <condition> THEN <action>. Each rule is a production.
Working Memory (Global Database): A data structure representing the current state of the problem. Rules match against working memory.
Control System (Inference Engine): Selects which rule to fire when multiple rules match. Uses strategies like conflict resolution.

ALGORITHM: Production System Execution (Newell & Simon, 1972)

Match: Compare all production rules against the current working memory. Identify all rules whose LHS (left-hand side / condition) is satisfied. The result is the conflict set.

Conflict Resolution: If the conflict set is empty, halt (goal reached or no solution). Otherwise, select one rule to fire using a strategy: e.g., most recently added, most specific, highest priority.

Act (Fire): Execute the RHS (right-hand side / action) of the selected rule. This modifies working memory — adding facts, removing facts, or triggering external actions.

Check Goal: Test whether the current working memory satisfies the goal condition. If yes, halt and return solution path. Otherwise, goto Step 1.

Worked Example Production System for Tic-Tac-Toe

Working Memory (State)

Current board = [[X,O,_],[_,X,_],[O,_,_]] — X's turn to move.

Production Rules (Partial)

-- Rule R1: Win immediately if possible --
IF  board has two X's in a row/col/diag AND third cell is empty
THEN place X in the empty cell → "WIN"

-- Rule R2: Block opponent's win --
IF  board has two O's in a row/col/diag AND third cell is empty
THEN place X in the empty cell → "BLOCK"

-- Rule R3: Take centre if empty --
IF  centre cell is empty
THEN place X in centre → "STRATEGIC"

-- Rule R4: Take a corner if empty --
IF  any corner is empty
THEN place X in that corner → "STRATEGIC"

-- Rule R5: Take any empty cell --
IF  any cell is empty
THEN place X in that cell → "DEFAULT"

Execution Trace

Cycle	Working Memory	Rules Fired	Action
1	`[[X,O,_],[_,X,_],[O,_,_]]`	R1 matches! Two X's diagonal (0,0)+(1,1)	Place X at (2,2) — WIN ✓

Rule R1 fires immediately — winning takes priority over blocking or strategy. The goal test succeeds: X wins. The production system halts after one cycle.

Problem Characteristics

Not all AI problems are equally hard. The difficulty depends on several characteristics — understanding these helps us choose the right search strategy. This taxonomy is a staple of exam questions.

Characteristic	Options	Impact on Search	Example
Decomposability	Decomposable / Non-decomposable	Can we break the problem into independent sub-problems?	Sorting sub-arrays = Decomposable TSP = Non-decomposable
Solution Steps	Ignorable / Recoverable / Irrecoverable	Can we backtrack from wrong moves?	Chess = Recoverable; Surgery = Irrecoverable
State Space	Predictable / Unpredictable	Does the environment respond as expected?	8-puzzle = Predictable; Robot nav = Unpredictable
Good Solution	Absolute / Relative	Is optimal solution required, or is "good enough" acceptable?	Optimal path = Absolute; Route planning = Relative
Solution Required	Any path / Best path	Does cost matter? Do we need optimal or just valid?	Maze (any exit) vs. Shortest route
Knowledge	Much / Little available	Amount of domain knowledge affects algorithm choice (heuristic vs. blind)	Medical diagnosis (much) vs. Unknown game (little)

Issues in Designing Search Programs

Even with a well-defined problem, designing an effective search program requires navigating several fundamental tensions. These are the engineering challenges of search.

Completeness

A search algorithm is complete if it is guaranteed to find a solution when one exists. BFS is complete for finite graphs; DFS is not (may get trapped in infinite branches). This is a commonly tested property.

Optimality

A search algorithm is optimal if it always finds the least-cost solution. BFS is optimal when all step costs are equal; Greedy Best-First Search is generally not optimal; A* is optimal given an admissible heuristic.

Time Complexity

O(b^d) for BFS

How long does it take to find a solution? Expressed as a function of branching factor b and solution depth d.

Space Complexity

O(b^d) BFS / O(bd) DFS

How much memory is needed? DFS uses far less memory than BFS, at the cost of completeness.

Branching Factor

b = avg children/node

Number of successor states per state. High b makes search exponentially harder. 8-puzzle: b ≈ 3. Chess: b ≈ 35.

Heuristic Function

h(n) ≤ h*(n)

An admissible heuristic never overestimates the true cost h*. Used by A* to guide search towards the goal efficiently.

Watch Out — Combinatorial Explosion

The central challenge of AI search is combinatorial explosion. At branching factor b = 10 and depth d = 10, the search tree has 10¹⁰ = 10 billion leaf nodes. Without heuristics, even fast computers cannot search deep trees. This is why AI techniques (heuristics, pruning, abstraction) are essential — brute-force search fails on realistic problems.

ALGORITHM: General Search (Template for BFS, DFS, A*)

Initialise: Create a frontier (open list) with the initial state. Create an explored set (closed list), initially empty.

Check: If frontier is empty, return failure (no solution exists).

Select: Choose a node from the frontier according to the selection strategy. BFS = FIFO queue; DFS = LIFO stack; A* = priority queue ordered by f(n) = g(n) + h(n).

Goal Test: If the selected node is a goal state, return the solution path. Otherwise, add the node to the explored set.

Expand: Generate all successors of the node using ACTIONS and RESULT. For each successor not already in explored or frontier, add it to the frontier.

Repeat: Go to Step 2.

Final Answer — Key Summary

The design of a search program requires choosing: (1) a state representation, (2) a frontier management strategy (queue type), (3) whether to use heuristics, and (4) how to handle repeated states. These choices determine completeness, optimality, time complexity, and space complexity — the four evaluation criteria for search algorithms.

🎯 Quick Check: A production system fires rules against a data structure that holds the current problem state. What is this data structure called?

✅ Correct! The Working Memory (also called the Global Database) holds the current state of the problem. Rules in the Knowledge Base are matched against Working Memory. The Inference Engine selects which rule to fire. The Conflict Set is the set of all currently matching rules — from which one is selected. Knowing these four terms is essential for production system questions.

Section 04

Uninformed Search Strategies

The general search template from Section 3 becomes a concrete algorithm the moment we decide which node to expand next. When that decision uses no information about the goal — no hints, no distance estimates — we call it uninformed (or blind) search. These strategies are guaranteed to find solutions (under certain conditions) but may be expensive because they explore systematically rather than intelligently.

Two foundational uninformed strategies are Breadth-First Search (BFS) and Depth-First Search (DFS). Understanding them deeply, including their strengths, weaknesses, and complexity, is essential — they form the baseline against which all smarter algorithms are judged.

Why Study Uninformed Search?

Uninformed search algorithms are not just theoretical curiosities. BFS is used in shortest-path finding on unweighted graphs (network routing, social network distances). DFS underpins backtracking solvers (Sudoku, constraint satisfaction). Iterative Deepening DFS combines the best of both and is the standard uninformed strategy in production AI systems.

Breadth-First Search (BFS)

Breadth-First Search

BFS expands the shallowest unexpanded node first. It uses a FIFO queue as the frontier. All nodes at depth d are explored before any node at depth d+1.

BFS Complexity Time: O(b^(d+1)) — b = branching factor, d = depth of shallowest goal Space: O(b^(d+1)) — all nodes at depth d are in the frontier simultaneously Complete: YES (if b is finite) Optimal: YES (if all step costs are equal; finds shallowest = fewest steps)

Worked Example BFS on a State Space Graph — Step-by-Step Trace

Consider a simplified map of Romanian cities (the classic Russell & Norvig example). We want to travel from Arad to Bucharest. Below is the graph and the BFS expansion order.

Figure 4.1 — BFS expansion order on the Romania map. Numbers ①–⑩ show the order nodes are dequeued and expanded. BFS guarantees finding the shallowest goal (fewest edges = fewest road segments).

BFS Trace Table

Step	Node Expanded	Frontier (Queue — FIFO)	Explored
0	—	[Arad]	{}
1	Arad ①	[Zerind, Sibiu, Timisoara]	{Arad}
2	Zerind ②	[Sibiu, Timisoara, Oradea]	{Arad, Zerind}
3	Sibiu ③	[Timisoara, Oradea, RimnicuVilcea, Fagaras]	{Arad, Zerind, Sibiu}
4	Timisoara ④	[Oradea, RimnicuVilcea, Fagaras, Lugoj]	+ Timisoara
5–8	Oradea ⑤, RimnicuVilcea ⑥, Fagaras ⑦, Lugoj ⑧	[Pitesti, Craiova, Bucharest, ...]	+ depth-2 cities
9	Pitesti ⑨ → generates Bucharest	[Craiova, Bucharest, ...]	+ Pitesti
10	Bucharest — GOAL TEST PASSES ✓	—	Solution found!

BFS finds Bucharest via Arad → Sibiu → Fagaras → Bucharest (3 edges = shallowest path). Note: this is the fewest-edges path, not necessarily the shortest distance path. For that, we need weighted search (Uniform Cost Search or A*).

Depth-First Search (DFS)

Depth-First Search

DFS expands the deepest unexpanded node first. It uses a LIFO stack (or recursion) as the frontier. It dives as deep as possible before backtracking.

DFS Complexity Time: O(b^m) — m = maximum depth of state space (can be infinite!) Space: O(b \times m) — stores only the current path + siblings at each level Complete: NO (may get trapped in infinite branches / loops) Optimal: NO (first solution found may not be shallowest or cheapest)

Key Insight — Space Advantage

DFS's critical advantage over BFS is space efficiency. BFS must hold the entire frontier in memory — at depth 10 with branching factor 10, that is 10¹⁰ nodes = ~450 GB. DFS only holds the current path and its siblings: at most b × m = 10 × 10 = 100 nodes. This makes DFS practical for deep state spaces where BFS would run out of memory.

Worked Example DFS Trace on a Binary Tree

Consider a binary tree (branching factor b = 2). Goal is node G. DFS dives left first.

Figure 4.2 — DFS expansion order ①–⑧ on a binary tree. Orange dashed path shows DFS diving left; it backtracks from dead ends H and I before exploring E, then C's subtree where goal G resides.

DFS Stack Trace

Step	Node Popped	Stack (LIFO — top first)	Action
Init	—	[A]	Push start
1	A ①	[C, B]	Push children (B pushed last = top)
2	B ②	[C, E, D]	Expand B; D is top (left child)
3	D ③	[C, E, I, H]	Expand D; H is top
4	H ④	[C, E, I]	H is leaf — no children → backtrack
5	I ⑤	[C, E]	I is leaf — no children → backtrack
6	E ⑥	[C]	E is leaf — no children → backtrack
7	C ⑦	[G, F]	Expand C; F and G pushed
8	G ⑧ — GOAL ✓	[]	Goal test passes — return path A→C→G

BFS vs DFS — Head-to-Head Comparison

Property	BFS	DFS	Iterative Deepening (IDDFS)
Data Structure	FIFO Queue	LIFO Stack / Recursion	DFS repeated with depth limit
Completeness	✅ Yes (finite b)	❌ No (loops/infinite)	✅ Yes
Optimality	✅ Yes (uniform cost)	❌ No	✅ Yes (uniform cost)
Time Complexity	O(b^d+1)	O(b^m)	O(b^d)
Space Complexity	O(b^d+1) — HIGH	O(b·m) — LOW	O(b·d) — LOW
Best Use Case	Shallow goal, uniform cost	Deep goal, tight memory	Unknown depth, best practical choice

Exam Tip — IDDFS

Iterative Deepening DFS is the recommended uninformed strategy in practice. It runs DFS with depth limit 0, then 1, then 2, and so on until a solution is found. It combines BFS's completeness and optimality with DFS's O(b·d) space complexity. The cost of re-expanding nodes at each iteration is only a constant factor overhead (about b/(b−1) times DFS).

🎯 Quick Check: You are searching a state space where the goal is very deep (depth ≈ 100) and memory is severely limited. Branching factor is 4. Which search strategy should you choose?

✅ Correct! BFS at depth 100 with b=4 would require 4¹⁰⁰ ≈ 10⁶⁰ nodes in memory — the estimated number of atoms in the observable universe is only ~10⁸⁰. DFS requires only O(b×d) = O(4×100) = 400 nodes simultaneously. IDDFS is even better — same space as DFS but complete and optimal. For very deep state spaces, DFS-based strategies are the only viable option.

Section 05

Informed Search & the A* Algorithm

Uninformed strategies are blind — they have no idea which direction brings them closer to the goal. Given that real problems have enormous state spaces, blindness is expensive. Informed search strategies use a heuristic function h(n) — a problem-specific estimate of the cost to reach the goal from node n — to guide the search more efficiently.

The heuristic is the AI technique at work: domain knowledge encoded in a formula, steering the search away from fruitless paths. The most important informed algorithm — the one you must know for the exam — is A* (A-star), which combines actual cost incurred with an optimistic estimate of remaining cost.

Heuristic Functions

Heuristic Function h(n)

A heuristic function h(n) estimates the cost of the cheapest path from node n to a goal state. It encodes domain knowledge cheaply: computing h(n) should be much faster than solving the problem from scratch.

Admissibility: h(n) ≤ h*(n) for all n, where h*(n) is the true optimal cost. An admissible heuristic never overestimates. This is required for A* optimality.

Consistency (Monotonicity): For every node n and successor n' via action a: h(n) ≤ c(n, a, n') + h(n'). Consistency implies admissibility.

Classic Example Two Admissible Heuristics for the 8-Puzzle

Heuristic	h₁: Misplaced Tiles	h₂: Manhattan Distance
Definition	Count of tiles not in their goal position	Sum of \|row + col distances\| each tile is from its goal
Formula	h₁ = Σ [tile_i ≠ goal_i]	h₂ = Σ (\|r_i − r̂_i\| + \|c_i − ĉ_i\|)
Admissible?	✅ Yes — each misplaced tile requires ≥ 1 move	✅ Yes — each tile needs at least that many moves (slides only)
Which is better?	Weaker (lower estimate)	Stronger (higher, tighter estimate)
Dominance	h₂ dominates h₁: h₂(n) ≥ h₁(n) for all n. A stronger (higher) admissible heuristic expands fewer nodes.

Numerical Example

For the state [[7,2,4],[5,_,6],[8,3,1]] with goal [[1,2,3],[4,5,6],[7,8,_]]:

Tile	Current Position	Goal Position	Misplaced?	Manhattan Distance
1	(2,2)	(0,0)	✗ Yes	\|2−0\|+\|2−0\| = 4
2	(0,1)	(0,1)	✓ No	0
3	(2,1)	(0,2)	✗ Yes	\|2−0\|+\|1−2\| = 3
4	(0,2)	(1,0)	✗ Yes	\|0−1\|+\|2−0\| = 3
5	(1,0)	(1,1)	✗ Yes	1
6	(1,2)	(1,2)	✓ No	0
7	(0,0)	(2,0)	✗ Yes	2
8	(2,0)	(2,1)	✗ Yes	1
Total	—		h₁ = 6	h₂ = 14

h₂ = 14 gives a much tighter lower bound than h₁ = 6, so A* using h₂ will explore far fewer nodes before finding the optimal solution.

Greedy Best-First Search

Greedy Best-First Search expands the node that appears closest to the goal by choosing the node with the smallest h(n). It uses a priority queue ordered by h(n) only — ignoring how much it has already cost to reach the node.

Greedy Evaluation Function f(n) = h(n) \leftarrow only heuristic, ignores actual cost g(n) Complete: NO (can loop in infinite state spaces) Optimal: NO (greedy choices can lead to suboptimal solutions)

Greedy search is fast in practice but unreliable. It can be misled by a heuristic into a poor path. Example: using straight-line distance heuristic, going to Fagaras first looks good for reaching Bucharest — but A* discovers a shorter total path via RimnicuVilcea.

A* Search — The Gold Standard

A* (A-star) Search

A* combines the actual cost from the start to a node g(n) with the estimated cost to the goal h(n). It expands the node minimising the evaluation function:

A* Evaluation Function f(n) = g(n) + h(n) where: g(n) = actual cost from start to node n (path cost so far) h(n) = estimated cost from n to goal (heuristic) f(n) = estimated total cost of the path through n Properties (given admissible h): Complete: YES (if solution exists and b is finite) Optimal: YES (finds minimum-cost solution) Time: O(b^d) — exponential in worst case Space: O(b^d) — stores all generated nodes in memory

Worked Example A* on the Romania Map — Full Trace

Find the shortest path from Arad to Bucharest. We use the straight-line distance to Bucharest as the admissible heuristic h(n). Road distances give g(n).

City	h(n) = SLD to Bucharest (km)
Arad	366
Zerind	374
Sibiu	253
Timisoara	329
Rimnicu Vilcea	193
Fagaras	178
Pitesti	98
Bucharest (Goal)	0

A* Expansion Trace

Step	Node Expanded	g(n)	h(n)	f(n)=g+h	Best Frontier f-values
1	Arad	0	366	366	Zerind:449, Sibiu:393, Timisoara:447
2	Sibiu (f=393)	140	253	393	RimnicuVilcea:413, Fagaras:415, ...
3	RimnicuVilcea (f=413)	220	193	413	Pitesti:417, Fagaras:415, ...
4	Fagaras (f=415)	239	178	415 (wait!)	Pitesti:417, Bucharest:450 via Fagaras, ...
5	Pitesti (f=417)	317	98	417	Bucharest:418 via Pitesti!, ...
6	Bucharest (f=418) ✓	418	0	418	GOAL — optimal cost = 418 km

The optimal path is Arad (0) → Sibiu (140) → RimnicuVilcea (220) → Pitesti (317) → Bucharest (418 km). Crucially, A* did NOT go through Fagaras (which looks closer to Bucharest on the heuristic) because Fagaras→Bucharest costs 211 km for a total of 450 km — worse than the Pitesti route (418 km).

Key Takeaway

The reason A* beats Greedy search here: Greedy would choose Fagaras first (h=178 looks best) and find Bucharest at total cost 450 km. A* factors in g(n) — the actual road distance already travelled — so it correctly identifies the Pitesti path as 418 km, which is cheaper. The f(n) = g(n) + h(n) balance is what makes A* optimal.

Figure 5.1 — Greedy search finds a 450 km path by following the smallest heuristic value; A* finds the true optimal 418 km path by balancing actual cost g(n) with heuristic estimate h(n).

🎯 Quick Check: A heuristic h(n) is said to be admissible if it never overestimates the true cost. For the 8-puzzle, which of the following heuristics is NOT admissible?

✅ Correct! Option C is NOT admissible. It can overestimate the true cost h*(n) because multiplying by 3 can produce a value larger than the actual number of moves needed. h(n) = 0 (option D) is trivially admissible (never overestimates, but useless — A* degenerates to Uniform Cost Search). Misplaced tiles and Manhattan distance are both classic admissible heuristics because each individual tile requires at least that many moves.

Section 06

Adversarial Search & Minimax

Everything we have studied so far assumes the agent is alone in its environment — the world does not actively oppose it. But in games like chess, checkers, or Tic-Tac-Toe, there is an opponent who will deliberately try to defeat us. The environment is now adversarial. Single-agent search is replaced by game-tree search.

The key insight is that in a two-player, zero-sum game, maximising our score is equivalent to minimising the opponent's score. This leads directly to the Minimax algorithm — the foundational algorithm for adversarial AI, and the technique that powers everything from classical chess engines to modern game-playing neural networks (which use a learned version of the same principle).

Game Formulation

Formal Game Definition

A two-player zero-sum game is defined by:

S₀: Initial state — the starting board position.
PLAYER(s): Whose turn it is (MAX or MIN).
ACTIONS(s): Legal moves available in state s.
RESULT(s, a): Transition model — the state after move a in state s.
TERMINAL-TEST(s): True when the game is over (win, loss, draw).
UTILITY(s, p): The numerical value of terminal state s for player p. e.g., +1 for WIN, −1 for LOSS, 0 for DRAW.

MAX wants to maximise UTILITY; MIN wants to minimise it. The players alternate turns.

The Minimax Algorithm

ALGORITHM: Minimax (Von Neumann, 1928 / Turing, 1953)

Base Case: If the current state s is a terminal state, return UTILITY(s).

MAX's turn: If PLAYER(s) = MAX, return the maximum over all successors: max_a MINIMAX(RESULT(s, a)). MAX chooses the move with the highest minimax value.

MIN's turn: If PLAYER(s) = MIN, return the minimum over all successors: min_a MINIMAX(RESULT(s, a)). MIN chooses the move with the lowest minimax value.

Optimal move: The move MAX should make from the root is argmax_a MINIMAX(RESULT(s₀, a)).

Classic Example Full Tic-Tac-Toe Minimax Trace — 3 Plies Deep

Consider a near-terminal Tic-Tac-Toe position: X's turn to move. We trace minimax for 3 levels (3 plies = MAX, MIN, MAX).

Figure 6.1 — Minimax tree for a near-end Tic-Tac-Toe game (3 plies). MAX (X) evaluates three possible moves. MIN (O) responds optimally. MAX chooses the move yielding the highest guaranteed value: "X at (1,2)" gives minimax value +1 (X wins with perfect play).

Why MIN's "best" move at the leftmost node gives −1

After X plays at position (0,1), O has a winning move (two O's in a row — play to complete). O will always take a win. So MIN correctly returns −1 for that branch. X must not play at (0,1) since it lets O win.

Alpha-Beta Pruning — Making Minimax Practical

Minimax is correct but slow: it evaluates every node of the game tree. For chess (branching factor ~35, depth ~80), this is astronomically expensive. Alpha-Beta Pruning cuts branches that cannot possibly affect the final minimax value — achieving the same result as minimax but exploring far fewer nodes.

Alpha-Beta Pruning

α (alpha) = the best value MAX has found so far (starts at −∞).
β (beta) = the best value MIN has found so far (starts at +∞).

A branch is pruned when: at a MIN node, the value found is ≤ α (MAX already has something better); or at a MAX node, the value found is ≥ β (MIN already has something better). The result is identical to minimax — no quality is lost.

Alpha-Beta Complexity Best case (perfect ordering): O(b^(d/2)) — effective branching = \sqrtb Average case (random order): O(b^(3d/4)) Worst case (reverse order): O(b^d) — no pruning possible For chess: b^(d/2) vs b^d \to 35^40 vs 35^80 = difference between tractable and impossible

Worked Example Alpha-Beta Pruning Trace

Figure 6.2 — Alpha-beta pruning in action. MIN node 2 returns value 2, which is ≤ α=3 (MAX already found 3 via MIN node 1). The entire right subtree (3 nodes) is pruned without evaluation — the final result is still exactly 3.

Feature	Minimax	Alpha-Beta Pruning
Correctness	✅ Finds optimal move	✅ Identical result to Minimax
Time (worst)	O(b^d)	O(b^d) — no improvement
Time (best)	O(b^d)	O(b^d/2) — squares root of tree!
Space	O(bd)	O(bd) — same
Move ordering	Not needed	Critical — better ordering = more pruning
Practical impact	Chess: b=35, d=8 → 35⁸ ≈ 2.25×10¹²	Alpha-beta: 35⁴ ≈ 1.5 million — 1.5 million vs 2.25 trillion!

Key Insight — Move Ordering is Everything

Alpha-beta's best-case O(b^d/2) assumes the best moves are examined first. In practice, AI chess and Go engines spend enormous effort on move ordering heuristics — trying killer moves, captures, and history heuristics first — so that alpha-beta can prune as much as possible. AlphaZero uses a neural network to order moves, achieving near-optimal pruning on Go's b=250 branching factor.

🎯 Quick Check: In alpha-beta pruning, a MIN node with current value v causes a β-cutoff (pruning) when:

✅ Correct! A MIN node causes a β-cutoff (or α-cutoff from MAX's perspective) when the value found v ≤ α. This means MAX already found a path with value α elsewhere. Since MIN will only return something ≤ v ≤ α from this node, MAX will never choose this branch — so there is no reason to evaluate its remaining children. The pruning is safe because it cannot change the root's minimax value.

Section 04

Exam Preparation Summary

This section consolidates every definition, formula, diagram, and comparison from Unit I into a compact revision reference. Work through each sub-section carefully. If you can answer the challenge quiz at the end without hesitation, you are ready for the exam.

All Key Concepts at a Glance

Concept	Definition / Formula	Key Detail
AI (Rational Agent def.)	System that acts to maximise expected performance	Most widely adopted definition (Russell & Norvig)
AI Technique	Knowledge-based method to navigate solution space	Must be generalisable, modifiable, usable with incomplete info
Agent	Entity with sensors (percepts) + actuators (actions)	Agent function: f: P* → A
PEAS	Performance, Environment, Actuators, Sensors	Used to specify any task environment
Rationality ≠ Omniscience	Rational = best decision with current knowledge	Omniscient = knows actual outcomes (impossible)
Utility Function	EU(a\|e) = Σ P(RESULT(s,a)\|e) × U(RESULT(s,a))	Used by utility-based agents to choose actions
Problem Formulation	Initial state, Actions, Transition model, Goal test, Path cost	5 components — memorise all five
Production System	IF–THEN rules + Working Memory + Control System	Match → Conflict resolution → Act → Goal check
Minimax	Max player picks max; Min player picks min at each level	Terminal: +1 win, 0 draw, −1 loss; Tic-Tac-Toe: always draw with perfect play
Admissible Heuristic	h(n) ≤ h*(n) always	Never overestimates; guarantees A* optimality

Agent Types Comparison

Agent Type	Memory	Goal	Utility	Learning	Example
Simple Reflex	❌ None	❌ None	❌ None	❌ None	Thermostat
Model-based Reflex	✅ State model	❌ None	❌ None	❌ None	Robot with map
Goal-based	✅ State model	✅ Goal state	❌ None	❌ None	GPS navigator
Utility-based	✅ State model	✅ Goal state	✅ Utility fn.	❌ None	Self-driving car
Learning Agent	✅ State model	✅ Goal state	✅ Utility fn.	✅ Yes	AlphaGo, GPT

Environment Properties — Quick Reference

Environment Dimension	Easier End	Harder End	Why it Matters
Observability	Fully observable	Partially / Non-observable	Partial obs. → agent must maintain internal state estimate
Agents	Single agent	Multi-agent (adversarial)	Multi-agent → need game theory, adversarial search
Determinism	Deterministic	Stochastic	Stochastic → need probability, expected utility
Episodicity	Episodic	Sequential	Sequential → current action affects future choices
Dynamics	Static	Dynamic	Dynamic → agent must act under time pressure
Continuity	Discrete	Continuous	Continuous → infinite state space; needs calculus-based methods

Common Exam Mistakes

Watch Out!

Mistake 1: Confusing "rational" with "omniscient" — rational means best decision given current knowledge, NOT knowing the true future outcome.

Mistake 2: Saying Tic-Tac-Toe can be won by optimal AI — with perfect play from both sides, Tic-Tac-Toe is always a draw (provable by minimax).

Mistake 3: Confusing the Critic and the Learning Element in a learning agent — the Critic evaluates, the Learning Element modifies the performance element.

Mistake 4: Listing only 4 PEAS components without explaining each one for the specific agent asked — examiners expect the full table for the named agent.

Mistake 5: Calling DFS "complete" — it is NOT complete in infinite or cyclic state spaces. Only BFS (or iterative deepening DFS) is complete.

Typical Exam Question Types

Question Pattern	Required Approach	Key Terms to Include
"Define Artificial Intelligence"	Give all 4 definitions (2×2 grid); state which Russell & Norvig prefer	Rational agent, Turing Test, laws of thought, cognitive modelling
"Give PEAS for [Agent X]"	Draw 5-column table: agent, performance, environment, actuators, sensors	Specific performance metrics (not vague like "do well")
"Describe environment properties"	List all 6–7 dimensions; classify a given problem for each	Fully/partially observable, deterministic/stochastic, etc.
"Explain production system"	Give 3 components + 4-step execution cycle	Working memory, conflict set, conflict resolution, firing
"Define state space, formulate problem"	Give all 5 problem components; draw state space graph	Initial state, actions, transition model, goal test, path cost
"What are issues in search program design?"	Completeness, optimality, time/space complexity, heuristics, branching factor	Combinatorial explosion, admissible heuristic

One-Line Summaries

Unit I Core Idea

Rational Agents

AI = building agents that act rationally in environments by selecting the best-expected action.

Agent Architecture

5 Types

Reflex → Model-based → Goal → Utility → Learning. Each adds one capability over the previous.

Problem Formulation

5 Components

Initial state · Actions · Transition model · Goal test · Path cost. Define all five to formulate any search problem.

Production System

Match → Fire

Rules fire against Working Memory through a 4-step cycle: Match → Resolve → Act → Goal-check.

Tic-Tac-Toe Result

Always Draw

With perfect minimax play from both sides, Tic-Tac-Toe always ends in a draw — provable by exhaustive search.

Search Challenge

Exponential

Combinatorial explosion (b^d nodes) makes brute-force search infeasible — heuristics are essential for real problems.

Challenge Quiz — Exam-Level Question

🎯 Challenge: An AI agent drives a taxi in a city. It can see only the immediate road ahead (not the full city map), other cars behave unpredictably, and the agent's choices now (e.g. which route to take) affect fuel cost and time for the rest of the trip. Which combination of environment properties CORRECTLY describes this taxi-driving environment?

✅ Correct! Let's verify each dimension: Partially observable — the agent sees only the immediate road, not the full city map. Stochastic — other cars behave unpredictably, so the same action can lead to different outcomes. Sequential — current route choices affect future fuel cost and arrival time. Dynamic — the city traffic changes while the agent is deciding. Continuous — steering angle, speed, and position are continuous variables. The taxi driving environment is considered one of the hardest environment types in AI.