Search

C1: Search

1

Most materials in this chapter are based on materials from https://ai.berkeley.edu

C1

Search

COMP3270

Introduction to Artificial Intelligence

Chapter Roadmap Define the Problem Abstraction, states, actions, goals, and costs Find a Solution Uninformed, informed, local, and constraint-based search Compe

2

Chapter 1: Search Roadmap

Define the Problem Abstraction, states, actions, goals, and costs

Find a Solution Uninformed, informed, local, and constraint-based search

Compete Against an Opponent Minimax, pruning, and uncertainty

Search Looks Ahead: Which Actions Reach the Goal?

3

Source

To Look Ahead, Build a Simpler Model

4

To Look Ahead, Build a Simpler Model

Real World Search Model

A robot turning the complex real world into a simpler puzzle-like model

Abstraction keeps only what the decision needs

States · Actions · Goal · Costs

Choose the Search Strategy to Match the Problem

5

Choose the Search Strategy to Match the Problem

No Guidance Uninformed Search

A Helpful Estimate Informed Search

Improve One Current State Local Search

Hard Constraints Constraint Satisfaction

An Opponent Adversarial Search

We have a model. Now how should we search it?

The answer depends on what the problem gives us.

With no guidance about where the goal lies, uninformed methods such as BFS, DFS, and uniform-cost search explore systematically.

If we have a helpful estimate of how close a state is to the goal, informed methods such as greedy search and A* use that estimate.

If we only need to improve one current state, local search changes that state to make it better. Gradient descent is one example.

If choices must satisfy hard rules, constraint satisfaction methods use those constraints to eliminate impossible choices. AC-3 is one example.

If another agent is working against us, adversarial search plans for that opponent. Minimax and alpha–beta pruning are examples.

We will begin by defining a search problem precisely, then study these strategies in turn.

[Sources] - Recovered COMP3270 2024–25 source slide 5: 01_search.pptx. - Canonical visual layer: 01_search.pdf.

Defining a Search Problem

6

Defining a Search Problem

State Representation What information describes a situation?

Initial State Where does the agent begin?

Actions and Transition Model What can the agent do, and what changes?

Goal Test How do we recognise success?

Path Cost How do we compare solutions?

A solution is a sequence of actions from the initial state to a goal state

We now know there are several ways to search.

But none of them can begin until we define the problem precisely.

First, what information do we need to describe one situation? That information defines the state representation.

Second, which state does the agent begin from? That is the initial state.

Third, what actions are available, and what new state does each action produce? Together, these are the actions and transition model.

Fourth, how do we recognise success? The goal test tells us whether a state is a goal state.

Fifth, how expensive is a route? Path cost lets us compare different sequences of actions.

When every action has the same cost and we only need any solution, the path cost may be left implicit. That is why the next N-Queens examples do not list it separately.

A solution is a sequence of actions that takes us from the start state to a goal state.

Next, we will define the same N-Queens puzzle in two different ways. Both definitions are valid, but they produce very different search spaces.

[Sources] - Recovered COMP3270 2024–25 source slide 6: 01_search.pptx. - Canonical visual layer: 01_search.pdf.

N-Queens Definition A: Place Anywhere, Check at the End

7

N-Queens Definition A: Place Anywhere, Check at the End

Start Empty board

Action Add a queen to any empty square

State Any arrangement of 0–n queens

Goal n queens, none attacking

Attacking partial boards are still states

Source

Let us apply the five-question checklist to N-Queens.

In Definition A, we begin with an empty board.

An action adds one queen to any empty square. We do not check yet whether that queen attacks another queen.

Continue applying that action. A state can therefore be any arrangement of zero to n queens, including arrangements in which queens attack each other.

Because our actions only add queens, an attacking partial board cannot later become a valid goal. It is already a dead end.

The goal requires n queens on the board with no queen attacking another.

The important consequence is that attacking partial boards are still states in Definition A.

This definition makes the search consider many states that cannot lead to a solution. Can we rule those states out earlier?

[Sources] - Recovered COMP3270 2024–25 source slide 7: 01_search.pptx. - Canonical visual layer: 01_search.pdf.

N-Queens Definition B: Rule Out Bad States Early

8

N-Queens Definition B: Rule Out Bad States Early

Start Empty board

Action Add one non-attacking queen to an empty column

State One queen per column, none attacking

Goal n queens on the board

Invalid partial boards never enter the state space

Definition B starts from the same empty board, but changes what counts as a state and which actions are allowed.

An action adds one queen to an empty column only when it does not attack any queen already on the board.

Every state has at most one queen per column, and no queen attacks another.

An invalid partial board is rejected immediately instead of becoming another state to search.

The goal is reached when n queens are on the board. The non-attacking requirement is already guaranteed by the state and action definitions.

Invalid partial boards never enter the state space in Definition B.

The physical puzzle is unchanged. The abstraction changed, so the size of the search problem changed.

Which definition has the larger state space?

[Sources] - Recovered COMP3270 2024–25 source slide 8: 01_search.pptx. - Canonical visual layer: 01_search.pdf.

A State Space Contains Every Reachable State

9

A State Space Contains Every Reachable State

Different problem definitions produce different state spaces

TASK

Which definition has the larger state space?

Definition A Place anywhere. Check at the end.

Definition B Rule out bad states early.

Same Puzzle, Very Different State Spaces

10

Same Puzzle, Very Different State Spaces

SOLUTION

Definition A · Count Every Placement

$|S_A| = \sum_{k=0}^{8} \binom{64}{k}$

Download: comp3270.dirk.hk/n_queens_definition_a.py

Definition B · Keep Only Safe Placements

$|S_B| = ?$

Download: comp3270.dirk.hk/n_queens_definition_b.py

$|S_A| \approx 43{,}126 \times |S_B|$

We will count the two state spaces separately before comparing them.

Definition A permits any arrangement of zero to eight queens on the sixty-four squares. For exactly k queens, we choose k squares, so the formula sums sixty-four choose k from zero to eight.

Run the program on the left. Python's comb function performs each combination calculation and produces 5,130,659,561 states.

Definition B counts only safe partial boards. Run the program on the right. It counts the current board, then recursively tries each safe queen in a later column.

Using later columns ensures that every distinct board is counted once. The result is 118,969 states.

The comparison says that |S_A| is about 43,126 times |S_B|.

The physical puzzle did not change. The abstraction changed, and that dramatically changed how much there is to search.

[Sources] - Recovered COMP3270 2024–25 source slide 10: 01_search.pptx. - Canonical visual layer: 01_search.pdf.

A Search Tree Records Action Sequences

11

A Search Tree Records Action Sequences

State Space Graph

Each distinct state appears once

Search Tree

Each action sequence creates a tree node

Different paths to G create different search-tree nodes

A state space graph contains each distinct state once. The graph on the left therefore contains one node for G.

A search tree records action sequences from the initial state. We will unfold this finite graph into a tree.

The root of the search tree represents the empty action sequence, so it contains the initial state S.

Expanding S creates one child for the sequence leading to A and another for the sequence leading to B.

Expanding A and B reaches G through two different action sequences. The state space graph contains one G, but the search tree contains two G nodes.

This is the key distinction: tree nodes represent paths, not merely distinct states.

Next, students will construct a complete search tree for another finite graph.

[Sources] - Pedagogical redesign of recovered COMP3270 2024–25 source slides 11–12: 01_search.pptx. - Canonical visual layer: 01_search.pdf.

Draw the Search Tree

12

Draw the Search Tree

Starting at S, draw the complete search tree. How many times does G appear?

TASK

State Space Graph

Search Tree

SOLUTION

G appears three times because three action sequences reach it

Trace the Search Tree

How many times does G appear in the complete search tree?

TASK

Cyclic State Space Graph

Search Tree Prefix

SOLUTION

Infinitely many: A and B can alternate any number of times before moving to G

Give students the finite state space graph and ask them to draw the complete search tree from S.

Ask them to count how many times G appears. The graph has no cycles, so the complete tree is finite.

Start the tree at S and expand it to A and B.

A reaches C. B reaches another C node and also reaches G directly. The same state C now appears twice because two action sequences reach it.

Each C node reaches its own G node. Together with the direct path from B, G appears three times in the search tree.

The state space graph has one G state, but the search tree has three G nodes because it records three distinct action sequences.

Return to the original cyclic example. Ask students how many times G appears in the complete search tree.

The important clue is that A and B can lead back to one another.

G appears infinitely many times. The search can alternate between A and B any number of times before taking an action to G.

The diagram shows only a finite prefix. The alternating branches continue without end, which motivates repeated-state checking in graph search.

[Sources] - Pedagogical redesign of recovered COMP3270 2024–25 source slides 11–12: 01_search.pptx. - Canonical visual layer: 01_search.pdf.

Define the Romania Route Problem

13

