Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 46 · Practice and Review

Classical AI Cheat Sheet

A one-page classical AI cheat sheet: search, heuristics, CSP, games, logic, planning, probability, MDP and robotics formulas, complexity tables and how to pick a method.

This page puts the whole course on one page: which algorithm to use, what it guarantees, what it costs, and the handful of formulas you will use again and again. Bookmark it and come back when you need to check a bound, compare two methods or pick an approach for a new problem. Every section links to the lesson that explains the idea.

It does not replace the lessons, because a table cannot tell you why something works. Use it after you have worked through the course, together with the exercises and the interview questions.

Picking the right method

Start from the shape of the problem, not from the algorithm.

graph TD
    Q["What kind of problem?"] --> A{"Opponent?"}
    A -- "yes" --> G["Games: minimax + alpha-beta<br/>or MCTS for huge trees"]
    A -- "no" --> B{"Is the world known<br/>and deterministic?"}
    B -- "no" --> P["Probabilistic: Bayes nets, HMMs,<br/>MDPs, particle filters"]
    B -- "yes" --> C{"Is it a path to a goal<br/>or just a good final state?"}
    C -- "good final state" --> L["Constraints? CSP solver.<br/>Otherwise local search / annealing"]
    C -- "path / action sequence" --> D{"Structured actions<br/>with preconditions?"}
    D -- "yes" --> PL["Planning: STRIPS/PDDL<br/>with a relaxed heuristic"]
    D -- "no" --> S["Search: A* with an admissible<br/>heuristic; IDA* if memory is tight"]

A first-pass decision tree. Real problems often mix several branches, for example A inside a robot that also runs a filter.*

If you have... Reach for... Lesson
A graph, unit costs, no heuristic BFS (shallowest goal) or iterative deepening (low memory) BFS and DFS
A graph with varying costs, no heuristic Uniform-cost search (Dijkstra) Uniform-cost
A graph, costs and a good admissible heuristic A* A*
A huge space and memory limits IDA*, beam search, weighted A* Memory-bounded search
Only the final configuration matters Hill climbing with restarts, annealing, genetic algorithm Local search
Variables with domains and constraints Backtracking with MRV, forward checking and AC-3 CSPs
Two players, perfect information Minimax with alpha-beta; MCTS when no evaluation function exists Games
Facts and rules, need to derive consequences Forward or backward chaining, resolution, SAT Logic
Actions with preconditions and effects STRIPS/PDDL planner with delete-relaxation heuristics Planning
Uncertain world, noisy sensors Bayes rule, filters, MDPs Probability
A robot arm or mobile robot Kinematics, PID, A* on a grid, RRT in high dimensions Robotics

Search algorithms compared

b = branching factor, d = depth of the shallowest goal, m = maximum depth of the space, C* = optimal cost, ε = smallest step cost, ℓ = depth limit.

Algorithm Complete Optimal Time Space Notes
Breadth-first Yes Yes (equal step costs) O(b^d) O(b^d) Memory runs out first
Depth-first No No O(b^m) O(bm) Tiny memory; may loop in graphs without an explored set
Depth-limited Only if d <= ℓ No O(b^ℓ) O(bℓ) DFS with a cutoff
Iterative deepening Yes Yes (equal step costs) O(b^d) O(bd) Preferred uninformed method for big spaces
Uniform-cost Yes Yes O(b^(1+⌊C*/ε⌋)) same Dijkstra's algorithm
Bidirectional Yes Yes (equal costs) O(b^(d/2)) O(b^(d/2)) Needs reversible actions and an explicit goal
Greedy best-first No No O(b^m) O(b^m) Orders by h(n) only; fast but can be badly misled
A* Yes Yes if h admissible (tree) / consistent (graph) exponential, depends on h O(b^d) Orders by g(n) + h(n); memory is the limit
Weighted A* Yes Cost at most w times optimal usually much faster smaller f = g + w·h, w > 1
IDA* Yes Yes if h admissible like A*, with re-expansion O(bd) Depth-first with an f-limit
Beam search No No O(bk·m) O(bk) Keeps only the best k nodes per level

Heuristic facts. Admissible: h(n) <= h*(n). Consistent: h(n) <= c(n, a, n') + h(n'), which implies admissible. A heuristic h2 dominates h1 if h2(n) >= h1(n) for all n (both admissible); h2 expands no more nodes. Relax the problem to get a heuristic; combine several admissible ones with max. Effective branching factor b* is the solution of N + 1 = 1 + b* + (b*)² + ... + (b*)^d.

