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

This lecture, presented by Brian Yu, introduces foundational concepts of artificial intelligence (AI) focusing primarily on search algorithms as a way for AI agents to find solutions to problems. The lecture covers classicalA* Search problems, uninformed and informedA* Search strategies, and adversarialA* Search in games, concluding with a brief preview of future topics in AI.

Main Ideas and Concepts

1. **Introduction to AI andA* Search**

AI enables computers to perform tasks that appear intelligent or rational, such as face recognition, game playing, or natural language understanding.
The lecture focuses onA* Search as a fundamental AI technique: an AI agent searching for a solution in an environment.
Examples ofA* Search problems:
- Sliding tile puzzles (e.g., the 15 puzzle).
- Maze navigation or driving directions.
- Game moves selection (e.g., tic-tac-toe).

2. **Key Terminology inA* Search Problems**

Agent: An entity perceiving and acting within an environment.
State: A configuration of the agent within the environment.
Initial State: The starting point of theA* Search.
Actions: Possible moves or choices available in a given state.
Transition Model (Result Function): Defines the state resulting from taking an action in a state.
State Space: The set of all states reachable from the initial state via sequences of actions.
Goal Test: A function to determine if a state is a goal state.
Path Cost: A numerical cost associated with a path (e.g., time, distance), used to find optimal solutions.
Solution: A sequence of actions leading from the initial state to a goal state.
Optimal Solution: A solution with the lowest path cost.

3. **Data Structures forA* Search**

Node: A data structure storing:
- Current state.
- Parent node (previous state).
- Action taken to reach current state.
- Path cost to current node.
Frontier: A collection of nodes available for exploration.
Explored Set: A set of nodes already visited to avoid revisiting and infinite loops.

4. **BasicA* Search Algorithm Framework**

Initialize frontier with the initial state node.
Loop:
- If frontier is empty → no solution.
- Remove a node from frontier.
- If node is goal → return solution by backtracking parents.
- Else, add node to explored set.
- Expand node by adding neighbors (new nodes from valid actions) to frontier if not in frontier or explored.

5. **UninformedA* Search Algorithms**

Depth-FirstA* Search (DFS):
- Frontier is a stack (Last-In, First-Out).
- Explores as deep as possible along one path before backtracking.
- May find a solution but not guaranteed to be optimal.
- Can get stuck in infinite loops without explored set.
Breadth-FirstA* Search (BFS):
- Frontier is a queue (First-In, First-Out).
- Explores all nodes at the current depth before moving deeper.
- Guarantees finding the shortest path (optimal in terms of number of steps).
- May explore many unnecessary nodes, leading to higher memory use.

6. **InformedA* Search Algorithms**

Use problem-specific knowledge (heuristics) to guideA* Search.
Greedy Best-FirstA* Search (GBFS):
- Expands the node estimated to be closest to the goal based on a heuristic function \( h(n) \).
- Heuristic example: Manhattan distance in maze solving.
- Fast but not guaranteed to find the optimal solution.
A* Search:
- Considers both path cost \( g(n) \) and heuristic estimate \( h(n) \).
- Expands nodes with the lowest \( f(n) = g(n) + h(n) \).
- Guarantees optimality if heuristic is admissible (never overestimates true cost) and consistent (heuristic value respects triangle inequality).
- Often more efficient than BFS and GBFS but uses more memory.

7. **AdversarialA* Search in Games**

Search problems where multiple agents have opposing goals (e.g., tic-tac-toe).
Minimax Algorithm:
- Models two players: Max (tries to maximize score) and Min (tries to minimize score).
- Assigns utilities to terminal states (win = +1, lose = -1, draw = 0).
- Recursively evaluates game tree by alternating max and min moves.
- Max chooses actions that maximize value; Min chooses actions that minimize value.
Alpha-Beta Pruning:
- Optimization to Minimax that prunes branches that cannot affect the final decision.
- Keeps track of two values