Define the Romania Route Problem

Find a route from Arad to Bucharest

TASK

SOLUTION

Map of Romania showing Arad and Bucharest

StateCurrent city

StartArad

Actions and TransitionChoose a neighboring city and move there

GoalReach Bucharest

Path CostSum of road distances

Source

We need a small running example for the search algorithms that follow.

Suppose we begin in Arad and want to reach Bucharest. The first column names the five parts of the search problem. Ask students to suggest each answer.

The A marker locates Arad in western Romania. This is our initial state.

The B marker locates Bucharest in the southeast. The search must connect these two locations through the road network.

A state records the current city, and the initial state is Arad.

An action chooses a neighboring city. The transition model moves us there. Bucharest satisfies the goal test, and the path cost is the sum of the road distances.

[Sources] - Pedagogical redesign of recovered COMP3270 2024–25 source slide 13: 01_search.pptx. - Geographic map: Google Maps, www.google.com/maps/place/Romania/. - Canonical visual layer: 01_search.pdf.

Romania as a State-Space Graph

14

Romania as a State-Space Graph

Cities are states · roads are transitions · distances are step costs (ignored for now)

Weighted state space graph for the Romania route problem

Source

The geographic map is now abstracted into a weighted state space graph.

Each city is a state. Each road represents a legal transition, and its number is the step cost for taking that road.

From this point onward, we use each city’s initial as its state label: A for Arad and B for Bucharest.

Reveal the initial used for every city. In this example, all city names have different first letters, so each initial can serve as a unique state identifier.

This is only a convenient shorthand for this graph. In general, state identifiers must be unique even when names share an initial.

[Sources] - Pedagogical redesign of recovered COMP3270 2024–25 source slide 14: 01_search.pptx. - Romania state space graph: AIMA, http://aima.cs.berkeley.edu/. - Canonical visual layer: 01_search.pdf.

Expanding A Generates Three Successors

15

Expanding A Generates Three Successors

Western portion of the weighted Romania state space graph around Arad

Download: comp3270.dirk.hk/roads_from_arad.py

Source

The dictionary stores connectivity using city initials. Each key is a state, and its value lists the neighboring states.

For now, ignore the road distances and focus on which successors can be generated from A.

The cropped graph keeps the Arad neighborhood visible beside the runnable code.

The first entry in the list for A is S, so highlight the road from Arad to Sibiu and generate state S.

The second successor is T for Timisoara.

The third successor is Z for Zerind. A, S, T, and Z use equal-sized state circles.

A is rendered after the road overlays, so the start state remains in the foreground. Run the example to confirm the output S, T, Z.

[Sources] - Pedagogical redesign of recovered COMP3270 2024–25 source slides 14–15: 01_search.pptx. - Original Romania dictionary example from recovered COMP3270 2024–25 source slide 15: 01_search.pptx. - Romania state space graph: AIMA, http://aima.cs.berkeley.edu/. - Canonical visual layer: 01_search.pdf.

The Frontier Stores Nodes Waiting to Be Expanded

16

The Frontier Stores Nodes Waiting to Be Expanded

Frontier = generated nodes waiting to be expanded. It is the search algorithm’s current set of choices.

Which node should be expanded next: S, T, or Z?

The frontier is the collection of generated nodes that have not yet been expanded. It is the set of choices currently available to the search algorithm.

Initially, only the root node has been generated. That node contains state A, so the frontier contains one node labelled A.

The algorithm selects the node labelled A, removes it from the frontier, and expands it.

A selected node leaves the frontier because it is no longer waiting to be expanded.

The expansion generates the three children listed in the dictionary: S, T, and Z.

They are added to the frontier because each is now available for later expansion.

The frontier now contains three choices. Which node should be removed and expanded next?

A search strategy answers that question by defining the order of node expansion.

[Sources] - Pedagogical redesign of recovered COMP3270 2024–25 source slide 15: 01_search.pptx. - Romania state connections: AIMA, http://aima.cs.berkeley.edu/. - Canonical visual layer: 01_search.pdf.

A Search Strategy Chooses the Next Node to Expand

17

A Search Strategy Chooses the Next Node to Expand

It is the rule that determines the order of node expansion.

How should we compare search strategies?

Four Questions Compare Search Strategies

18

Four Questions Compare Search Strategies

We compare what a strategy guarantees and what resources it requires.

Completeness Will it find a solution whenever one exists?

Optimality Will it find a least-cost solution?

Time How many nodes are generated?

Space What is the maximum number of nodes held in memory?

Search Complexity Depends on b, d, and m

19

Search Complexity Depends on b, d, and m

b = 3 maximum branching factor

d = 2 depth of the shallowest goal

m = 4 maximum path length

Search Repeats: Select, Test, Expand

20

The search strategy supplies the rule used at Select.

Uninformed Search and Informed Search

21

Uninformed Search and Informed Search

Uninformed Search

Problem definition

No estimate to a goal

BFS · DFS · UCS

Informed Search

Problem definition

estimate to a goal

Greedy · A*

We begin with BFS.

One Strategy, Two Search Algorithms

22

One Strategy, Two Search Algorithms

The strategy orders the frontier; TSA and GSA handle repeated states differently.

We begin with BFS-TSA.

Separate two choices. A search strategy determines the order in which nodes leave the frontier. The tree-search and graph-search algorithms determine how repeated states are handled.

Tree search treats each path as a branch of the search tree. Because it does not keep a separate record of explored states, the two paths can create two different nodes containing state C.

Graph search remembers explored states across paths. When a node contains a state that has already been explored, the algorithm can skip expanding it again. The precise duplicate-checking rule will be introduced later.

We begin with the tree-search form of breadth-first search: BFS-TSA. The next slide explains how its FIFO frontier orders the search nodes.

[Sources] - AIMA Python search implementations: https://aima.cs.berkeley.edu/python/search.html. - UC Berkeley CS188, Uninformed Search: https://inst.eecs.berkeley.edu/~cs188/textbook/search/uninformed.html. - Pedagogical redesign of recovered COMP3270 2024–25 source slide 18: 01_search.pptx. - Canonical visual layer: 01_search.pdf.

BFS Explores One Depth at a Time

23

BFS Explores One Depth at a Time

BFS uses a FIFO frontier: earlier nodes stay ahead of newly generated nodes.

Which node should be expanded next?

TASK

SOLUTION

C is next: it entered the frontier at depth 1 before D, E, F, and G.

Begin with only S in the frontier. Breadth-first search removes the node that has waited longest: first in, first out.

Expand S. Its children A, B, and C enter the frontier in that order.

Expand A. Remove A from the front, then append its children D and E at the back. The frontier is now B, C, D, E.

Expand B. Remove B from the front, then append F and G. The frontier is now C, D, E, F, G.

Replace the FIFO statement with the task question. Ask students which node should be expanded next from the frontier C, D, E, F, G.

Reveal the answer: C is next. Highlight C both in the search tree and at the front of the frontier.

C entered the frontier when S was expanded, before the depth-2 nodes D, E, F, and G were generated. A FIFO frontier therefore keeps every depth-1 node ahead of nodes added at depth 2.

[Sources] - Pedagogical redesign of recovered COMP3270 2024–25 source slide 20: 01_search.pptx. - Canonical visual layer: 01_search.pdf.

Python’s deque Implements a FIFO Frontier

24

Download: comp3270.dirk.hk/queue_demo.py

A deque—pronounced “deck”—is a double-ended queue. It supports adding and removing at either end. For a breadth-first frontier, we use only two operations: append at the back and remove from the front.

Begin with an empty frontier. A is appended first, so A is at the front.

B is appended second, behind A.

C is appended third, behind B. The insertion order is therefore explicit: A, then B, then C.

popleft() removes and returns A, the item that entered first, leaving B and C. Run the code to confirm the same frontier order in Python.

[Sources] - Python documentation for collections.deque, append(), and popleft(): https://docs.python.org/3/library/collections.html#collections.deque - Pedagogical redesign of recovered COMP3270 2024–25 source slide 21: 01_search.pptx.

A Search Node Stores the Path So Far

25

A Search Node Stores the Path So Far

For our lecture code, a path string records one route through the search tree.

'S' → 'Sa' → 'Sab' → 'SabG'

path[-1] gives 'b'

path[-1] gives 'G'

search treemany possible routes

pathone route

current statelast character

Download: comp3270.dirk.hk/search_path_demo.py

The search tree contains many possible routes. For our lecture code examples, we use a compact string to record one route from the start to a particular node. The initial one-state path is ‘S’.

The tree branches to a and c. Following the highlighted branch to a gives the path ‘Sa’; the other branch remains part of the tree, but not this path.

Following the next highlighted branch gives ‘Sab’. The final character, obtained with path[-1], is ‘b’, so b is the current state.

