Search - Lecture 0 - CS50's Introduction to Artificial Intelligence with Python 2020

Course Overview

Brian Yu introduces artificial intelligence as the methods that let computers perform tasks that seem intelligent or rational—for example, recognizing faces, playing games, understanding speech, and filtering spam. The course covers search, knowledge and inference, probability and uncertainty, optimization, machine learning, neural networks, and natural-language processing.

The lecture begins with search: finding a sequence of actions that takes an agent from its current situation to a desired outcome.

How to Formulate a Search Problem

The lecture defines the main components used to describe a search problem:

• Agent: An entity that perceives its environment and acts on it.
• State: A particular configuration of the agent and its environment.
• Initial state: The state where the search begins.
• Actions: The choices available in a given state. Formally, actions(s) returns the actions possible in state s.
• Transition model: Describes the state resulting from an action. Formally, result(s, a) gives the state reached by taking action a in state s.
• State space: All states reachable from the initial state by some sequence of actions, often represented as a graph of nodes and edges.
• Goal test: Determines whether a state satisfies the objective.
• Path cost: A numerical measure of the cost of a sequence of actions, such as distance, time, or money.

A solution is a sequence of actions that reaches a goal. An optimal solution is one with the lowest path cost among the possible solutions.

Nodes and the General Search Procedure

Search algorithms commonly represent a state using a node, which records:

• The current state.
• Its parent node—the node from which it was reached.
• The action used to reach it.
• The path cost so far.

The frontier stores nodes that are available to explore but have not yet been selected. A general search process is:

1. Put the initial state on the frontier.
2. If the frontier is empty, report that there is no solution.
3. Remove a node from the frontier.
4. If it passes the goal test, reconstruct and return the solution by following its parent links.
5. Otherwise, expand it—find its successor states—and add eligible successors to the frontier.
6. Repeat.

To avoid repeatedly traveling between states or entering loops, track explored states. When adding successors, avoid states already in either the frontier or the explored set.

The frontier data structure and removal order determine which search strategy is used.

Uninformed Search

Depth-First Search (DFS)

• Uses a stack: last in, first out.
• Expands the deepest available node, following one route as far as possible.
• If it reaches a dead end, it backtracks and tries another route.
• In a finite state space, it will eventually explore all reachable states and can find a solution if one exists.
• It is not guaranteed to find the optimal solution. It may find a long route even when a shorter one is available.
• It may use less memory than breadth-first search in some situations.

Breadth-First Search (BFS)

• Uses a queue: first in, first out.
• Explores nodes in order of their distance in steps from the initial state—first one step away, then two, and so on.
• When every action has equal cost, BFS finds an optimal solution in terms of the fewest steps.
• It can use substantial memory because it stores many frontier states, and it may explore many states before reaching a distant goal.

The lecture illustrates these methods with mazes: DFS commits to a route and backtracks when necessary, while BFS spreads its exploration across routes and reaches the nearest goal first.

Informed Search and Heuristics

Uninformed methods such as DFS and BFS do not use problem-specific knowledge to guide exploration. Informed methods use additional information to prioritize promising states.

A heuristic function, written h(n), estimates how far a state is from the goal. For a grid maze, the lecture uses Manhattan distance: the number of horizontal and vertical steps between two cells, ignoring walls and disallowing diagonal movement.

Greedy Best-First Search

• Expands the frontier node with the lowest heuristic value, h(n).
• It can be more efficient than BFS when the heuristic points toward the goal.
• It is not guaranteed to find the optimal path. A locally promising direction can lead to a worse overall route.

A* Search

A* ranks nodes using both the cost already incurred and the estimated cost remaining:

• g(n): The cost of reaching node n.
• h(n): The estimated cost from n to the goal.
• A* expands the node with the lowest g(n) + h(n).

This avoids relying only on apparent closeness to the goal: a node that looks promising may still be less attractive if it took a long time to reach. A* is optimal under appropriate conditions on the heuristic:

• Admissible: The heuristic never overestimates the true remaining cost.
• Consistent: For any node and successor, the heuristic estimate at the node is no greater than the step cost plus the successor’s estimate.

Choosing a useful heuristic is often a major challenge, and A* can require considerable memory.

Adversarial Search and Minimax

Some search problems involve an opponent with an opposing goal, as in tic-tac-toe. In adversarial search, an agent must choose a move while anticipating the opponent’s responses.

The lecture presents Minimax for deterministic, two-player games:

• Assign numerical utilities to terminal outcomes. In the tic-tac-toe example, an X win is 1, a draw is 0, and an O win is -1.
• Treat X as the maximizing player, seeking the highest score, and O as the minimizing player, seeking the lowest.
• Represent the possible moves as a game tree. Each level corresponds to a player’s turn.
• Work backward from terminal states:
  • At a maximizing state, choose the action with the highest resulting value.
  • At a minimizing state, choose the action with the lowest resulting value.
• Use recursion to evaluate future moves, alternating between the max and min perspectives until reaching terminal states.

This lets a player choose a move based on the assumption that both sides will play optimally.

Alpha-Beta Pruning

Minimax can examine many states that cannot affect its final decision. Alpha-beta pruning improves efficiency by keeping track of bounds on what the players can achieve:

• Alpha represents the best value the maximizing player can guarantee so far.
• Beta represents the best (lowest) value the minimizing player can guarantee so far.
• If further exploration cannot change the decision, prune that branch and skip its remaining states.

Pruning can reduce the amount of search without changing the result of Minimax.

Depth-Limited Minimax

For large games, searching all the way to the end is often computationally infeasible. Depth-limited Minimax stops after a chosen number of moves. Since those cutoff states may not be terminal, it uses an evaluation function to estimate their expected utility. The quality of that function strongly affects the quality of the resulting decisions.

Main Takeaways

• Search problems can be described using states, actions, transitions, goals, and costs.
• The structure of the frontier controls the search strategy.
• DFS explores deeply; BFS explores by increasing depth and, with equal action costs, finds a shortest path.
• Heuristics guide informed search. Greedy best-first search uses estimated distance alone, while A* combines that estimate with the cost already incurred.
• In games, Minimax models opposing goals, alpha-beta pruning avoids unnecessary work, and depth limits make search more practical for large game trees.

Speakers and Sources Featured

• Brian Yu: Lecturer and the only speaker in the subtitles.
• XKCD: Referenced as the source of a webcomic about optimal tic-tac-toe moves.
• Google Maps: Mentioned as an example of using search to find routes; not a speaker.
• Email spam filtering: Mentioned as an example of machine learning; not a speaker or attributed source.