AI Fundamentals Cheat Sheet
agents · search · planning · propositional logic · first-order logic · CSP · knowledge representation
Sheet 1 of 3
AI Fundamentals
Foundational
Printable
Intelligent Agents
An intelligent agent perceives its environment through sensors and acts upon it through actuators to maximise a performance measure.
Agent Function
f: P* → A
Maps percept sequences P* to actions A. The agent program implements this function. Rational agent maximises expected performance measure.
PEAS Framework
PEAS = (Performance, Environment, Actuators, Sensors)
Always define PEAS before designing an agent. E.g. taxi driver: Performance=safe/fast trip, Environment=roads, Actuators=steering/brakes, Sensors=cameras/GPS.
| Agent Type | Decision Basis | Memory | Example |
|---|---|---|---|
| Simple Reflex | Current percept only | None | Thermostat |
| Model-Based Reflex | Percept + internal state | World model | Self-driving (partial) |
| Goal-Based | Goals + search | World model | Route planner |
| Utility-Based | Utility function | World + util | Chess engine |
| Learning | Experience | All + learn | AlphaGo |
| Environment Property | Description |
|---|---|
| Fully observable | Agent sees complete state |
| Partially observable | Agent has incomplete info |
| Deterministic | Next state is fixed given action |
| Stochastic | Next state has uncertainty |
| Episodic | Each episode is independent |
| Sequential | Decisions affect future states |
| Discrete | Finite states and actions |
| Continuous | Infinite state/action spaces |
Rationality ≠ Omniscience: A rational agent maximises expected performance given its percept sequence — it cannot be faulted for not knowing unknowable information.
Uninformed Search
Search without domain-specific knowledge. Explores the state space systematically using only problem structure.
| Algorithm | Complete? | Optimal? | Time | Space |
|---|---|---|---|---|
| BFS | Yes* | Yes (unit cost) | O(bd) | O(bd) |
| DFS | No | No | O(bm) | O(bm) |
| UCS | Yes* | Yes | O(bC*/ε) | O(bC*/ε) |
| IDS | Yes* | Yes (unit cost) | O(bd) | O(bd) |
| Bidir. | Yes* | Yes* | O(bd/2) | O(bd/2) |
b = branching factor · d = solution depth · m = max depth · C* = optimal cost · ε = min step cost · * = if b finite
BFS Implementation
from collections import deque def bfs(start, goal, graph): queue = deque([(start, [start])]) visited = {start} while queue: node, path = queue.popleft() if node == goal: return path for nb in graph[node]: if nb not in visited: visited.add(nb) queue.append((nb, path+[nb]))
IDS = best of both: Iterative deepening combines BFS's completeness and optimality with DFS's O(bd) linear space. Standard choice for large state spaces with unknown depth.
Informed Search
A* Evaluation Function
f(n) = g(n) + h(n)
g(n) = actual cost from start to n. h(n) = heuristic estimate from n to goal. A* is optimal if h is admissible (never overestimates).
Admissibility & Consistency
h(n) ≤ h*(n) · h(n) ≤ c(n,a,n') + h(n')
h*(n) = true cost to goal. Admissible: never overestimates. Consistent (monotone): triangle inequality holds. Consistent → admissible.
| Algorithm | Heuristic | Optimal? | Notes |
|---|---|---|---|
| Greedy BFS | h(n) only | No | Fast, not optimal |
| A* | g(n)+h(n) | Yes (admissible h) | Gold standard |
| IDA* | g(n)+h(n) | Yes | Linear space |
| RBFS | g(n)+h(n) | Yes | Memory-efficient |
A* with heapq
import heapq def astar(start, goal, h, graph): pq = [(h(start), 0, start, [start])] visited = {} while pq: f, g, node, path = heapq.heappop(pq) if node == goal: return path if node in visited: continue visited[node] = g for nb, cost in graph[node]: g2 = g + cost heapq.heappush(pq, (g2+h(nb), g2, nb, path+[nb]))
Local Search & Optimisation
Local search operates on complete state configurations and iteratively improves them. No path is maintained — only the current state matters. Useful for large optimisation problems.
Hill Climbing
snext = argmaxs'∈N(s) f(s')
Greedy: always move to best neighbour. Gets stuck at local maxima, plateaux, ridges. Variants: random restart, sideways moves, stochastic HC.
Simulated Annealing — Acceptance
P(accept) = eΔE/T if ΔE < 0
T = temperature (decreases over time). Accepts worse states early (high T) to escape local optima. Converges to global optimum if T decreases slowly enough.
| Algorithm | Finds Global Opt? | Memory | Best For |
|---|---|---|---|
| Hill Climbing | No (local only) | O(1) | Quick approximate |
| Random Restart HC | Eventually | O(1) | Many local optima |
| Simulated Annealing | Prob. yes | O(1) | Continuous spaces |
| Genetic Algorithm | Prob. yes | O(pop) | Combinatorial, NLP |
| Beam Search | No | O(k) | NLP generation |
Simulated Annealing
import math, random def simulated_annealing(s0, energy, neighbour, T0=1000, alpha=0.995): s, T = s0, T0 while T > 0.1: s2 = neighbour(s) dE = energy(s2) - energy(s) if dE < 0 or random.random() < math.exp(-dE/T): s = s2 T *= alpha return s
Genetic Algorithm — Skeleton
def genetic_algorithm(pop, fitness, crossover, mutate, gens=100): for _ in range(gens): # Selection (roulette / tournament) fits = [fitness(i) for i in pop] parents = select(pop, fits) # Crossover + mutation pop = [ mutate(crossover(parents[i], parents[i+1])) for i in range(0, len(parents), 2) ] return max(pop, key=fitness)
Plateau problem: Hill climbing stalls when all neighbours have equal value. Use random sideways moves (allow equal-value moves up to a limit) or random restarts from new starting states.
Propositional Logic
| Connective | Symbol | Meaning | True when |
|---|---|---|---|
| Negation | ¬P | NOT P | P is false |
| Conjunction | P ∧ Q | P AND Q | Both true |
| Disjunction | P ∨ Q | P OR Q | At least one true |
| Implication | P → Q | IF P THEN Q | P false OR Q true |
| Biconditional | P ↔ Q | P IFF Q | Same truth value |
Key Logical Equivalences
P → Q ≡ ¬P ∨ Q (implication elimination)
¬(P ∧ Q) ≡ ¬P ∨ ¬Q (De Morgan)
¬(P ∨ Q) ≡ ¬P ∧ ¬Q (De Morgan)
¬(P ∧ Q) ≡ ¬P ∨ ¬Q (De Morgan)
¬(P ∨ Q) ≡ ¬P ∧ ¬Q (De Morgan)
Inference Rules
Modus Ponens: P, P→Q ⊢ Q
Modus Tollens: ¬Q, P→Q ⊢ ¬P
Resolution: (P∨Q), (¬P∨R) ⊢ Q∨R
Modus Tollens: ¬Q, P→Q ⊢ ¬P
Resolution: (P∨Q), (¬P∨R) ⊢ Q∨R
Resolution is complete for propositional logic in CNF. Used in SAT solvers and theorem provers.
CNF (Conjunctive Normal Form): Every sentence can be converted to a conjunction of disjunctions (clauses). Required for resolution-based inference. Steps: eliminate ↔, eliminate →, push ¬ inward, distribute ∧ over ∨.
First-Order Logic (FOL)
FOL extends propositional logic with objects, relations, and quantifiers — allowing statements about all or some members of a domain.
| Element | Syntax | Example |
|---|---|---|
| Constant | John, 42 | Specific object |
| Variable | x, y | Placeholder for objects |
| Predicate | Loves(x,y) | Relation between objects |
| Function | Father(x) | Maps objects to objects |
| Universal ∀ | ∀x P(x) | "For all x, P holds" |
| Existential ∃ | ∃x P(x) | "There exists x, P holds" |
FOL Inference — Unification
UNIFY(p, q) = θ where Subst(θ, p) = Subst(θ, q)
θ = substitution that makes two FOL sentences identical. Required for generalised Modus Ponens and resolution in FOL.
Key FOL Equivalences
∀x P(x) ≡ ¬∃x ¬P(x)
∃x P(x) ≡ ¬∀x ¬P(x)
∀x (P→Q) ≡ P→∀x Q (x not free in P)
∃x P(x) ≡ ¬∀x ¬P(x)
∀x (P→Q) ≡ P→∀x Q (x not free in P)
Skolemization: To convert FOL to CNF, replace ∃x with a Skolem constant or function. E.g. ∃x Loves(x, y) becomes Loves(f(y), y). Required for resolution theorem proving.
AI Planning
Planning finds a sequence of actions to achieve a goal from an initial state. Classical planning assumes full observability, determinism, and finite discrete actions.
STRIPS Action Schema
Action(Name(params), PRECOND: P, EFFECT: E)
PRECOND = literals that must hold. EFFECT = literals added (positive) or deleted (negative) after action. E.g. Move(b,x,y): PRECOND: On(b,x)∧Clear(y), EFFECT: On(b,y)∧¬On(b,x).
| Approach | Direction | Strategy |
|---|---|---|
| Forward (progression) | Init → Goal | Apply actions, check goal |
| Backward (regression) | Goal → Init | Work backwards from goal |
| Plan-Space | Partial order | Refine partial plans |
| GraphPlan | Level graph | Mutex + extract plan |
| SAT Planning | Encode as SAT | SAT solver finds plan |
PDDL — Domain & Problem
; Domain definition (define (domain blocks) (:predicates (on ?b ?x) (clear ?b) (ontable ?b)) (:action move :parameters (?b ?from ?to) :precondition (and (on ?b ?from) (clear ?b) (clear ?to)) :effect (and (on ?b ?to) (not (on ?b ?from)) (clear ?from) (not (clear ?to))))) ; Problem definition (define (problem p1) (:domain blocks) (:init (on A table) (on B A) (clear B)) (:goal (on A B)))
Heuristics for Planning
hadd: sum of costs of sub-goals
hmax: max cost among sub-goals
hff: relaxed plan (delete-free) length
hmax: max cost among sub-goals
hff: relaxed plan (delete-free) length
hff (Fast-Forward heuristic): solve a relaxed problem ignoring delete effects. Highly effective in practice — used in FF, LAMA planners.
| Planner | Key Approach |
|---|---|
| FF | Forward + hff heuristic |
| LAMA | Landmark-based heuristics |
| FastDownward | Causal graph + SAS+ |
| MCTS planners | Monte Carlo + simulation |
Real-world planning: Classical STRIPS/PDDL assumes perfect information. Real applications need conditional effects (sensing), probabilistic transitions (MDPs), or temporal constraints (temporal planning).
Constraint Satisfaction (CSP)
CSP Definition
CSP = (X, D, C)
X = {X1…Xn} variables · D = {D1…Dn} domains · C = constraints. Solution = assignment satisfying all constraints. E.g. map colouring, Sudoku, scheduling.
| Algorithm | Strategy | Key Idea |
|---|---|---|
| Backtracking | Systematic DFS | Assign + check + undo on fail |
| Forward Checking | Look-ahead | Prune domains of unassigned vars |
| AC-3 | Arc consistency | Remove inconsistent domain values |
| MRV heuristic | Variable order | Choose var with fewest legal values |
| LCV heuristic | Value order | Choose value ruling out fewest options |
| Min-conflicts | Local search | Repair conflicting assignments |
Backtracking CSP Solver
def backtrack(assignment, csp): if complete(assignment): return assignment var = select_unassigned_var(csp) # MRV for val in order_values(var, csp): # LCV if consistent(var, val, assignment): assignment[var] = val result = backtrack(assignment, csp) if result: return result del assignment[var] return None
Knowledge Representation
| Representation | Form | Best For |
|---|---|---|
| Propositional Logic | P ∧ Q → R | Simple boolean facts |
| First-Order Logic | ∀x P(x)→Q(x) | Rich relational facts |
| Semantic Networks | Nodes + edges | Taxonomy, IS-A relations |
| Frames | Slot-value pairs | Object-like structures |
| Production Rules | IF cond THEN act | Expert systems |
| Ontologies (OWL) | Classes + props | Web semantics, KG |
| Knowledge Graphs | (entity, rel, entity) | Wikidata, Google KG |
Closed-World vs Open-World Assumption
CWA: ¬KB ⊢ P → assume ¬P
OWA: ¬KB ⊢ P → P is unknown
OWA: ¬KB ⊢ P → P is unknown
Databases use CWA (what's not stored is false). OWL/ontologies use OWA (absence of info ≠ false). Critical difference for reasoning systems.
Knowledge Graph triple: (Subject, Predicate, Object) — e.g. (Einstein, bornIn, Ulm). RDF/SPARQL for querying. Neo4j for graph databases. Wikidata has 100M+ triples.
Adversarial Search
Used in two-player zero-sum games. MAX player maximises utility; MIN player minimises it.
Minimax Value
MINIMAX(s) = UTILITY(s) if TERMINAL(s)
= maxa MINIMAX(RESULT(s,a)) if MAX
= mina MINIMAX(RESULT(s,a)) if MIN
= maxa MINIMAX(RESULT(s,a)) if MAX
= mina MINIMAX(RESULT(s,a)) if MIN
Alpha-Beta Pruning
Prune if α ≥ β
α = best value MAX can guarantee. β = best value MIN can guarantee. Prune a branch when it cannot affect final decision. Reduces time from O(bm) → O(bm/2) with perfect ordering.
| Technique | Purpose |
|---|---|
| Alpha-Beta | Prune irrelevant branches |
| Move ordering | Try best moves first → more pruning |
| Quiescence search | Extend volatile positions (captures) |
| Transposition table | Cache evaluated positions (hash) |
| MCTS | Simulation-based (AlphaGo, chess) |
MCTS (Monte Carlo Tree Search): UCB1 selection → expansion → random rollout → backpropagation. No evaluation function needed. Foundation of AlphaGo, AlphaZero, and modern game AI.
AI Fundamentals Mastery Checklist
Agents & Search
- Define an intelligent agent using the PEAS framework for a real application
- Classify an environment across all 8 properties (observable, stochastic, etc.)
- Implement BFS and DFS and compare their time/space complexity
- Explain why IDS is preferred over BFS for unknown solution depths
- Implement A* with an admissible heuristic and verify optimality
- Prove a heuristic is admissible and consistent for a given problem
Logic & Knowledge
- Convert any propositional sentence to CNF form step by step
- Apply modus ponens, modus tollens, and resolution inference rules
- Write FOL sentences using ∀, ∃, predicates, and functions
- Apply unification to two FOL literals and compute the substitution θ
- Distinguish CWA from OWA and explain when each is appropriate
- Describe three knowledge representation schemes and their trade-offs
Planning, CSP & Games
- Write a STRIPS action schema with preconditions and effects
- Implement backtracking search with MRV and LCV heuristics for a CSP
- Apply AC-3 arc consistency to prune CSP domains manually
- Trace minimax on a small game tree and identify the optimal move
- Apply alpha-beta pruning to a game tree and identify pruned branches
- Implement simulated annealing and tune the cooling schedule