Appending G updates the path to ‘SabG’. Now path[-1] is ‘G’. The runnable code performs exactly those two ideas: read the last state, then extend the path.

[Sources] - Pedagogical redesign of recovered COMP3270 2024–25 source slide 22: 01_search.pptx. - Berkeley CS188, Search: https://inst.eecs.berkeley.edu/~cs188/textbook/search/index.html

BFS-TSA Repeats Three Operations

26

BFS-TSA Repeats
Three Operations

Remove the next path

Frontier['A'] -> []

Path'A'

Test its final state

Frontier[]

Goal testA ≠ B

Append every extension

Frontier[] -> ['AS', 'AT', 'AZ']

Download: comp3270.dirk.hk/bfs_tsa_romania.py

Romania road map with cities and road distances

The code on the right is the runnable BFS tree-search implementation used on the next Romania slide. Keep one invariant in mind: every frontier item is a path string.

First, popleft() removes the path that has waited longest. The frontier changes from [‘A’] to empty, and the removed item becomes the current path ‘A’. That FIFO operation is what makes the search breadth-first.

Second, read the path’s last character and test whether that state is the goal. The state is A, not B, and this test does not change the frontier.

Otherwise, extend ‘A’ with successors S, T, and Z. Appending ‘AS’, ‘AT’, and ‘AZ’ makes those three paths the current frontier.

[Sources] - AIMA Romania route problem: https://aima.cs.berkeley.edu/python/search.html - Python documentation for collections.deque: https://docs.python.org/3/library/collections.html#collections.deque - Berkeley CS188, Uninformed Search: https://inst.eecs.berkeley.edu/~cs188/textbook/search/uninformed.html - Pedagogical redesign of recovered COMP3270 2024–25 source slide 23: 01_search.pptx.

What Happens When a Path Returns to A?

27

Program Output

A -> ['AS', 'AT', 'AZ']

AS -> ['AT', 'AZ', 'ASA', 'ASF',
'ASO', 'ASR']

AT -> ['AZ', 'ASA', 'ASF', 'ASO',
'ASR', 'ATA', 'ATL']

AZ -> ['ASA', 'ASF', 'ASO', 'ASR',
'ATA', 'ATL', 'AZA', 'AZO']

Search Tree

Explore A again?

Read the first trace line as an expansion. BFS-TSA removes ‘A’, expands state A, and appends the three paths ‘AS’, ‘AT’, and ‘AZ’. The tree keeps only the state labels so the expansion order remains visually clear.

FIFO means ‘AS’ is removed next. Expanding S creates four children: ‘ASA’, ‘ASF’, ‘ASO’, and ‘ASR’. They go behind ‘AT’ and ‘AZ’, which were already waiting.

Next, BFS removes ‘AT’. Expanding T adds ‘ATA’ and ‘ATL’ at the back. The path ‘ASA’ is still waiting behind ‘AZ’.

Then BFS removes ‘AZ’. Expanding Z adds ‘AZA’ and ‘AZO’. Now ‘ASA’ has reached the front of the frontier.

The next path is ‘ASA’, whose final state is A. Ask the question on screen and let students recognize the problem: tree search is about to expand A again.

[Sources] - AIMA Romania route problem: https://aima.cs.berkeley.edu/python/search.html - Berkeley CS188, Uninformed Search: https://inst.eecs.berkeley.edu/~cs188/textbook/search/uninformed.html - Pedagogical redesign of recovered COMP3270 2024–25 source slides 24–26: 01_search.pptx.

TSA Repeats States Because It Has No Memory

28

PROBLEMTSA revisits states

It does not remember where it has been

SOLUTION Remember explored states explored = {'A', 'S'} A ∈ explored → skip

TSA+explored states=GSA

Repeated states are skipped instead of expanded again

BFS-GSA Remembers Explored States

29

Frontier['AS','AT','AZ']stores path strings

Explored{'A'}stores states only

Create the memoryexplored = set()

Skip a repeated statestate in explored

Remember before expandingexplored.add(state)

Download: comp3270.dirk.hk/bfs_gsa_romania.py

Romania State-Space Graph

30

Run BFS-GSA on Romania

31

frontier: pathsexplored: states

Source

Download: comp3270.dirk.hk/bfs_gsa_romania.py

BFS-GSA Practice

32

BFS-GSA Practice

TASK

Run BFS-GSA from S to G

RecordExplored orderReturned path

Add successors alphabetically

SOLUTION

S -> ['Sa', 'Sd', 'SG']
explored: ['S']

Sa -> ['Sd', 'SG', 'Sab']
explored: ['S', 'a']

Sd -> ['SG', 'Sab', 'Sdb', 'Sde']
explored: ['S', 'a', 'd']

solution: SG

Explored S → a → d Path S → G

Run the BFS-GSA Practice Code

33

Download: comp3270.dirk.hk/bfs_gsa_practice.py

BFS-TSA Properties

34

BFS-TSA Properties

TASK

Complete?

Optimal?

Time complexity?

Space complexity?

SOLUTION

Yes

Nounless all step costs are equal

O(b^d+1) =^* O(b^d)

b maximum branching factor d depth of the shallowest solution *If we treat b as fixed

Assume b = 10, 1 million nodes/second, 1000 bytes/node

Depth	Nodes	Time	Memory
2	110	0.11 milliseconds	110 kilobytes
4	11,110	11 milliseconds	11 megabytes
6	1.11 × 10⁶	1.1 seconds	1.1 gigabytes
8	1.11 × 10⁸	1.9 minutes	111 gigabytes
10	1.11 × 10¹⁰	3.1 hours	11 terabytes
12	1.11 × 10¹²	12.9 days	1.1 petabytes
14	1.11 × 10¹⁴	3.5 years	111 petabytes
16	1.11 × 10¹⁶	352 years	11 exabytes

Ask students to evaluate BFS-TSA using the four questions introduced earlier: completeness, optimality, time, and space. This analysis does not use an explored set.

BFS-TSA is complete when the branching factor is finite and a solution exists at a finite depth.

BFS-TSA is not optimal in general: it returns a shallowest solution, which need not be the least-cost solution.

The exception is when all step costs are equal. Then minimizing depth also minimizes path cost.

The goal G is the final depth-three path removed. Before reaching it, BFS expands earlier depth-three paths and adds their children at depth four. The dots indicate omitted successors and subtrees when the branching factor is greater than two.

Our code tests for the goal when a path is removed from the frontier. In the worst case, it generates paths at depth d plus one before removing the goal, giving O(b^d+1). If we treat b as fixed, this is also written O(b^d).

Space has the same bound because the frontier may contain those depth d plus one paths while the goal is still waiting to be removed.

Now replace the small tree with branching factor ten. The node count is the sum from depth one through depth d, excluding the root. Times and memory use decimal units and are rounded. Red values mark the point at which even this simplified search becomes impractical for an interactive system.

[Sources] - AIMA, Chapter 3, breadth-first search properties. - Recovered COMP3270 2024–25 source slide 32: 01_search.pptx.

BFS Explores the Shallowest Node First

35

Breadth-first search explores a search space one shallow layer at a time

frontier is a queue (first in first out data structure)

DFS Explores the Deepest Node First

36

frontier is a stack (last in first out data structure)

Python’s deque Implements a LIFO Frontier

37

Download: comp3270.dirk.hk/stack_demo.py

Run DFS-GSA on Romania

38

frontier: pathsexplored: states

Download: comp3270.dirk.hk/dfs_gsa_romania.py

DFS-GSA Follows the Newest Path

39

Program Output

A -> ['AS', 'AT', 'AZ']
explored: ['A']

AZ -> [..., 'AZA', 'AZO']
explored: ['A', 'Z']

AZO -> [..., 'AZOS', 'AZOZ']
explored: ['A', 'O', 'Z']

AZOS -> [..., 'AZOSR']
explored: ['A', 'O', 'S', 'Z']

Search Tree

LIFO follows the newest path.

DFS-GSA Practice

40

DFS-GSA Practice

TASK

Run DFS-GSA from S to G

RecordExplored orderReturned path

Add successors alphabetically

SOLUTION

S -> ['Sa', 'Sd', 'SG']
explored: ['S']

solution: SG

Explored S Path S → G

Run the DFS-GSA Practice Code

41

Download: comp3270.dirk.hk/dfs_gsa_practice.py

DFS-TSA Properties

42

DFS-TSA Properties

TASK

Complete?

Optimal?

Time complexity?

Space complexity?

SOLUTION

Nounless the search tree is finite

No

O(b^m)

O(bm)

b maximum branching factor m maximum search-tree depth

Evaluate DFS-TSA using the same four questions used for BFS-TSA. There is no explored set.

DFS-TSA is not complete in general because it can follow an infinite branch or cycle forever.

If the search tree is finite, every branch eventually ends and DFS-TSA becomes complete.

