Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 46 ยท Practice and Review

Practice: Classical AI Exercises

Twenty graded exercises with runnable Python solutions covering search, CSPs, games, logic, planning, probability and robotics kinematics.

Reading about search, logic and probability is easy. Doing a problem with a pencil is where the ideas become yours. This page has twenty graded exercises that cover the whole course: uninformed and informed search, constraint satisfaction, games, logic, planning, probability, decisions and robot kinematics.

How to use it: read the statement, try it on paper first, open the hint only if you are stuck, and then compare with the solution. Most solutions come with code you can run, so you can check your hand calculation against the machine. Each exercise has a level: easy (one idea, a few minutes), medium (a short calculation or a small program) and hard (needs insight, or a derivation you must justify).

Scoring yourself. Give yourself 1 point for each easy exercise solved without the hint, 2 for medium and 3 for hard. The maximum is 37. Below 15, re-read the lessons linked in the solutions. Above 28, move on to the interview questions.

Exercise 1 (easy): the size of the 8-puzzle

How many different arrangements of the tiles 1 to 8 and the blank exist? How many of them can be reached from the goal by legal slides? What is the average number of moves available from a state, and how many moves does the hardest reachable puzzle need?

Hint. The 3 by 3 board has 9 cells. Exactly half of all arrangements are unreachable because of a parity argument. For the rest, run a breadth-first search from the goal and record each state's depth.

Exercise 2 (easy): BFS versus DFS order

The graph below has start S and goal G. Children are expanded in alphabetical order, and the goal test happens when a node is removed from the frontier. In what order does breadth-first search expand nodes? In what order does depth-first search expand them? Which one finds the path with fewer moves?

graph LR
    S --> A
    S --> B
    A --> C
    A --> D
    B --> D
    B --> G
    D --> G

The graph for exercise 2. Directed edges go from left to right.

Solution to exercises 1 and 2. The 8-puzzle has 9! = 362,880 arrangements, and exactly half, 181,440, are reachable. The program confirms it and also reports that the hardest puzzle needs 31 moves. The average branching factor is 8/3, because the blank has two moves in a corner, three on an edge and four in the centre. For exercise 2, BFS expands S A B C D G: it finds G through B after looking at all of depth 1 and the shallow nodes C and D first. DFS dives down the first branch and expands S A C D G, which reaches the goal along S, A, D, G: three moves, while BFS returns S, B, G, which is two. BFS is optimal in the number of moves, and DFS is not. See BFS and DFS.

Python Solutions 1 and 2: counting states and ordering expansions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Exercise 3 (medium): admissible, consistent, or neither?

Edges: S to A costs 1, S to B costs 4, A to B costs 2, A to G costs 12, B to G costs 5. A heuristic gives h(S)=7, h(A)=7, h(B)=4, h(G)=0. Is it admissible? Is it consistent? Does A* still find the optimal path?

Hint. Compute the true cost to the goal from every node, then compare. For consistency check the inequality h(u) <= cost(u, v) + h(v) on every edge.

Exercise 4 (medium): uniform-cost search by hand

For the weighted graph in the code below (edges S-A 2, S-B 5, A-C 2, A-G 9, B-G 3, C-G 6), list the order in which uniform-cost search expands nodes, with their path costs, and give the cost of the optimal path.

Exercise 5 (hard): the price of iterative deepening

Iterative deepening re-generates the upper levels again and again. For branching factor b = 10 and a goal at depth d = 5, how many nodes does it generate compared to breadth-first search? Argue why the overhead is small.

Solution to exercises 3, 4 and 5. The true costs to the goal are 8 for S, 7 for A and 5 for B. Every heuristic value is at most the true cost, so h is admissible. It is not consistent: on the edge A -> B we have h(A) = 7, which is larger than 2 + h(B) = 6. Because the heuristic is admissible, A* with a graph search that is willing to reopen a node whose g improves still returns the optimal cost 8 along S, A, B, G. Without the reopening rule an inconsistent heuristic can make graph-search A* miss the optimum, which is why consistency is the property most implementations rely on (see admissible and consistent heuristics).

For exercise 4, uniform-cost search expands S (0), A (2), C (4), B (5) and G (8). Notice that G is first generated at cost 11 through A and later at 10 through C, but it is expanded only when it is the cheapest node in the frontier, at cost 8 through B. The optimal cost is 8 with the path S, B, G. That is the reason uniform-cost search tests the goal when a node is removed, not when it is generated.

For exercise 5, breadth-first search generates 111,111 nodes. Iterative deepening builds level i a total of d - i + 1 times, which gives 123,456 nodes, only 11 percent more. The deepest level, which holds almost all the nodes, is built once, and each level is about b times larger than the previous one, so the repeated upper levels are cheap. The memory saving, from exponential to linear, easily pays for the overhead (iterative deepening).

Python Solutions 3, 4 and 5: heuristics, UCS and deepening cost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 2: Constraint satisfaction

Exercise 6 (easy): formulate map colouring

