Search Studio

Free, open-source visual studio for AI search algorithms: BFS, DFS, DFID, A*, IDA*, hill climbing, simulated annealing, genetic algorithms, ant colony, TSP heuristics, Minimax, Alpha-Beta, SSS*, planning, AO*, Rete and constraint satisfaction. Step-by-step OPEN/CLOSED traces, beginner explanations and printable exports.

The interactive studio needs JavaScript. Every algorithm also has a plain page:

Week 2

Breadth First Search — OPEN is a queue: new children are appended, so the shallowest node is expanded first. Finds a path with the fewest edges.
Depth First Search — OPEN is a stack: new children are prepended, so the deepest node is expanded first. Little memory, no optimality.
Depth First Iterative Deepening — Run depth-bounded DFS with bound 0, 1, 2, … until the goal is found. The path of BFS with the memory of DFS, at the price of repeated work.

Week 3

Brute force (exact) — Fix the first city and try every ordering of the rest; for a symmetric TSP each tour appears twice, so (n−1)!/2 distinct tours.
Nearest Neighbour — Grow one path from a start city, always moving to the closest unvisited city; return home at the end.
Greedy heuristic — Scan edges shortest first; accept an edge unless a city would get degree 3 or a cycle shorter than n would close.
Savings heuristic — Start with an out-and-back trip from the base to every city, then merge trips in decreasing order of savings S(i,j) = C(base,i) + C(base,j) − C(i,j).
2-city exchange — Swap the positions of any two cities: n(n−1)/2 neighbours. Steepest-descent hill climbing until no swap helps.
Best First Search — OPEN is a priority queue on h(N), the heuristic estimate of distance to the goal. Fast when h is good, not optimal.
2-edge exchange (2-opt) — Remove two non-adjacent edges and reconnect the other way, which reverses the block between them: n(n−3)/2 neighbours.
Hill Climbing — Move to the best-looking neighbour (lowest h) as long as it improves on the current node. Constant memory, but it stops at the first local optimum, which need not be the goal.
Or-opt (move a city) — Take one city out and insert it between two other neighbours: a special 3-edge exchange.
Beam Search — Generate the children of every node in the beam and keep only the w best by h. Memory is bounded by w; a narrow beam can discard the only way to the goal.
3-edge exchange — Remove three edges and reconnect the three segments in a new way (pure 3-opt moves).
Variable neighbourhood descent — Hill climb with a sparse neighbourhood, then continue from its local optimum with denser ones. A local optimum of one MoveGen need not be one of the next.
Beam search — Keep the w best neighbours of all beam members at every level; stop when the best of the level is no better than the best so far. w = 1 is hill climbing.
Tabu search — Always move to the best neighbour that is not tabu, even if it is worse. A move's key (the swapped pair / removed edges) stays tabu for tt iterations; aspiration allows a tabu move that beats bestSeen.
Iterated hill climbing — Repeat: random start tour, steepest-descent hill climbing to a local optimum. Return the best local optimum found.
Random walk — Pure exploration: ignore the evaluation function and step to a random neighbour each time, remembering the best tour seen.
Simulated annealing — Pick a random neighbour and move to it with probability P = 1/(1 + e^(−ΔE/T)), ΔE = cost(current) − cost(next). T falls geometrically: high T ≈ coin flip, T → 0 ≈ hill climbing.

Week 4

Genetic algorithm — Population of tours. Roulette-wheel selection (fitness = K / cost), pairwise crossover, swap mutation, then the weakest members are replaced by the strongest offspring.
Crossover lab — Apply one TSP crossover to two parents: cycle, PMX, order (path representation), alternating edges and heuristic (adjacency), ordinal + single-point, or naive single-point to see why it fails.
Ant colony optimisation — Each ant builds a tour city by city with P(i→j) ∝ τ^α (1/d)^β over unvisited cities. Then pheromone evaporates, τ ← (1−ρ)τ, and every ant deposits Q/L on the edges of its tour.