DFS is not optimal. It can return a deep goal before considering a shallower or cheaper goal.

The diagram shows the key memory advantage: DFS follows one path while retaining the unexpanded sibling paths along that branch.

In the worst case, DFS explores a b-ary tree to maximum depth m, taking O(b to the m) time.

At each of m levels, the frontier retains at most O(b) siblings, so tree-search space is O(bm).

[Sources] - AIMA, Chapter 3, depth-first search properties. - Pedagogical redesign of recovered COMP3270 2024–25 source slide 40: 01_search.pptx.

BFS vs. DFS

43

BFS vs. DFS

TASK

SOLUTION

BFS

When can it outperform DFS?

When a solution is shallow

DFS

When can it outperform BFS?

When a solution lies deep along an early branch

TSA vs. GSA

44

TSA vs. GSA

	TSA	GSA
Memory	Frontier	Frontier + explored set
Repeated state	Expand it again	Skip it
Trade-off	Less memory	Fewer repeated expansions

BFS, DFS, and UCS can each use either algorithm

Compare tree search and graph search one item at a time. The row labels establish the three questions before either answer appears.

Tree search stores only the frontier.

Graph search stores the frontier and an explored set.

Without an explored set, tree search can expand a state again.

Graph search skips a path when its final state has already been explored.

Tree search uses less memory because it does not store explored states.

Graph search often avoids repeated expansions, at the cost of storing the explored set.

This bookkeeping choice is independent of the frontier rule. BFS, DFS, and UCS can each use tree search or graph search.

[Sources] - Recovered COMP3270 2024–25 source slide 42: 01_search.pptx. - AIMA, Chapter 3, tree-search and graph-search algorithms.

UCS Explores the Cheapest Node First

45

Miners explore a mountain containing rewards at different accumulated costs

frontier is a priority queue (smallest total path cost first)

A Priority Queue Removes the Cheapest Path

46

Download: comp3270.dirk.hk/priority_queue_demo.py

Run UCS-GSA on Romania

47

Romania state-space graph with road distances

frontier: (cost, path)explored: states

Download: comp3270.dirk.hk/ucs_gsa_romania.py

UCS-GSA Follows the Cheapest Path

48

Program Output

A @ 0 -> [(75, 'AZ'), (118, 'AT'), (140, 'AS')]
explored: ['A']

AZ @ 75 -> [(118, 'AT'), (140, 'AS'), ...]
explored: ['A', 'Z']

AT @ 118 -> [(140, 'AS'), (146, 'AZO'), ...]
explored: ['A', 'T', 'Z']

AS @ 140 -> [(146, 'AZO'), (150, 'AZA'), ...]
explored: ['A', 'S', 'T', 'Z']

AZO @ 146 -> [(150, 'AZA'), (217, 'AZOZ'), ...]
explored: ['A', 'O', 'S', 'T', 'Z']

Search Tree

Romania state-space graph with road costs

Next path = smallest total path cost

UCS-GSA Practice

49

UCS-GSA Practice

TASK

SOLUTION

Run UCS-GSA from S to G

RecordExplored orderReturned path and cost

Add successors alphabetically

S @ 0 -> [(2, 'Sd'), (3, 'Sa'), (10, 'SG')]
explored: ['S']

Sd @ 2 -> [(3, 'Sa'), (3, 'Sdb'), (6, 'Sde'),  (10, 'SG')]
explored: ['S', 'd']

Sa @ 3 -> [(3, 'Sdb'), (6, 'Sde'), (8, 'Sab'),  (10, 'SG')]
explored: ['S', 'a', 'd']

Sdb @ 3 -> [(4, 'Sdbe'), (5, 'Sdbc'), (6, 'Sde'),  (8, 'Sab'), (10, 'SG')]
explored: ['S', 'a', 'b', 'd']

Sdbe @ 4 -> [(5, 'Sdbc'), (6, 'Sde'), (7, 'SdbeG'),  (8, 'Sab'), (10, 'SG')]
explored: ['S', 'a', 'b', 'd', 'e']

Sdbc @ 5 -> [(6, 'Sde'), (7, 'SdbeG'), (8, 'Sab'),  (9, 'SdbcG'), (10, 'SG')]
explored: ['S', 'a', 'b', 'c', 'd', 'e']

Solution (7, 'SdbeG')Explored S → d → a → b → e → cPath S → d → b → e → G

Ask students to trace UCS-GSA. They must report the explored order, returned path, and total path cost. Successors are listed alphabetically, while the priority queue removes the smallest cost.

S generates Sd at cost 2, Sa at cost 3, and SG at cost 10.

Sd is cheapest. Expanding d adds Sdb at cost 3 and Sde at cost 6.

Sa and Sdb tie at cost 3. Python’s tuple ordering removes Sa first, and expanding a adds Sab at cost 8.

Sdb now leaves at cost 3. Expanding b adds Sdbe at cost 4 and Sdbc at cost 5.

Sdbe is cheapest at cost 4. Expanding e adds the goal path SdbeG at cost 7.

Sdbc still costs only 5, so c is explored before the goal path is removed.

The goal path SdbeG leaves at cost 7 before the direct path SG at cost 10. Separate the returned path from the explored order.

Run the UCS-GSA Practice Code

50

Download: comp3270.dirk.hk/ucs_gsa_practice.py

UCS-TSA Properties

51

UCS-TSA Properties

TASK

Complete?

Optimal?

Time complexity?

Space complexity?

SOLUTION

Yes, iffinite b; c ≥ ε > 0

Yesgoal test on removal

$\mathrm{O}\!\left(b^{\left\lfloor C^*/\varepsilon \right\rfloor+1}\right)$

Optimality allows c ≥ 0; completeness requires c ≥ ε > 0

C^∗ cost of an optimal solutionε smallest positive step cost

Evaluate uniform-cost tree search using the same four questions as BFS and DFS.

Throughout our examples, step costs are nonnegative. Completeness needs the stronger condition that each step costs at least some positive ε; otherwise infinitely many zero-cost steps could fit below a finite solution cost.

UCS is optimal when the goal test occurs after the path leaves the priority queue. At that point no cheaper path remains.

C star denotes the optimal solution cost. Epsilon denotes the smallest positive step cost.

The diagram replaces depth layers with cost contours. The old ε, 2ε, and 3ε labels have been removed because siblings at the same depth need not have those exact costs.

A path costing at most C star can contain at most floor of C star over epsilon steps. Including the next generated layer gives the stated exponential time bound.

The frontier can retain the generated paths, so the space bound matches the time bound.

[Sources] - AIMA, Chapter 3, uniform-cost search properties.

Uninformed Search Strategies

52

Uninformed Search Strategies

Strategy	Frontier	Next path	Optimal?
BFS	FIFO queue	Shallowest	Only with equal step costs
DFS	LIFO stack	Deepest	No
UCS	Priority queue	Cheapest	Yes

UCS uses only costs already incurred: g(path)

Informed Search

53

Source

A Heuristic Estimates the Remaining Cost

54

How far is a node from the goal?

h(n): Estimated cost of the cheapest path from the state at node n to a goal

Straight-line distance to B

h(A) = 366 km

An estimate, not a road route

h(B) = 0

Use the estimate to guide which frontier node to explore next

Greedy Search Selects the Lowest h(n)

55

Expand the frontier node estimated closest to the goal

Frontier after expanding A

Priority queue · smallest h first

Path	Priority
`AS`	h(S) = 253
`AT`	h(T) = 329
`AZ`	h(Z) = 374

Remove AS; explore S next

Greedy uses the estimated cost remaining; UCS uses the cost so far

Greedy Follows the Heuristic

56

Select the frontier node with the smallest h(n)

Original Greedy Follows the Heuristic mining illustration

Source: UC Berkeley CS188

Greedy-GSA Follows the Smallest Estimate

57

Search Trace · @ = h(final state)

A @ 366 →
[(253, 'AS'), (329, 'AT'), (374, 'AZ')]
explored: ['A']

AS @ 253 →
[(176, 'ASF'), (193, 'ASR'), ...]
explored: ['A', 'S']

ASF @ 176 →
[(0, 'ASFB'), (193, 'ASR'), ...]
explored: ['A', 'F', 'S']

ASFB @ 0 → goal B
solution: ASFB

Search Tree

Greedy Search Is Not Always Optimal

58

Greedy · ASFB

140 + 99 + 211 = 450

UCS · ASRPB

140 + 80 + 97 + 101 = 418

A smaller h-value does not guarantee a cheaper complete path

Greedy-TSA Practice

59

Start: S · Goal: G

Which states are expanded?
Which path is returned? Is it the cheapest?

Initial frontier: [(7, 'S')]

Exploring: S at h = 7
Frontier:
[(0, 'SG'), (5, 'Sd'), (9, 'Sa')]

Solution path: SG

