ACI — slides explained, in plain words.

This unpacks the Artificial & Computational Intelligence (AIMLCZG557) lecture slides — contact sessions CS1 through CS8, the mid-semester syllabus — rewritten in plain, easy language. Not bullet points: the full concept behind each slide, the why, and worked intuition. Textbook is Russell & Norvig, Artificial Intelligence: A Modern Approach (4th ed.). Built lecture by lecture; more sections land as I work through the decks.

CS1 — Introduction to AI & intelligent agents

CS1 · Module 1

The first session answers three questions: what is AI, where did it come from, and what is the basic object we study — the agent. The whole course is really about one thing: designing rational agents. Everything else (search, logic, probability, learning) is a technique an agent uses to act well.

A one-minute history of AI

AI as a named field starts in 1956 at the Dartmouth workshop, where the term "Artificial Intelligence" was coined. But the ideas are older — formal logic (Aristotle), the Turing Test (1950), the first perceptron (1957), ELIZA the first chatbot (1965). The field went through two "AI winters" (roughly 1974–80 and 1987–93) where funding and hype collapsed because the promises outran the technology.

The modern explosion is recent: backpropagation made multi-layer networks trainable, then AlexNet (2012) showed deep learning crushing image recognition, "Attention Is All You Need" (2017) introduced the Transformer, and from there BERT, GPT-1/2/3, ChatGPT (2022) and beyond. The milestone to remember for exams: 1956 = AI is born; 1950 = Turing Test; 2017 = Transformer.

Foundations — which fields fed into AI

AI didn't appear from nowhere; it borrows from many disciplines. You should be able to name what each contributed:

Field	What it gave AI
Philosophy	Logic, methods of reasoning, the idea that the mind is a physical system operating by rules; foundations of learning, language, rationality.
Mathematics	Formal logic (propositional, first-order), proof, computation, algorithms, probability.
Economics	Formal theory of rational decisions; decision theory + probability for choosing under uncertainty; game theory; Markov decision processes.
Neuroscience	How real brains work, and how they compare to computers.
Psychology	How we think and act; cognitive science treats the brain as an information-processing machine.
Computer engineering	The fast machines that make AI runnable at all.
Control theory / cybernetics	Systems that sense, act, and self-correct toward a goal.
Linguistics	Structure of language — essential for natural-language AI.

What is intelligence? What is artificial intelligence?

Intelligence (loosely) is the capacity for learning, reasoning, understanding, and acting in the world: perceiving, reasoning (proving theorems, diagnosis), planning (taking decisions), learning and adapting, and understanding text/speech/scenes. The slides nudge you with awkward questions — are humans always intelligent? can non-human behaviour be intelligent? — to show "intelligence" is slippery to define.

So AI researchers define the field along two axes: do we care about thought or behaviour, and do we measure against humans or against an ideal of rationality? That gives a famous 2×2:

	Human-like	Rational (ideal)
Thinking	(1) Thinking humanly — cognitive modelling	(3) Thinking rationally — laws of thought
Acting	(2) Acting humanly — the Turing Test	(4) Acting rationally — the rational agent

This course commits to box (4): acting rationally. Here's why each box matters, and why (4) wins.

(1) Thinking humanly — the cognitive-modelling approach

Goal: make the machine think the way a human actually thinks. Problem: we barely understand human thinking. We capture it through introspection, psychological experiments, and brain imaging — all imperfect. The famous analogy: aeronautical engineers don't try to build planes that flap so convincingly that real pigeons are fooled — they build things that fly. Likewise, "Deep Blue" beat the world chess champion without thinking like a human. Newell & Simon's General Problem Solver (1961) was the early flagship — notable as the first system that separated knowledge from the inference engine.

(2) Acting humanly — the Turing Test

Alan Turing's idea: stop arguing about whether a machine "thinks," and just test behaviour. An interrogator chats (via text, through a wall) with a human and a machine. If the interrogator can't reliably tell which is which, the machine passes. To pass, a machine needs NLP (to converse), knowledge representation (to store what it knows), automated reasoning (to answer and draw conclusions), and machine learning (to adapt). The Total Turing Test adds computer vision and robotics so the machine can perceive and manipulate the physical world.

(3) Thinking rationally — the laws of thought

Aristotle asked: what are correct argument structures? He invented formal logic and syllogisms ("In all boring classes, students sleep; this is a boring class; therefore students sleep here"). If we can encode knowledge as logical statements, a machine can derive correct conclusions. Two problems: (1) not all intelligent behaviour goes through logical deliberation — reflexes don't; and (2) it's computationally explosive — even a few hundred facts can blow up, so pure logic doesn't scale.

(4) Acting rationally — the rational-agent approach (this course)

A rational agent acts to achieve the best outcome — or, under uncertainty, the best expected outcome. "Acting rationally" is broader and more practical than "thinking rationally" because:

• It includes correct inference (logic) when that helps — e.g. deciding when to brake.
• It allows acting without a guaranteed-correct inference — e.g. a self-driving car choosing the least-bad action in an unavoidable accident.
• It allows acting without inference at all — reflexes, like recoiling from a hot stove.

"Doing the right thing" means the action expected to maximise goal achievement given the information available. That's a clear, measurable engineering target — which is exactly why the field (and this course) builds on it.

Risks of AI

The slides flag that powerful AI carries real risks — worth listing because ethics shows up later in the course:

• Lethal autonomous weapons — systems that locate, select and kill targets with no human in the loop; the danger is scalability (a few people could deploy huge numbers).
• Surveillance & persuasion — mass monitoring, and tailoring information feeds to manipulate behaviour.
• Biased decision-making — ML used for parole, loans, hiring can encode race/gender bias, often because the training data already reflects societal bias.
• Impact on employment — shifts wealth from labour to capital, worsening inequality even while raising overall productivity.
• Safety-critical use — self-driving cars, water systems; AI needs engineering/ethical standards like other safety fields.
• Cybersecurity — AI both defends against and strengthens attacks (automated phishing, malware); plus deepfakes and sustainability concerns.