Formulate the map of Australia as a CSP with three colours: the regions are WA, NT, SA, Q, NSW, V and T (Tasmania). WA borders NT and SA; NT borders SA and Q; SA borders Q, NSW and V; Q borders NSW; NSW borders V. How many variables and constraints are there? What can you say about Tasmania?

Exercise 7 (medium): AC-3 on a chain

Three variables X, Y, Z each have the domain {1, 2, 3}, with the constraints X < Y and Y < Z. Run AC-3 and give the final domains.

Exercise 8 (medium): which variable next?

After assigning WA = red in exercise 6 and removing red from its neighbours (forward checking), which variable does the minimum-remaining-values (MRV) heuristic pick? What breaks a tie?

Solution to exercises 6, 7 and 8. There are 7 variables, each with the domain {red, green, blue}, and 9 binary constraints "these two regions have different colours", one per border. Tasmania touches nothing, so it is an independent sub-problem: any colour works, and a solver should not waste backtracking on it. For exercise 7, AC-3 shrinks the domains in five revisions to X = {1}, Y = {2}, Z = {3}, which is the unique solution found with no search at all. For exercise 8, after WA = red both NT and SA have only two colours left, so MRV is tied. The degree heuristic picks the more constrained one in the constraint graph: SA has 5 neighbours and NT has 3, so SA is chosen. See backtracking for CSPs and constraint propagation.

Python Solutions 6, 7 and 8: a CSP workbench

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 3: Games

Exercise 9 (easy): minimax by hand

The root is a MAX node with three MIN children. Their leaves, from left to right, are (5, 9, 1), (7, 6, 8) and (2, 4, 3). What is the minimax value and which move does MAX choose?

graph TD
    R["MAX"] --> A["MIN"]
    R --> B["MIN"]
    R --> C["MIN"]
    A --> A1["5"]
    A --> A2["9"]
    A --> A3["1"]
    B --> B1["7"]
    B --> B2["6"]
    B --> B3["8"]
    C --> C1["2"]
    C --> C2["4"]
    C --> C3["3"]

The game tree for exercises 9 and 10.

Exercise 10 (medium): alpha-beta on the same tree

Run alpha-beta pruning, visiting children and leaves left to right. Which leaves are examined, which are pruned, and why does the answer not change?

Exercise 11 (hard): the best case of alpha-beta

A game has branching factor b = 10 and the search looks m = 6 plies ahead. How many leaves does plain minimax visit and how many does alpha-beta visit at best? What does that mean for how deep you can search?

Solution to exercises 9, 10 and 11. The MIN values are 1, 6 and 2, so the minimax value is 6 and MAX picks the middle move. In alpha-beta, the first subtree is fully explored (MAX now has at least 1), and the second gives 6, so alpha = 6. In the third subtree the first leaf is 2, which is at most alpha, so MIN could only make this branch even worse for MAX and the leaves 4 and 3 are pruned: 7 of 9 leaves are examined and the value is still 6. Pruning never changes the result; it only skips work that cannot matter. For exercise 11, plain minimax visits 10^6 = 1,000,000 leaves. With perfect move ordering alpha-beta needs about b^(m/2) = 1,000, so in the same time you can search twice as deep. Real programs get part of the way there with good move ordering (alpha-beta pruning).

Python Solutions 9, 10 and 11: minimax and pruning

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 4: Logic

Exercise 12 (easy): entailment by truth table

Does the knowledge base (P -> Q) and (Q -> R) entail P -> R? Check all eight models.

Exercise 13 (medium): a resolution proof

The knowledge base is P or Q, not P or R, not Q or R. Prove R by resolution refutation.

Hint. Add the negated query not R to the clauses and derive the empty clause.

Exercise 14 (medium): unification

Unify P(x, f(y)) with P(a, f(g(z))). Then try P(x, x) with P(a, b), and x with f(x).

Solution to exercises 12, 13 and 14. The knowledge base is true in 4 of the 8 models, and in each of them P -> R is true as well, so the entailment holds (this is the hypothetical syllogism). For exercise 13, resolve not R with not Q or R to get not Q, resolve not R with not P or R to get not P, resolve not Q with P or Q to get P, and finally P with not P gives the empty clause. A contradiction means that not R cannot hold together with the knowledge base, so R is entailed. For exercise 14, the first unification succeeds with x = a and y = g(z). The second fails because x would have to be both a and b. The third fails the occurs check: x cannot equal a term that contains x, since that would be an infinite term. See resolution and first-order logic.

Python Solutions 12, 13 and 14: logic in 70 lines

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 5: Planning

Exercise 15 (medium): applying a STRIPS action

Write the action Move(b, from, to) for the blocks world. In the state on(A,table), on(B,A), on(C,table), clear(B), clear(C), apply Move(B, A, C). Is Move(A, table, C) applicable?

Exercise 16 (hard): relaxed heuristics

A cake needs flour and eggs, each bought with one action that needs money, and then one bake action. Compute h_add and h_max of the goal cake in the delete-relaxed problem. Is either guaranteed to be admissible?