A* Motivation: UCS

60

Cheap so far can still lead away from the goal

After expanding a

Sab: g=2 Sad: g=4 Sae: g=9

Follow the cheap branch

Sab → Sabc
c is a dead end

Return to the waiting path

Sad → SadG
Solution cost: 6

A* Motivation: Greedy Search

61

Greedy selects using h(n) alone

Same frontier, new priority

Sab: h(b)=6 Sad: h(d)=2 Sae: h(e)=1

Chase the smallest estimate

Sae is selected first
h(e)=1 is the smallest estimate

Then select Sad

Sad and Saed tie at h=2
Path-string order selects Sad

The Tortoise and the Hare

62

UCS

Cost so far

Greedy

Estimated cost remaining

Can we combine their strengths?

A*

Use both costs

Source: UC Berkeley CS188

A* Combines Cost So Far and Cost Remaining

63

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

Cost so far

Actual path cost from A to S

Estimated cost remaining

Heuristic estimate from S to B

Node n represents path AS

Select the frontier node with the smallest f(n)

A* Motivation: Combine Both Costs

64

Now revisit the same choices using g + h

After expanding a

Sab: 2 + 6 = 8 Sad: 4 + 2 = 6 Sae: 9 + 1 = 10

Select Sad

Its estimated total cost is smallest
SadG: 6 + 0 = 6

Reach G without either detour

Expanded: S → a → d
Returned path: SadG, cost 6

A* Uses Both Costs

65

Select the frontier node with the smallest g(n) + h(n)

Original A* Uses Both Costs mining illustration

Source: UC Berkeley CS188

A*-TSA Code

66

Download: a_star_tsa.py

A* Selects the Smallest g + h

67

Same frontier paths · a new priority

Frontier after expanding A

g: path cost · h: estimate at final state

Path	g	h	f = g + h
`AS`	140	253	393
`AT`	118	329	447
`AZ`	75	374	449

Remove AS: 393 is smallest

A* Keeps Comparing Frontier Paths

68

Which path leaves the frontier next?

Expanded path	f	Two lowest frontier priorities
A	366	AS: 393 · AT: 447
AS	393	ASR: 413 · ASF: 415
ASR	413	ASF: 415 · ASRP: 417
ASF	415	ASRP: 417 · AT: 447
ASRP	417	ASRPB: 418 · AT: 447

ASRPB: g=418, h(B)=0, f=418

Remove ASRPB and stop
Solution cost: 418

Tree shows the competing routes
Other generated branches are omitted

A*-TSA Practice {.comp3270-source-slide .source-slide-heading .comp3270-native-slide data-source-slide=“astar-practice”}

A*-TSA Practice

69

Start: S · Goal: G

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

Predict the expansion order
and returned path

Break ties by path-string order

Initial frontier: [(7, 'S')]

S @ 7 -> [(7, 'Sd'),
(10, 'SG'), (12, 'Sa')]

Sd @ 7 -> [(7, 'Sdb'), (9, 'Sde'),
(10, 'SG'), (12, 'Sa')]

Sdb @ 7 -> [(7, 'Sdbc'), (7, 'Sdbe'), (9, 'Sde'),
(10, 'SG'), (12, 'Sa')]

Sdbc @ 7 -> [(7, 'Sdbe'), (9, 'SdbcG'), (9, 'Sde'),
(10, 'SG'), (12, 'Sa')]

Sdbe @ 7 -> [(7, 'SdbeG'), (9, 'SdbcG'), (9, 'Sde'),
(10, 'SG'), (12, 'Sa')]

Solution path: (7, 'SdbeG')

Is A* Always Optimal?

70

It worked on Romania. Is that a guarantee?

Source: UC Berkeley CS188

Is A*-TSA Optimal? {.comp3270-source-slide .source-slide-heading .comp3270-native-slide data-source-slide=“astar-overestimate-question”}

Is A*-TSA Optimal?

71

Start: S · Goal: G
Which path will A*-TSA return?

Initial frontier: [(7, 'S')]
S @ 7 -> [(5, 'SG'), (7, 'Sa')]

Solution path: (5, 'SG')

Returned: SG, cost 5
Cheaper path: SaG, cost 1 + 3 = 4

h(a) = 6 overestimates the
true remaining cost of 3

Admissibility of Heuristic

72

An optimistic estimate

0 ≤ h(n) ≤ h*(n)

h*(n) is the true cheapest remaining cost

h(n) may underestimate, but must not overestimate

At a goal

h(goal)=0

Admissibility of Heuristic

73

Is h admissible for this graph?

h(a) = 6 > h*(a) = 3

h(S) = 7 > h*(S) = 4

Keep the same edge costs

What values are allowed for h(a)?

What values are allowed for h(S)?

Admissibility: Check Every State

74

From a

h*(a)=3
Therefore 0 ≤ h(a) ≤ 3

From S

h*(S)=min(5, 1+3)=4
Therefore 0 ≤ h(S) ≤ 4

Optimality of A*

75

Let

A be an optimal goal node
B be a suboptimal goal node
h be admissible

Claim

A will exit the frontier before B

Optimality of A*

76

Let n be an ancestor of A

Let B and n both be on the frontier

Claim: n exits the frontier before B

f(n) ≤ f(A)

Admissibility, with n on the optimal route to A

f(A) < f(B)

B is suboptimal and both goal heuristics are zero

Optimality of A*

77

All ancestors of A exit the frontier before B

A exits the frontier before B

A*-TSA is optimal with admissible h

Is This Heuristic Admissible?

78

True remaining costs

h*(G) = 0, h*(c) = 3
h*(a) = 4, h*(b) = 5
h*(S) = 5

Compare with h

0 ≤ 0 · 1 ≤ 3 · 4 ≤ 4
1 ≤ 5 · 2 ≤ 5

All estimates pass

Yes, this heuristic is admissible

Optimality of A*: TSA {.comp3270-source-slide .source-slide-heading .comp3270-native-slide data-source-slide=“astar-tsa-success”}

Optimality of A*: TSA

79

Start: S · Goal: G

Initial frontier: [(2, 'S')]

S @ 2 -> [(2, 'Sb'), (5, 'Sa')]

Sb @ 2 -> [(4, 'Sbc'), (5, 'Sa')]

Sbc @ 4 -> [(5, 'Sa'), (6, 'SbcG')]

Sa @ 5 -> [(3, 'Sac'), (6, 'SbcG')]

Sac @ 3 -> [(5, 'SacG'), (6, 'SbcG')]

Solution path: (5, 'SacG')

Optimal path: SacG, cost 5

Optimality of A*: GSA

80

Our GSA never expands a state twice

Initial frontier: [(2, 'S')]
Explored: ∅

S @ 2 -> [(2, 'Sb'), (5, 'Sa')]
Explored: {S}

Sb @ 2 -> [(4, 'Sbc'), (5, 'Sa')]
Explored: {S, b}

Sbc @ 4 -> [(5, 'Sa'), (6, 'SbcG')]
Explored: {S, b, c}

Sa @ 5 -> [(3, 'Sac'), (6, 'SbcG')]
Explored: {S, b, c, a}

Skip Sac: c already explored

Solution path: (6, 'SbcG')

What went wrong?

Consistency of Heuristic

81

Definition

For every arc a → c

h(a) − h(c) ≤ cost(a,c)

Equivalently

h(a) ≤ cost(a,c) + h(c)

Here: 4 ≤ 1 + 1 is false

Consequence of consistency

The f value along a path never decreases

Consistency Keeps f from Decreasing

82

Recall the cheaper path S → a → c

g = 1 · h = 4

f = 1 + 4 = 5

g = 2 · h = 1

f = 2 + 1 = 3

g rises by 1 · h falls by 3 → f falls by 2

Consistency: h cannot fall by more than the step costs

f(v) − f(u) = cost(u, v) − (h(u) − h(v)) ≥ 0

With consistent h, GSA first expands each state via a cheapest path
Closing the state cannot block a cheaper route later

Consistency of Heuristic

83

Is h consistent for this graph?

h(u) ≤ cost(u, v) + h(v)

S → a: 2 ≤ 1 + 4

S → b: 2 ≤ 1 + 1

a → c: 4 > 1 + 1

b → c: 1 ≤ 2 + 1

c → G: 1 ≤ 3 + 0

No: a → c violates consistency

Keep all edge costs fixed
How could we repair h?

Two Ways to Repair the Heuristic

84

Lower h(a) from 4 to 2

a → c: 2 ≤ 1 + 1
S → a: 2 ≤ 1 + 2

Or raise h(c) from 1 to 3

a → c: 4 ≤ 1 + 3
c → G: 3 ≤ 3 + 0

Both repairs work

Other edges remain consistent
Both heuristics remain admissible

A*: Key Takeaways

85

A*-TSA

Returns a cheapest solution when h is admissible