Agents — the core object of the course

An agent is anything that perceives its environment through sensors and acts on it through actuators. That's the whole definition, and it covers a lot:

• Human agent — sensors: eyes, ears; actuators: hands, legs, mouth.
• Robotic agent — sensors: cameras, range finders; actuators: motors.
• AI/softbot agent — perceives a digital environment, processes information, decides, and acts toward an assigned objective.

Agent function and agent program

Formally, the agent function maps every possible percept history to an action: f : P* → A (P* is the sequence of everything perceived so far; A is the set of actions). The agent program is the concrete implementation that runs on the hardware to produce that function. The slogan to memorise:

agent = architecture + program

The architecture is the physical machine (sensors, actuators, compute); the program is the logic that decides what to do. Same architecture can run different programs.

The vacuum-cleaner agent (the running example)

A tiny world with two squares, A and B. The agent perceives its location and whether that square is dirty — e.g. [A, Dirty]. Its actions are Left, Right, Suck, NoOp. You can write the agent function as a table mapping percept sequences to actions:

Percept sequence	Action
[A, Clean]	Right
[A, Dirty]	Suck
[B, Clean]	Left
[B, Dirty]	Suck
[A, Clean], [A, Clean]	Right
[A, Clean], [A, Dirty]	Suck

The point: the agent function is just "given what I've seen, do this." A real program implements this rule compactly instead of storing an infinite table.

Rational agents, performance measure, and rationality ≠ omniscience

A rational agent does "the right thing" — the action that makes it most successful, judged by a performance measure (an objective success criterion). For the vacuum agent that could be dirt cleaned, time taken, electricity used, noise generated. Choosing a good performance measure is itself a design decision — reward "amount of dirt cleaned" and a clever agent might dump dirt out to clean it again.

The textbook definition of an ideal rational agent: "for each possible percept sequence, do whatever action is expected to maximise its performance measure, given the evidence perceived so far and its built-in knowledge." Two subtleties:

• Rationality is not omniscience. An omniscient agent knows the actual outcome of every action; a rational agent only maximises expected performance given what it could reasonably know. Crossing a road rationally and getting hit by a freak falling object doesn't make you irrational.
• Rational agents gather information and explore — they can act to improve future percepts — and a rational agent is autonomous if its behaviour comes from its own experience (it learns and adapts), not just from what the designer hard-wired.

PEAS — how to specify a task environment

Before designing any agent you must describe the problem. The standard tool is PEAS:

• P — Performance measure (how success is judged)
• E — Environment (where it operates)
• A — Actuators (how it acts)
• S — Sensors (how it perceives)

Example — an automated taxi driver:

P	E	A	S
Safe, fast, legal, comfortable trip; maximise profit	Roads, other traffic, signals, pedestrians, customers	Steering, accelerator, brake, signal, horn	Cameras, sonar, speedometer, GPS, odometer, engine sensors

Get PEAS right and the rest of the design (which agent type, which algorithms) follows from it. CS2 picks up here with the different types of agents and environments.

CS2 — Intelligent agents, environments & problem-solving

CS2 · Module 1–2

CS2 builds on CS1 in three moves: (1) classify the environment an agent lives in, (2) classify the agent itself into five standard types, and (3) turn "act rationally" into a concrete recipe — the problem-solving agent that formulates a problem, searches for a solution, and executes it. This last part sets up all the search algorithms in CS3–CS5.

PEAS again — two more worked examples

Reinforcing CS1's PEAS, with non-driving examples:

System	P	E	A	S
Medical diagnosis	Healthy patient, minimise costs & lawsuits	Patient, hospital, staff	Screen display: questions, tests, diagnoses, treatments, referrals	Keyboard entry of symptoms, findings, answers
Part-picking robot	% of parts in correct bins	Conveyor belt with parts, bins	Jointed arm and hand	Camera, joint-angle sensors

Properties of environments (the big classification)

Before choosing an algorithm you classify the environment along six axes. Each axis changes how hard the problem is and which agent design fits.

Axis	Meaning & example
Fully vs partially observable (vs non-observable)	Do the sensors reveal the complete state at each step? Chess/tic-tac-toe = fully observable; poker = partially (you can't see opponents' cards). Think fully-lit room vs dimly-lit vs pitch dark.
Deterministic vs stochastic	Is the next state fully fixed by the current state + action? Calculator = deterministic; weather, dice, a football robot's shot = stochastic. "Same action → same result" = deterministic; "same action → different results" = stochastic. (If only other agents add the unpredictability, it's called strategic.)
Episodic vs sequential	Episodic: each decision is independent (classify this image: is there a cat? spam filter). Sequential: now's decision affects the future, so you must plan ahead (Pac-Man, an investment-portfolio bot).
Static vs dynamic (vs semi-dynamic)	Does the world change while the agent is thinking? Crossword/Rubik's cube = static; driving in rain = dynamic. Semi-dynamic: world is fixed but your score changes with time — chess with a clock.
Discrete vs continuous	Countable, finite states/actions (chess moves) = discrete; infinitely-valued (speed, position, angle in driving) = continuous.
Single vs multi-agent	Are there other agents that sense and act? Multi-agent splits into cooperative, competitive, and self-interested.

The five agent types

Agents are classified by how much internal machinery they have. The one-word summary the slides give is worth memorising: model-based → remembers; goal-based → aims; utility-based → optimises; learning → improves.

Type	How it decides	Limitation it fixes
Simple reflex	Condition–action rules on the current percept only ("if dirty then Suck"). No memory.	Baseline. Fails when the current percept isn't enough.
Model-based reflex	Keeps internal state + a model of how the world evolves and what its actions do, so it can act in a partially observable world.	Adds memory — handles partial observability.
Goal-based	Considers the future: "what will the world be like if I do action A?" and picks actions that reach a goal.	Adds look-ahead / planning.
Utility-based	When many action sequences reach the goal, uses a utility function ("how happy will I be in that state?") to pick the best, and to trade off conflicting goals under uncertainty.	Adds quality/preference, not just "goal or not".
Learning	Improves from experience over time.	Adds adaptation — no need to hand-code everything.

