Search

These notes are adapted from the lecture notes of CS50’s Introduction to Artificial Intelligence with Python by Brian Yu and David J. Malan (Harvard University), licensed under CC BY-NC-SA 4.0, and are shared under the same licence. Sections 7 to 11 add material from the chapter on adversarial search and games in Russell and Norvig’s Artificial Intelligence: A Modern Approach (4th ed.).

1. Search problems
2. Nodes, the frontier and the explored set
3. Depth-first search
4. Breadth-first search
5. DFS and BFS side by side
6. In the code: maze.py
7. Adversarial search
8. Minimax
9. Alpha-beta pruning
10. Too big to search to the end
11. Search in the real world
12. Check yourself, key terms and reading

1Search problems

A sat-nav finding a route, a person solving a maze and a program solving a sliding-tile puzzle are all doing the same job. Each starts in one situation, wants to reach a goal, and has to find the steps that get it there. That is a search problem.

To make a computer solve these problems, we describe each one with the same few words. Learn these: they come back every week until Week 6.

Example: actions depend on the state

How many actions are there? It depends where the gap is. With the gap in the middle there are 4 moves, on an edge there are 3, and in a corner only 2. That is why ACTIONS takes the state as its input: different states allow different actions.

Example: a road map, and what “best” means

A solution is any sequence of actions from the initial state to a goal. An optimal solution is a solution with the lowest path cost. Here there are three solutions:

Notice that we chose minutes as the path cost. If the path cost were miles or fuel, a different route might be “best”. The seminar comes back to this: choosing the path cost is a design decision, and it affects people.

2Nodes, the frontier and the explored set

As a search runs, it keeps a small record for every state it reaches. That record is called a node.

The parent link is what lets us read off the solution at the end. When the search reaches the goal, it follows the parents back (Salisbury → Stockbridge → Winchester) and then reverses the list of actions: “drive to Stockbridge, then drive to Salisbury”.

The frontier

The frontier is a to-do list: the nodes we have found but not looked at yet. The loop below is the search algorithm. Every search in Weeks 2 and 3 is this loop with one line changed.

Expanding a node means using ACTIONS and RESULT to find its neighbours, then adding them to the frontier as new nodes.

The search tree

Each new node points back to its parent, so as the loop runs, the nodes it creates join up into a tree.

The search tree is not the same thing as the state space. The state space (Figure 2) has one box for each state. The search tree has one node for each path the search has found, so the same state can appear in it more than once. Figure 4 shows the top of the search tree for the road map, with every road usable in both directions.

Three things to notice:

• The same state can appear in several nodes. Salisbury appears three times, once for each route, with path costs of 55, 50 and 60 minutes. The state is the same; the paths are different. That is why a node stores its parent and its path cost, not just its state.
• The search tree can be much bigger than the state space. Every road goes both ways, so Winchester appears again below each town, and below each of those the whole tree starts again. The map has only five towns, but its search tree never ends.
• A search does not draw the whole tree first. It grows the tree one node at a time, and stops as soon as it takes a goal out of the frontier. The frontier is the bottom edge of the part built so far: the nodes found but not yet expanded.

Why the explored set?

Leave out the three highlighted lines and the search can follow the endless branches in Figure 4: from Winchester to Stockbridge, back to Winchester, and so on for ever. The explored set remembers the states we have already looked at, so we never add them to the frontier again. Then each state gets at most one node, and in a state space of finite size the loop always stops.

Going further: Russell & Norvig call a search that checks for repeated states in this way a graph search, and one that does not a tree-like search.

Which node comes out next?

The loop says “remove a node from the frontier”, but which one? There are two simple choices.

3Depth-first search

Depth-first search (DFS) uses a stack, so it always takes the newest node in the frontier. In practice, it goes as deep as it can down one route, and only turns back when it reaches a dead end.

An everyday picture: you are looking for your keys. With depth-first search, you empty every pocket of your jeans before you look anywhere else in the house.

Worked example: DFS on the Week 1 maze