Our A*-GSA

Returns a cheapest solution when h is consistent

Will it find a solution?

Yes, if one exists, with finite branching
and every step cost ≥ ε > 0

Time and memory

Can still grow exponentially

Local Search

86

Planning vs. Identification

87

Planning

The path matters

Find a sequence of actions

Compare path costs and depths

Use heuristics and a frontier

Identification

The final arrangement matters

Find an assignment to variables

Example: assign a position to each queen

Local search can be faster for some problems

Example: 8-Queens

88

Lower cost is better
Goal: zero attacking pairs

State

Eight queens on the board, one per column

Successors

Move one queen to another square
in the same column

Every such move gives a neighbour

Cost function

Count pairs of queens that attack each other

Same row or diagonal

Direct: Q₆ and Q₈

Indirect: Q₂ and Q₈, with Q₆ between

Count Attacking Pairs

89

What is the cost of this state?

Count each pair once

Q₁ with Q₂, Q₃, Q₅+3

Q₂ with Q₃, Q₄, Q₆, Q₈+4

Q₃ with Q₅, Q₇+2

Q₄ with Q₅, Q₆, Q₇+3

Q₅ with Q₆, Q₇+2

Q₆ with Q₇, Q₈+2

Q₇ with Q₈+1

3 + 4 + 2 + 3 + 2 + 2 + 1 = 17

Count the Neighbours

90

How many different one-queen moves are possible?

One queen

7 other rows

Eight queens

8 × 7 = 56 neighbours

Evaluate the Neighbours

91

What would the cost be after each move?

Each number is the cost of the whole board
after moving that column’s queen

Example: move Q₂ to the top row
The resulting board costs 12

The current board costs 17

Lowest of all 56 costs: 12

Several moves tie; choose one at random

Improve the Current State

92

Current state

Cost: 17

Cost: 12

Compare neighbouring states

Three of the 56 neighbours; each moves the highlighted queen

Cost: 16

Cost: 12

Choose this state

Cost: 14

Cost = attacking pairs · Lower is better

Replace the current state, then repeat

Very little memory · Often finds good solutions in large spaces

Hill Climbing: One Attempt

93

Steepest descent for a cost we want to minimise

Start with a random state
If cost = 0, return the solution
Find the lowest-cost neighbour
Break ties at random
If its cost ≥ current cost, stop this attempt
Otherwise replace the current state; return to step 2

Accept only strictly lower costs

When Improvement Stops

94

Current cost: 2

Lowest neighbour cost: 2

No strictly better move

Stop, but not solved

An equal-cost move would be a sideways move

Try the Experiment

Download: comp3270.dirk.hk/eight_queens_hill_climbing.py

Does the Experiment Match?

96

Five seeds × 10,000 independent attempts

Solved

14.07%

Mean moves if solved

4.08

Mean moves if stopped

3.06

7,035 solutions in 50,000 attempts

Success across the five seeds: 13.23%–14.42%

Close to AIMA’s approximate 14% success and 4 / 3 moves

One strict attempt, without sideways moves · Accepted moves only

Try a New Starting State

97

Random restart: begin each attempt from a fresh random board

Attempt 1

Stopped: cost 1

Attempt 2

Stopped: cost 3

Attempt 3

Solved: cost 0

Task Preparation

Log in to Moodle → Click Ed

98

Task: BFS-GSA

TASK

SOLUTION

Solution: BFS-GSA

99

Start at S, goal G
Frontier: Add alphabetically

1. Exploration Order

2. Solution path

Uppercase strings, no spaces
Example: SAG

Submit on Ed

Explored
SABCDEFJH

Solution
SAEG

Task: DFS-TSA

TASK

SOLUTION

Solution: DFS-TSA

100

Start at S, goal G
Frontier: Add alphabetically

1. Exploration Order

2. Solution path

Uppercase strings, no spaces
Example: SAG

Submit on Ed

Explored
SCJFIH

Solution
SCFIHG

Task: UCS-GSA

TASK

SOLUTION

Solution: UCS-GSA

101

Start at S, goal G
Frontier: Add alphabetically

1. Exploration Order

2. Solution path

Uppercase strings, no spaces
Example: SAG

Submit on Ed

Explored
SBADECFJHI

Solution
SBEHG
Cost: 14

Task: A*-GSA

TASK

SOLUTION

Solution: A*-GSA

102

Submit on Ed

Start at S, goal G
Frontier: Add alphabetically

1. Exploration Order

2. Solution path

3. Admissible?

4. Consistent?

Uppercase strings, no spaces
Example: SAG

Explored: SABEH

Solution: SBEHG
Cost: 14

Admissible: Yes
$h(n)\leq h^*(n)$

Consistent: No
$B\to A:\;1<12-10$
$B\to E:\;5<12-6$

Task: Local Search

TASK

SOLUTION

Solution: Local Search

103

Minimise attacking pairs
No sideways moves

1. Sequence of moves

2. What is the cost after the last move?

Uppercase cells, separated by one space
Example: B4 E2

Submit on Ed

1. A4 D2

2. 1

One queen per column · Move within its column

Constraint Satisfaction Problems

104

Constraint Satisfaction Problems

105

A factored state records a value for each variable

A solution assigns every variable a value that satisfies all constraints

Use constraints to rule out combinations before exploring them

Defining CSPs

106

Variables $X=\{X_1,\ldots,X_n\}$

Domains $D_i$ contains the allowed values of $X_i$

ConstraintsAllowable combinations of values

A state is a partial or complete assignment $\{X_i=v_i,\;X_j=v_j,\ldots\}$

Solutions to CSPs

107

Consistent: no constraint is violated

Complete: every variable has a value

A solution is both consistent and complete

Australia: Map Colouring

108

Variables $X=\{\mathrm{WA,NT,Q,NSW,V,SA,T}\}$

Domains $D_i=\{\mathrm{red,green,blue}\}$

ConstraintsNeighbours have different colours

Constraint Graph It can be helpful to visualize a CSP as a constraint graph Nodes correspond to variables Arcs show existence of constraints 99 Q NSW V NT WA SA

Constraint Graph

109

Nodes represent variables

Edges represent constraints

Tasmania is independent
of the mainland variables

Q

NSW

V

NT

WA

SA

T

Solving CSPs

110

StateThe values assigned so far

Initial StateEmpty assignment $\{\}$

SuccessorAssign a value to an unassigned variable

Goal TestComplete and consistent

Breadth-First Search

111

All solutions are at depth 7

…

Try DFS

DFS

112

…

Early mistake …

…

Backtracking Search

113

Choose one unassigned variable at each levelBranch over its legal values

Try only values consistent with earlier assignments

If no legal value remains, backtrack

Depth-first search with these two ideas is backtracking search

Source

Backtracking 104 D = {red, green, blue} X = {WA, NT, Q, NSW, V, SA, T} . . .

Backtracking

114

. . .

Backtracking

115

Variables:

\{\mathrm{NSW},\mathrm{WA},\mathrm{NT},\mathrm{Q},\mathrm{SA},\mathrm{V},\mathrm{T}\}

Colors:

\{\mathrm{red},\mathrm{green},\mathrm{blue}\}

Q

NSW

V

NT

WA

SA

T

NSW

WA

NT

Q

SA

Q

NT

Q

SA

Q

NT

Q

WA

NT

Q

SA

V

T

Follow NSW, WA, NT, Q, SA, V, T; try red, green, blue. Each click shows a candidate, including rejected colours.

Assign NSW red.

WA may also be red: WA and NSW are not neighbours.

Reject NT red: it conflicts with WA.

Assign NT green.

Reject Q red: it conflicts with NSW.

Reject Q green: it conflicts with NT.

Assign Q blue.

Reject SA red: it conflicts with NSW and WA.

Reject SA green: it conflicts with NT.

Reject SA blue: it conflicts with Q. No SA value works; backtrack.

Restore Q and SA to unassigned. Try NT blue.

Reject Q red: it conflicts with NSW.

Assign Q green.

Reject SA red: it conflicts with NSW and WA.

Reject SA green: it conflicts with Q.

Reject SA blue: it conflicts with NT. Backtrack to Q.

Reject Q blue: it conflicts with NT. Q has no further value; backtrack to WA.

Restore NT and Q to unassigned. Try WA green.

Assign NT red.

Reject Q red: it conflicts with NSW and NT.

Assign Q green.

Reject SA red: it conflicts with NSW and NT.

Reject SA green: it conflicts with WA and Q.

Assign SA blue.

Reject V red: it conflicts with NSW.

Assign V green.

Assign T red. The complete assignment satisfies every constraint.

[Sources] - Original COMP3270 2024–25 source slide 105: 01_search.pptx. - Original graph, candidate-colour reveals and click count retained; domain states recomputed from the fixed-order Australia CSP.

Backtracking Search