Inside the learning agent

The learning agent has four parts — a common exam diagram:

• Performance element — picks actions from percepts (this is "the agent" in the earlier types).
• Learning element — improves the performance element so it picks better actions (optimises the utility).
• Critic — gives feedback on how well the agent did, judged against a fixed performance standard. (E.g. brake too hard → critic returns −2.)
• Problem generator — deliberately suggests sub-optimal, exploratory actions so the agent discovers things it would never learn by always playing safe.

Table-lookup agent — and why it fails

You could implement any agent function as a giant table: look up the whole percept sequence, return the stored action. It's correct but useless in practice — the drawbacks are the point: the table is astronomically huge, takes forever to build, has no autonomy, and even with learning would take far too long to fill. Real agents need compact programs (rules, models, search) instead of tables.

Problem-solving agents — formulate, search, execute

This is the heart of CS2 and the gateway to search. A problem-solving agent works in three steps:

1. Formulate — define the problem and its components.
2. Search — find a sequence of actions that reaches the goal (a search algorithm takes the problem in, returns an action sequence).
3. Execute — carry out that fixed sequence of actions.

This works under simplifying assumptions: the environment is observable, discrete, known, and deterministic. Under those, the solution is just a fixed sequence of actions computed up front.

Problem formulation — the five components

Any search problem is defined by five things (memorise these — they're examined directly):

Component	Meaning	Romania example (Arad→Bucharest)
Initial state	Where the agent starts.	In(Arad)
Actions (operators)	What's applicable in a state.	ACTIONS(In(Arad)) = {Go(Sibiu), Go(Timisoara), Go(Zerind)}
Transition model	Result of an action in a state: RESULT(s,a).	RESULT(In(Arad), Go(Sibiu)) = In(Sibiu)
Goal test	Is this state a goal?	IsGoal(In(Bucharest)) = Yes
Path cost	Numeric cost of a path (sum of step costs).	cost(In(Arad), Go(Sibiu)) = 140 km

Solution = a path (sequence of actions) from initial to goal; an optimal solution is the lowest path cost.

States, state space, nodes

A state is all the information needed to decide. The state space is the set of all states reachable from the initial state — a graph where nodes are states and arcs are actions; a path is a sequence of states joined by actions. State-space representation underlies nearly every AI method.

Two toy problems to know:

• Vacuum world — 2 locations × dirt-or-not, with the agent in one location: 2 × 2² = 8 states; actions Left, Right, Suck; goal = both squares clean; each step costs 1.
• 8-puzzle — slide tiles into the blank. States = 9!/2 (only half the permutations are reachable, so divide by 2); actions = move the blank Up/Down/Left/Right; goal = the target configuration; each step costs 1.

Search strategies and how we judge them

A search strategy is just the rule for picking which node to expand next. The frontier (the set of nodes waiting to be expanded) is stored in a queue, and the queue discipline is the strategy: FIFO (oldest first → breadth-first), LIFO (newest first → depth-first), or a priority queue (best first). Every strategy is evaluated on the same five yardsticks:

Criterion	Question it answers
Completeness	Does it always find a solution if one exists?
Time complexity	How many nodes are generated?
Space complexity	Max nodes held in memory at once?
Optimality	Does it always find the least-cost solution?
Systematicity	Does it visit each node at most once?

Time and space are expressed using three numbers: b = branching factor (max successors per node), d = depth of the shallowest goal, m = maximum depth of the state space (possibly ∞).

Two families: uninformed vs informed

Search splits into two big families — the whole of CS3–CS5 lives here:

• Uninformed (blind) search — uses only the problem definition, no hint about which non-goal state is closer to the goal. Members: BFS, Uniform-Cost Search, DFS, Depth-Limited Search, Iterative-Deepening DFS, Bidirectional. They work but are slow because they search blindly.
• Informed (heuristic) search — uses an extra heuristic estimate of how promising a state is, so it can head toward the goal. Members: Best-First Search, A*, AO*.

CS3 — Uninformed & informed (heuristic) search

CS3 · Module 2

CS3 is the algorithms lecture. It works through the uninformed (blind) searches, then adds a heuristic to get informed search — Greedy Best-First and the star of the course, A* — and finishes with the two properties that make A* trustworthy: admissibility and consistency.

The uninformed searches, compared

Recall b = branching factor, d = depth of shallowest goal, m = max depth. The four to know cold:

Algorithm	Frontier	Complete?	Optimal?	Time	Space
BFS (breadth-first)	FIFO queue	Yes (b finite)	Only if step costs equal	\(O(b^d)\)	\(O(b^d)\)
DFS (depth-first)	LIFO stack	Yes in finite spaces	No	\(O(b^m)\)	\(O(bm)\)
UCS (uniform-cost)	priority queue by g(n)	Yes	Yes	\(\sim O(b^{1+\lfloor C^*/\varepsilon\rfloor})\)	large
IDS (iterative deepening)	LIFO, repeated	Yes (b finite)	Only if step costs equal	\(O(b^d)\)	\(O(bd)\)

BFS is "cautious" — it checks all paths of length i before length i+1, so it finds the shallowest goal, but its memory blows up (it must hold an entire level). DFS is "aggressive" — it dives down a complete path first, using a stack; memory is tiny (O(bm), only the current path + siblings) but it can go down the wrong infinite branch and isn't optimal. (Applications mentioned: BFS for shortest path / bipartite check; DFS for connectivity / topological sort.)

Uniform-Cost Search — cheapest first

UCS expands the frontier node with the lowest path cost g(n), not the shallowest. The frontier is a priority queue ordered by g(n). Two subtleties make it correct: the goal test is applied when a node is expanded, not when generated (a goal generated early may not be on the cheapest path), and if a cheaper path to a frontier node is found, it's replaced. The slides walk Sibiu→Bucharest: expand Sibiu → frontier {RV 80, Fagaras 99}; expand RV (cheapest) → adds Pitesti 177; expand Fagaras → generates Bucharest 310 (don't stop — not tested at generation); expand Pitesti → finds Bucharest via 278, replaces the 310; finally expand Bucharest (cheapest, 278) → goal test passes → return. That replacement is exactly why UCS is optimal and greedy/BFS aren't.