Common grid heuristics. 4-way moves: Manhattan |dx| + |dy|. 8-way moves with equal cost: Chebyshev max(|dx|, |dy|). 8-way with diagonals costing √2: octile max + (√2 − 1)·min. Any direction: Euclidean √(dx² + dy²).

Some numbers worth remembering

The program below prints the sizes of some well-known search spaces, how fast trees grow, and what alpha-beta saves.

Python Sizes of search spaces and trees

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The 15-puzzle has more than ten trillion reachable states, so it cannot be solved with BFS, yet A* with a good heuristic solves it. Trees with branching factor 10 are unreachable beyond depth 10, which is the reason heuristics matter. At b = 35 (chess) the best case for alpha-beta turns 2.2 trillion leaves into about 1.5 million for an 8-ply search, and that is the "twice as deep" rule in numbers.

Method Idea Weakness Fix
Hill climbing Move to the best neighbour while it improves Local maxima, plateaus, ridges Random restarts, sideways moves
Min-conflicts Pick a conflicted variable, give it the least-conflicting value Plateaus Tabu list, random walk
Simulated annealing Accept a worse move with probability exp(−Δ/T); lower T over time Needs a cooling schedule Tune the schedule, restart
Genetic algorithm Population + selection + crossover + mutation Many parameters, premature convergence Larger populations, elitism, diversity

Constraint satisfaction

Technique What it does
Backtracking Assign one variable at a time, undo on conflict
MRV Choose the variable with the fewest legal values left
Degree heuristic Tie-break: the variable involved in the most constraints on unassigned variables
LCV Try the value that rules out the fewest values for neighbours first
Forward checking After an assignment, remove inconsistent values from neighbours' domains
AC-3 Make every arc (X, Y) consistent; O(c·d³) for c arcs and domain size d
Tree-structured CSP Solve in O(n·d²) after ordering variables from the root
Cutset conditioning Fix a small set of variables so that the rest forms a tree

Games