The pictures below use the same rules as the maze program in the practical (Section 6): neighbours are added in the order up, down, left, right. Lilac squares have been taken out of the frontier, with the step number when that happened. Dashed squares are waiting in the frontier. The ringed square is the one just taken out.

In Week 1 you probably found the 17-step path along the top. DFS did not: it stops at the first path it finds, and that path went through the middle.

• If it happens to pick the right way first, DFS can be very fast.
• The path it finds may not be the shortest one.
• At worst, it explores almost every state before it finds the goal.

4Breadth-first search

Breadth-first search (BFS) uses a queue, so it always takes the oldest node in the frontier. It takes one step in every direction, then two steps, then three, like a ripple spreading out from the start.

The keys again: with breadth-first search you check one pocket, then one drawer, then the table, and only after one quick look everywhere do you go back for the second pocket.

Worked example: BFS on the same maze

• BFS always finds the shortest path, when every step costs the same.
• It often explores many states, because it looks everywhere nearby first.
• The frontier can grow very large, so it needs a lot of memory.

Back to Week 1: if your maze pseudocode always took the newest square, you wrote depth-first search. If it took the oldest, you wrote breadth-first search. If it took the square closest to B, you wrote greedy best-first search, which we meet in Week 3.

5DFS and BFS side by side

Here is the search loop from Section 2 (remove a node from the frontier, check it, add it to explored, expand it) run on a small tree instead of a maze, once with a stack and once with a queue. The search starts at A and the goal is D. When a node is expanded, its children join the right-hand end of the frontier, left child first. A stack takes from the right-hand end; a queue takes from the left-hand end.

The two searches split at step 2: DFS takes C (added last) and BFS takes B (added first). Both return the path A → B → D, but BFS took out 4 nodes and DFS took out 6, because DFS went down the C branch first. If D had been under C instead, DFS would have been the lucky one.

The table below sums up the two searches. Its last two rows use two more mazes, maze2.txt and maze3.txt, which come with the maze program in the practical (Section 6).

6In the code: maze.py

The practical uses week02-search/maze/maze.py. Each part of the loop above is in the code.

class Node():
    def __init__(self, state, parent, action):
        self.state = state       # where we are, e.g. (row, column)
        self.parent = parent     # the node we came from
        self.action = action     # "up", "down", "left" or "right"

There is no path cost in this Node, because every step in a maze costs the same (1). The two frontiers differ in one method only:

# StackFrontier (DFS): take the last
def remove(self):
    node = self.frontier[-1]
    self.frontier = self.frontier[:-1]
    return node

# QueueFrontier (BFS): take the first
def remove(self):
    node = self.frontier[0]
    self.frontier = self.frontier[1:]
    return node

In Python, [-1] is the last item of a list and [0] is the first. The solve method is the loop from Section 2: it removes a node, checks for the goal, adds the node to self.explored, and adds each neighbour that is not already in the frontier or explored.

7Adversarial search

In a maze, nobody fights back. In a game, an opponent chooses every other move, and wants the opposite result to you. Searching in this setting is called adversarial search. The classic example is tic-tac-toe (noughts and crosses).

What kind of game?

This week we look at the simplest kind of game. Tic-tac-toe and chess are both of this kind:

• two players, who take turns;
• fully observable: both players can see the whole board. Game theorists call this perfect information;
• deterministic: there are no dice or shuffled cards, so a move always has the same result;
• zero-sum: what is good for one player is equally bad for the other.

You met “fully observable” and “deterministic” in Week 1, as two of the questions we ask about an environment. In a game, a position on the board is a state and a move is an action, so the words from Section 1 still work.

Games can be sorted with two questions. Does chance play a part? And can each player see everything?

The other three boxes need more than search. With dice, a program has to weigh up what is likely to happen; with hidden cards, it has to guess what the opponent holds. Both need probability, which is the subject of Week 5, but we do not come back to games there.

Describing a game

Compare this with a maze: we still have an initial state, actions and a transition model. The goal test becomes TERMINAL, and the path cost becomes UTILITY, because what matters is how the game ends, not how long it takes. X is called MAX, because X wants the score as high as possible. O is MIN, because O wants it as low as possible.

