AI Search Strategies

This cheat sheet outlines fundamental concepts in Artificial Intelligence search, including problem formulation, search algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS), and adversarial search techniques like Minimax.

Core Principles

• Search problems are defined by an initial state, actions, transition model, goal test, and path cost.
• Uninformed search strategies explore states without problem-specific knowledge.
• Informed search strategies use problem-specific knowledge (heuristics) to guide the search.
• Adversarial search is used in games where multiple agents compete.
• Minimax is a fundamental algorithm for adversarial search, assuming optimal play from both players.

Key Terms

• Agent: An entity that perceives its environment and acts upon it.
• State: A configuration of the agent and its environment.
• Initial State: The state in which the agent begins.
• Actions: Choices that can be made in a given state.
• Transition Model: Describes the state resulting from performing an action in a given state.
• Goal Test: Determines if a given state is a goal state.
• Path Cost: The numerical cost associated with a given path.
• Solution: A sequence of actions leading from the initial state to a goal state.
• Optimal Solution: A solution with the lowest path cost among all possible solutions.
• Node: A data structure tracking state, parent, action, and path cost.
• Frontier: The set of nodes that have been generated but not yet expanded.
• Explored Set: The set of nodes that have already been expanded.
• Uninformed Search: Search strategy using no problem-specific knowledge.
• Informed Search: Search strategy using problem-specific knowledge for efficiency.
• Heuristic Function (h(n)): Estimates the cost from a node to the goal.
• Admissible Heuristic: A heuristic that never overestimates the true cost to the goal.
• Consistent Heuristic: A heuristic where h(n) <= h(n') + cost(n, a, n') for any node n, successor n', and action a.
• Minimax: An algorithm for choosing the next move in a two-player game, assuming optimal play from both sides.
• Evaluation Function: Estimates the expected utility of a game state.

Real World Examples

• Navigating a maze: Illustrates basic search concepts like states, actions, and finding a path.
• Solving the 8-puzzle or 15-puzzle: Demonstrates state-space search, heuristics, and algorithms like A*.
• Playing games like Tic-Tac-Toe or Chess: Applies adversarial search techniques like Minimax and Alpha-Beta pruning.