116

Choose a variable → Try a consistent value → Recurse → Undo

Download: csp_backtracking.py

Improving Backtracking

117

Can we detect inevitable failure earlier?

Forward checking: remove conflicting values from neighbours

Constraint propagation: repeat these deductions with AC-3

Forward Checking

118

After each assignment, remove conflicting values
from the domains of unassigned neighbours

WA	NT	Q	NSW	V	SA	T

Detect failure earlier

Backtracking with Forward Checking

119

Variables:

\{\mathrm{NSW},\mathrm{WA},\mathrm{NT},\mathrm{Q},\mathrm{SA},\mathrm{V},\mathrm{T}\}

Colors:

\{\mathrm{red},\mathrm{green},\mathrm{blue}\}

Q

NSW

V

NT

WA

SA

T

NSW

WA

NT

Q

NT

Q

NT

Q

WA

NT

Q

SA

V

T

Follow the fixed variable and colour order. Chips show domains of unassigned variables only.

Assign NSW red; remove red from Q, SA and V.

Assign WA red; remove red from NT.

Assign NT green. Q and SA now each have only blue.

Try Q blue. SA loses its last value, so this branch fails.

Restore the failed branch. Try NT blue; Q and SA now each have only green.

Try Q green. SA loses its last value, so backtrack again.

Restore domains and unassign NT and Q. Try WA green.

Assign NT red. Q still has green or blue; SA has only blue.

Assign Q green. SA remains blue.

Assign SA blue; V is now forced to green.

Assign V green.

Assign T red. All constraints are satisfied.

[Sources] - Original COMP3270 2024–25 source slide 109: 01_search.pptx. - Original graph, candidate-colour reveals and click count retained; domain states recomputed from the fixed-order Australia CSP.

When Forward Checking Misses Failure

120

After each assignment, remove conflicting values
from the domains of unassigned neighbours

WA	NT	Q	NSW	V	SA	T

Doomed to
fail

Can we detect
this earlier?

Consistency of an Arc An arc X ⟶ Y is consistent iff for every x in the tail there is some y in the head which could be assigned without violating a constrain 1

Consistency of an Arc

121

An arc

X\to Y

is consistent if every

x\in D_X

has a compatible

y\in D_Y

WA	NT	Q	NSW	V	SA	T

\forall x\in D_X,\;\exists y\in D_Y:\;C_{XY}(x,y)

Link

Constraint Propagation

122

When a domain shrinks, recheck arcs pointing into it
Repeat until no domain changes, or a domain is empty

X\to Y

: every value in

D_X

needs a compatible value in

D_Y

WA	NT	Q	NSW	V	SA	T

AC-3

123

Why exclude
the reverse arc?

Revise an arc → Revisit affected incoming arcs

Download: csp_ac3.py

Why Exclude the Reverse Arc?

124

$X_i$

$X_j$

$X_{k_1}$

$X_{k_2}$

$X_{k_3}$

Why don’t I have to add this one ?

Update the domain
of $X_i$

$X_i$ has four neighbours
including $X_j$

$=X_{k_4}$

Link

Backtracking with AC-3

125

Variables:

\{\mathrm{NSW},\mathrm{WA},\mathrm{NT},\mathrm{Q},\mathrm{SA},\mathrm{V},\mathrm{T}\}

Colors:

\{\mathrm{red},\mathrm{green},\mathrm{blue}\}

Q

NSW

V

NT

WA

SA

T

NSW

WA

NT

WA

NT

Q

SA

V

T

Use the same variable and colour order. Chips show AC-3 domains for unassigned variables; restore them on backtracking.

Assign NSW red. AC-3 removes red from its neighbours.

Assign WA red. NT, Q and SA retain green or blue; arc consistency has not detected the failure.

Try NT green. Propagation empties a domain before Q is assigned; backtrack.

Restore domains and try NT blue. Propagation again empties a domain.

Restore domains, unassign NT and try WA green. AC-3 forces the remaining mainland colours.

Assign the forced red value to NT.

Assign the forced green value to Q.

Assign the forced blue value to SA.

Assign the forced green value to V.

Assign T red. The complete assignment is consistent.

[Sources] - Original COMP3270 2024–25 source slide 115: 01_search.pptx. - Original graph, candidate-colour reveals and click count retained; domain states recomputed from the fixed-order Australia CSP.

Variable and Value Ordering

126

Variable Ordering

Minimum Remaining Values (MRV)

Choose the variable with the fewest legal values

Most constrained variable

Fail-first heuristic

Break MRV Ties

Degree Heuristic

Most constraints on unassigned variables

Value Ordering

Least Constraining Value (LCV)

Rules out the fewest values in unassigned neighbours

Variable Ordering (MRV) Minimum remaining values Choose the variable with the fewest legal left values in its domain Most constrained variable Fail-first heuris

Variable Ordering (MRV)

127

Minimum Remaining Values

Choose the unassigned variable with the fewest legal values

Most constrained variable · Fail-first heuristic

Using Forward Checking

