1.2 Search and Games

This is the second submodule in the first module. It is a large module that you should go through carefully and step by step. It covers several lectures including uninformed search, informed search and adversarial search.

We will cover some of the following topics:

Problem-solving as state space search. Formulation of state-space search problems. Representing states and actions. Basic search algorithms and their properties. Breadth-first search, depth-first search, backtracking search, depth-limited and iterative deepening search. Heuristic search. Finding optimal solutions. Best first search. A* Search: Adding Heuristics to Branch and Bound Search.

As before, I suggest that you follow the sequence listed below in your reading material, starting first with the textbook and then moving to the online and digital lecture materials. For those of you who have already covered the material, then I suggest that you do some additional implementation for fun. See additional material below.

Course Book Reference for this submodule

Part II Problem-solving
Chapter 3 Solving Problems by Searching page 63
Chapter 4 Search in Complex Environments page 110
Chapter 5 Adversarial Search and Games page 146

On the importance of Representation in A.I.

A wide range of problems in AI—including, among others, theorem proving, game playing, planning, and
learning—can be formulated at an abstract level as essentially search problems.

Have a look at the following lecture to see how to create a representation for a vaccuum agent. Note that the solution is not AI but the key is the representation.

An example about representation (A. Loutfi) (Watch from 23:42 for the most relevant parts)

Lectures on Search from various sources

Lecture - Uninformed Search
Lecture - Informed Search
Lecture - Adversarial Search
Lecture - Expectimax
[recommended!] Sean Holden's Lecture Series

Additional Material

The search spaces encountered in AI problems usually grow exponentially with the length of the solution
(i.e., path to a goal) and seldom will we attempt to enumerate the entire search space. Control of search to
minimize the fraction of the search space that needs to be explored in arriving at a solution is a key topic of
research in AI.

Here are some additional examples that you can try to solve.

• Chickens and Foxes: There are 3 chickens, 3 foxes, and 1 boat that can carry up to
two animals on one side of a river. The goal is to move all the chickens and foxes across the river.
Constraint on any state is that chickens can never be outnumbered by foxes on either side of
the river, or else the chickens are killed. The states correspond to configuration of chickens and
foxes and boat on each side of the river. The operators specify movement of the boat containing
some set of occupants across the river (in either direction) to the other side.

• Cryptarithmetic Find an assignment of digits (0, ..., 9) to letters so that a given arithmetic expression
is true. For example, SEND + MORE = MONEY Note: In this problem, the
solution is NOT a sequence of actions that transforms the initial state into the goal state, but rather
the solution is simply finding a goal node that includes an assignment of digits to each of the distinct
letters in the given problem. Such search problems are often called pathless search problems.

• Water Jug Problem Given a 5-gallon jug and a 2-gallon jug, with the 5-gallon jug initially full of water
and the 2-gallon jug empty, the goal is to fill the 2-gallon jug with exactly one gallon of water. We
can specify the states by ordered pairs of the form (x, y), where x = number of gallons of water in
the 5-gallon jug and y is gallons in the 2-gallon jug. The initial state is (5, 0). the goal State = (⋆, 1),
where ⋆ denotes an arbitrary number. Operators can be specified as follows:
– (x, y) → (0, y); empty the 5-gallon jug
– (x, y) → (x, 0) ; empty the 2-gallon jug
– (x, 2) → (x+2, 0) provided x ≤ 3; pour 2-gallon into 5-gallon jug making sure that the jug won’t
overflow
– (x, 0) → (x − 2, 2) provided x ≥ 2 ; pour 5-gallon into 2-gallon jug
– (1, 0) → (0, 1); empty 5-gallon jug into the 2-gallon jug