A self-contained, terminal-friendly repository that teaches the classic algorithms of artificial intelligence through plain-language explanations and small, runnable programs.
Before deep learning dominated the headlines, "artificial intelligence" meant a toolbox of ideas developed roughly between the 1950s and the 1990s: searching through possibilities, playing games by looking ahead, learning simple patterns from data, reasoning with rules, and improving solutions by trial and error. These techniques are classic in both senses of the word — they are old, and they have lasted. They still run inside route planners, game engines, spam filters, spell checkers, business rule engines, and robotics stacks, and they are the conceptual ancestors of modern machine learning. Because each one is small enough to implement in a few hundred lines, they are also the best possible way to learn how AI actually works, with nothing hidden inside a framework.
Every algorithm here is implemented directly and visibly. No machine-learning library does the interesting work for you.
- Python 3.11 or newer. Every topic has a Python implementation with no third-party
dependencies — the standard library is enough. There is no
requirements.txtbecause nothing needs installing. - Comfort with basic Python (functions, lists, dictionaries, classes).
- No advanced mathematics. Every formula that appears is explained in plain language.
- Optional, only for the extra-language examples: a C/C++ compiler (
gcc/g++, or MSVC on Windows), SWI-Prolog (swipl), and a Scheme interpreter such as Guile or Chez.
Every topic directory stands alone. To run a topic's demonstration, cd into its directory
and run the primary script; to run its tests, use the standard-library unittest runner:
cd breadth-first-search
python bfs.py
python -m unittest discover
Windows note: if
pythonon your PATH is old, use the launcher instead:py -3 bfs.pyandpy -3 -m unittest discover.
To run every Python demonstration at once from the repository root:
python scripts/run_python_examples.py
python scripts/run_python_examples.py --check-determinism
The second form runs each example twice and verifies the output is identical, proving that every randomized example is seeded and reproducible.
If you have make (on Windows: under WSL or Git Bash), the root Makefile
wraps the common chores: make test, make run-examples, make check-determinism,
make extras (builds and runs the C/C++/Prolog/Scheme examples), and make clean. It
skips optional language toolchains that are not installed.
Optional languages. A handful of topics include a second implementation in C, C++, Scheme, or Prolog — only where that language genuinely illuminates the algorithm. Each such topic's README gives exact build and run commands, for example:
gcc -std=c99 -Wall -O2 -o bfs bfs.c && ./bfs # C
g++ -std=c++17 -Wall -O2 -o astar astar.cpp && ./astar # C++
swipl -q -s dfs.pl -g main -t halt # Prolog
guile minimax.scm # Scheme
The topics are ordered from easiest and most approachable to most advanced. The path moves through five arcs: searching for solutions, playing games by looking ahead, improving solutions by trial and error, learning from data and from interaction, and finally reasoning with explicit rules. Each topic's README ends with a pointer to the next one, so you can simply follow the chain from top to bottom.
| # | Topic | What it teaches | Extra languages |
|---|---|---|---|
| 1 | Breadth-First Search | Explore a graph level by level; find shortest paths in unweighted graphs | C |
| 2 | Depth-First Search | Dive deep before backtracking; recursion and stacks; contrast with BFS | Prolog |
| 3 | Hill Climbing | Greedy local search; local versus global maxima; random restarts | — |
| 4 | A* Search | Informed search with heuristics; g/h/f scores; compared against Dijkstra and greedy best-first | C++ |
| 5 | Minimax | Perfect play in two-player games by exploring the game tree | Scheme |
| 6 | Alpha-Beta Pruning | Skip provably irrelevant branches of the game tree without changing the answer | C++ |
| 7 | Simulated Annealing | Escape local optima by sometimes accepting worse moves, less often as "temperature" falls | — |
| 8 | Genetic Algorithms | Evolve a population of candidate solutions with selection, crossover, and mutation | — |
| 9 | K-Nearest Neighbors | Classify by looking at the most similar known examples; distance and feature scaling | — |
| 10 | Naive Bayes | Classify text with probabilities; priors, likelihoods, smoothing, and log arithmetic | — |
| 11 | Decision Trees | Learn human-readable if/then rules from data; entropy and information gain | — |
| 12 | Perceptron | The first trainable neuron; weight updates; why a single line can't solve XOR | C |
| 13 | Backpropagation | Train a multi-layer network from scratch; the chain rule made concrete; solves XOR | — |
| 14 | Hidden Markov Models | Infer hidden causes from visible evidence; the forward and Viterbi algorithms | — |
| 15 | Q-Learning | Learn good behavior from rewards alone; exploration versus exploitation in a grid world | — |
| 16 | Expert Systems | Encode knowledge as rules; forward and backward chaining; explainable inference | Prolog |
The notes below give a one-paragraph description of each topic and the main ideas you should be comfortable with before moving on — treat them as a checklist.
- Breadth-First Search explores a graph outward from a start node in expanding layers, guaranteeing the shortest path when every step costs the same. Before moving on: the queue discipline (first in, first out), why a visited set prevents infinite loops, and how a parent map turns a search into a reconstructable path.
- Depth-First Search follows one branch as deep as it can before backtracking. Before moving on: the stack/recursion duality, why DFS finds a path but not necessarily the shortest, and when its low memory use makes it the right choice.
- Hill Climbing repeatedly steps to the best neighboring solution until no neighbor is better. Before moving on: the difference between a local and a global maximum, why the starting point determines the destination, and how random restarts buy robustness.
- A* Search is BFS with brains: it expands the node that looks cheapest counting both the cost already paid (g) and an optimistic estimate of what remains (h). Before moving on: what makes a heuristic admissible, why A* is optimal when the heuristic never overestimates, and how A* relates to Dijkstra (h = 0) and greedy best-first (g ignored).
- Minimax plays two-player games perfectly by assuming both sides play their best and scoring positions from the bottom of the game tree upward. Before moving on: game trees, terminal evaluation, and the alternation of maximizing and minimizing turns.
- Alpha-Beta Pruning makes minimax fast by skipping branches that provably cannot change the decision. Before moving on: what the alpha and beta bounds mean, why the answer is identical to plain minimax, and why examining good moves first prunes more.
- Simulated Annealing improves a solution like hill climbing but sometimes accepts a worse neighbor — boldly at high "temperature," rarely as it cools — to escape local optima. Before moving on: the acceptance probability, cooling schedules, and the exploration-to-exploitation arc they create.
- Genetic Algorithms keep a whole population of candidate solutions and breed the fittest with crossover and mutation. Before moving on: fitness, selection pressure, why crossover and mutation play different roles, and what elitism protects.
- K-Nearest Neighbors classifies a new example by a majority vote of the k most similar training examples. Before moving on: Euclidean distance, choosing k, tie handling, and why unscaled features silently break distance-based methods.
- Naive Bayes scores each class as prior × word likelihoods and picks the biggest, pretending features are independent. Before moving on: priors versus likelihoods, Laplace smoothing, and why sums of logarithms replace products of probabilities.
- Decision Trees repeatedly split data on the most informative question until leaves are (nearly) pure. Before moving on: entropy as "mixedness," information gain, stopping conditions, and why deeper is not better (overfitting).
- Perceptron is a single trainable neuron: weighted sum, threshold, and a beautifully simple update rule. Before moving on: the update rule, linear separability, and why XOR defeats any single straight line — the cliffhanger that backpropagation resolves.
- Backpropagation trains multi-layer networks by pushing the error signal backward through the chain rule. Before moving on: the forward pass, the loss, how gradients flow layer to layer, and how a numerical gradient check certifies the math.
- Hidden Markov Models reason about hidden states from visible observations. Before moving on: transition versus emission probabilities, the forward algorithm's running belief, and Viterbi's max-instead-of-sum trick with back-pointers.
- Q-Learning learns how good each action is in each state purely from rewards. Before moving on: the Q-update rule, learning rate and discount factor, and the epsilon-greedy balance between exploring and exploiting.
- Expert Systems capture human expertise as IF–THEN rules and derive conclusions mechanically. Before moving on: facts versus rules, forward versus backward chaining, conflict resolution, and why an explanation trace matters.
Python is the primary language for every topic. A second language appears only where it teaches something Python cannot:
| Language | Topics | Why it's there |
|---|---|---|
| Python | all 16 topics | Clear, complete reference implementations with tests |
| C | Breadth-First Search, Perceptron | The queue, the visited array, and the neuron's dot product become explicit memory — nothing is hidden |
| C++ | A* Search, Alpha-Beta Pruning | The languages of real pathfinding and game engines; STL containers with visible performance |
| Scheme | Minimax | Game trees are just recursion; minimax collapses to a few elegant lines |
| Prolog | Depth-First Search, Expert Systems | Prolog's own execution is depth-first search with backtracking, and rules are the program |
Every implementation here favors clarity and education over production performance. Loops are explicit, variables have long names, intermediate values get printed, and data sets are small enough to check by hand. If you need industrial-strength versions of these algorithms, reach for a well-tested library — and you will understand exactly what it is doing, because you built one yourself.