Russell and Norvig use slightly different names for three of these. They write TO-MOVE(s) instead of PLAYER(s), and IS-TERMINAL(s) instead of TERMINAL(s). Their utility function, UTILITY(s, p), has a second input: the player p whose score we want. In a zero-sum game one score is enough, because the other player’s score is the same number with the sign changed.

In Figure 5, X has three empty squares to choose from. Top-middle looks tempting, because it gives X two in the top row. But O has the centre and the bottom-right, so O is threatening the diagonal through top-left. A program finds the right move by looking ahead at the opponent’s replies, which is what minimax does (next section).

The game tree

Start from the initial state and draw every possible move, then every possible reply to each, and so on. The result is a game tree: the search tree (Section 2) of the game, followed all the way to the end of every game. The levels take turns. X (MAX) moves at the top, O (MIN) at the next level down, then X again, until the game ends. Each finished game at the bottom has its utility: +1, 0 or −1. Figure 6 shows the top of the tree for tic-tac-toe.

To read it, follow the left-hand edge: X plays top-left, O replies top-middle, X plays top-right, and after a few more moves the game ends. The three finished games at the bottom all start that way. In the first, O has completed the middle column (−1). The second is a full board with no line, a draw (0). In the third, X has completed the diagonal from top-right to bottom-left (+1).

Even this small game has a big tree. On the empty board X has 9 squares to choose from, then O has 8, then X has 7, and so on. That gives at most 9 × 8 × 7 × … × 1 = 362,880 paths from the top to the bottom. There are fewer real games (255,168), because many games end before the board is full. Section 8 looks at a small part of this tree, starting from the position in Figure 5.

A game small enough to draw in full

Tic-tac-toe’s tree does not fit on a page, so here is one that does. In this tiny game of Nim there is one pile of 3 counters. On your turn you take 1 or 2 counters. Whoever takes the last counter loses. Figure 7 is the whole tree.

Nim can be described with the same six words as tic-tac-toe (the table beside Figure 5). The initial state is the pile of 3 counters, and any later state is the number of counters left. The players take turns. The actions are “take 1” and “take 2”, and the result of an action is a smaller pile. The game is over (TERMINAL) when no counters are left, and the utility is +1 if your opponent took the last one and −1 if you did. Because the whole tree is on the page, you can see every way the game can go: there are only three. In Section 8 you will be able to work out the best first move from this tree, and there is a question on it at the end. A bigger version of Nim comes back in Week 7, as the game a program learns to play by playing against itself.

A game is not a maze

In a maze, the answer is a fixed list of moves: up, up, left, and so on. In a game you cannot write that list in advance, because you do not know what your opponent will do. So the answer to a game is a strategy instead.

Games also have time limits. A chess player has a clock, and a program usually cannot search all the way to the end of the game before its time runs out. So it has to make a good guess about how good a position is. Section 10 shows how.

8Minimax

Minimax assumes the opponent plays perfectly. MAX imagines each of its moves, then imagines MIN’s best reply to it, and so on to the end of the game. Then it works back up: MIN always picks the lowest score, and MAX the highest.

Example: the board in Figure 5

The same idea with numbers

Real games have many more moves, so we draw the tree with numbers instead of boards. Figure 9 has the same shape: MAX chooses a move, MIN replies, and the bottom row holds the scores of finished games. The scores can be any numbers, not just +1, 0 and −1: higher is better for MAX.

In pseudocode, two functions call each other:

Given a state s, MAX picks the action a with the highest MIN-VALUE(RESULT(s, a)), and MIN picks the action with the lowest MAX-VALUE(RESULT(s, a)). Why start at −∞ in MAX-VALUE? So that the first real score is always bigger and replaces it. MIN-VALUE starts at +∞ for the same reason. A function that calls itself, here through the other function, is called recursive: you need to be able to read it, not write it. Russell and Norvig add a third function for that first step, which returns MAX’s best action, not just its value.

