Problem Solving and Search


This is a 1st-year course in the UvA's BSc Artificial Intelligence programme. It provides an introduction to algorithmic thinking and basic problem solving techniques in AI. Special emphasis is put on search algorithms, including both uninformed search algorithms such as depth-first search and breadth-first search, and heuristic-guided search with the A* algorithm. These algorithms are implemented in the declarative programming language Prolog. This website provides some general information on the course as well as access to the lecture notes and the slides used during classes. For day-to-day information, including homework assignments, please refer to the UvA Blackboard system.

Examples. During weekly homework assignments you will encounter a wide variety of exciting but challenging problems in AI and you will learn how to solve them by applying the fundamental principles and techniques taught during lectures. Below are some representative examples.

In the Letters Game, familiar from the famous television game show Countdown (also known as Cijfers en Letters), the contestants have to construct the longest possible word from a given list of nine letters. For example, for the list [r,d,i,o,m,t,a,p,v], a strong answer would be 'dioptra'.

You will learn that it is fairly easy to write a program that beats any human player hands down at this game.

In the Numbers Game, also part of Countdown, contestants are given one large and six smaller numbers. They have to construct a mathematical expression using only the small numbers to get as close as possible to the large one. For example, for the list [25,50,75,100,3,6] and target 444, a perfect solution would be 3*(50+100)-6.

Although much more challenging than the Letters Game, you will still learn how to write a program that can beat the very best human contestants also at this game.

At the heart of online travel recommendation services such as the one offered by Google are algorithms for finding the shortest path between two points on a map.

Google Travel Recommendation for the Amsterdam-Maastricht Route

You will learn how to write a program to find the shortest route between any two major cities in the Netherlands.

In the Treaty of Rome (1957) the six founding members of the European Union fixed the voting rule to decide on proposals in the European Council. To pass, a proposal had to get at least 12 votes. France, Germany, and Italy each had 4 votes; Belgium and the Netherlands each had 2 votes; and Luxembourg had 1 vote. Is that fair?

Treaty of Rome Signing Ceremony (source: Wikipedia)

You will learn how to write a program to compute the voting power of each country, so as to be able to discuss such questions of fairness systematically.

You will learn how to write a program to automatically solve some of the most difficult exercises for your Logic course, such as producing a semantic tableau to prove that a given conclusion logically follows from a given set of premises.

Blackboard with Tableau Rules (source: Introduction to Logic, IIT Kanpur)

Alas, by the time you will know enough about algorithms and programming to do this, the Logic course will have moved on to even more difficult material.

In 1742, in a letter to the famous mathematician Leonhard Euler, Christian Goldbach conjectured that every even number greater than 2 is the sum of two prime numbers. To date, no mathematician has been able to prove that Goldbach's Conjecture really is true for all even numbers.

Goldbach's letter to Euler (source: Wikipedia)

You will learn how to write a program that confirms the conjecture for all numbers up to 10,000 in under 1 second.

Suppose a robot starts in the upper lefthand corner of the maze shown below and wants to move to the lower righthand corner...

You will learn how to write a program to help the robot find its way through this and any other kind of maze.

The Eight Queens Problem is a famous chess problem asking you to place eight queens on a chess board in such a way that none of them can attack any of the others.

Chess Board (source: chesshouse.com)

You will learn how to write a program that solves the problem in under 10 milliseconds. And it will enumerate all possible solutions in under 100 milliseconds.

A farmer wants to get a fox, a chicken, and a bag of grain across a river, but at most one of these will fit in his boat besides himself. He mustn't leave the fox and the chicken on their own, nor the chicken and the grain, for fear of one of them getting eaten by the other. Is it possible to move everything safely to the other side?

You will learn how to write programs to solve puzzles of this kind in a systematic fashion.

Why Prolog? In Prolog you can write very short and elegant programs to solve nontrivial problems. For example, the nine problems described above on average require fewer than 30 lines of code. (Well, to be completely precise, for the route-finding application we also need access to a database of cities and roads in the Netherlands; and for the Letters Game we also need access to a lexicon.) The course will focus on the general patterns underlying the solutions to such problems. For example, finding a perfect answer in the Numbers Game, helping the robot through the maze, and solving the Eight Queens Problem can all be done by using the same kind of fundamental search algorithm.

Topics. The course covers the following topics: