Artificial Intelligence Tutorial: Learn AI from Scratch (2026)
Artificial intelligence has evolved from a niche academic discipline into the defining technology of our era. Having shipped AI systems that serve millions of users, I have learned that effective AI development requires a balance of theoretical understanding and practical engineering. This tutorial covers the foundational algorithms of AI — search, knowledge representation, planning, and reasoning under uncertainty — that underpin everything from game-playing engines to robotic controllers.
We begin with uninformed and heuristic search, move through constraint satisfaction and logical inference, and conclude with probabilistic reasoning and planning. Each algorithm is implemented from scratch, with clear explanations of why it works and where it applies.
Uninformed Search: BFS, DFS, and Iterative Deepening
Uninformed search algorithms explore a state space without any domain-specific knowledge. Breadth-first search (BFS) guarantees the shortest path in unweighted graphs by exploring all nodes at the current depth before going deeper, using a queue. Depth-first search (DFS) uses a stack and explores as far as possible along each branch before backtracking — it uses far less memory but may explore infinitely deep paths.
from collections import deque
def iddfs(graph, start, goal, max_depth=100):
def dls(node, depth, visited):
if depth == 0 and node == goal: return [node]
if depth > 0:
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
path = dls(neighbor, depth - 1, visited.copy())
if path: return [node] + path
return None
for depth in range(max_depth):
result = dls(start, depth, set())
if result: return result
return NoneHeuristic Search and A*
Heuristic search uses domain knowledge — in the form of an admissible heuristic — to guide exploration toward the goal. A* combines the cost so far (g) with a heuristic estimate (h) to prioritize nodes via f = g + h. If the heuristic is admissible, A* is guaranteed to find the optimal path. Manhattan distance for grid navigation and Euclidean distance are common heuristics.
import heapq
def a_star(graph, start, goal, heuristic):
open_set = [(0, start)]; g_score = {start: 0}; came_from = {}
while open_set:
_, current = heapq.heappop(open_set)
if current == goal:
path = []; c = current
while c in came_from: path.append(c); c = came_from[c]
path.reverse(); return path
for neighbor, cost in graph.get(current, []):
tentative_g = g_score[current] + cost
if neighbor not in g_score or tentative_g < g_score[neighbor]:
g_score[neighbor] = tentative_g
heapq.heappush(open_set, (tentative_g + heuristic(neighbor, goal), neighbor))
came_from[neighbor] = current
return NoneConstraint Satisfaction Problems
Constraint satisfaction problems (CSPs) are defined by variables, domains, and constraints. Sudoku, map coloring, and scheduling are classic CSPs. Backtracking search with constraint propagation dramatically reduces the search space. The minimum remaining values (MRV) heuristic selects the variable with the fewest legal values.
def backtrack(csp, assignment):
if len(assignment) == len(csp['variables']): return assignment
var = select_unassigned_variable(csp, assignment)
for value in order_domain_values(var, csp, assignment):
if is_consistent(var, value, assignment, csp):
assignment[var] = value
inferences = infer(csp, var, value)
if inferences is not None:
result = backtrack(csp, assignment)
if result: return result
del assignment[var]
return None
def select_unassigned_variable(csp, assignment):
unassigned = [v for v in csp['variables'] if v not in assignment]
return min(unassigned, key=lambda v: len(csp['domains'][v]))Logical Inference and Propositional Logic
Propositional logic deals with Boolean variables connected by logical operators. Inference rules like Modus Ponens and resolution allow us to derive new truths from known facts. The resolution algorithm refutes the negation of a query by repeatedly applying the resolution rule until the empty clause (contradiction) is derived.
def resolve(c1, c2):
resolvents = []
for l1 in c1:
for l2 in c2:
if l1 == -l2:
new = (set(c1) | set(c2)) - {l1, l2}
resolvents.append(list(new))
return resolvents
def resolution(kb, query):
clauses = kb + [[-query]]; new = set()
while True:
for i in range(len(clauses)):
for j in range(i+1, len(clauses)):
resolvents = resolve(clauses[i], clauses[j])
if [] in resolvents: return True
new.update(tuple(c) for c in resolvents)
if new.issubset(set(tuple(c) for c in clauses)): return False
clauses.extend([list(c) for c in new])First-Order Logic and Knowledge Representation
First-order logic (FOL) extends propositional logic with quantifiers, variables, predicates, and functions. This expressiveness allows representing general knowledge. The resolution algorithm extends to FOL through unification — finding substitutions that make two literals identical. The unification algorithm finds the most general unifier (MGU) when one exists.
def unify(x, y, theta={}):
if theta is None: return None
if x == y: return theta
if isinstance(x, str) and x.islower(): return unify_var(x, y, theta)
if isinstance(y, str) and y.islower(): return unify_var(y, x, theta)
if isinstance(x, list) and isinstance(y, list) and len(x) == len(y):
for xi, yi in zip(x, y):
theta = unify(xi, yi, theta)
return theta
return None
def unify_var(var, x, theta):
if var in theta: return unify(theta[var], x, theta)
if x in theta: return unify(var, theta[x], theta)
if occurs_check(var, x): return None
theta[var] = x; return thetaAutomated Planning: STRIPS and PDDL
Automated planning involves finding a sequence of actions that transforms an initial state into a goal state. The STRIPS representation models the world as a set of first-order literals; each action has preconditions and effects (add and delete lists). PDDL standardizes this representation.
class Action:
def __init__(self, name, preconditions, add_effects, del_effects):
self.name = name; self.preconditions = set(preconditions)
self.add_effects = set(add_effects); self.del_effects = set(del_effects)
def applicable(self, state): return self.preconditions.issubset(state)
def apply(self, state): return (state - self.del_effects) | self.add_effects
def forward_search(initial, goals, actions):
from collections import deque
queue = deque([(initial, [])]); visited = set()
while queue:
state, plan = queue.popleft()
if goals.issubset(state): return plan
if frozenset(state) in visited: continue
visited.add(frozenset(state))
for action in actions:
if action.applicable(state):
queue.append((action.apply(state), plan + [action.name]))
return NoneFrequently Asked Questions
What is the difference between informed and uninformed search?
Uninformed search (BFS, DFS) uses no domain knowledge beyond the problem definition. Informed search (A*, greedy best-first) uses a heuristic function that estimates the cost from a state to the goal.
What makes a heuristic admissible?
A heuristic h(n) is admissible if it never overestimates the true cost to reach the goal. For example, straight-line distance on a map is admissible because the shortest path is at least the straight-line distance.
Is first-order logic complete?
First-order logic is semi-decidable — if a statement is entailed by the knowledge base, resolution will eventually prove it. However, if a statement is not entailed, the algorithm may run forever.
What is the frame problem in AI planning?
The frame problem asks how to efficiently represent everything that does NOT change when an action is executed. STRIPS handles this by explicitly listing add and delete effects.
Originally published on Ayodhyyya. Last updated June 1, 2026.