Variable Ordering (MRV + Deg) Degree Heuristic (Deg) Choose the variable with the most constraints on remaining variables 118 using forward checking D = {red, g

Variable Ordering (MRV + Deg)

128

Degree Heuristic

Among MRV ties, choose the variable with the most
constraints on unassigned variables

using forward checking

Value Ordering (LCV) Choose the value that rules out the fewest values in the remaining variables Least constraining value (LCV) 119 Suppose we have decided to

Value Ordering (LCV)

129

Least Constraining Value

Try the value that removes the fewest options
from unassigned neighbours

Assign Q Next
Which Colour First?

Backtracking with All Heuristics

130

AC-3 · MRV · Degree · LCV

Variables:

\{\mathrm{NSW},\mathrm{WA},\mathrm{NT},\mathrm{Q},\mathrm{SA},\mathrm{V},\mathrm{T}\}

Colors:

\{\mathrm{red},\mathrm{green},\mathrm{blue}\}

Q

NSW

V

NT

WA

SA

T

SA

NSW

WA

NT

Q

V

T

Choose with MRV, then remaining degree, then the listed tie order. LCV chooses the colour; colour ties use red, green, blue.

SA has degree 5. All colours tie under LCV, so choose red.

NSW wins the remaining degree tie. Green and blue tie under LCV. Choose green; AC-3 forces the other mainland domains.

NT has two unassigned neighbours, WA and Q. MRV and degree therefore select NT next.

WA, Q and V are singleton domains with degree zero. The listed order selects WA.

Q is next in the remaining singleton tie.

Assign the forced blue value to V.

T has no constraints. All colours tie, so choose red. The assignment is complete and consistent.

[Sources] - Original COMP3270 2024–25 source slide 120: 01_search.pptx; retained native graph and colour reveals. - Selection order and domain propagation checked in documents/c1_csp_content_review.md.

Adversarial Search

131

Other Agents Choose Their Own Moves

132

Our next state depends on our move and their response

Chance: Later

Here: Two Players · Alternating Turns · Deterministic · Fully Observable

Zero-Sum: What Helps MAX Hurts MIN

Defining a Game

133

State s; Initial State s₀

Board configuration and player to move

Player(s)

Whose turn is it?

Actions(s); Result(s, a)

Legal moves; state after a move

TerminalTest(s)

Has the game ended?

Utility(s, p)

Final payoff for player p

Game Tree: Nodes Are States; Edges Are Moves

Tic-Tac-Toe Game Tree

134

Players

X is MAX
O is MIN

Utility for X

Win: +1
Draw: 0
Loss: −1

State Includes
the Player to Move

Think About Their Reply

135

One agent reasons about its opponent, who reasons about its opponent

Back Up Values from the Leaves

136

MAX Chooses Left: 3 Is Larger Than 2

Minimax Follows the Tree Recursively

137

def minimax(tree, maximizing=True):
    if not isinstance(tree, list): return tree
    values = [minimax(child, not maximizing) for child in tree]
    return max(values) if maximizing else min(values)

Base Case
A leaf returns its utility

Recursive Step
Visit every child and switch the player

Back Up
MAX returns max; MIN returns min

One Recursive Call per State in the Game Tree

Run Minimax on a Deeper Tree

138

Download: minimax.py

Minimax Practice

139

MIN Moves First: What Is the Root Value? Which Move?

Value 1 · MIN Chooses the Middle Branch

Task: Minimax

Solution: Minimax

TASK

SOLUTION

140

Find the Values of x That Make Left Strictly Better

Use x on the left
No spaces
Example: x<3

Submit on Ed

Left = min(max(x, −8), 11) · Right = 8

x > 8: Left Wins · x = 8: Tie

What Does Minimax Guarantee?

141

An Optimal Strategy Against Optimal Opposition

Different opponents may choose differently

It Maximizes the Worst-Case Payoff

It Does Not Predict Every Opponent’s Actual Move

What If MIN Makes Mistakes?

142

Left Guarantees 10 · Right Guarantees 9

If MIN Chooses Randomly: Right Averages 54.5

Minimax Properties

143

Finite Game Tree · Branching Factor b · Maximum Depth m

Complete?

Yes, for a finite game tree

Optimal?

Yes, against optimal opposition

Time

O(

b^{m}

)

Space

O(bm), with DFS and stored successor lists

Search All Replies, Depth First

Full Search Is Too Large

144

Illustrative Chess Estimate

b ≈ 35 · m ≈ 100

$35^{100}$ ≈ 2.6 × $10^{154}$

We Cannot Search to Every Terminal Position

Resource Limits

145

Agent can see only part of a large search landscape

Stop at a Depth Limit

146

Depth Limit ℓ = 2 · MAX and MIN Still Alternate

Terminal: Exact Utility · Cutoff: Estimate the Position

Time: O( $b^{ℓ}$ ) · Space: O(bℓ)

Back Up the Cutoff Estimates

147

Estimated Root Value: 4 · Choose Right

The Guarantee Depends on the Estimates

Evaluate a Non-Terminal Position

148

Eval(s): Estimate the Position’s Value for MAX

Ideal: The True Minimax Value

Useful: Fast Enough to Evaluate Many Positions

A Larger Number Should Mean a Better Position for MAX

Task: Evaluation Functions

Solution: Evaluation Functions

TASK

SOLUTION

149

LEFT POSITION

Left: Pacman at 1, food at 4, ghost at 8

RIGHT POSITION

Right: Pacman at 1, food at 3, ghost at 4

Which Functions Prefer the Left Position?

$f = distance to food \cdot g = distance to ghost$

A. $\frac{1}{f}$

B. $g$

C. $g + \frac{1}{f}$

D. $g + \frac{1000}{f}$

Left: f = 3, g = 7 · Right: f = 2, g = 3

B and C Prefer Left · A and D Prefer Right

Combine Features into an Evaluation

150

$Eval (s) = w_{1} f_{1} (s) + \dots + w_{n} f_{n} (s)$

Pawn

1

Knight / Bishop

3

Rook

5

Queen

9

Chess board: material is only part of the evaluation

Feature: MAX’s Material − MIN’s Material

Also Consider King Safety and Pawn Structure

Material Is Not Enough

151

Who Has the Advantage in Each Position?

Two chess positions that differ only in the lower-right rook

(a) Material Count: Black Has More Material

(b) Tactical Check: White Can Capture the Queen

Material Alone Can Miss an Immediate Tactic

Depth and Evaluation Error

152

At the Cutoff, We Estimate a Non-Terminal State

A Deeper Cutoff Is Often Closer to the Real Outcome

Tradeoff: Better Features or More Search?

The Horizon Effect

153

A Bad Consequence Lies Just Beyond the Cutoff

A Delaying Move Pushes It Out of Sight

The Delay May Make the Final Outcome Worse

A search agent sees only a limited horizon

Can Black Save the Bishop?

154

Black to Move

Can a Delaying Tactic Avoid the Loss?

No · It Only Pushes the Loss Beyond a Shallow Horizon

Can We Skip Part of the Tree?

155

Can We Compute the Exact Minimax Choice Without Visiting Every Node?

Yes · When a Branch Cannot Affect the Decision

A Branch Cannot Beat the Current Best

156

Left Gives 3 · Right MIN Finds 2

The Other Right Leaves Cannot Change MAX’s Choice

Alpha–Beta Pruning

157

Skip Branches That Cannot Change the Root Decision

Result

Same minimax value and optimal root action

Benefit

Often visits far fewer nodes

Requirement

Track bounds while searching left to right

Pruning Changes Work, Not the Answer

MIN Pruning

158

MIN Pruning at Greater Depth

159

MIN Pruning at Greater Depth

160

MIN Pruning at Greater Depth

161

Pruning Conditions

162

Which Values Can Change the Choice?

163

MIN Pruning

164

Initial Bounds

165

Root α = −∞ · Current β = +∞

First MAX Returns 6

166

Left MIN updates β to 6

Left MIN Sets Alpha to 6

167

Root updates α to 6

Middle MAX Returns 2

168

Middle MIN updates β to 2

Middle MIN Reaches the Cutoff

169

β = 2 ≤ α = 6

Middle Branch Pruned

170

β = 2 ≤ α = 6

Right MAX Returns 8

171

Right MIN updates β to 8

Next MAX Sees 9

172

Current v = 9 · Right MIN β = 8

Right MAX Reaches the Cutoff

173

v = 9 ≥ β = 8

Right MIN Returns 8

174

Root α = 6 · Right value = 8

Root Chooses 8

175

Final α = 8

Alpha–Beta Search in Python

176

Task: Alpha–Beta Pruning

Solution: Alpha–Beta Pruning

TASK

SOLUTION

177

Search Left to Right · Which Branch Is Pruned?

QR code for the first alpha-beta pruning Ed question

Submit on Edhttps://edstem.org/au/courses/41129/lessons/119785/slides/821213

Pruned Branch: F · Left MIN Gives 8, Then Right MIN Finds 4 ≤ α

Task: Deeper Alpha–Beta Pruning

Solution: Deeper Alpha–Beta Pruning

TASK

SOLUTION

178

Search Left to Right · Which Branches Are Pruned?

QR code for the deeper alpha-beta pruning Ed question

Submit on Edhttps://edstem.org/au/courses/41129/lessons/119786/slides/821214

Pruned Branches: F, J, M, N

A Bound Is Not an Exact Value

179

Search Left to Right · Which Move Should MAX Keep?

A Returns 10 · Keep A and Set α = 10

B Returns 10 as a Bound · This Does Not Prove a Tie

Keep A · Replace the Best Move Only on a Strict Improvement

Move Ordering Controls Pruning

180

Same Minimax Value: 3 · Different Amount of Search

Good Ordering Searches Much Less

181

Minimax: O( $b^{m}$ )

Ideal Alpha–Beta Ordering: O( $b^{m/2}$ )

Roughly Twice the Search Depth for the Same Node Budget

Example: b = 10 and m = 6 Gives 10⁶ Leaves vs About 10³

Worst Case Remains O( $b^{m}$ )

Knuth & Moore (1975), An Analysis of Alpha-Beta Pruning

Worst Case Uses MIN’s Choice

182

MAX Chooses Left: 10 > 9

Chance Uses the Expected Value

183

MAX Chooses Right: 54.5 > 10

Why Chance Nodes Appear

184

Explicit randomness

Dice, shuffled cards, noisy outcomes

Agent model

An opponent policy represented by probabilities

Action failure

The intended action may not occur

A Chance Node Needs a Probability Model

Expected Value Is Only as Good as That Model

Expectimax Search

185

MAX Node

Take the Largest Child Value

CHANCE Node

Take the Probability-Weighted Average

Terminal Node

Return Utility

An agent reasons about uncertain outcomes

CHANCE: V(s) = Σ pᵢ V(sᵢ)

Expectimax Example

186

0.9(2) + 0.1(3) = 2.1

0.9(1) + 0.1(4) = 1.3

MAX Chooses Left: 2.1 > 1.3

Task: Minimax or Expectimax?

187

TASK

QR code for the Pacman minimax and expectimax Ed activity

Submit on Ed

Pacman First: WEST or EAST

After WEST and Both Ghosts, Pacman: EAST or SOUTH

Lower Ghost: NORTH or EAST · Upper Ghost: WEST only

Minimax: Worst Legal Ghost Move

Expectimax: Lower Ghost N/E with Probability 0.5 Each

Only Food Eaten: Win · Ghost Collision: Loss

Score: −1 per Pacman action · +10 food · +500 win · −500 loss

Collision on Food: Loss, No Food Points

1. Under minimax, what is Pacman’s optimal first action?

2. What value does minimax assign to the root?

3. Under expectimax, what is Pacman’s optimal first action?

4. What value does expectimax assign to the root?

Solution: Pacman Game Tree

188

SOLUTION

Solution: Minimax

189

SOLUTION

Solution: Expectimax

190

SOLUTION

More Than Two Agents

191

Utility Vectors

192

Red chooses the first value · Green the second · Blue the third

Reading

193

AIMA Chapter 3

Search · 88 pageshttps://comp3270.dirk.hk/AIMA_Chapter_3.pdf

AIMA Chapter 4

Search in Complex Environments · 62 pageshttps://comp3270.dirk.hk/AIMA_Chapter_4.pdf

AIMA Chapter 5

Adversarial Search · 63 pageshttps://comp3270.dirk.hk/AIMA_Chapter_5.pdf

AIMA Chapter 6

Constraint Satisfaction · 50 pageshttps://comp3270.dirk.hk/AIMA_Chapter_6.pdf

Password: Dirk