Idea Formula or rule
Minimax MAX node = max of children, MIN node = min of children; O(b^m) time, O(bm) space
Alpha-beta Prune when alpha >= beta; same value as minimax; O(b^(m/2)) at best
Move ordering Try the likely best moves first (captures, killer moves, previous iteration's best)
Evaluation function Weighted sum w1·f1(s) + w2·f2(s) + ... at the depth cutoff
Quiescence search Keep searching volatile positions beyond the cutoff
Expectimax Chance node = probability-weighted average of children
MCTS Selection, expansion, simulation, backpropagation; UCB1 mean + c·√(ln N / n)
Transposition table Cache positions already searched (hash of the board)

Logic and knowledge

Concept Summary
Entailment KB ⊨ α: α is true in every model of KB
Sound / complete Derives only entailed sentences / derives all entailed sentences
CNF conversion Remove <-> and ->, push not inward (De Morgan), distribute or over and
Resolution From (A or x) and (B or not x) derive (A or B); empty clause means contradiction
Horn clause At most one positive literal; forward/backward chaining are complete and linear for propositional Horn
DPLL Backtracking + unit propagation + pure literals; CDCL adds clause learning
Unification Find a substitution that makes two terms identical; use the occurs check
FOL Objects, predicates, quantifiers; entailment is semi-decidable

Planning

Concept Summary
STRIPS action Preconditions, add list, delete list; unlisted facts keep their value
PDDL Standard language: domain (actions, predicates) plus problem (objects, init, goal)
Forward state-space search Start from the initial state, apply applicable actions
Delete relaxation Ignore delete lists to make an easier problem and use it for h
h_max / h_add Max / sum of the costs of the preconditions plus 1; h_max is admissible, h_add is not
Planning graph (GraphPlan) Layers of facts and actions with mutex links; a level-based lower bound
HTN Decompose high-level tasks into subtasks with methods

Probability and decisions

Core formulas:

  • Product rule: P(a, b) = P(a | b) P(b). Marginalization: P(a) = Σ_b P(a, b).
  • Bayes' rule: P(h | e) = P(e | h) P(h) / P(e). Independence: P(a, b) = P(a) P(b).
  • Bayesian network: P(x1, ..., xn) = Π P(xi | parents(xi)).
  • HMM filtering: P(X_t | e_1:t) ∝ P(e_t | X_t) · Σ_x P(X_t | x) P(x | e_1:t−1).
  • Expected utility: EU(a) = Σ_s P(s | a) U(s).
  • Bellman equation: V(s) = max_a Σ_s' P(s' | s, a) [R(s, a, s') + γ V(s')].
  • Q-learning: Q(s, a) ← Q(s, a) + α [r + γ max_a' Q(s', a') − Q(s, a)].
Method Use
Enumeration / variable elimination Exact inference in Bayesian networks
Rejection, likelihood weighting, Gibbs Approximate inference by sampling
Forward algorithm Filtering in an HMM
Viterbi Most likely state sequence in an HMM
Kalman filter Linear-Gaussian filtering
Particle filter Non-linear, non-Gaussian filtering with samples
Value / policy iteration Solve a known MDP
Q-learning Learn a policy from experience without a model

The next program shows several of these formulas as numbers: grid distances, the chance that annealing accepts a worse move, UCB1 scores, a Bayes update, a Bellman backup and the effective branching factor.

Python Formulas you will reuse

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the annealing table: at T = 100 almost every move is accepted, while at T = 0.1 almost none are, which is the "hot to cold" transition. In the UCB1 list, move A has the same mean as move B but a smaller bonus, because it has been tried more often; the formula sends the next simulation to B, the move we know the least about.

Robotics

Topic Formula
Rotation in 2-D R(θ) = [[cos θ, −sin θ], [sin θ, cos θ]]
Homogeneous transform T = [[R, t], [0, 1]]; transforms compose by matrix multiplication
Two-link arm, forward x = l1 cos θ1 + l2 cos(θ1 + θ2), y = l1 sin θ1 + l2 sin(θ1 + θ2)
Two-link arm, inverse cos θ2 = (x² + y² − l1² − l2²) / (2 l1 l2) (out of reach if `
Differential drive v = (v_r + v_l)/2, ω = (v_r − v_l)/L, ẋ = v cos θ, ẏ = v sin θ, θ̇ = ω
PID control u(t) = Kp·e(t) + Ki·∫e dt + Kd·de/dt
Path planning Grid: A*; continuous high-dimensional space: PRM or RRT; local reactive: potential fields
Localization Histogram, Kalman or particle filter: predict with the motion model, update with the sensor model

Checklist for any new problem. (1) Write the PEAS description. (2) Classify the environment. (3) Choose a state representation that is as small as possible. (4) Pick the simplest algorithm that gives the guarantee you need. (5) Think of a relaxation for the heuristic. (6) Test on tiny instances where you can verify the answer by hand. (7) Measure nodes expanded, not just runtime.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. You have a weighted graph, no heuristic, and you want the cheapest path. Which method fits best?

    Uniform-cost search expands nodes in order of path cost and is optimal for positive step costs. DFS and greedy search offer no optimality guarantee.
  2. 2. Which search needs only O(bd) memory and still finds the shallowest goal when step costs are equal?

    Iterative deepening runs depth-limited DFS with growing limits. It keeps the memory of DFS and the completeness and optimality of BFS.
  3. 3. A problem asks only for a final arrangement that satisfies many local rules, and the path to it is irrelevant. Which family is the natural first choice?

    When only the final configuration matters, CSP solvers and local search work directly on assignments instead of paths.
  4. 4. In the two-link arm formulas, what does |cos θ2| > 1 tell you?

    cos θ2 cannot exceed 1, so the target distance is greater than l1 + l2 or smaller than |l1 − l2|, and the arm cannot reach it.

Summary

  • Choose the method from the problem's shape: opponent, uncertainty, constraints, structured actions or plain pathfinding.
  • BFS, DFS, uniform-cost and iterative deepening differ in completeness, optimality and memory; A* adds a heuristic and needs admissibility (and consistency for graph search).
  • Memory-bounded variants (IDA*, beam, weighted A*) trade optimality or time for space.
  • CSP solving is MRV + LCV + forward checking + AC-3; local search needs an escape from local optima.
  • Alpha-beta equals minimax in value and can search twice as deep with good ordering; MCTS needs no evaluation function.
  • Logic: entailment, soundness, completeness, resolution, DPLL; planning: STRIPS with relaxed heuristics.
  • Probability and decisions come down to Bayes' rule, the HMM filter and the Bellman equation.
  • Robotics adds kinematics, PID control, path planning and filtering on top of everything else.

You have reached the end of the course. To revisit the foundations, go back to What Is Classical AI?.