Iterative Deepening Search

IDS runs Depth-Limited Search with limit ℓ = 0, 1, 2, … until the goal is found. It marries DFS's tiny memory (O(bd)) with BFS's completeness and shallowest-goal optimality (when step costs are equal). Re-exploring shallow nodes repeatedly sounds wasteful, but the cost is dominated by the deepest level, so time is still O(b^d) — the same order as BFS. This is the preferred uninformed search when the search space is large and depth is unknown.

Informed (heuristic) search

The idea: be smart about which paths to try. A node is picked for expansion using an evaluation function that estimates cost to the goal. The key ingredient is a heuristic function h(n) — it takes the current state and estimates how close it is to the goal. A heuristic doesn't guarantee the best answer, but it gets a good answer in reasonable time. For route-finding the classic heuristic is straight-line distance to the destination.

Greedy Best-First Search — f(n) = h(n)

Greedy expands whichever node looks closest to the goal — it uses f(n) = h(n) only, ignoring the cost already spent. On the Romania map it goes Arad → Sibiu → Fagaras → Bucharest because each step picks the smallest straight-line distance. Fast, but:

• Not optimal — it only optimises the immediate next step, so it can take a longer total route (the true shortest is Arad→Sibiu→RV→Pitesti→Bucharest).
• Not complete — it can run into dead ends or loops because the heuristic is just an approximation.
• Time and space O(b^m) in the worst case.

A* Search — f(n) = g(n) + h(n)

A* is greedy's fix: it adds back the cost already spent. It expands the node minimising the evaluation function

f(n) = g(n) + h(n)

where g(n) = cost so far to reach n, h(n) = estimated cost from n to goal, and f(n) = estimated total cost of a path through n. By balancing "how far I've come" against "how far I have to go," A* avoids expanding paths that are already expensive. It's the standard for pathfinding in games and maps. On Romania, A* expands Arad(366) → Sibiu(393) → then weighs Fagaras(415=239+176) vs RV(413=220+193), follows RV→Pitesti(417), and reaches Bucharest at 418 — the true optimal route, which greedy missed.

When is A* optimal? Admissibility & consistency

A* only guarantees the optimal path if its heuristic obeys conditions. These are heavily examined.

Property	Definition	Plain meaning
Admissible	h(n) ≤ h*(n) where h*(n) is the true cost to the goal	Never overestimates — the heuristic is optimistic. Straight-line distance is admissible because real roads can't be shorter than a straight line.
Consistent (monotonic)	h(n) ≤ c(n,n′) + h(n′) for every node n and successor n′	The estimate drops gradually — never by more than the actual step cost (a triangle inequality). Guarantees f never decreases along a path, so once A* expands a node, the best path to it is already found.

What makes a good heuristic?

A good heuristic is admissible (never overestimates), consistent (obeys the triangle inequality), and informative (close to the true cost). Between two admissible heuristics, the one with larger values h₂(n) ≥ h₁(n) dominates — it gives a stronger estimate and expands fewer nodes. The extremes show the trade-off:

Heuristic	Effect on A*
h(n) = 0	Always optimal, but slow — A* degenerates into Uniform-Cost Search.
Admissible but weak	Optimal, but explores many nodes.
Admissible & informative	Optimal and efficient — the sweet spot.
Overestimating	May be faster, but can lose optimality.
Inconsistent	May force re-opening nodes to stay optimal.

CS4 — Designing heuristics & local search

CS4 · Module 2

CS4 has two halves. First: where do good heuristics come from? (A* is only as good as its h.) Second: a different style of search entirely — local search, where you don't care about the path, only the final state, and you improve one configuration step by step. This is also the gateway to the computational-intelligence methods (genetic algorithms, swarm) later in the course.

Designing heuristics

Since the heuristic decides how well A* performs, we want one that is admissible, consistent, informative, and cheap to compute. How good a heuristic is can be measured by the effective branching factor b*: if the search generates N nodes and finds the solution at depth d, then N+1 = 1 + b* + (b*)² + … + (b*)^d. A b* close to 1 means a very focused, efficient search. There are four standard recipes for inventing heuristics:

1. Relaxed problems

A relaxed problem removes some constraints from the original. Because the relaxed problem is easier, its solution cost is a lower bound on the real cost — which is exactly what "admissible" means. The 8-puzzle is the classic illustration:

Problem version	Constraint removed	Heuristic it yields
Original	—	(true cost)
Relaxed 1	Tiles can jump anywhere	h₁ = number of misplaced tiles
Relaxed 2	Tiles can move through each other	h₂ = sum of Manhattan distances