Week 5

Week 6

Sequence alignment (dynamic programming) — Fill a table D(i,j) = cheapest alignment of the first i letters of a with the first j letters of b, one row at a time, then trace back the optimal path through the lattice.
Sequence alignment (A*) — Treat each lattice point (i,j) as a state and search from (0,0) to (m,n) with A*. h(i,j) = gap × |(m−i) − (n−j)| never overestimates, because that many gaps are unavoidable.
Admissibility & monotone check — Compute the true remaining cost h* by a backward Dijkstra from the goal, then test every node for admissibility (h ≤ h*) and every edge for the monotone condition h(m) ≤ k(m,n) + h(n).
IDA* — Depth-first search that never expands a node with f = g + h above a bound. Start with bound f(S); after a failed pass, raise the bound to the smallest f that was cut off. Optimal with admissible h, memory linear in depth.
Recursive Best-First Search — Explore the best child while its f stays below the best alternative elsewhere; when it exceeds that limit, back up its f value and switch. Keeps only the current path and its siblings.
Divide & Conquer Frontier Search — Frontier search drops CLOSED: each OPEN node remembers which neighbours already used an edge to it, so expanded nodes are never regenerated. A relay node halfway along each path lets the path be rebuilt by two smaller searches.

Week 7

Minimax — Evaluate the game tree depth-first from left to right: a MAX node takes the largest child value, a MIN node the smallest. The root's value is the outcome with best play from both sides.
Alpha-Beta pruning — Carry a window (α, β): α is the best value MAX can already guarantee, β the best MIN can guarantee. When α ≥ β at a node, the remaining children cannot matter and are pruned.
SSS* — A best-first algorithm for game trees. OPEN holds triples (node, LIVE or SOLVED, merit h). It refines the most promising strategy first and never evaluates a leaf that Alpha-Beta would prune; it can skip leaves Alpha-Beta evaluates.

Week 8

Forward state-space planning — Search forward from the initial state: every applicable operator gives a successor state. Breadth-first search returns a shortest plan, but the branching factor is the number of applicable actions.
Backward state-space planning — Search backwards from the goal. An operator is relevant if it adds a goal and deletes none; regressing the goal set G through it gives (G − add) ∪ pre. Stop when the initial state satisfies the current goal set.
Goal Stack Planning — Keep a stack of goals and actions. Pop satisfied goals; replace an unsatisfied goal by an action that achieves it plus that action's preconditions; when an action reaches the top its preconditions hold, so apply it. Goals are solved one at a time, which is why the Sussman anomaly makes it undo its own work.
Partial Order Planning — Search in the space of partial plans. Start with steps Start (effects = initial state) and Finish (preconditions = goal). Repeatedly pick an open precondition, support it with an existing or a new step via a causal link, and resolve threats by promotion or demotion. Backtrack when stuck.

Week 9

AO* — Follow the marked (currently best) connectors from the start to an unexpanded node, expand it, then revise costs upwards: each node's cost is its cheapest connector, an AND connector costs the sum over its children. A node is solved when all children of its marked connector are solved.

Week 10

Forward chaining — Repeat the recognise–act cycle: match every rule against working memory to build the conflict set, choose one instantiation by a conflict-resolution strategy, fire it (add or remove facts), until no new instantiation remains.
Rete algorithm — Compile the conditions into a network. Alpha nodes test one pattern and remember the facts that pass; beta (join) nodes combine partial matches with consistent variable bindings; terminal nodes feed the conflict set. A new fact only travels the paths it affects, so nothing is re-matched.

Week 11

Backtracking — Assign variables one at a time in a fixed order, trying values in order. If a value conflicts with an earlier assignment try the next; if none is left, go back to the previous variable (chronological backtracking).
Forward checking — Combine search and reasoning: after assigning a variable, delete the values of its future neighbours that conflict with it. If some future domain becomes empty, backtrack at once instead of discovering the failure later.
Arc consistency (AC-1, AC-3) — Delete every value that has no supporting value in a neighbouring variable. Revise(X, Y) removes unsupported values of X with respect to Y. AC-1 sweeps all arcs until nothing changes; AC-3 keeps a queue and re-examines only the arcs into a variable whose domain shrank.
Waltz algorithm — Interpret a line drawing of a polyhedral scene. Each junction starts with every labelling its type allows (L, fork, arrow, T); a labelling survives only if each of its lines can get the same label from the junction at the other end. Propagate with an AC-3 style queue.
Model-based diagnosis — Assume components work as their models say and propagate values through the circuit. A contradiction with an observation implicates the components whose models were used: a conflict set. A diagnosis is a minimal set of components that hits every conflict.

AI: Search Methods for Problem Solving

Watch search algorithms think, one step at a time.

Learn each algorithm in plain language, then trace it on worked examples or on problems you create. Every OPEN list, table and choice is on screen.

Open the studio Browse the library

Nearest Neighbour on six cities

01 · Learn Read before you run Beginner introductions, definitions, pseudocode line by line, formulas and why they hold, and exam traps for 46 algorithms. Open the library → 02 · Studio Step through every decision Run any algorithm on built-in examples, a random problem from a seed, or your own matrix, graph, game tree or constraint problem. Open the studio → 03 · Course map Find it by week Weeks 1–11 of the course, from depth-first search to the Waltz algorithm, each linked to its learn page and studio run. Open the course map →

Jump straight in

Reading the stage

current node on OPEN / candidate on CLOSED path, goal, solved rejected, removed, pruned alternative / second parent 2small yellow number = depth, g, h, value

Guide

How to use Search Studio

Three places matter: the library, where you learn an algorithm; the studio, where you run it; and the export panel, where you take the trace away.

1. Learn the algorithm first

Open the library and pick an algorithm. Its page has:

Introduction in plain language, and a precise definition.
Pseudocode with a sentence on what each line does and why.
Formulas: each written out, read aloud in words, and justified.
Properties (complete? optimal? time and space) and common traps.

Press Try it to open the studio with that algorithm and a suitable example already loaded.

2. Run it in the studio

Choose a problem

Examples come with the site: the six-city instance from the TSP deck, two five-city practice matrices, and three graphs for uninformed and informed search.
Random makes a new TSP or graph from a size and a seed. The same seed always gives the same problem, so you can share it.
Edit shows the problem as text you can change (format below) and saves it under My problems in this browser.
Import accepts a problem as JSON (paste it or choose a file); Export problem gives you that JSON back.

Choose an algorithm and its settings

Only algorithms that fit the problem type are listed. Settings such as start city, beam width, tabu tenure, temperature or random seed appear below. Changing anything re-runs the algorithm from the start.

Step through

← → step back and forward, Space plays or pauses, Home / End jump to the first or last step.
The slider scrubs; the speed menu sets seconds per step.
The Trace tab lists every step's caption; click one to jump to it.

3. Read the stage

Left: the graph. Right: the working table for this algorithm, with the current row highlighted, and a small chart where one helps (temperature runs, restarts, roulette wheels). Below: the lists, such as OPEN and CLOSED written as node pairs (node, parent, value). At the bottom, in yellow, one sentence says what just happened.

you see	it means
yellow ring	the node being expanded or the city the tour is at
orange ring	on OPEN (generated, waiting), or a candidate being considered
grey node	on CLOSED (already expanded)
green	path found, accepted edge, optimum, goal (double ring)
red dashes	an edge being removed or a choice being rejected
orange dashes	candidate edges from the current city
blue dashes	the second parent tour, or an out-and-back trip in the savings heuristic
thick orange edges (ACO)	pheromone: thicker means more

4. Problem text formats

TSP: names, then the matrix

A B C D E
0 58 92 34 81
58 0 20 46 70
92 20 0 28 53
34 46 28 0 12
81 70 53 12 0

Use any whitespace or commas. The matrix may be asymmetric; the site tells you when it is.

Graph: start, goal, heuristic, edges

start S
goal G
undirected
h S 7
h A 5
# edges: from to cost
S A 2
S B 5
A G 6
B G 1

Write directed instead of undirected for one-way edges. Lines starting with # are comments. Nodes without a position are placed on a circle.

5. Take it away

Printable trace: a self-contained HTML page with a cover (problem, settings, pseudocode) and one step per printed page. Open it in a browser and print, or save as PDF.
Trace JSON / CSV: every step's caption, table and lists, for notes or spreadsheets.
Current step as SVG: the graph drawing, for slides.

Conventions used everywhere

Ties are broken alphabetically unless a setting says otherwise; MoveGen lists neighbours alphabetically.
Tours are written in path representation; the edge back to the start is always included in the cost.
Graph search is graph search: a node already on OPEN or CLOSED is not added again; UCS and A* update it when they find a cheaper path.
The goal test happens when a node is picked from OPEN, as in the course.
Random choices use a seeded generator, so a run can always be repeated exactly.

About

About Search Studio

A study companion for search methods: the algorithms of state-space search, informed search and stochastic optimisation, traced exactly the way they are traced by hand.

Why it exists

Search algorithms are easy to describe and surprisingly easy to trace wrongly: a missed tie-break, a child added twice, a forgotten closing edge, a savings pair merged that should have been refused. Seeing every step, with the working table and the OPEN and CLOSED lists side by side, makes those mistakes visible.

What it covers

State-space search: Breadth First, Depth First, Depth First Iterative Deepening, Uniform Cost, Best First and A* (with weighted A*).
Travelling salesperson, constructive: Nearest Neighbour, Greedy, Savings, and brute force as the exact reference.
Perturbation and local search: 2-city exchange, 2-edge exchange, Or-opt, 3-edge exchange, Variable Neighbourhood Descent, Beam Search, Tabu Search, Iterated Hill Climbing, Random Walk, Simulated Annealing.
Population methods: Genetic Algorithm with cycle, PMX, order, alternating-edges, heuristic and ordinal crossover, and Ant Colony Optimisation.

Notation

The site follows the notation of AI: Search Methods for Problem Solving (Prof. Deepak Khemani, IIT Madras) and his book A First Course in Artificial Intelligence: MoveGen and GoalTest, OPEN and CLOSED as lists of node pairs, path representation for tours, the sigmoid acceptance rule for simulated annealing, and the course's crossover conventions. It is an independent study aid and is not affiliated with or endorsed by IIT Madras.

How results are checked

Every algorithm is run against every example and against random problems on each build. Tours must be permutations whose reported cost matches a recomputation; paths must run from start to goal with the reported cost. On the six-city instance the results are compared with an independent Python implementation (optimum 224, Nearest Neighbour 264, Greedy 238, Savings 224, and so on).

Add an algorithm or an example

The library is the algorithms/ folder. Add a file, run the build, and it appears on the site with its own learn page and studio entry.

Project layout

search-studio/
├── algorithms/          one file per algorithm, grouped by family
│   ├── _template.js     copy this to start (files starting with _ are skipped)
│   ├── search/          bfs.js, dfs.js, dfid.js, ucs.js, best-first.js, a-star.js
│   └── tsp/             nearest-neighbour.js, greedy.js, savings.js, …
├── examples/            one JSON file per built-in problem
├── src/
│   ├── core/            registry, problem model, search engine, TSP helpers
│   ├── ui/              stage renderer and the app
│   ├── pages/           home, guide, about, contribute (plain HTML)
│   └── styles/          studio.css
├── tools/
│   ├── build.mjs        scans the folders and builds the site
│   └── test.mjs         runs every algorithm on every example
├── index.html           generated: the site, loading files from the folders
└── dist/search-studio.html   generated: the whole site in one file

Add an algorithm in four steps