Tracing it once: for the left MIN node in Figure 9, MIN-VALUE starts with v = +∞, then v = min(+∞, 4) = 4, then min(4, 8) = 4, then min(4, 5) = 4, and returns 4.

How good is minimax?

Russell and Norvig judge every search algorithm with the same four questions. You have met two of them already: the table in Section 5 asked whether DFS and BFS find a path if there is one (is the search complete?) and whether that path is the shortest (is it optimal?). The other two ask how much time and how much memory the search needs. Two numbers come up in those answers. Suppose every position has about the same number of legal moves, and call that number b, the branching factor. Suppose a game lasts about m ply. Here are the answers for minimax.

What if the opponent is not perfect? Minimax still gets at least its minimax value, because it has planned for the worst. But it may miss a chance to do better. Suppose that in Figure 9, MIN is careless and always plays its left-hand reply. Then the left move would give MAX 4, the middle 9 and the right 2, so the middle move would be best. Minimax still plays left, because it assumes MIN will spot the 3. Playing safe is the right choice when you know nothing about your opponent.

How much work is it? MAX has b moves, MIN has b replies to each, MAX has b replies to each of those, and so on, m times: b × b × … × b = b^m games in all. Computer scientists write the time as O(b^m), read “order b to the power m”: it grows like b^m.

Memory is much smaller: about b × m positions, written O(bm). That is because minimax searches depth-first, like DFS in Section 3. MAX-VALUE calls MIN-VALUE, which calls MAX-VALUE, all the way down one line of play before it tries the next. So it only has to remember the positions on that one line, plus the other moves waiting at each step.

9Alpha-beta pruning

Minimax looks at every possible game. Alpha-beta pruning gets the same answer while skipping parts of the tree that cannot change it.

Pruning never changes the answer; it only saves work. In real games the saving is much bigger than here, because whole branches with thousands of games below them are skipped, not single leaves.

Alpha and beta

To know when it can skip a branch, the algorithm carries two numbers down the tree. They give it its name.

The rule: if a branch can give MAX no more than alpha, MAX will avoid it, so stop looking at it. In the same way, if a branch can give MIN no less than beta, MIN will avoid it.

Reading Figure 10 with alpha: after the left move, alpha = 4, because MAX is sure of 4. Under the middle move, MIN finds a 3, so that move is worth at most 3. That is less than alpha, so MAX will never choose it, and the 7 is skipped. Under the right move, the first leaf is 2, also less than alpha, so the 4 and the 6 are skipped.

A second example: the textbook’s tree

Russell and Norvig use the tree in Figure 11. It has the same shape as Figure 9, with different scores. Work out the minimax answer yourself first, then read the trace below.

The alpha-beta algorithm

Alpha-beta is minimax with two extra inputs, alpha and beta, and two extra lines in each function (highlighted).

How to read the two new lines in MAX-VALUE:

• if v ≥ β: return v. MAX has found a move worth at least v here. But MIN, higher up the tree, already has a way to hold MAX to β. If v is at least β, MIN will never let the game reach this state, so there is no point looking at MAX’s other moves here.
• α = MAX(α, v). If this is the best MAX has found so far, raise alpha, so that the levels below know what MAX is already sure of.

MIN-VALUE is the mirror image. It stops when v is at most α, because MAX already has something at least as good elsewhere, and it lowers beta. The search starts with MAX-VALUE(initial state, −∞, +∞). As with minimax, a third function makes this first call and returns the best action.

How much does alpha-beta save?

• The answer never changes. Alpha-beta only skips branches that cannot affect the choice.
• Order matters. It prunes most when the best moves are looked at first, as Figure 11 showed. Chess programs try the most promising moves first, such as captures.
• With perfect ordering it looks at about b^m/2 games instead of b^m. In practice this means it can search about twice as deep in the same time: if minimax has time to look 4 ply ahead, alpha-beta can look about 8 ply ahead.
• It is still not enough for chess. With b ≈ 35 and m ≈ 100, perfect ordering cuts 35¹⁰⁰ games to 35⁵⁰, which is about 10⁷⁷. That is still far too many.