Both are admissible; h₂ dominates h₁ (it's larger but still never overestimates), so A* with h₂ explores fewer nodes. For the deck's sample board h₁ = 8 (misplaced) and h₂ = 18 (total Manhattan distance). For N-queens the slides try several: number of conflicting pairs (minimise), non-conflicting pairs (maximise), number of "safe" queens.

2. Pattern databases

Solve a sub-problem exhaustively (say, just getting tiles 1–4 home), store the exact cost of every configuration of that sub-problem in a database, then during search just look up the cost. The stored sub-problem costs are admissible heuristics for the full problem.

3. Landmarks

Pick a few landmark states that are easy to reach from everywhere, and pre-compute distances to them. The heuristic for a node n is its known distance to the nearest landmark. This is how real route-planners scale — you can't pre-compute distance between every pair of street corners, so you anchor on landmark cities. Often more informative than simple relaxed-problem heuristics on huge graphs.

4. Learning heuristics from experience

Let the machine learn a heuristic. Metalevel learning = the AI watches its own search and learns to avoid dead ends. Feature learning = solve thousands of random instances, find which features (e.g. how many tiles are out of order) predict the true cost, and combine them. The deck's reference paper trains a neural network h(s, θ) (s = grid state, θ = learned weights; 7 conv layers + CoAt blocks → one scalar) and plugs that learned h into both A* (f = g + h, optimal-ish) and Greedy Best-First (f = h, faster, not optimal) on Sokoban, mazes-with-teleports, and the sliding-tile puzzle.

Local search & optimization

Everything before CS4 treated the path to the goal as the answer. But for many problems — 8-queens, scheduling, hyperparameter tuning, VLSI layout — the path is irrelevant; the final configuration is the solution. These are optimization problems: every state has an objective / fitness function, and the goal is the state with the best (max or min) value.

Local search keeps a single current state and repeatedly moves to a neighbouring state to improve it — ignoring paths entirely. Its big advantages: tiny memory (it holds one state, not a tree) and it works in huge or even infinite/continuous state spaces. The methods split into two families:

Single-instance (local) search	Population-based search
Hill Climbing (& variants), Simulated Annealing, Local Beam Search, Tabu Search	Genetic Algorithms, Ant Colony Optimization, Particle Swarm Optimization

The single-instance ones come now; the population-based ones (the "computational intelligence" half of the course) come in later sessions.

Hill Climbing

The simplest local search: from the current state, always move to the highest-valued neighbour; stop when no neighbour is better. The textbook loop:

current ← initial state
loop:
    neighbor ← highest-valued successor of current
    if VALUE(neighbor) ≤ VALUE(current): return current   # local optimum
    current ← neighbor

For 4-queens the fitness is the number of non-conflicting (or conflicting) queen pairs, and each move slides one queen within its column to the best-scoring position. It's fast and uses almost no memory — but it's greedy and short-sighted.

Escaping local optima — the variants

Variant	Idea	Stop / behaviour
Random-restart hill climbing	Run hill climbing from many random starting states; keep the best result.	Stop on: (1) no better successor, (2) global optimum reached, or (3) a preset number k of restarts done.
Stochastic hill climbing	Pick the next state probabilistically, weighted by fitness, instead of always the steepest. Less greedy, explores more.	Chooses among successors by probability ∝ fitness.
Simulated annealing	Sometimes accept a worse move to escape local optima. Accept an improving move always; accept a worsening move (ΔE<0) with probability e^(ΔE/T). Temperature T starts high (lots of random jumps) and cools (becomes greedy).	As T→0 it behaves like plain hill climbing.

CS5 — Beam search, genetic algorithms, online search & ACO

CS5 · Module 2–3

CS5 recaps hill climbing (see CS4) and then adds the rest of the local-search toolkit: local beam search (track several states at once), the first population-based method — genetic algorithms — plus the distinction between offline and online search, and an intro to Ant Colony Optimization. This is the bridge from classical AI search into the "computational intelligence" (nature-inspired) half of the course.

Local beam search

Hill climbing keeps one state. Local beam search keeps k states at once: generate all successors of all k states, then keep the best k overall and repeat. It's not the same as running k independent hill climbs — good states attract effort, because all successors are pooled and the best k are chosen together, so promising regions get more attention.

• Stochastic beam search — instead of keeping the strict top k, choose the k successors probabilistically, weighted by fitness. This keeps diversity and avoids all k states collapsing onto the same peak (the failure mode of plain beam search).

Genetic algorithms (the first population method)

A genetic algorithm (GA) is a population-based optimizer inspired by evolution: inheritance, selection, crossover (recombination), and mutation. You start with a population of random candidate solutions and evolve it generation by generation; each generation, fitter individuals are more likely to reproduce. There's no convergence guarantee — you stop after a max number of generations or when a good-enough solution appears. The vocabulary maps biology onto search:

GA term	Biology	In the algorithm
Population	Group of individuals	Collection of candidate states
Individual	An organism	One candidate solution
Fitness	Health / survival odds	Objective function — how close to the solution
Selection	Survival of the fittest	Pick fitter states to reproduce
Crossover	Mating / recombination	Swap segments between two parent states
Mutation	Random DNA change	Randomly alter part of a state

The loop (illustrated on 8-queens, where a state is encoded as one column-position per queen and fitness = number of non-attacking pairs, threshold 28 for 8-queens / 6 for 4-queens):

1. Represent individuals (e.g. the string 1 4 2 2 = queen rows per column).
2. Initialize a population of k random states.
3. Fitness — score every individual.
4. Selection — pick parents weighted by fitness, e.g. the roulette wheel: each individual gets a wheel slice proportional to its fitness; spin to pick. (Also tournament, rank selection.)
5. Crossover — combine two parents to make children. Strategies: single-point (cut at one position, swap tails), multi-point, or uniform (each gene from a randomly chosen parent).
6. Mutation — randomly tweak a gene to inject diversity (escape local optima).
7. Repeat until an individual hits the fitness threshold or time runs out.

function GENETIC-ALGORITHM(population, FITNESS-FN) returns an individual
  repeat
    new_population ← empty
    for i = 1 to SIZE(population):
        x ← RANDOM-SELECTION(population, FITNESS-FN)   # weighted by fitness
        y ← RANDOM-SELECTION(population, FITNESS-FN)
        child ← REPRODUCE(x, y)                        # crossover
        if (small random probability): child ← MUTATE(child)
        add child to new_population
    population ← new_population
  until fit enough, or out of time
  return best individual

Offline vs online search

Everything so far was offline search: the agent has a complete model of the problem before acting — the whole state space is known, it can simulate actions, produce a full plan, then execute. BFS, UCS, A*, hill climbing, and beam search are all offline. A route planner that already has the full map is offline.

Online search agents don't know the environment in advance. They must act, observe the result, update their knowledge, and continue — planning and execution interleave. This is essential when the world is unknown, dynamic, or too big to model. A robot exploring an unfamiliar building can't plan the whole route up front; it moves, senses nearby paths, updates its map, and decides the next step. Online search is where the exploration vs progress-toward-goal trade-off becomes unavoidable.

Ant Colony Optimization (ACO)

ACO is a population-based, nature-inspired method modelled on how real ants find short paths: they lay pheromone on trails, shorter trails get traversed faster so accumulate more pheromone, and pheromone evaporates over time so bad trails fade. Many simple agents (ants) thus collectively discover good routes. The standard parameters:

Symbol	Meaning
N	Number of ants (N > 1)
τij	Pheromone deposited on edge i→j
ηij	Cost / desirability of edge i→j
α, β	Importance of pheromone vs route cost
ρ	Evaporation coefficient (0 < ρ < 1)
Q, fk	Pheromone constant; route cost found by ant k

The mechanics: each ant chooses its next node by a transition probability that favours edges with more pheromone (\(\tau^\alpha\)) and lower cost (\(\eta^\beta\)):

After a tour, pheromone is updated — old pheromone evaporates and new is laid in proportion to route quality:

Evaporation \((1{-}\rho)\) drives exploration (forget stale trails); reinforcement \((Q/f_k)\) drives exploitation (strengthen good trails). It stops after a set number of iterations — with the caveat that an ant can "drop" if it hasn't reached the destination before the iteration cap.

CS6 — ACO in action + Neural Architecture Search

Lecture CS#6 · ant colony optimization worked example · neuroevolution · NEAT → DeepNEAT → CoDeepNEAT

CS6 has two halves. First it takes the Ant Colony Optimization machinery from CS5 and runs it by hand on a small Travelling Salesman Problem so you can see every number move. Then it pivots to a bigger idea: instead of using evolution to find a route, use it to design a neural network — Neural Architecture Search (NAS), the "era of self-designing AI."

ACO on the Travelling Salesman Problem — a full walkthrough

The Travelling Salesman Problem (TSP): visit every city exactly once and return to the start, with the shortest total distance. With n cities there are (n−1)!/2 possible tours — it blows up fast, so we don't brute force it. ACO lets a colony of ants discover a short tour by laying pheromone.

The deck uses 5 cities, the ant starting at node 4, and these settings:

Parameter	Value	What it does
α (alpha)	0.5	Weight on pheromone — how much an ant trusts the trail
β (beta)	0.75	Weight on visibility η=1/distance — how much it trusts "shorter is better"
ρ (rho)	0.1	Evaporation — 10% of old pheromone fades each update
Q	100	Pheromone constant — total laid is Q/(tour cost)

The mechanics from CS5 stay the same; here's how one ant builds a tour step by step:

1. Stand at node 4. List the cities not yet visited (1, 2, 3, 5).
2. Score every reachable next city with the transition rule \(P_{ij} = (\tau_{ij})^\alpha(\eta_{ij})^\beta \,/\, \sum(\tau_{ih})^\alpha(\eta_{ih})^\beta\). Here \(\eta_{ij} = 1/\text{distance}(i,j)\), so close cities get a higher \(\eta\). The numerator rewards "lots of pheromone and short edge"; the denominator normalises so the probabilities over all unvisited cities sum to 1.
3. Pick the next city probabilistically from those scores (roulette-wheel style — higher NTP = more likely, but not guaranteed; that randomness is what keeps the colony exploring).
4. Move, mark the city visited, repeat until all five are covered, then return to the start node 4 to close the loop.

Working it through with these numbers, the ant builds the tour 4 → 2 → 3 → 5 → 1 → 4. Once the tour is complete you compute its total cost \(f_k\), then update pheromone on every edge:

So every edge first loses 10% (evaporation), and the edges on this tour gain 100/(tour length). A shorter tour means a bigger deposit, so good routes get reinforced harder. Run many ants over many iterations and the pheromone concentrates on the genuinely short edges — the colony converges on a near-optimal tour without anyone ever computing all (n−1)!/2 possibilities.

The pivot: from routes to architectures

Second half of CS6. Designing a neural network by hand is hard — how many layers? what filter sizes? which connections? The search space is astronomically large and humans are the bottleneck. Neural Architecture Search asks: what if evolution designs the network for us? CS6 frames this as bilevel optimization:

Level	What evolves	How
High level — "DNA"	The architecture / topology (which layers, how connected)	Evolutionary algorithm (mutation + crossover over generations)
Low level — "weights"	The numbers inside each network	Ordinary gradient descent / backprop

So the genetic algorithm searches structures, and for each candidate structure normal training fills in the weights. The structure is the genotype; the trained network is the phenotype.

Neuroevolution and NEAT

Neuroevolution = using genetic algorithms to evolve neural networks. The core loop is exactly the GA loop from CS5: (1) create a population of networks, (2) train each, (3) measure fitness (how well it performs), (4) select the best, (5) breed new ones via mutation and crossover, (6) repeat.

NEAT (NeuroEvolution of Augmenting Topologies) is the classic method. Key ideas:

• A network is a graph — nodes are neurons, edges are connections (with weights).
• It starts minimal (tiny networks, few connections) and augments — adds nodes and connections over generations, growing complexity only when it helps.
• Every new connection gets a unique innovation number. During crossover these IDs let two different-shaped parents line up matching genes correctly — solving the "how do you cross two networks of different size" problem.
• Speciation — similar networks are grouped into species that evolve separately, so a promising-but-not-yet-optimised new structure isn't immediately killed off by older, fitter rivals. This protects diversity.

DeepNEAT — nodes become layers

DeepNEAT extends NEAT to deep networks with one change in meaning: a node is no longer a single neuron — it's an entire layer.

• Each node stores layer details: type (Convolution, Dense, LSTM) plus hyperparameters (number of filters, kernel size, activation function).
• Edges define how layers connect — the flow of data. Unlike NEAT, edges don't store weights (weights are learned later by gradient descent).
• To build the actual network: walk the chromosome graph, create one layer per node, wire them per the edges. Multiple inputs to a node are merged by concatenation or summation; size mismatches are fixed with pooling/downsampling.

CoDeepNEAT — co-evolving blueprints + modules

CoDeepNEAT (the "Co" = co-evolution) is the headline method of CS6. It splits evolution into two populations that evolve at the same time:

Population	Role	Analogy
Blueprints (macro-architecture)	High-level graph of the whole network. Each blueprint node is a module species ID (a placeholder), not a real layer. Edges define data flow between modules.	The skeleton / floor plan
Modules (micro-architecture)	Small reusable sub-networks — a few layers with their types and hyperparameters. Evolved independently in subpopulations.	Reusable Lego blocks

This mirrors how real deep networks are built: you design a good block once and reuse it, instead of building every layer from scratch. The result is networks that are structured, efficient, and scalable.

Phenotype construction — from genotype to trainable network

The phenotype is the actual deep network that gets trained. You assemble it like this:

1. Select a blueprint — it defines the overall structure / data flow.
2. For each blueprint node (a module species placeholder), pick a concrete module from that species' subpopulation.
3. Replace each node with its chosen module — every placeholder expands into a small sub-network.
4. Connect the modules following the blueprint's edges → a complete deep network.

In the deck's "Assembled Network" diagram: the top diamond is the input, white nodes are intermediate flow, yellow nodes are inserted modules (each yellow node = one expanded sub-network, and the same module can be reused at several positions), and the bottom node is the output. Innovation numbers again keep crossover aligned so recombination stays valid.

The full generational loop (cat-vs-dog example)

CS6 grounds all of this in a concrete CNN-evolving run:

• Initialization ("The Big Bang") — start with ~100 randomly generated, simple networks (minimal layers). Starting simple lets complexity grow only when it earns its keep.
• Fitness evaluation — instantiate each architecture, train it briefly (e.g. 5–10 epochs) on the cat-vs-dog dataset, and score it by validation accuracy (90 correct out of 100 → fitness 90%). Validation, not training, accuracy — so we reward generalisation, not memorisation.
• Selection — fitness-proportionate (roulette wheel): A=80%, B=60%, C=40%, D=20% means A and B breed often, C sometimes, D rarely. Balances exploitation and exploration.
• Crossover — recombine two parent architectures. Parent1 (Conv→Pool→Dense) × Parent2 (Conv→Conv→Dense) → child Conv→Conv→Dense (inherits deeper feature extraction). Innovation numbers align matching layers.
• Mutation — add a layer, add a skip connection, or tweak a hyperparameter (e.g. change filter 3×3 → 5×5 to capture broader features; can lift validation accuracy 85% → 92%).
• Speciation — group by similarity (shallow nets vs deep nets), compete within species to preserve diversity.
• Repeat across generations — Gen 1 ≈ 50% (random), Gen 20 ≈ 75% (basic features), Gen 50 ≈ 95% (advanced feature extraction). Keep the highest-validation architecture.

The deck closes by tracing a forward pass through an evolved CNN so you see what the layers learned: a 32×32×3 image becomes 3072 normalised numbers → Conv (edges: ears, body outline) → ReLU f(x)=max(0,x) (drop negatives) → Conv (textures: fur, eye regions) → Max-pool 2×2 (shrink, keep strongest features — "is it present?" not "exactly where") → higher layers (triangular ears, small nose, whiskers) → flatten to a vector → Dense ("whiskers + triangular ears → likely cat") → Softmax P(yi)=ezi/Σezj giving Cat=0.92, Dog=0.08. During training, a wrong prediction creates a loss that backprop + gradient descent use to nudge the weights.

CS7 — Game playing: adversarial search & minimax

Lecture CS#7 · Module 3 · adversarial settings · game trees · static evaluation · minimax

CS7 opens Module 3 and switches the whole frame of the course. Everything in CS2–CS6 assumed the world is passive — it sits still while a single agent searches. Games break that assumption: there is a second agent who is actively trying to make you lose. CS7 first recaps how NAS (NEAT/CoDeepNEAT) wrapped up, then introduces adversarial search, the game tree, static evaluation functions, and the minimax algorithm.

From normal search to adversarial search

In ordinary (single-agent) search the only question is "what sequence of actions gets me to the goal cheapest?" In a game you must also ask "what will my opponent do in response?" Your opponent's gain is your loss — these are two-player zero-sum games. You can't plan a fixed path because after every move you make, the opponent gets to move, and they will pick whatever is worst for you.

Aspect	Normal search	Adversarial search
Number of agents	Usually one	At least two, with conflicting goals
Goal	Reach a goal state	Win / maximise your utility
Environment	Passive	Strategic and competitive
Next state depends on	Only your action	Your action and the opponent's action
Example	Route finding	Chess, tic-tac-toe, Go, checkers

Games are studied in AI because they are a clean, hard testbed: a small set of rules but an astronomically large search space, where smart pruning beats brute force. Characteristics that describe a game are its observability (can you see the whole board?), stochasticity (is there dice/chance?), time granularity (turn-based vs real-time) and number of players.

A game as a search problem

Just like CS2 formalised a problem with five components, a game is formalised with six. This is the bridge that lets us reuse search machinery on a competitive setting:

Component	Meaning
Initial state S0	The starting board / position
PLAYER(s)	Whose turn it is in state s
ACTIONS(s)	The legal moves available from s
RESULT(s, a)	The new state after playing move a (the transition model)
TERMINAL-TEST(s)	Is the game over (win / lose / draw)?
UTILITY(s, p)	The final numeric payoff to player p at a terminal state

Typical utilities: Win = +1, Draw = 0, Loss = −1 (chess often uses ±1/0; tic-tac-toe the same). We name the two players MAX (wants the score as high as possible) and MIN (the opponent, wants it as low as possible). Because the game is zero-sum, if MAX scores +1 then MIN effectively gets −1 — exactly opposite goals.

The game tree

A game tree lays out every possible sequence of moves. Levels alternate between the players: the root is MAX's turn, the next level is MIN's turn, then MAX again, and so on. Leaves are terminal states (or, when the tree is too deep, estimated states — see below). The rule for backing values up the tree:

• At a MAX node, take the largest value among the children (MAX picks the best move for itself).
• At a MIN node, take the smallest value among the children (MIN picks the move that hurts MAX most).

The minimax principle

Minimax chooses the move with the best guaranteed outcome, assuming the opponent always plays optimally against you. The key mental shift: MAX does not grab the branch that contains the single biggest leaf — because after MAX moves, MIN replies and will steer toward the worst leaf in that branch. So MAX picks the branch whose worst case is best ("maximise the minimum").

Worked through on the tree above: evaluate the MIN nodes first — left MIN = min(4,7)=4, right MIN = min(2,6)=2 — then the root MAX = max(4,2)=4. Best move for MAX is the left branch, with a guaranteed value of 4, because even after MIN's best response MAX still gets 4. The classic student mistake is to chase the +5 (or here, the 7) leaf; but MIN sits between MAX and that leaf and will never let MAX have it.

Static evaluation functions

A static evaluation function estimates the utility of a non-terminal position by looking at the board as it is, without searching deeper. A good one gives higher numbers to states that are good for MAX, lower numbers to states good for MIN, is fast to compute, and correlates with the real chance of winning. A chess example: Eval = material advantage + king safety + mobility + board control, e.g. 5 + 2 + 1 + 2 = +10 for White (MAX).

The simplest possible version is just a piece count: Score = (MAX pieces) − (MIN pieces). With MAX holding 8 pieces and MIN holding 5, Score = +3 (positive ⇒ good for MAX, negative ⇒ good for MIN, zero ⇒ balanced). It's crude, but it gives the agent a usable estimate exactly when full search is impossible. When you back these estimated leaf values up the tree with the minimax rule, you get a backed-up minimax value — e.g. left MIN = min(+3,+5)=+3, right MIN = min(−2,+4)=−2, root = max(+3,−2)=+3.

CS8 — Alpha-beta pruning & Monte Carlo Tree Search

Lecture CS#8 · Module 3 · alpha-beta pruning · move ordering · MCTS · mid-sem wrap-up

CS8 is the last mid-sem deck. It makes minimax faster with alpha-beta pruning (same answer, far fewer nodes), shows why move ordering matters, then introduces a completely different, simulation-based approach — Monte Carlo Tree Search (MCTS), the engine behind modern Go programs — and closes with mid-semester exam logistics.

Alpha-beta pruning — same result, fewer nodes

Plain minimax evaluates every leaf. Alpha-beta is an improved minimax that skips branches which cannot possibly change the final decision. It gives the exact same move as minimax, just dramatically faster. The idea: as you search, keep two running bounds.

• Alpha (α) — the best (highest) value MAX is guaranteed so far along the current path. Starts at −∞.
• Beta (β) — the best (lowest) value MIN is guaranteed so far. Starts at +∞.

General principle: at a node n, if a player already has a better option at the parent of n (or higher up), then n will never actually be reached in optimal play — so the entire subtree under n can be pruned. The cutoff test is simply β ≤ α: once that becomes true, stop expanding the remaining siblings, because they can't affect the result.

At a MAX node	At a MIN node
If value > α, set α = value	If value < β, set β = value
If β ≤ α → prune remaining siblings	If β ≤ α → prune remaining siblings

Reading the figure: the left MIN node evaluates its children (6, 8) and returns 6, so MAX now has α = 6 guaranteed. The right MIN node then sees a child worth 2. Since MIN will pick at most 2 there, and MAX already has 6 elsewhere, MAX will never choose the right branch — so the right MIN's other child is irrelevant and gets pruned. Same root answer (6), one fewer leaf evaluated. On a big tree this compounds enormously.

Monte Carlo Tree Search (MCTS)

Alpha-beta needs a good static evaluation function. For games like Go, no one knew how to write one — the board is too subtle. MCTS sidesteps the problem: instead of evaluating a position with hand-crafted rules, it plays out random games (simulations / "rollouts") from that position and uses the win/loss statistics as the evaluation. It blends tree search with the reinforcement-learning idea of learning from sampled outcomes.

The naïve version — run many full random simulations at every node — is far too slow and noisy (a single rollout gives only a 0/1 signal). MCTS's insight is to use simulation results to grow the tree selectively, balancing exploitation (spend effort on moves that look promising) against exploration (try moves whose value is still uncertain). The standard balance is the UCB (Upper Confidence Bound) formula: a node's selection score increases with its win rate (exploit) and decreases with how often it's already been visited (explore), and every option is tried at least once.

MCTS applies to combinatorial games — two-player, sequential (turn-taking), perfect-information, finite well-defined moves: chess, checkers, Go, tic-tac-toe. Each iteration runs four phases:

Phase	What happens
1. Selection	Start at the root and repeatedly pick the most promising child (UCB = balance high win-rate vs few visits) until you reach a node with unexplored moves.
2. Expansion	Add one new child node for an unexplored legal move — the tree grows a little rather than all at once.
3. Simulation (rollout)	From the new node, play the game to the end using random / lightweight-heuristic moves. The aim isn't perfect play, just an estimate of win / loss / draw.
4. Backpropagation	Send the result back up every node on the path, updating each node's visit count and win score (and hence its average win rate).

Repeat these four phases thousands of times; the tree grows preferentially toward strong moves, and when the time budget runs out you play the child with the best statistics. This is exactly the family of methods that powered AlphaGo (with neural networks guiding selection and simulation), and they recur in cybersecurity, robotics and text generation too.

References

• T1 — Stuart Russell & Peter Norvig, Artificial Intelligence: A Modern Approach, 4th ed., Pearson, 2022 (course textbook). CS1 maps to Ch. 1–2.
• R3 — Elaine Rich, Kevin Knight, Shivashankar B. Nair, Artificial Intelligence, 3rd ed., Tata McGraw Hill.
• Course: BITS Pilani WILP — Artificial & Computational Intelligence (AIMLCZG557).