Copy algorithms/_template.js to algorithms/<family>/<name>.js.
Fill in the metadata (id, name, family, problem), the learn block and run.
Run node tools/build.mjs. The build loads every file, checks that it registers, runs it on the examples, and regenerates index.html, the manifest and the single-file build. Use node tools/build.mjs --watch while you work.
Open index.html (or serve the folder with npx serve) and find your algorithm in the library.

The algorithm file

Studio.register({
  id: "tsp-my-method",            // unique, used in links: #algo-tsp-my-method
  name: "My method",
  family: "TSP · local search",   // the library groups by this
  problem: "tsp",                 // tsp, graph, game, andor, planning, rules, csp, linedrawing, circuit, alignment
  week: 3,                        // course week 1–11: places it on the course map
  order: 200,                     // position inside the family
  summary: "One sentence for the library card.",
  pseudocode: `...`,
  complexity: "O(n²) per step",
  learn: {
    intro: "Plain-language introduction.",
    definition: "Precise definition.",
    steps: [["pseudocode line", "what it does and why"]],
    formulas: [{ f: "formula", read: "in words", why: "why it holds" }],
    why: "When it works and when it fails.",
    traps: ["Common mistake"],
    props: { complete: "no", optimal: "no", time: "…", space: "…" }
  },
  params: [
    { key: "start", label: "Start city", type: "city", default: P => P.ids[0] },
    { key: "w", label: "Beam width", type: "int", default: 2 },
    Studio.seedParam(1)
  ],
  run(P, params) {
    // P.ids, P.d(a, b), P.cost(tour) for TSP; P.adj, P.h, P.start, P.goal for graphs
    return { steps: [ /* one object per snapshot */ ], result: { tour, cost } };
  }
});

What a step can contain

field	shape	shown as
`caption`	string	the yellow sentence under the stage (required)
`nodes`	`{ A: { state, badge } }`	node colours; states: plain, current, open, closed, visited, path, goal, start
`edges`	`[{ u, v, state, label }]`	edges; states: faint, tour, path, candidate, added, removed, rejected, alt, tree, pheromone
`table`	`{ title, columns, rows, rowStates }`	the working table; row states: ok, bad, warn, cur, dim
`lists`	`[{ label, items: [{ text, state }] }]`	OPEN / CLOSED style rows
`stats`	`[{ label, value, state }]`	small figures under the graph
`chart`	`{ kind: "walk" \| "drops" \| "bars" \| "pie", … }`	a small chart beside the table

Helpers in src/core do most of the work: Studio.search.run for OPEN/CLOSED searches, Studio.tsp.moveGens for 2-city, 2-edge, Or-opt and 3-edge neighbourhoods, Studio.tspSteps.hillClimb for traced hill climbing, Studio.tsp.crossovers for every crossover, and Studio.rng(seed) for repeatable randomness.

Add an example problem

Drop a JSON file into examples/ and rebuild. In the studio, Export problem gives you a file in exactly this shape.

{ "id": "graph-my-maze", "type": "graph", "name": "My maze",
  "note": "One line shown under the problem selector.",
  "nodes": [{ "id": "S", "x": 0, "y": 0, "h": 4 }, …],
  "edges": [["S", "A", 2], …], "start": "S", "goal": "G", "directed": false }

{ "id": "tsp-my-cities", "type": "tsp", "name": "My cities",
  "cities": [{ "id": "A", "x": 1, "y": 2 }, …],
  "matrix": [[0, 12, …], …] }          // optional: without it, 10 × Euclidean distance

Checklist before you share

node tools/test.mjs passes: every step has a caption, edges and nodes exist, tours are permutations with correct costs.
Ties are broken the course's way (alphabetically) or a setting says otherwise.
The learn block explains every formula you use and at least one trap.
Random choices go through Studio.rng(seed) so runs repeat exactly.

Source and license

The code is on GitHub, with a CONTRIBUTING.md that repeats this page. Everything is released into the public domain under the Unlicense: copy, change, teach with or sell it, no attribution needed. By contributing you release your work the same way.