Alpha-beta is a simple example of metareasoning: reasoning about which calculations are worth doing. Before doing a calculation, the program asks whether its result could change the decision. If it could not, the calculation is skipped.

10Too big to search to the end

There are 255,168 possible games of tic-tac-toe, so a computer can play them all out in a moment. Chess is different. Section 8 showed that minimax would need about 10¹⁵⁴ games of a sensible length, and Section 9 that even alpha-beta with perfect ordering would need about 10⁷⁷. If you count every legal game of chess, including very long ones, there are roughly 10²⁹⁰⁰⁰: a 1 followed by 29,000 zeros. No computer will ever play out every game of chess, so a chess program has to stop early and guess.

Depth-limited minimax gives up the guarantee of the perfect move: the evaluation function is only a guess, so the move it picks is only as good as that guess. In return, it can answer within the time limit, and with alpha-beta it can look deeper in the same time.

11Search in the real world

• Sat-navs and map apps: road junctions are states and roads are actions.
• Game engines: chess and Go programs use adversarial search, with an evaluation function. IBM’s Deep Blue beat the world chess champion, Garry Kasparov, in 1997 with alpha-beta search, a carefully built evaluation function and very fast hardware. Go has about 250 legal moves in a position, too many for alpha-beta, so AlphaGo (2016) used a different search that plays out many sample games, guided by neural networks (Week 8).
• Warehouse robots: plan paths that avoid shelves and other robots.
• Video games: characters find their way round the map.
• Puzzle solvers: Rubik’s cube and sliding-tile puzzles.

In the seminar you describe a sat-nav, a chess engine and a warehouse robot as search problems, and discuss who decides what the “best” route is. Remember Figure 2: the answer depends on the path cost, and someone has to choose it.

Where these ideas came from

Most of this week’s ideas about games are older than the name “artificial intelligence” (1956, Week 1).

Check yourself

Try these without looking back. The answers are at the end.

1. In a 4 × 4 sliding puzzle, how many actions are there when the gap is in a corner? Why does ACTIONS take the state as its input?
2. Describe a sat-nav as a search problem: give its initial state, actions, transition model, goal test and path cost.
3. What could go wrong if the search loop had no explored set?
4. What is the difference between the state space and the search tree? In Figure 4, why does Salisbury appear three times?
5. The frontier holds P, Q and R, added in that order. Which node does DFS take out next? Which does BFS take out?
6. On the tree in Section 5, make F the goal instead of D. In what order does each search take nodes out of the frontier?
7. Why does BFS not find the 50-minute route on the road map in Figure 2?
8. Put each game in Table 1: Connect Four, Ludo, Battleships and poker. Which of them could plain minimax play?
9. Use minimax (Section 8) on the Nim tree in Figure 7. What is the minimax value of each state, and should you take 1 or 2 counters first?
10. In Figure 9, change the 3 in the middle branch to a 6. Which move does MAX choose now, and what is it worth?
11. With that change, can alpha-beta pruning still skip the 7? Can it still skip anything?
12. In Figure 11, suppose the leaves under the right move came in the order 2, 5, 14. How many of the nine leaves does alpha-beta look at now?
13. A game has 10 legal moves in every position and always lasts 20 ply. About how many games does minimax look at? About how many does alpha-beta look at with perfect move ordering?
14. Why can a chess program not use plain minimax, and what does it do instead?

Key terms

Reading and next week

• Russell & Norvig, Artificial Intelligence: A Modern Approach (4th ed.): sections 3.1 to 3.4 (search problems, uninformed search) and 5.1 to 5.3 (games, minimax, alpha-beta). In the Global Edition, games are in Chapter 6.
• Poole & Mackworth, Artificial Intelligence: Foundations of Computational Agents (3rd ed., free at artint.info): sections 3.1 to 3.5 and 14.3.

Next week: smarter search. A heuristic estimates how far a state is from the goal, and greedy best-first search and A* search use it to look in the right direction first. Then logic: writing knowledge down precisely, and letting a computer work out what follows from it.