Solution to exercises 15 and 16. The preconditions of Move(b, from, to) are on(b, from), clear(b) and clear(to). It adds on(b, to) and clear(from), and it deletes on(b, from) and clear(to). After Move(B, A, C) block A is clear, B sits on C, and C is no longer clear. Move(A, table, C) is not applicable, because clear(A) is false while B sits on it. For exercise 16, h_add(cake) = 1 + 1 + 1 = 3 (bake plus the costs of flour and eggs, added), while h_max(cake) = 1 + max(1, 1) = 2. The true plan has 3 steps. h_max is admissible, because it takes only the most expensive precondition. h_add is informative but not admissible in general: when two subgoals share an action, adding counts it twice. Here it happens to be exact, because flour and eggs need different actions (planning heuristics).

Python Solutions 15 and 16: STRIPS and delete relaxation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 6: Probability and decisions

Exercise 17 (easy): the screening paradox

A disease affects 1 percent of a population. A test detects it in 90 percent of sick people and gives a false positive for 5 percent of healthy people. A random person tests positive. What is the probability that they are sick?

Exercise 18 (medium): one filtering step

A weather model has two states, Rain and Sun. Rain is followed by Rain with probability 0.7, Sun by Sun with 0.8. You carry an umbrella with probability 0.9 on rainy days and 0.2 on sunny days. Your belief is (0.5, 0.5) and today you see an umbrella. What is the new belief?

Exercise 19 (medium): value iteration

A three-state chain has the states 0, 1 and 2. State 2 is terminal with value 10. Each step costs 1 and the discount is 0.9. The action right moves one state to the right with probability 0.8 and otherwise stays; stay stays. Do three sweeps of value iteration.

Solution to exercises 17, 18 and 19. For exercise 17, think of 1,000 people: 10 are sick and 9 of them test positive; of the 990 healthy people about 49.5 test positive too. So only 9 of the 58.5 positives are sick: 15.4 percent, far lower than most people guess, because the disease is rare. For exercise 18, the prediction step gives Rain 0.45 and Sun 0.55. The umbrella multiplies them by 0.9 and 0.2, giving 0.405 and 0.11, and normalizing gives Rain 0.786 and Sun 0.214. For exercise 19, right is better than stay in both non-terminal states, so the values grow towards the goal: after the first sweep V = [-1, 6.2, 10], after the second [3.284, 7.316, 10], after the third [4.859, 7.517, 10]. Information travels one state per sweep, and the values converge to a fixed point. See filtering and MDPs.

Python Solutions 17, 18 and 19: Bayes, filtering and value iteration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 7: Robotics

A planar arm has two links of length 1. (a) Where is the end effector when the first joint is at 90 degrees and the second joint at -90 degrees? (b) Which joint angles reach the point (1, 1)? (c) Can the arm reach (2.5, 0)?

Solution to exercise 20. (a) The forward kinematics give (cos 90 + cos 0, sin 90 + sin 0) = (1, 1). (b) Inverse kinematics has two solutions, called elbow-up and elbow-down: joint angles (0, 90) and (90, -90) degrees both reach (1, 1). The second is the pose from part (a). (c) No: the arm's maximum reach is 1 + 1 = 2, so a point 2.5 away is outside the workspace and the inverse function returns an empty list. See forward and inverse kinematics.

Python Solution 20: forward and inverse kinematics

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In exercise 3 the heuristic is admissible but not consistent. What is the safe way to run A* with it on a graph?

    With an inconsistent heuristic the first path found to a node may not be the cheapest. Re-opening a node when its g-value improves keeps A* optimal.
  2. 2. Why does alpha-beta pruning not change the minimax value?

    A pruned branch is one where a player already has a better option elsewhere, so its exact value cannot change the value at the root.
  3. 3. A test is 90 percent sensitive with a 5 percent false positive rate for a disease with 1 percent prevalence. A positive result means about:

    Bayes rule gives 0.009 / 0.0585 = 15.4 percent. The false positives from the large healthy group outnumber the true positives.
  4. 4. A two-link arm of total length 2 is asked to reach a point at distance 2.5. What does inverse kinematics return?

    The farthest point the arm can reach is at distance 2 from the base. Beyond that the cosine of the elbow angle would be greater than 1, which is impossible.

Summary

  • Counting states and checking small cases by program is the fastest way to build intuition about search spaces.
  • Admissibility (never overestimating) is what optimal A* needs; consistency makes the search simpler and avoids reopening nodes.
  • Constraint propagation can solve small CSPs without any search, and MRV with the degree heuristic picks the most constrained variable.
  • Alpha-beta pruning keeps the minimax value while skipping irrelevant branches; with good ordering it searches twice as deep.
  • Resolution refutation and unification are mechanical procedures that a computer can run.
  • Bayes rule, filtering and value iteration are all small loops over probabilities.
  • Inverse kinematics can have two solutions or none.

Next: Classical AI Interview Questions.