Seven Algorithm Lessons from Games

Games are algorithms’ most patient examiner: a 16 ms frame budget, an opponent who hits back, a space that tightens as you succeed — constraints no textbook provides. This post merges seven algorithm essays previously published on this site; the seven lessons cover how to choose a pathfinding algorithm, how a Snake AI survives inside a wall of its own making, why recursion deserves trust, how dynamic programming and union-find divide the labor, how order gets built and kept, what the skeleton of search looks like, and what each of game AI’s three weapons is for. All seven share one undertone: the choice of algorithm follows the scenario’s constraints.

Pathfinding: Optimality, Budget, and Readability

Pathfinding is the most everyday algorithm in games, and the field most easily taken hostage by the “learned A*, so everything is a nail” mindset. Textbooks line BFS, Dijkstra and A* up into one straight line of evolution, as if A* were always the terminus; in real game engineering all three show up often, and the choice depends on three constraints of the scenario: whether an optimal path is required, how many microseconds the budget holds, and whether the target is one point or a crowd. The site happens to have three widgets that each act out one of those constraints: the solver in Maze wants the shortest path, the ghosts in Pac-Man want to “look smart”, and Tower Defense simply nails the path down and makes the pathfinding problem disappear. Alongside the embedded ant-pathfinding demo, where every step of the search is visible frame by frame, this chapter settles the ledger for the three scenarios separately.

Three Generations of Algorithms, One Ledger

Nail down the division of labor first. A grid map is a graph by nature: cells are nodes, adjacent corridors are edges.

With all edge weights equal (one step is one step), the three generations relate as follows.

BFS (breadth-first): expand outward ring by ring, and the depth at which it first touches the goal is the shortest step count. It is a special-purpose shortest-path solution, optimal only when all edge weights are equal. It wins on ten lines of code, no parameters, absolute stability.

Dijkstra: BFS generalised to weights, with a priority queue that pops the node of least accumulated cost each time. Optimal under non-negative weights. The flaw is that it spreads in every direction without discrimination: the goal may be due east and it still floods half the map westward.

A*: Dijkstra plus an intuition. Give each node a lower bound $h(n)$ on “how far is left to the goal”, and sort the queue by $f(n) = g(n) + h(n)$ ($g$ being the cost already paid). As long as $h$ never overestimates the true remaining distance (admissibility), the path at the first pop of the goal is still guaranteed shortest.

The priority queue hides one more engineering trap worth naming.

Every round, Dijkstra/A* has to “update the cost of a node already in the queue” (a shorter $g$ was found). The textbook writes this as a decrease-key operation, which demands an indexed heap. Real implementations more often use lazy deletion: leave the old entry, push the new one, and discard stale entries on pop.

The latter is shorter code with smaller constants, at the cost of redundant entries piling up in the queue. Grid pathfinding almost always takes the latter. The choice has nothing to do with correctness; it is purely a cost trade-off between two ways of holding a heap. But get it wrong (no staleness check on pop) and the search returns phantom paths — another major source of pathfinding bugs.

Why A* saves work fits in one sentence: the heuristic turns the priority queue into “Dijkstra aimed at the goal”. Nodes far from the goal get their priority raised by $h$ and sink, and the expanding frontier drives at the target in a cone.

But note the boundary of that guarantee: optimality holds only if $h$ never overestimates.

Manhattan distance ($|x_1-x_2| + |y_1-y_2|$) is the best-known admissible heuristic for four-directional movement: each step reduces it by at most 1, so the true remaining step count can never be less.

Switch to eight-directional movement and you need Chebyshev distance, or an eight-way distance with diagonal weights. Switch to a movement model where a unit can dash in a straight line, and only then does Euclidean distance stop overestimating.

Pick a heuristic that mismatches the movement model and A* quietly starts returning suboptimal paths. And usually nobody notices.

The grid model has one more trap that only shows in eight directions: corner cutting.

The diagonal gap between two wall cells placed corner to corner does not exist in a four-directional model, yet an eight-directional unit squeezes through it diagonally. Weird routes — hugging walls, slipping through seams — all start here.

The fix is a legality check on diagonal moves: of the two adjacent orthogonal cells, at least one must be walkable (the stricter version demands both).

Rules like this live in the geometry of the grid model itself. Which is why nine out of ten pathfinding bugs are not in the algorithm layer but in “how the graph is built”.

Maze

A maze is a closed loop by nature: it sets the puzzle and solves it too.

The most common way to generate a maze is recursive backtracking: start from the origin, pick an unvisited neighbor at random, knock through the wall between them, and step over. When all four sides are visited, back up to the previous junction.

That is a randomised DFS in essence, and what it leaves behind after covering the graph has an exact graph-theoretic identity: a spanning tree.

Hang the name “perfect maze” on that tree and it means two properties: exactly one path between any two points, and no cycle anywhere in the maze.

Those two properties decide how the solving side behaves.

First: since the path between any two points is unique, “the shortest path” is “that one path”. BFS, A*, even DFS with no optimality ambition, all hand back the same route in the end. The difference lies entirely in how they find it.

DFS runs down a single corridor, backtracks in whole sheets, visits little but twists. BFS floods in rings from the start, often covering half the map. A* sits between them, led by the heuristic in a cone toward the goal.

The solver in Maze makes all three switchable options and replays the visit order cell by cell. Run one maze three times and the difference in expanded area is obvious at a glance.

Second: “unique path” is a dirty word where player experience is concerned. A maze full of dead ends tests memory.

So many generators remove a few interior walls at random afterwards, manufacturing loops by hand. Every wall removed adds an edge to the spanning tree, hence a cycle, and the choice space for the player (and any pursuer) grows with it.

This two-stage recipe — “generate a perfect maze, then punch loops” — is the standard formulation for maze-like content.

More Than One Generation Algorithm

“Random spanning tree” leaves room for more than one kind of randomness, and each kind gives the maze a completely different temperament.

Recursive backtracking is randomised depth-first, and the tree is one long vine of varying depth. Long corridors, deep dead ends, and a high rate of “walked the whole way only to find it is a dead end”.

Randomised Prim is randomised breadth expansion, and the tree comes out squat. Dense junctions, shallow dead ends; plenty of choice, and no single wrong turn is fatal.

Divide and conquer cuts the map into blocks, generates each, then joins them; the structure is tidy but it feels the most human-designed.

In spanning-tree language, the three are the same skeleton with different growth biases. None is absolutely better; which to pick depends on who receives the maze. Puzzle players want the frustration of deep dead ends, chase games (the subject of the next section) want the escape options that loops provide.

Choosing a generation algorithm is, at bottom, picking a tree of the right shape for the gameplay downstream.

A Small Engineering Ledger for Wall Models

A note on representation, while we are here. Maze cells are commonly stored two ways: four booleans per cell (walls up, right, down, left), or an “odd-even grid” that gives walls cells of their own.

The former is intuitive and easy to edit. The latter turns “knocking through a wall” into “changing one character”, and the code gets shorter.

The Maze here uses the former, because the solving animation draws wall lines per face and the four booleans map straight onto four segments. Pac-Man uses the latter, because its maze is nothing but a lookup table for move legality.

Same algorithm, representation following the downstream need.

Pac-Man Ghosts

Pac-Man’s ghosts are often the first memory people have of “game AI”. But take apart the Pac-Man implementation here and the answer is very honest: the ghosts never compute a shortest path.

Each ghost moves one step every other tick (deliberately slower than the player), and its choice is a fifty-fifty split. Half the time it picks a legal direction at random; the other half it picks the direction that minimises Manhattan distance to the player. A one-step greedy, with not even two-step lookahead.

Why so crude? Because the three real constraints on pathfinding in a real-time chase all argue against exact algorithms.

Budget. A 16 ms frame has to draw, run physics and decide for four ghosts, leaving a budget per ghost measured in microseconds. A Manhattan greedy is a zero-cost query; A* is an expense. The cycles saved are worth more elsewhere.

Motion continuity. A pathfinding algorithm outputs a route, while a ghost has a current heading, and most Pac-Man rules forbid reversing on the spot. However perfect the route, folding in the heading constraint means re-sorting it at a discount. A one-step greedy is compatible with heading by construction.

Readability. This is the most counter-intuitive and the most important: an opponent that is too smart kills the game. If all four ghosts encircled with perfect A* from four directions, the player would be surrounded at the second junction and the round would end in thirty seconds. Random perturbation walks a ghost into a dead end now and then, and only then is there the thrill of “I fooled it”. Difficulty design is, at bottom, injecting exactly the right amount of defect into the AI.

The loop generation from earlier shows its second purpose here. In a perfect maze (no cycles) with sparse four-way junctions, a purely greedy ghost can still corner the player in a single corridor. It is the loops the generator punched by removing walls that save the player’s life.

What looks like “game balance” at the algorithm level is often one line in the map generator.

Many Targets, One Computation

Suppose one day you do give every ghost a shortest path; you still should not run A* once per ghost.

The real structure of a chase is that all the ghosts share one target point.

Run BFS (or Dijkstra) once from the player’s cell and write a “distance to the player” field over the whole map. Afterwards any unit anywhere looks up the table and knows which way is closer to the player. One computation, shared by everyone.

This flow-field pathfinding is the standard answer for large unit counts in tower defense and RTS. It flips the viewpoint from “every unit finds a path” to “every cell records a flow direction”.

Even if the ghosts never implement it, the flip is worth understanding. The first cut in optimizing multi-target pathfinding always lands on “there is really only one target”.

A* Visualization

With the abstractions done, the ledger is worth checking inside Shortest Path.

A 25×25 grid, roughly two-tenths random obstacles, start top left, goal bottom right. Click any cell to flip a wall on the spot, then watch the algorithm unfold as an animation: the pale visited region spreads first, and the yellow backtracked path lights up last.

The tool is drawn to A*‘s internal structure. Every node’s $g$, $h$ and $f$ are really computed, and the open list takes the minimal $f$ each round.

One implementation detail is worth a look too. The open list is a plain sorted array rather than a binary heap. On a grid of a few hundred nodes the sort cost is negligible; a heap is for maps with tens of thousands of nodes. The moment to upgrade a data structure follows the size of the problem, a judgment more important than knowing how to use a heap.

Three experiments in the visualizer beat three paragraphs of prose.

Block the road: draw a wall across the diagonal route the search just found and run it again. The visited region grows noticeably, because the heuristic is helpless about detours — $h$ only sees straight-line distance. That shows plainly why A*‘s advantage over Dijkstra shrinks on maps with more obstacles and more winding structure.

Swap start and goal: search from bottom right to top left and the animation looks almost identical. Manhattan distance is symmetric under coordinate flips. Switch to an asymmetric heuristic (an $h$ with a directional penalty, say) and it no longer holds — a common way to crash while debugging a heuristic.

Clear the field: wipe every obstacle and run again, and A* goes almost straight while the visited area approaches zero. On an obstacle-free map the heuristic is perfectly accurate. A*‘s cost is essentially spent on “how far the map deviates from the heuristic’s assumptions”: the more the map resembles what the heuristic imagines, the cheaper the search.

Weighted A*

Real-time scenarios have one more dial between A* and pure greed worth knowing: multiply $h$ by a factor greater than 1.

In $f = g + \varepsilon h$, the larger $\varepsilon$ is, the more say the heuristic has, the more the search resembles greed heading straight for the goal, and the smaller the expanded area. The price is a degraded optimality guarantee.

But the degradation has a floor: $\varepsilon$-weighted A* guarantees the returned path is no longer than $\varepsilon$ times the optimal.

The trade is extremely common in engineering. $\varepsilon = 2$ means “at most twice the length, for possibly an order of magnitude fewer cells visited” — a sure profit for game AI that does not care about a few extra steps.

It also strings the three generations into one continuous slider. $\varepsilon = 0$ is Dijkstra ($h$ does nothing), $\varepsilon = 1$ is A*, $\varepsilon \to \infty$ is pure greedy best-first search. Optimality versus speed is a knob you can turn.

Tower Defense

Tower Defense is the odd one out of the three: the enemies do no pathfinding at all.

The path is a string of waypoints the designer wrote in advance; a spawned enemy advances along that polyline by parameterised position — which segment, how far into it, linearly interpolated between frames, turning hard at the corners. Towers cannot be built on path cells, so the whole “graph” degenerates into one fixed corridor.

Is that laziness? Quite the opposite; it is the soberest of the three.

Tower defense’s core loop is “building a tower changes the battlefield”. If every tower triggered a full-map shortest-path recompute for all enemies, forget the cost — the gameplay would immediately run wild. Enemies wandering into dead ends, unpredictable routes cutting through kill zones: balance would be out of the question.

Nail the path down, and the designer has moved the pathfinding problem from runtime to design time. All the play happens in the static analysis of “how many towers on which stretch”. The only “search” left at runtime is targeting: each tower finds the nearest target inside its range circle. A local query of a few loops, needing no graph at all.

Fixed paths bring another algorithmic dividend that is easily overlooked: enemies become parameterisable as a whole.

Compute each segment’s length and cumulative mileage up front, and at any moment any enemy’s position is just a mapping from one scalar — distance travelled — to coordinates. Movement, ordering (who is in front) and hit detection (which mileage a bullet crosses) all degenerate into arithmetic on a one-dimensional mileage.

Targeting’s “nearest” often gets one refinement too: hit the enemy with the greatest mileage in range (the one furthest along) rather than the geometrically closest. That way every shot is spent on the likeliest escapee.

The same fixed path makes “pick a target”, which should be expensive, a matter of reading one number.

The opposite design exists too: let enemies ignore any fixed route, and recompute the whole map’s shortest path in real time on every tower built. The player’s goal shifts from “playing tower defense” to “using towers to herd the enemy into the fire”. That makes the shortest-path algorithm itself the object of play.

Neither design is superior, but the latter demonstrates one thing clearly: the choice of pathfinding algorithm often disguises itself as a gameplay-design question. Should the path be dynamic, who edits the map, how often. Answer those three and the BFS/Dijkstra/A* decision is nearly automatic.

The three tiers each have their own choice: maze solving is offline, single-target and optimality-hungry, with a small graph and an unlimited budget — pick A* for the beauty of the cone, or BFS for ten lines of code; the real-time chase is online, high-frequency and readability-hungry — one-step greed plus random perturbation, amortised with a flow field when many units chase one target; tower defense has a static path and gameplay first — make the path a constant and leave only parameterised movement and local targeting at runtime. In engineering the choice is decided by three dimensions: the optimality requirement, the time budget, and how often the graph changes — fix those three coordinates first and the algorithm floats up on its own. Beyond the tiers, one invisible principle runs through everything: correctness in pathfinding is the responsibility of “graph modeling”, not of “the search algorithm” — corner-cutting rules, stale queue entries, a heuristic mismatched to the movement model: the crash sites named here all sit in the graph or the queue. And there is a direct touchstone for whether an implementation thought these three things through: ask it “who recomputes when the target moves”. If the answer is “every unit”, it wants a flow field. If it is “nobody, the graph does not change”, it is tower defense. If it is “each unit itself”, better confirm the budget really is there.

Snake AI: Short-Sighted Greed and the Absolutely Safe Cycle

The graph pathfinding works on is dead; the Snake’s obstacle is alive, and of its own making — the snake grows one segment per food eaten, wide open at the start, inch by inch impossible at the end. Around “how to survive inside a self-made wall”, Snake AIs split into two sharply delineated schools: the food-chasing greed and the Hamiltonian cycle, where the former makes a decision on every move and the vast majority of the latter’s moves are execution. The site’s Snake is the arena for verifying both ideas first-hand, and Tron is the adversarial version of the same spatial intuition.

Why Snake is an AI litmus test

First, the evaluation criteria.

A Snake AI’s score is measured by two numbers: average length (or average score) and survival rate (run ten thousand games, count the deaths).

The trouble is that these two quantities naturally fight. A long-lived strategy must be conservative, and conservative means not eating distant food, so the length never climbs. Chase length and the death count climbs with it.

So “which AI is better” has no single answer; the verdict is always relative to a metric. That makes Snake an excellent teaching sample: it forces you to declare the goal before discussing the algorithm.

It also has two engineering advantages other games envy.

First, matches can be sped up without limit. Rendering can be switched off entirely and only logic frames run; ten thousand games take minutes on a laptop. The evaluation regime can therefore be made extremely strict, which is hard to do in real-time adversarial games.

Second, states can be reproduced perfectly. The only randomness is the food spawn point; fix the random seed and you get fully reproducible games, and any single death can be replayed frame by frame for attribution.

Cheap evaluation, easy attribution — with these two in place, Snake becomes the ideal racetrack for strategy iteration. You can clearly see the trace each change leaves on the death-cause distribution.

Structurally, three properties of Snake determine its strategy space.

The obstacles are dynamic. The body deforms every step: the tail leaves, the head enters. Shortest-path algorithms for static maps cannot be transplanted directly, because the answer to “can I walk this square” changes every frame.

The target exists forever. Food respawns after being eaten, and the game has no terminal condition other than death. The AI is thus optimizing an endless process, not a one-shot search.

State explosion, simple structure. The full state is “body sequence + food position”; exact solutions (dynamic programming, say) are infeasible at that state count. Practical AIs all trade off inside a hybrid of “local judgment + global insurance”.

One environmental variable is often ignored: the board size itself rewrites the effectiveness of strategies.

On a small board (10×10, say), the body soon claims a sizable share, “space” becomes the bottleneck before “distance” does, and safety checks pay off early. On a large board (30×30), greed can run rampant for a long time before self-encirclement, and the Hamiltonian school’s running time becomes unacceptably slow.

The same algorithm on a different board can flip the strength ranking. This is really the universal phenomenon of all game AIs: an algorithm’s strength depends on whether it fits its environment.

The short-sighted greed that chases food

The first version of the AI takes ten lines. Every step, head toward the food; if that direction hits a wall or the body, pick a direction that doesn’t.

It plays, and it dies in three highly fixed ways.

It is worth giving this version its due first. It already has a safety floor: the “don’t crash” check means it never commits immediate suicide, which sets it fundamentally apart from the zeroth-order strategy of “head at the food, period”.

The real algorithmic step from zeroth order to first order is bigger than the step from first to second (adding safety checks). All three deaths are structural problems that detonate only many steps later, not tactical blunders that crash on the spot.

That observation points straight at the improvement: a mechanism that looks ahead more than one step.

Death one: self-encirclement.

Greed always picks the direction closer to the food, utterly indifferent to how much room to move it will have left afterwards.

The classic script: the snake chases food in circles hugging its own body, ring inside ring, until it suddenly finds a wall ahead of its head and three segments of its own body behind. Locally optimal on every step, locked shut in combination.

Death two: trap food.

Food spawns at the bottom of a U-shaped pocket; greed dives in headfirst, eats, then discovers the only exit is plugged by the body it just lengthened.

Food positions are random, so this kind of trap must occur eventually; the only variable is how long the snake is when it does.

Death three: severed route.

In the direction of the nearest straight-line distance, the road is cut in half by its own body, and the greedy detour happens to run into another body segment.

The longer the body, the bigger the gap between “Manhattan distance” and “actually reachable distance”. The greedy AI’s IQ decays with body length.

The fix

The fix for all three deaths is one idea: before each move, confirm you are still alive after taking it.

It comes in two layers.

Layer one is the tail-chasing check.

After this move, can the snake still catch its own tail?

Reaching the tail is nearly equivalent to “there is still a looping way out”. The tail is a square guaranteed to move aside (as long as no food is eaten), the only “quasi-safe zone” among dynamic obstacles. This check intercepts most of death one in advance.

The implementation treats “chasing the tail” as one shortest-path search. The target square is the tail tip, the obstacles are the body (the tail tip itself counts as enterable); if the search finds a path, clear to go.

One detail deserves attention: the safety check must cover both branches, “eat” and “don’t eat”. If stepping toward the food is safe, go. If not, rather circle in place waiting for the tail to open up room than eat.

A snake doesn’t fear hunger; it fears gorging itself to death. Set that priority right and the greedy AI’s death rate immediately halves.

Layer two is space counting.

Flood fill from the snake head, count the reachable empty squares after this move, and compare with the snake’s length.

If the reachable space is smaller than the body length, part of the body has wedged itself dead inside the available space. However close this move is, it cannot be taken.

Both checks cost a few small searches, but the grid has only a few hundred squares and a flood fill is microsecond-level. Safety is bought with search.

A third road

Beyond the two schools there is a compromise engineering route: no binary safety verdict, but a weighted sum of several metrics.

Score each candidate direction on several counts — distance to food (negative contribution), reachable space after the move (positive), margin from the walls, tail reachability — combine them linearly into a total, and take the highest.

It has more global vision than pure greed and more flexibility than the Hamiltonians, in a few dozen lines.

The price is that the weights need tuning, and weight tuning is famously mystical. One point more on food weight and it charges into a dead end; one point more on space weight and it circles forever without eating.

In practice it usually serves as the “medium difficulty” tier. More respectable than naked greed, cheaper than full safety search, it exactly fills the gap between the two schools.

The extreme form of short-sighted greed has its prototype in Tron: both sides ride light cycles drawing walls, and touching any trail means death.

Its AI filters out only the “immediately fatal” directions each step, then drives straight on vibes with an occasional turn. Not one extra layer of lookahead.

That you can beat it easily is precisely the demonstration of how insufficient one-layer filtering is in adversarial settings. The opponent will exploit the space traps your short-sightedness leaves behind.

It is also a natural exam room for testing greedy improvements. Port the tail-chasing check and space counting over and it instantly becomes a respectable opponent. Get serious and add “compare both sides’ reachable space after this move” as an adversarial score, and you are already at the doorstep of the Tron strategy at the end of this chapter.

The absolute safety of the Hamiltonian cycle

The second school simply swaps the problem: instead of deciding every step, first construct a cycle through every square on the grid and have the snake follow it forever.

That cycle is graph theory’s Hamiltonian cycle: a loop through every vertex exactly once.

As the head advances along the cycle, the squares behind it vacate one by one in cycle order, and the way ahead is always clear. Mathematically guaranteed never to hit a wall, never to bite itself; food is merely a matter of passing by.

On rectangular grids with an even number of sides, Hamiltonian cycles are easy to construct. The plainest is the serpentine: first row left to right, second row right to left, folding back and forth until the last two columns, where one vertical corridor connects back to the start and strings all rows into a ring.

Once constructed, the AI’s “decision-making” degenerates to zero: each step moves one square along the cycle.

The cost is equally plain: slow.

If food spawns a hundred squares “downstream” on the cycle, this snake dutifully travels those hundred squares to eat it. At the serpentine cycle’s rhythm, filling a 20×20 board takes hundreds to over a thousand steps, and the whole run watches like an ox turning a millstone.

Maximum safety is bought with efficiency. This is the two schools’ fundamental trade-off: greed has a high expected length and high variance (it dies); the Hamiltonian has a 100% survival rate and a pitiable expected time.

Run ten thousand games and the greedy AI might average forty or fifty in length with occasional sudden deaths. The Hamiltonian AI fills the board every game, but not one of its games is quick.

Cycle + shortcuts

Practical top-tier Snake AIs are almost all hybrids of the two schools: follow the cycle normally, but allow shortcuts.

The rule is ingenious and simple. Number the cycle’s squares 0 to n−1; the head sits at number h, the tail at number t. If a step can “jump” off-cycle to a square with a larger number, and the number jumped to does not exceed the tail’s number, the shortcut is allowed.

Because the cycle order guarantees those skipped squares are all still empty right now — they sit in the “future” segment between head and tail.

Shortcuts cut the average time by an order of magnitude while keeping the absolute-safety frame; in dangerous situations (space tight), tighten the shortcut conditions, fall back to pure cycle mode, and safety is instantly restored.

This “framework as floor, opportunity as speedup” structure beats either pure school. It is also the general shape of many engineering decisions: use an invariant to guarantee the lower bound, and do your greedy inside the invariant’s slack.

The Hamiltonian cycle is that invariant. As long as you never leave it, death is logically excluded. All the freedom of shortcuts is constrained inside what the invariant permits.

How to draw the cycle

The construction itself deserves a short section, because it hides a pit every beginner steps in.

Anyone can draw the serpentine fold — first row left to right, second row right to left. The hard part is joining the two ends of this snake back together without breaking “each square once”.

For a grid of even height, the standard drawing reserves the last column as a dedicated corridor. All preceding rows serpentine within the first n−1 columns; after reaching the bottom left, run up the last column, exactly stringing the corridor squares together and closing back at the top-right start.

Two constraints must hold at once. The total square count is even (the cycle’s length must be even, or the ends misalign in color when joined — the grid graph’s two-coloring tripping you). And the corridor column is reserved separately (mixing it into the serpentine region causes self-intersection).

Grids of odd height are fussier, requiring an extra two-square corridor patched onto the bottom or side as a remedy.

This little construction is a good example: in graph theory, “a Hamiltonian cycle exists” is one thing; drawing one is another. The latter is engineering.

Comparing the schools

Since the two metrics naturally fight, comparing strategies requires designing the exam well, or “which AI is stronger” degenerates into a dispute over impressions.

The exam has three elements: batch runs (hundreds to thousands of games, so the randomness of food gets averaged out), quantiles (report median length, not mean — death is a heavy-tailed event, and a few super-long survivals can distort the mean beyond recognition), and death-cause classification (wall crashes, self-bites, space lockouts, and head-on collisions counted separately; the death-cause distribution carries far more information than total mortality, and it tells you which death your next improvement should target).

Run this exam and the two schools’ portraits usually read like this. The Hamiltonian school’s median length approaches a full board, zero deaths, frighteningly slow. Safe greed is an order of magnitude faster on average, with occasional sudden deaths in the long tail.

Define the exam first, then debate the rankings. This holds for all game AIs, and it is only especially glaring in Snake, because its two metrics are directly mutually exclusive.

Seeing the snake board through A*‘s eyes

Both schools can use A*, just in different ways.

In the greedy school’s improved version, A* computes “the real shortest path around the body”. Body as obstacles, food as goal — many fewer deaths than Manhattan greed. The Hamiltonian school’s shortcut judgment also needs a reachability search as a backstop.

The body as an obstacle has one dynamic property worth exploiting: the snake vacates one square every step (the tail leaves). Strictly speaking the obstacle carries a time dimension; “that body segment” may already be gone by step k.

Simplified implementations treat the tail square as passable, or do a time expansion by “will it have moved aside by the time I arrive”. For the exact version, layer each square by time and multiply the complexity by a time axis. That is also the generic modeling for many “dynamic-obstacle pathfinding” problems.

If basic search expansion is unfamiliar, go draw a few walls and run a few searches in Shortest Path; far more comfortable than debugging directly on the snake board. The 25×25 static grid has no real-time pressure, and every expansion step is fully visible.

The site’s Snake also provides environmental variables for testing strategies.

Classic mode suits observing the greedy strategy’s death-cause distribution. Run it long enough and the death scripts turn out highly repetitive.

In race mode the speed keeps climbing with each meal, further compressing the error margin of short-sighted decisions and magnifying the value of safety checks.

The two-snake versus mode adds food competition and head-on collisions. Pure greed will charge headfirst into the opponent’s body for food, and at that point “space counting” turns from insurance into a weapon. Deliberately laying your body between the opponent and the food is setting a trap in reverse with the same algorithm.

From Snake to Tron

Finally, pull the lens back to Tron, the purified thought experiment of Snake. Remove food and growth, keep only “draw walls, don’t die, wall in the opponent”.

In this pure adversarial version, the two schools merge into one core judgment: whoever holds more reachable space wins.

Both sides start with equal space, and every move’s value can be scored as “my reachable squares after the move − the opponent’s”. Once one side seals itself into a small compartment, defeat is a countdown.

This move is called territory comparison, Tron AI’s standard opening. Its core is exactly that flood-fill count from Snake’s improved version, only upgraded from “life-saving insurance” to “offensive weapon”.

Two further details come in actual play.

First, territory comparison holds only while both regions are still connected. Once walls fully separate the two sides, the match becomes two independent “survival-length contests”, and the goal switches from suppressing the opponent to maximizing your own survival steps.

Second, the advantaged side should hand complexity to the opponent. Deliberately play the moves that shatter the board, forcing the opponent to err first on the fragmented remainder.

Create chaos when ahead, seek simplification when behind — the old rule of adversarial play executes most nakedly in pure spatial games.

Two AIs, one duel — both land on the same question in the end: in a constraint space that keeps tightening, how much are aggressive gains and conservative guarantees each worth. The fastest way to test your own judgment of these two strategies is to leave the site’s two boards idling for an hour each: watch the greedy snake’s death-cause distribution, watch the Tron AI’s straight-line rate. In this class of games the resource that decides the outcome is always space.

Tower of Hanoi: The Leap of Trust, the Lower Bound, and the Gray Code

Back from adversaries to foundations. Almost every algorithms course opens its recursion examples with the Tower of Hanoi; the choice looks hackneyed and is in fact carefully picked: the recursive solution is three lines long, and those three lines hold every checkpoint of recursive thinking — how do you shrink the problem, when dare you stop, on what grounds do you trust the jump that says “assume the subproblem is already solved”. Three pegs of a Tower of Hanoi are enough to turn recursion from a matter of faith into engineering you can check by hand.

The three questions

Three questions before writing any recursion; this is the fixed checklist of all recursive design.

What is the base case? How is the subproblem smaller than the original? How do the subproblem’s answers assemble into the answer for the original?

Answer the three and recursion is mysticism no longer; answer them and the code is mere translation.

Hanoi’s three answers fit together without a gap.

Task definition: move n disks from the source peg to the target peg, using a buffer peg, with a larger disk never resting on a smaller one.

Base case: n = 1, move it directly.

Shrink: the n-disk problem splits into “first get the top n−1 disks out of the way”. A Tower of Hanoi with n−1 disks is the same problem at a smaller size.

Assemble: three steps.

1
function hanoi(n, from, to, via):
2
    if n == 1: move disk 1 from → to; return
3
    hanoi(n-1, from, via, to)     # clear the top n-1 disks onto the buffer peg
4
    move disk n from → to          # the largest disk is now free
5
    hanoi(n-1, via, to, from)     # then stack the n-1 disks back on top

Note the confidence in the second step: once all n−1 disks sit on the buffer peg, the largest disk may legally move to any peg.

The key to the whole problem hides in that observation. “The largest disk is always free” is premised on “every disk smaller than it may well not be on the target peg”.

The three questions land one by one here: the base case is a trivial move, the shrink is “handle the top n−1”, the assembly is “clear, drop, restack”.

Beginners’ two classic bugs aim at exactly the three questions, and are worth naming in advance.

First, stuffing “move disk n” into the subproblem. Written as move the largest first, then recurse, ignoring the n−1 disks still stacked on it. That is the shrink question answered wrong: the precondition of the recursive call (the largest disk exposed) does not hold at call time.

Second, passing the arguments in the wrong order. The four positions of hanoi(n-1, from, via, to) and hanoi(n-1, via, to, from) are extremely easy to copy wrong. Once source, target and buffer get mixed up, the program runs happily and every single move is illegal.

The two bugs share one cause: the arguments of a recursion are pure semantics, so permute the positions and one wrong bit makes everything wrong. Writing each parameter’s meaning into a comment is cheaper insurance than any debugging trick.

The leap of trust

Three lines of code written, and the real difficulty begins: do you dare believe it correct without looking inside.

The biggest obstacle to learning recursion is the instinct to unroll and trace. hanoi(3) enters hanoi(2), which enters hanoi(1). Three levels and it is mush, five levels and you are lost.

And the whole trick of recursive thinking is precisely to refuse to unroll. Writing hanoi(n), assume hanoi(n−1) is a black box that does its job correctly the moment you call it. Your only jobs are arranging when to call it, with what arguments, and what to do once it returns.

This leap of trust is no psychological comfort; it has an exact counterpart: mathematical induction.

To prove the recursive solution correct you prove two things. Correct at n = 1 (the base case). If correct at n−1, correct at n (the inductive step).

The “if correct at n−1” in the second is the leap of trust in formal dress.

Induction is legitimate because base case plus transitivity automatically covers every n. Recursion is correct because the base case plus self-consistent calls automatically covers every depth.

Recursion is induction made executable. The reverse reading is the more practical one: any structure you can induct over can almost certainly be written as recursion. Conversely, a recursion that leaves you unable to finish the inductive step probably does have a bug.

The leap of trust has a commonly ignored by-product: it settles your relationship with the debugger.

When recursive code breaks, stepping into the third level already violates the trust principle. The right debugging posture is to check two things first: whether the base case can be missed (infinite recursion), and whether the subproblem’s arguments really do shrink while keeping their meaning (a bad shrink).

The overwhelming majority of recursion bugs live in those two places, not in any particular unrolling.

If you absolutely must watch it run, there is a crude trick far more efficient than single-stepping: print with indentation by depth. Print one log line indented by two spaces on entry to each level, and the output immediately takes on the shape of the whole call tree, the layer and branch housing the problem visible at a glance.

The trick works for any recursion in any language, and costs two lines.

2^n − 1

Counting moves is the natural next step.

Let T(n) be the minimum number of moves to shift n disks; the recursive solution gives the equation:

Two shifts of n−1 disks and one move of the largest. Expand term by term (or subtract 1 on both sides and substitute $S(n) = T(n) + 1$) and $T(n) = 2^n - 1$ falls straight out.

This is where the accounting usually stops, but the question actually worth asking next is: is this “our solution needs this many moves”, or “the problem needs this many moves”?

The two are worlds apart. The first is one algorithm’s bill, the second is the problem’s lower bound.

The lower-bound proof is, neatly, another induction, run in the other direction.

To move the largest disk n from source to target, at that moment the n−1 disks above it must all be stacked on the buffer peg. If even one still rests on disk n, n cannot move. If the n−1 disks are scattered across source and target, the top of the target is not empty either.

And gathering n−1 disks onto the buffer peg takes at least $2^{n-1} - 1$ moves by the inductive hypothesis. After disk n moves, those n−1 disks must all come from the buffer onto the target, another $2^{n-1} - 1$ moves at least. Add the single move of disk n itself:

Lower and upper bound close at $2^n - 1$. The recursive solution is optimal, not one move to spare.

This convergence, where the recurrence’s solution is also the lower bound, is the prettiest ending in algorithm analysis. The whole proof uses no internal structure of any algorithm, only the rule “what must hold before the largest disk moves”.

While we are here, settle the number from the legend: 64 disks give $2^{64} - 1 \approx 1.8 \times 10^{19}$, and even at one disk per second that is over five hundred billion years. The Indian legend about the world ending is essentially exponential violence demonstrated with astronomical numbers.

Loosen the rules and the analysis is tested at once.

Add a fourth peg to the Tower of Hanoi and the same lower-bound derivation collapses. n−2 disks can be split across two buffer pegs, so the premise “all of them must be stacked on one peg” no longer holds.

The optimal move count for the four-peg Tower comes from the Frame–Stewart algorithm. Move $k$ disks to one buffer peg (recursing under the four-peg rules), shift the remaining n−k disks onto the target under the three-peg restriction, then bring the k disks home with four pegs, with k chosen to minimise the total.

Its growth is pressed down to roughly $2^{\Theta(\sqrt{n})}$. The exponent of the exponent has been square-rooted, and optimality in the four-peg case was later proved rigorously.

The contrast between three and four pegs demonstrates “the lower bound follows the constraints” cleanly: a proof is not a template laid over an algorithm, it is a corollary read out of the rules.

There is one more strengthening that is rarely mentioned. Not only is Hanoi’s optimal move count determined; starting from any legal position, the optimal solution is unique as well.

On the shortest path from any legal state to the goal, at any moment at most one legal move wastes no steps.

The skeleton of the proof is the same as the lower bound’s. In any position, look at the smallest disk and the rest separately: the non-smallest disks admit at most one legal move (between two disk tops only “smaller onto larger” is legal, and among three peg tops the legal destination is unique). And if the smallest disk departs from the Gray code rhythm, the next step necessarily pays one move of backtracking. Any deviation costs at least a step within two moves, so the optimal track has no forks.

That uniqueness makes Hanoi a perfect teaching prop: any wrong step a student takes is a definite departure from the optimal track, with no “all roads lead to Rome” to hide a misunderstanding.

Solvable without recursion

Beyond the recursive solution there is a fully iterative one, with rules short enough to memorise.

The smallest disk (disk 1) moves every other step, in a direction fixed by the parity of n. For odd n it cycles toward the target peg forever; for even n, the other way.

On every other step, the only legal non-smallest move is the correct move. A legal move not involving the smallest disk is at most one per position (if both disk tops allowed it they would fight each other; in practice only smaller-onto-larger is legal).

Loop “move the smallest disk → make the one legal move” until finished, with no recursion and no stack anywhere.

Why is “the only legal move” so certain?

At any moment at most three peg tops are exposed, so candidate moves involving non-smallest disks number at most three pairs. Every “larger onto smaller” direction is illegal. Half of the remaining legal destinations would bury the smallest disk or have just been vacated by it. Rule them out one by one and exactly one is left.

This “unique move per step” property hands Hanoi a curious by-product: it is one of the very few puzzles you cannot get wrong with your eyes closed. Obey the two rules and error becomes hard to commit; all the difficulty is patience for the $2^n - 1$ steps.

The automatic demo on the site’s Tower of Hanoi pre-generates the entire move sequence from exactly this kind of rule and replays it frame by frame. With the speed control you can watch the smallest disk’s pendulum rhythm. It changes peg every other step, never rests, and the regularity can be confirmed with the naked eye.

The iterative rule is no coincidence; behind it is a strict bijection: every step of the Tower of Hanoi corresponds to one more step of the n-bit Gray code.

The Gray code (adjacent codewords differ in exactly one bit) is generated by “bit i flips every $2^i$ steps”. The smallest disk (disk 1) moves every two steps, disk 2 every four, disk 3 every eight, strictly isomorphic to the bit-flip rhythm of the Gray code.

Check the full seven moves for three disks against the table: the sequence is 1, 2, 1, 3, 1, 2, 1. Which disk moves at step k equals the position of the lowest set bit in the binary of k. k=1 (001) moves disk 1, k=2 (010) moves disk 2, k=3 (011) moves disk 1, k=4 (100) moves disk 3, up to k=7 (111) moving disk 1 to finish.

Further, “which disk is on which peg” at any moment can be read straight off the binary representation of the current step count, and the reverse holds too.

Hanoi thus gains a second identity: it is a physical model of the Gray code, much as a mechanical version of a binary counter.

Why does a zero-recursion solution exist? The recursive solution’s call tree is deterministic, and flattening it onto a single time axis naturally shows periodic structure. Beneath the recursive appearance sits the substance of a counting process.

The cost of recursion

Beyond trust you have to count the money.

A recursion’s runtime cost sits in two ledgers: time (number of calls) and space (call-stack depth).

Hanoi’s call count is also exactly $2^n - 1$, in one-to-one correspondence with the moves. The stack depth, though, is only n. Each level’s frame is released as it returns, and the deepest moment is “from hanoi(n) all the way down to hanoi(1)”, n frames.

Compare the two shapes of recursion. Linear recursion like factorial, which “returns and is done”, can be tail-call optimized down to O(1) stack. Hanoi is tree-shaped recursion, “two calls sandwiching one move”, with the move blocking between the calls, so tail-call optimization has nowhere to start.

To get rid of the stack you must turn the call tree into an explicit data structure by hand (a queue or a stack), and the code that comes out is the manual edition of the iterative rule in the previous section.

Which explains an engineering phenomenon: why Hanoi’s iterative solution is not the mechanical product of “recursion converted to a loop” but an independently discovered law. Tree recursion has no free flattening; the price of flattening is seeing through the Gray code first.

The stack-depth ledger also answers a common worry: can Hanoi recursion overflow the stack?

n=64 means 64 frames. Depth was never the problem; $2^{64}$ moves of time is.

Keeping “depth” and “count” apart as two dimensions is the first step in judging any recursive algorithm.

Transferring the three questions

The three-question template is worth carrying elsewhere and testing right away.

Tree traversal: base case, the empty tree; shrink, “from a tree to its left and right subtrees”; assemble, “the root’s position decides pre/in/post order”. Answer the three and the code for six traversals grows by itself.

Quicksort: base case, length ≤ 1; shrink, “split in two around the pivot”; assemble, “left half + pivot + right half” joined in place. Note that its assembly happens after the recursion (process first, join before returning), while Hanoi’s move sits between two calls. That ordering difference is the shape difference between “process after dividing” and “process while dividing”.

Fractals like the Sierpinski triangle: base case, the scaling limit; shrink, “take three smaller copies of yourself”; assemble, geometric translation.

All three examples share one meta-rule with Hanoi: a recursive function answers only for its own level, and every relation between levels is pressed into the arguments.

Once the argument semantics go fuzzy (“which peg are these n−1 disks on right now”), the leap of trust cannot be made. Hanoi’s three-parameter signature (n, from, to, via) is the classic textbook form precisely because every parameter is pure positional semantics, with not one bit of hidden state.

Recursion and DP

Hanoi explains recursion thoroughly and stands exactly outside DP’s door. This counterexample explains what DP is better than ten positive ones.

Dynamic programming needs two conditions. Optimal substructure: the optimum of the big problem is assembled from the optima of subproblems. Overlapping subproblems: the same subproblems recur as the recursion unrolls, so a cache pays.

Hanoi has only the first. hanoi(n−1, from, via, to) appears exactly once in the whole call tree, with no repeated subproblem anywhere, so memoisation saves not one line.

Its $2^n$ time complexity is not an inefficient implementation; the solution itself is $2^n$ long. The output is exponentially long, and no algorithm escapes that.

Problems whose complexity is pinned by their output length draw a clear line against the problems a DP table can fold (the repeated subproblems of interval DP and connectivity DP in the Dynamic Programming and Union-Find chapter, say).

By the same token, the question “can Hanoi be sped up with DP” has an exact answer. Not the solution itself, but queries like “how many moves remain from this position” can be preprocessed. Compute the move table for all $3^n$ positions and look up in O(1), at the cost of exponential space.

In the contract of trading space for time, exponential space is usually the breach clause.

The kinship between the two lies in the conversion trick: top-down recursion and bottom-up table filling are two traversal orders of the same computation.

DP folds the exponential into a polynomial not by “turning recursion into a loop” but because overlapping subproblems make the cache hit.

The hands-on test of whether a recursion can become DP is minimal. Write down all the call arguments and count the duplicates. If there are some, go to the DP Algorithm Visualizer and find the matching table shape (knapsack, LCS, LIS, coin change, interval, digit, bitmask, memoisation — eight common table shapes cover the DP spectrum from beginner to advanced). If there are none, let the recursion run naked like Hanoi’s: it is already optimal.

The account can be cross-checked from the state-space side too.

Hanoi has $3^n$ legal positions in total (each disk picks a peg independently), while the optimal solution takes only $2^n - 1$ steps. The number of states visited is far below the number of states.

The recursive solution walking the Gray code track without ever turning back means it lives natively on the one-dimensional parameter “step k from the start”, not in the $3^n$-dimensional space of positions.

What DP needs is exactly an overlapping structure keyed by position (the subproblem arguments). Every node of Hanoi’s call tree appears once, so “a cache keyed by position” has nothing to work with.

Measuring “how big the problem space is” separately from “how long the solution path is” is the opening move for reading the complexity of any recursive algorithm.

Hanoi leaves three conclusions for this lesson: recursive confidence comes from induction, cost is settled by the lower bound, and the way out depends on whether subproblems meet again. Three pegs and three rules lay out both the roads the craft can take (linear, exponential, tree decomposition) and the moment it should step aside (when overlapping subproblems appear). The next time recursion stalls, pose the problem as the three questions first — where does it stop, how does it shrink, how does it assemble — and the code is often half written.

Dynamic Programming and Union-Find: A Table and a Forest

The way out of recursion depends on whether subproblems meet again. When they do, there is dynamic programming (DP) — a thoroughly lazy idea: never compute twice what you have already computed, splitting a big problem into small ones you have already solved, folding “repeated computation over time” into a static table. But for problems whose structure itself evolves under operations, where sets keep merging, “fill a table” is not even applicable; those go to union-find, which in a few dozen lines props up minimum spanning trees, dynamic connectivity, and a whole swathe of problems, hanging “constantly merging relationships” onto a forest that keeps growing. This chapter takes each tool to the point where it is usable, then looks at how they cooperate on the same class of problems.

First Half: Dynamic Programming

Two Preconditions

A problem can be solved with DP only if two conditions hold, and neither can be missing:

• Overlapping subproblems: once the recursion unfolds, the same subproblem is hit again and again. This is the premise for “caching pays off”;
• Optimal substructure: the optimal solution of the big problem is assembled from the optimal solutions of smaller ones. This is the premise for “caching the optimal value is enough”. You only need to record each subproblem’s answer, not every path that led to it.

A counterexample helps: the longest simple path lacks optimal substructure (gluing two optimal paths together may form a cycle and stop being a legal path), so “longest path” has no naive DP, while “shortest path” does.

Whether the conditions hold has nothing to do with how the problem looks, and everything to do with its mathematical structure.

Three Stages of Fibonacci

Stage one: naive recursion, $O(2^n)$.

Expand fib(n) = fib(n-1) + fib(n-2) directly and fib(n-2) is computed twice, fib(n-3) three times… the same subproblem repeats explosively.

Draw the recursion tree and the overlap is plain.

Stage two: memoization, O(n).

Store what has been computed in a hash table and look it up on sight.

Three lines of code changed, exponential becomes linear. That is the dividend “overlapping subproblems” pays out.

The top-down form keeps the recursive intuition, which suits writing it out first to verify.

Stage three: tabulation + space compression, O(n) time and O(1) space.

Go bottom-up and fill the table in the reverse order of the recursion. Then observe that fib(n) depends only on the previous two terms, and the whole table collapses into two variables.

DP’s final form is usually “a table rolled up and compressed”. That compression trick is standard equipment in knapsack.

The three stages map out DP’s complete method: write the brute-force recursion → spot the overlap → add a cache → fill the table in reverse → compress away the unnecessary dimensions.

Every step is mechanical; there is no seat for inspiration.

0-1 Knapsack

n items each with weight w and value v, a knapsack of capacity W, each item taken or not — maximise the total value.

DP’s difficulty is never in the code but in the state definition. It has to answer, in one go, “what information is enough to decide the future”.

The correct state for knapsack:

dp[i][c] = the maximum value considering only the first i items, with capacity c left.

With the definition in hand, the transition is a binary choice over “take item i or not”, keeping the larger:

The first term is not taking (same as the row above); the second is taking (free wᵢ of space, trade in vᵢ of value).

The whole problem becomes an n×W table filled top to bottom, right to left, with the answer in the bottom-right corner.

The rolling array is the space magic here: row i depends only on row i−1, so the 2D table compresses to 1D.

But the inner loop must run backwards (from c = W down to wᵢ), otherwise dp[c − wᵢ] already holds a value “taken in this row”, which amounts to allowing one item to be taken twice (that turns it into complete knapsack. Flip the order and you have changed the problem; this detail is the most classic trap in the knapsack series).

Run the knapsack once in the DP Algorithm Visualizer, stare at each cell to see which two cells its value comes from, and the transition equation turns from a formula into an action.

Longest Increasing Subsequence

LIS (longest strictly increasing subsequence) is the best teaching material for 1D DP, because it has two solutions of wildly different complexity that exactly trace DP’s ability boundary.

The standard O(n²) DP: dp[i] = the length of the longest increasing subsequence ending at element i, with the transition dp[i] = max(dp[j] + 1) over every j < i where a[j] < a[i].

The “ending at i” qualifier in the state definition is the key. It gives the subproblem a definite interface, which is what lets big problems be assembled.

Greedy + binary search, O(n log n): maintain an array tails, where tails[k] = “the smallest tail element among increasing subsequences of length k+1”.

Scan the elements one by one, binary-searching for the position where each should replace or append.

tails stays sorted at all times, so the binary search is legal.

The crux: tails is not a DP table.

dp[i] means “the optimal solution ending at i”; tails[k] means “the smallest tail among all length-(k+1) candidates”. The latter mixes in global information and throws away the path of “which subsequence it actually was”.

The boundary this contrast draws is worth remembering: every cell of a DP table must answer its subproblem self-sufficiently.

Once a faster algorithm relies on a “globally mixed” intermediate, it has already stopped being DP. Faster, but harder to extend (when you need to print the solution or allow range updates, the O(n²) version is the easier one to adapt).

Coin Change

A famous detail of complete knapsack, worth a section of its own.

Problem one: “the minimum number of coins that make amount n”. A 1D table dp[c] = min(dp[c − coin] + 1), coins outer and amounts inner — the order does not matter, because min is immune to commutativity.

Problem two: “the number of combinations that make amount n” (1+2 and 2+1 count as the same), and loop order suddenly becomes life or death.

Coins in the outer loop gives combinations; amounts in the outer loop gives permutations.

The reason is in the fill order: with coins outer, the moment each coin type enters is “layered”, so 1+2 gets counted exactly once, while processing the 2. With amounts outer, every step may use any coin, so 1+2 and 2+1 get counted once each as two different paths.

The outer loop decides the degrees of freedom of state expansion, and that is precisely the shape of the problem statement.

This is the most exquisite lesson in the knapsack family, and the place where “copying the template without reading the order” crashes.

Working the whole family onward from 0-1 knapsack, the four variants differ only in “how many times each item may be taken”:

One and the same 1D table — the direction of the inner loop and the layering separate the four problems.

Which is why understanding “loop order is the problem statement” pays better than memorising four templates.

A Glimpse of Interval DP

Every table so far stages on “the first i items / row i”.

One more family stages on interval length: the answers for small intervals assemble the answer for a large one.

The classic is longest palindromic substring: dp[l][r] says whether s[l..r] is a palindrome, and the transition only looks at whether the two end characters match and whether the inner substring is a palindrome. Fill the table by increasing interval length.

Stone merging and “burst the balloons”-type problems belong to the same family.

Interval DP has O(n²) states and O(n) transitions — one dimension pricier than linear DP, but the skeleton does not change.

The table + transition + fill order trio applies as-is; only the “stage” is measured by a different quantity.

State-Machine DP

For one class of problems the state is not “progress” but the mode you are in.

The classic example is Best Time to Buy and Sell Stock (with a cooldown): each day you either hold shares or sit flat, and having sold yesterday you cannot buy today.

Set “holding / idle” as two states; the table’s two rows are the two modes, and the transition rules translate the trading rules straight into code:

1
holding[t] = max(holding[t-1],       # already holding since yesterday
2
                 idle[t-1] - price)  # bought today
3
idle[t] = max(idle[t-1],             # already idle since yesterday
4
              holding[t-1] + price)  # sold today

The cooldown simply adds a delay to the “sell → buy” edge (after selling you enter a “frozen” state for one day).

The point of this kind of DP is to translate constraints into the transition, not into a check.

Constraints in the transition make every cell legal by construction. Constraints left to runtime checks grow a pile of ifs in the code.

The signal phrase for “this is state-machine DP” is “while in state X you cannot / may only X”. When you see it, think state machine first.

Two Specially Shaped Tables

A table’s dimension is not always “the first i items”.

Tree DP hangs the table on tree nodes: dp[node][take/skip], with transitions flowing bottom-up through the subtrees.

The classics, minimum vertex cover and maximum independent set, are templates of “each node picks one of two, parent and child constrain each other”, and the fill order is simply post-order traversal.

A tree has no “linear stage”, but it has the equivalent “this subtree is finished”, so the no-aftereffect property holds all the same.

Bitmask DP encodes “what has been used” into the index: for the traveling salesman problem, dp[set of visited cities][current city], with the set expressed as the bits of an integer — n cities give 2ⁿ sets.

It moves “exponential states” out of the recursion’s call stack and into an explicit table; the complexity is still exponential (O(2ⁿ·n²)), but at n ≤ 20 it is entirely computable.

Which is why bitmask DP problems always pin the scale around 20.

When “n is small” and “combinations of take and skip” both show up, think bitmask.

The Debugging Trio

When DP code is “logically right but the answer is wrong”, troubleshoot in a fixed order:

1. Print the full table at a small scale. A scale like n=4, W=10 can be hand-computed in full; diff it cell by cell against the program’s output, and the row and column of the first deviation point straight at the wrong term in the transition;
2. Brute-force cross-check. Write a pure recursive brute force (no memoization) and compare it against the DP on random small inputs. The first input that disagrees is your minimal reproduction case;
3. The boundary three: empty input (0 items), zero capacity, all elements equal. Out-of-bounds i−1 and c−w in the transition, plus the initialization mistake between “must fill exactly” and “need not fill exactly” (a legal “unreachable” should be initialized to +∞, not 0) — nine tenths hide in these three places.

Top-Down or Bottom-Up

The two forms are equivalent; the trade-offs are practical:

• Memoization (top-down): easy to write, computes only the states it needs. When a large part of the state space is never touched (sparse states), you win it for free. The downsides are recursion-stack overhead and stack-overflow risk. In Python, functools.lru_cache is a ready-made memoization decorator, good for getting correctness running first;
• Tabulation (bottom-up): no recursion, compressible space, easy constant-factor tuning. The downside is computing states you never needed.

For interview whiteboarding, start from memoization (land correctness first); for production code, prefer tabulation (performance and memory under control).

Checklist: Can This Problem Be Solved with DP

1. It asks for an extremum, a count, or feasibility, not for the concrete plan itself (the plan can be backtracked at the end, but the objective has to be an aggregate);
2. Once the state is written down, the future is independent of the path (no aftereffect). Given dp[i][c], the next decision needs no knowledge of how c came about;
3. The total number of states is finite and not explosive. DP creates no complexity; it only compresses exponential repetition into polynomial, unique computation;
4. The transition covers every decision. Each choice can be derived from existing states.

Pass all four and DP basically holds.

When you are stuck on item 2, the usual fix is to add a dimension to the state that “carries the necessary history”.

Dimensions rise, legality comes back — routine surgery in state design.

Switching the Stage

The DP table carries an implicit premise: the state space is fixed before you start.

But for one class of problems the structure itself evolves with the operations. Edges arrive one by one, sets merge one into another, groupings drift with events.

“Fill a table” is not even applicable to it. Tables are prepared for static problems; dynamic relationships need a structure that maintains itself incrementally under operations.

Union-Find is that structure, and it happens to have its own three-stage evolution “from naive to nearly constant”, echoing DP’s method from across the room.

Second Half: Union-Find

Union-Find (Disjoint Set Union) props up Kruskal’s minimum spanning tree, dynamic connectivity, transitive closure, and a whole swathe of problems.

Its entire secret hides in two optimizations: union by rank and path compression.

If you want to watch the trees grow, the site’s Union-Find lets you step through it.

The Problem and the Naive Version

Union-Find maintains disjoint sets and supports two operations:

• find(x): which set x belongs to (returns the representative);
• union(x, y): merge the sets containing x and y.

The naive version raises one tree per set: each node stores a parent pointer, find climbs the parent pointers to the root, and union hangs one tree’s root under the other’s.

The trouble is that the direction of “hanging” is left to chance. If the big tree always ends up under the small one, chained merges degenerate the tree into a long chain, and find becomes an O(n) climb:

1
1 → 2 → 3 → 4 → 5   (every find has to walk from 1 to 5)

The two optimizations each attack one property of that chain: height and paths.

Optimization One: Union by Rank

Hanging is no longer left to chance: the short tree goes under the tall one (rank records an upper bound on height; “union by size”, using set size instead of rank, works similarly).

Why is the height O(log n)?

Induct: a tree of rank r contains at least $2^r$ nodes. Because a new root of rank r+1 only appears when two trees of rank strictly less than r merge.

Node count is at least exponential in height; inverted, height is O(log n).

This step presses find from O(n) down to O(log n).

Union-Find with union by rank alone already handles the vast majority of scenarios. But half the dividend is still unclaimed.

Two choice-level details to add.

First, pick either rank or size, not both; the asymptotics are identical. Union by size is more direct to implement (compare element counts at union time, the winner becomes the root, the sizes accumulate). Union by rank does not rely on “knowing the set size” (when elements carry weights and set sizes must be maintained separately, the rank semantics are cleaner).

Both are common in engineering; do not agonise.

Second, a seemingly contradictory fact: the two optimizations trade a property away between them. Once path compression is added, the tree’s actual shape gets ironed flat, the height information recorded in rank goes stale from then on, and union by rank degenerates into “union by historical rank”.

It remains correct (the proof only needs rank to be an upper bound), but this also explains why rollback union-find must give up path compression: undoing depends on “the merge history being replayable”, and path compression destroys the tree’s historical shape.

The competitive rollback version keeps only union by rank/size, O(log n) per operation, recording each merge’s changes on a stack and restoring them in reverse on rollback.

Far more useful than a “compressed but un-undoable” correct version.

Optimization Two: Path Compression

Path compression attacks “repeated climbing”: since find(x) has to reach the root anyway, on the way out, repoint every node along the path straight at the root.

The next find on those nodes is one step to the top:

1
Before:   1 → 2 → 3 → 4 → 5
2
After:    1 → 5
3
          2 → 5
4
          3 → 5
5
          4 → 5

Taken as a single operation, compression is a casual gesture. The beauty is its amortized effect once combined with union by rank.

With both in force, the amortized cost per operation is O(α(n)), where α is the inverse Ackermann function.

In practice the most common form is not even full compression but path halving: jump the current node to its grandparent, one line, same asymptotics:

1
find(x):
2
    while parent[x] != x:
3
        parent[x] = parent[parent[x]]   # path halving: jump to the grandparent
4
        x = parent[x]
5
    return x

Paired with a union-by-rank union, the whole data structure is a dozen-odd lines, no recursion, no stack-overflow risk.

The engineering confidence to treat it as a constant comes from exactly this simplicity.

What Kind of Monster Is α(n)

The Ackermann function A(m,n) grows too fast to be described by elementary functions; its inverse α(n) grows absurdly slowly.

For n ≤ $2^{65536}$ (a number far beyond the atom count of the universe), α(n) ≤ 4.

So in practice α(n) is a constant no greater than 4, and a single union-find operation is simply used as O(1).

The rigorous proof (Tarjan 1975 onward, with the final bound α(n)) is long, but the intuition fits in one sentence: path compression makes the cost of “climbing a long chain” paid only once, after which everyone who passes through goes straight to the root.

Union by rank guarantees long chains are hard to produce in the first place.

One optimization presses height, the other presses paths; together, the operation history keeps ironing the tree’s shape flat, and every node’s distance to the root becomes negligible.

Compression without rank, or rank without compression, never reaches α(n).

The former is still O(log n) amortized at worst, the latter O(log n) worst-case.

The dividend is only paid in full when both work together.

A Full Walkthrough

Take the step-by-step merges 1-2, 2-3, 3-4, 3-5 (union by rank plus compression on find):

1. union(1,2): two single-node trees, hang either way, 1 becomes the root, rank(1)=1;
2. union(2,3): find(2) finds root 1; find(3) is 3 itself; 3 hangs under 1;
3. union(3,4): find(3)=1, find(4)=4, 4 hangs under 1;
4. union(3,5): likewise 5 hangs under 1;
5. find(5): the path is 5→1, two steps; and conveniently there is no long chain to compress.

You can see that under union by rank the tree is naturally flat, and path compression only kicks in once a “chain” appears.

For instance, after all elements are unioned serially onto the same root, a single find flattens the whole chain.

Both scenarios can be reproduced by hand on the visualization page.

Kruskal deserves a full walkthrough, because it shows union-find’s place in algorithms better than anything else.

n nodes and m edges, scanned by ascending weight: each edge first finds both endpoints. Same root means this edge would form a cycle, so skip it. Different roots means union, taking the edge into the spanning tree. Once n−1 edges are collected, you are done.

All the way through, union-find answers exactly one question: “are these two nodes connected right now?”

Without it, every edge Kruskal accepted would trigger a fresh full-graph connectivity check, and the complexity explodes outright.

The combination “scan in order + O(α) connectivity queries” is the entire engineering support that turns the greedy (sorting by edge weight) into a workable algorithm.

Where It Gets Used

• Kruskal minimum spanning tree: try edges in ascending weight, with union-find answering in O(α) whether the endpoints are already connected. Union-find is the precondition for this algorithm to work at all;
• Cycle detection in undirected graphs: add edges one by one; an edge whose endpoints already share a root is a cycle. Kruskal’s cycle check used on its own;
• Dynamic connectivity: keep adding edges, query at any time whether two nodes are connected;
• Equivalence-class merging: modeling variable equivalence, set partitioning, friend circles, and the like;
• Dynamic programming + merging: in interval and connectivity DP, union-find skips interval endpoints that have already been merged, pressing O(n²) down to near-linear. See the “convergence” section below;
• Offline lowest common ancestors (Tarjan offline LCA): DFS the tree, and each time you leave a node, “merge” its subtree into itself. When answering an LCA query (u, v), the root of v’s set is exactly the answer. DFS’s recursion order plus union-find’s merging power turn an “climb upwards” problem into a “look up the root” problem — the classic pattern of the two working in concert.

Weighted union-find deserves to be pulled out of that list and expanded on its own, because its modeling is the cleverest.

Hang a “weight to the parent” on the parent pointer (an age difference, a color difference, a numerator/denominator ratio — anything works); when find compresses the path it accumulates the weights along the way; at union time the new weight is solved out of “two known relations imply a third”.

A classic use: “a is 3 larger than b, b is 5 larger than c — what is the relation between a and c?” Store the ordering relation as a numeric difference, and any two nodes’ relative value comes out of a single find.

It upgrades union-find from “same class or not” to “within the same class, what is the relative relation”; ratio modeling (a/b = 3 style “evaluate division” problems) works with just a different weight semantics.

Two scraps of engineering experience: use arrays, not objects. parent/rank as two flat arrays indexed by element number saves memory and is cache-friendly compared with an object graph.

When the elements are arbitrary strings, discretize them into numbers offline first, so union-find only ever touches integers. That is the single adaptation cost imposed by “union-find only understands array indices”.

Two handy pieces of extra information are worth noting too: component size. With union by size, the size array at the root is directly the component’s element count, so “how big is the largest friend circle” costs nothing.

Component numbering: scan all elements once, and the order in which roots first appear is the numbering; grid coloring and connected-component labelling can take it as-is.

Finally, one boundary to know: union-find supports merging only, never splitting.

“Undo a merge” can go through the rollback version, but “re-answer connectivity after deleting an edge” is beyond its reach — that calls for offline algorithms or heavier dynamic-tree structures. On hitting such a requirement, first confirm you really cannot sidestep it with “reorder the queries offline”.

Kruskal’s Rival

Minimum spanning trees have two evenly matched algorithms, and comparing them shows union-find’s role most clearly.

Kruskal takes the edge view: sort all edges, try them one by one, use union-find to prevent cycles. The question it answers is “are these two nodes already connected”.

Prim takes the node view: grow the tree from any starting node, maintain “the cut edges from inside the tree to outside” in a min-heap, each step pop the shortest cut edge and absorb the new node. The question it answers is “which is the next node closest to this tree”.

Prim needs no cycle detection at all: the tree grows one node at a time, so structurally it cannot cycle.

The division of labor emerges naturally: on sparse graphs (E ≈ V) both are fine. On dense graphs (E ≈ V²) Prim wins either way — the heap at O(E log V) or the naive version at O(V²) — while Kruskal spends O(E log E) on the sort alone. Amplified by the dense graph’s edge count.

So the “sort + union-find” combination loses on dense graphs, and that is one boundary of union-find’s ability: it is good at deciding connectivity, and poor at partnering with “global sorting” to swallow oceans of edges.

Counting Islands

The grid island problem (‘1’ is land, count the connected components) is the smallest sample for observing the difference between the two tools.

DFS flood fill: launch a DFS from each unvisited land cell and paint the whole island as visited. O(cell count) time, five lines of code.

Union-find: scan the cells, union each land cell with the land cells above and to the left, then count the distinct roots. Also O(cells × α), but with an extra closing pass.

On a static grid, DFS is usually less trouble.

Union-find’s value shows in the dynamic case: land cells “surface” one at a time (each time one is added, ask for the current island count). DFS has to rescan the whole grid every time; union-find does one union and answers in O(α).

This confirms union-find’s positioning: it is not the fastest static tool for “computing connected components”, but the correct model for “connectivity evolving through time”.

When choosing, ask one question first: will the connectivity change incrementally? Only if yes does union-find get its turn.

Convergence: DP Meets Union-Find

The two tools meet in interval and connectivity DP: while filling the table you often find that “all endpoints of one stretch are already equivalent and can be skipped wholesale”.

“Equivalent and skippable wholesale” is exactly union-find’s day job.

Record merged intervals in the union-find; when the fill meets an already merged interval, jump along the root to the next unprocessed position, and the inner loop turns from “scan cell by cell” into “skip block by block”, pressing O(n²) down to near-linear.

The demo at the top of this chapter shows exactly this kind of collaboration: watch the fill order get accelerated by the merge operations.

Tarjan offline LCA is another instance of the same pattern: DFS handles the traversal order, union-find does the merge bookkeeping of “subtree already visited”.

The selection heuristic is now clear: the problem is static and the state space can be bounded in advance → reach for the DP table; relationships evolve under operations and you only need the answer to “same class or not” → reach for union-find; both appear at once → let union-find act as DP’s accelerator.

Summary

The core of the DP lesson is caching and state design — Fibonacci gives the skeleton, knapsack gives the soul, and “how many dimensions is the table, which cells does each cell come from” is the universal opening move. The core of the Union-Find lesson is incremental maintenance — on their own the two simple optimizations are only constant-factor cleverness; together they push the complexity to the theoretical limit. Next time a new problem arrives, first work out whether it wants “a table” or “a forest”; and when it wants both at once, you already know how they shake hands.

Order: Sorting to Build It, Red-Black Trees to Keep It

Union-find answers “same class or not”; sorting answers “who is bigger”. “Sorting algorithms are every programmer’s mandatory first lesson”, but sorting is only responsible for establishing order once. When data keeps gaining and losing elements and you need to ask “the k-th smallest / the smallest one bigger than this” at any moment, the responsibility shifts from algorithms to data structures. The first half of this chapter is sorting — three families, one lower bound, several famous pits; the second half is red-black trees — how to keep a “short and wide order” under any insertion sequence. Both stages share the same protagonist: order.

Part One: Sorting

Sorting algorithms have been explained to death. You can recite a string of names without ever building the intuition.

Try a different organization: instead of one algorithm at a time, split them into three families, each a response to the previous generation’s pain point.

Family One: Insertion

Idea: keep the left segment sorted and insert each new element into its place.

• Insertion sort: scan left to right, moving the current element to its spot inside the sorted prefix. Worst case O(n²), but with one underrated virtue: adaptivity. The closer the input is to sorted, the closer it gets to O(n). On nearly-sorted data (appended logs, almost-ordered streams) it is one of the fastest comparison sorts, with a tiny constant, and it is stable and in-place;
• Shell sort: insertion sort’s long-range version. First run insertion with a large gap (far-apart elements roughly settle first), halve the gap each round, and the last round is equivalent to ordinary insertion sort, except the array is nearly sorted by then. It feeds insertion sort’s adaptivity with “pre-sorting”.

The insertion family’s fate is that elements can only move one step at a time (each move removes one inversion); n² is this family’s ceiling.

Family Two: Divide and Conquer

The root of n² is “removing only one inversion at a time”.

The divide-and-conquer family changes tack outright: split the array in half, sort each half, then merge.

• Merge sort: split down to the minimum, merge pairwise (merging two sorted arrays is linear). Whatever the input looks like, a stable O(n log n) — that is its signature — at the cost of O(n) auxiliary space and cache-unfriendly merge scans. It also throws in two by-products: stability (equal elements keep their order) and a natural aptitude for external sorting (merging disk data block by block);
• Quicksort: no merging, partition first. Pick a pivot, fling the small ones left and the large ones right, recurse on both sides. Partitioning is in-place, saving the auxiliary array, with excellent cache locality and the smallest constant in practice. But partition quality depends on pivot luck: always hitting extremes degrades to O(n²). Random pivot selection (or median-of-three) pulls the expectation back to O(n log n), with a worst-case probability low enough to ignore in engineering;
• Introsort: quicksort up front, switch to heapsort as a backstop when the recursion runs too deep, finish small blocks with insertion sort. The C++ standard library’s std::sort is exactly this three-in-one, stitching the three families’ advantages together;
• Timsort: modern language standard libraries’ other answer. Python’s sorted and V8’s Array.prototype.sort are both it. The idea runs backwards: instead of forcing splits, find the naturally ordered runs in the data, extend short runs with insertion sort, then merge the runs. On nearly-sorted real data (which is almost always the case) plenty of runs are long already, and sorting comes close to O(n). It is the merge family’s skeleton plus the insertion family’s adaptivity — a hybrid that hybridized in exactly the right places.

A side note on why stability is worth money: multi-key sorting depends on it.

Sort by department once, then sort stably by name, and the department order is automatically preserved within equal names.

Unstable quicksort doing this would scramble the first pass’s result, leaving no choice but to pack the keys into a composite and sort once.

Family Three: Selection

Idea: each round, pick the extreme from the unsorted region and put it at an end.

• Selection sort: the naive implementation, always O(n²) and never adaptive, rarely used in practice. But it is the most “steady as a mountain” teaching model;
• Heapsort: upgrade “pick the extreme” to picking with a heap. Build the heap in O(n), extract the extreme in O(log n) each time, total O(n log n), in-place, O(1) auxiliary space. The cost is that jumping memory access is extremely cache-unfriendly, and in benchmarks it usually loses to quicksort, so it retires into the “backstop” role (Introsort’s fuse).

One Lower Bound

Why is it O(n log n) however you turn, with nobody faster?

The decision-tree argument fits on one page.

Regard comparison sorting as a binary decision tree. Each comparison is a fork, and the leaves hold the final ordering conclusions.

n elements have n! possible permutations, and each one must correspond to at least one leaf in the tree (otherwise two permutations would be indistinguishable, and one of them necessarily sorted wrong).

A binary tree that grows n! leaves has height at least log₂(n!).

Expanding with Stirling’s formula:

Any sort that relies only on comparisons cannot escape this lower bound in the worst case.

Quicksort, merge sort and heapsort all sit exactly against it, which makes them the optimal comparison sorts already.

Bypassing the Lower Bound

The lower bound’s premise is “comparison”. Each comparison outputs only yes or no, 1 bit of information.

Counting sort dispenses with comparison entirely: for a value range of [0, k], count how often each value occurs and expand them in order, O(n + k).

Radix sort goes one step further: for multi-digit numbers, run a stable counting sort digit by digit from the lowest position up, O(d·(n + k)).

They break past n log n because they trade comparison’s generality for “knowledge of the value range”.

Once you know what the elements look like, you need not ask which of them is bigger.

The cost is obvious too: it applies only to integers, or data mappable to integers, and the space fails once the value range is too large.

General and specialized: forever this pair of opposites.

There is actually a third road along the way: bucket sort.

Cut the value range evenly into k buckets, throw each element into its bucket by value, sort each bucket internally (usually with insertion sort), and concatenate in order.

When the input is roughly uniformly distributed, each bucket holds a constant number of elements in expectation, and the whole thing is expected O(n).

Its relationship to its two siblings deserves a side-by-side look: counting sort is “the extreme bucket, one cell per value” (no sorting inside the bucket), radix sort is “repeated bucketing by digit”, and bucket sort is “segment by value, hand the inside to a comparison sort”.

All three non-comparison sorts share one idea: trade distribution knowledge for comparison. They merely apply that “knowledge” at different granularities of the value range.

When the distribution is severely skewed, bucket sort degrades (every element crams into one bucket), one more instance of “non-comparison sorts all depend on the data’s shape”.

A Complete Cheat Sheet

Laying out the properties of the three families plus the non-comparison sorts:

Two cells hide subtleties: Shell sort’s complexity says “gap-dependent” because different gap sequences give different worst-case bounds (the original gaps are worst-case O(n²), finer sequences press lower).

Quicksort’s worst-case O(n²) refers to the deterministic-pivot version; after randomization the worst case is negligible in probability, and the expectation is O(n log n).

The stability column directly decides whether multi-key sorting is possible (see above); often written off as an insignificant footnote, it is in fact one of the hard constraints in algorithm selection.

The concrete cause of “unstable” is worth a look too, because it explains why instability is hard to repair: quicksort’s partition performs long-distance swaps (flinging a far-away element to the pivot’s other side), so the relative order of equal elements is scrambled at the moment of the swap and cannot be restored afterwards.

Heapsort does “swap heap top with heap tail” on extraction, likewise a large-span move.

Merge’s merging only happens between adjacent sorted runs, and insertion moves a single cell. Small-span moves preserve order by nature.

So the standard way to “patch stability onto quicksort” is not to fix quicksort but to attach an index to every element and widen the comparison key to (value, index). Trading extra information for stability, at the cost of space and constants.

When Memory Can’t Hold It

Everything above assumed the data sits in memory.

When the data is too big to fit, merge’s family advantage becomes the only answer: external merge sort.

Three steps: cut the file into blocks that fit in memory, read, sort and write each block back (use quicksort freely inside a block). Then merge the sorted blocks with a k-way merge: each time pick the smallest of the k blocks’ head elements and write it out (maintain “the current k heads” with a min-heap, O(log k) per extraction). Repeat until everything is merged.

The total number of I/O passes is proportional to “block count = N/M” (M being memory size), and a larger k reduces the number of merge rounds.

That is where the “way” in the disk era’s “multiway merge” comes from.

It is also the full meaning of merge’s “natural aptitude for external sorting” mentioned earlier: it is the only sort that merges by sequential scanning, and sequential reads are exactly what disks do best.

The Inverse: Shuffling Done Right

Sorting’s inverse problem is shuffling, and it has a famous scene where “most people’s implementation is wrong”.

The naive idea “swap each card with a randomly chosen card” is not uniform: it produces nⁿ equally likely swap paths, while a uniform shuffle needs each of the n! permutations to hold probability 1/n!.

The remainder of nⁿ not dividing n! makes some permutations systematically overrepresented.

The correct one is Fisher–Yates: in round i, pick at random only from the remaining unprocessed cards and swap it to position i. That yields exactly n! equally likely paths, every permutation precisely equally probable, in one O(n) pass.

The reverse way of thinking is common too: give each element a random key and sort by key (sort-by-random-key). Less hassle, but watch out for key collisions (ties let sorting stability introduce bias) and floating-point key precision.

Shuffling’s correctness proof and sorting’s lower-bound proof share the same counting intuition: count how many outcomes each path maps to, and any bias is immediately visible.

The Comparator Pitfall

Every comparison sort has one implicit contract with its comparator: strict weak ordering.

a and b must not be “mutually not-less-than”, and “less than” must be transitive.

The two most common violations in engineering: writing a <= b where a < b belongs (equal elements are “less than” each other, breaking incomparability), and comparators that depend on quantities that change during the sort (say a getter with side effects, or an unrounded float as the key — NaN compares false against everything, destroying transitivity outright).

The consequence of a violation is not “slightly wrong results” but undefined behavior.

The library’s quicksort or introsort assumes a law-abiding comparator: the partition pointers walk past each other, and the typical symptoms are out-of-bounds memory writes and a crashed process.

In the C++ world, “a broken comparator causing a segfault” is a decades-old classic accident, and the crash point is random and hard to reproduce.

Three rules avoid every known pit: use only < in comparators, never <=; compute comparison keys before the sort and store them; handle NaN in float keys first (or switch to “exact key plus float display”).

One optimization in the opposite direction, by the way: when comparisons themselves are expensive (very long strings, composite keys), don’t let the sort call the comparator over and over.

Compute each element’s key once (with the index attached), sort the lightweight keys, and finally rearrange the original elements by index.

Press “the number of comparisons” down to the lower bound while pressing down “the cost of each comparison” as well — two ledgers, kept separately.

In the Sorting Visualization, run several algorithms on the same data and watch two things: insertion sort’s “barely moving” on nearly-sorted data, and quicksort’s partition “jumping at scale”.

Compare them once and the selection table grows into your intuition.

After Order Is Built

Sorting solves “the batch at hand”: computed once, unchanged thereafter.

But in real systems the data is alive. New records keep arriving, stale entries keep leaving, and the business asks at any moment “what is the smallest element greater than this value”.

Inserting into a sorted array means shifting the back half, O(n) per step. Once insertions and deletions get frequent, the “sort once” strategy goes bankrupt.

What is needed then is a structure that is still ordered after every operation.

The binary search tree turns “ordered” from a one-time action into a persistent property: left subtree < root < right subtree, with lookup, insertion and deletion all O(log n).

Provided the tree does not degenerate.

The second half’s protagonist, the red-black tree, is the standard answer to “how to guarantee it never degenerates”.

Part Two: Red-Black Trees

The red-black tree is probably the highest-dropout subject in any data structures course: insertion needs recoloring, deletion sprawls into eight cases, and the properties are memorized, forgotten, memorized again.

Yet its design motive is remarkably plain: fit the binary search tree with a height insurance policy.

Skip the mnemonics and re-derive it from the problem.

The Problem: BSTs Degenerate

The lookup cost of a binary search tree (BST) equals its height.

Ideally n nodes give height log n, but a BST’s shape depends on the insertion order. Insert 1,2,3,…,n in order and it degenerates into a chain with O(n) lookups.

We need a mechanism that keeps the tree short and wide under any insertion sequence.

Mainstream solutions come in two families: force perfect balance (AVL, where every node’s left and right subtree heights differ by ≤ 1), or guarantee only “rough balance” (red-black trees).

The red-black tree chooses the latter. How loose it can afford to be, and how strict it stays, is all written in its five properties.

Five Properties and Their Jobs

The red-black tree marks each node red or black, requiring:

1. Every node is either red or black;
2. The root is black;
3. Leaves (NIL null pointers) count as black;
4. A red node’s children must be black (no two consecutive reds);
5. On the path from any node to all its descendant leaves, the number of black nodes is the same (equal black-height).

Of the five, the ones actually doing the work are 4 and 5.

From them follows the core theorem:

A red-black tree’s height ≤ 2·log₂(n+1).

The proof takes one line: property 4 forbids consecutive reds, which means on any path, red nodes ≤ black nodes.

Property 5 says all paths share the same black-height, and a tree of black-height bh has at least $2^{bh} - 1$ nodes (the full binary tree lower bound).

Clamping from both sides: the shortest path is all black (length bh), the longest alternates black and red (length 2bh), so the longest is at most twice the shortest.

The tree is “roughly” short and wide.

See this proof clearly and you understand the red-black tree’s design philosophy: do not chase perfect balance; chase only “the longest path no more than twice the shortest”.

What this looser constraint buys is the low maintenance cost discussed below.

There is also a viewpoint that gives the whole trick away: absorb every red node into its black parent (merge the red edges, nodes become multi-key), and the red-black tree turns into a 2-3-4 B-tree.

2-nodes, 3-nodes and 4-nodes correspond exactly to a black node carrying zero, one and two red children.

Red-black coloring is no mysticism: it is a notation that encodes a multiway B-tree’s balance in binary form — properties 4 and 5 together are precisely “all B-tree leaves at equal depth” translated into the binary world.

Seen this way, insertion’s “recolor and move up” is the B-tree’s node split, and rotations are merely the mechanical motions that split needs in its binary representation.

Many “why are the rules shaped like this” questions dissolve here all at once.

Rotations

Maintaining the properties relies on two kinds of local surgery.

Recoloring is free.

Rotation is the real structural change. It flips the parent-child relation around an axis, lowering one side’s height by one and raising the other’s by one, while the BST’s in-order sequence is untouched.

This is rotation’s essence: it is the only operation that adjusts tree height without touching the ordering property, costs O(1), and involves just three pointers.

Hand-trace a left rotation once; the pointer work is three steps.

Left-rotate around x (right child y floats up):

1
      x                 y
2
     / \               / \
3
    a   y     →       x   c
4
       / \           / \
5
      b   c         a   b

In-order traversal gives a, x, b, y, c on either side. Order unchanged is the entire basis of a rotation’s legality.

The pointer operations: ① x’s right pointer now points to b (y’s left subtree is adopted by x); ② y’s left pointer now points to x; ③ x’s original parent now recognizes y.

Three pointers written, x’s height drops by one and y’s rises by one, and the rest of the world does not move at all.

Right rotation is fully symmetric.

Turn it by hand a few times on the visualization page and feel “order unchanged, heights exchanged”.

Every balanced tree’s self-repair (AVL, red-black, Treap) wields this same scalpel.

Insertion

A new node is always inserted colored red first.

Why? Coloring red can violate only property 4 (a double red appears) and never touches property 5 (black-height unchanged).

Coloring black changes the black-height of every path — global damage.

So insertion’s repair problem compresses into a single “fix the double red”.

Fixing a double red has only two cases:

• Uncle is red: color the father and the uncle black, the grandfather red. Black-height unchanged, the conflict moves up two levels. It may bubble all the way to the root, which is finally colored black to close;
• Uncle is black: through one or two rotations plus recoloring, turn the “zigzag” into a “straight line” and then straighten it. Repaired locally, and the whole repair terminates.

The black-uncle case is worth drawing out, because the two rotations of “zigzag to line, then straighten” are the part people suffer to memorize.

Let the new node be z, the parent p, the grandparent g (p red, g black, uncle black).

z and p stand in one of only two relations:

• Straight line (z and p on the same side, both left children for instance): right-rotate g (opposite p’s direction), p rises to g’s position, then color p black and g red — done;
• Zigzag (z and p on opposite sides, p a left child and z a right child): first left-rotate p, flattening the zigzag into a line. Now z has become p’s senior and still sits on g’s side. Then apply the straight-line treatment (right-rotate g plus recoloring) — done.

The memory hook: a zigzag always becomes a straight line first; a straight line always ends with a single rotation.

The two rotations match exactly the “at most two rotations per insertion” bound, and after those two rotations you must recolor twice (p black, g red) to rebalance the black-height.

Hand-trace this process twice, and the “rotation direction” questions in deletion will resolve themselves too. They are the same geometry.

The key difference is termination: the red-uncle case bubbles upward, the black-uncle case ends in place.

So insertion costs at most two rotations and O(log n) recolorings.

Recoloring is cheap, rotation is expensive; insertion in a red-black tree trades expensive operations for cheap ones.

Deletion

Deletion is more trouble than insertion (deleting a black node breaks the black-height): it has to propagate “double black”, the cases split into many, but the skeleton is the same — recolor and move up when you can, rotate and terminate when you cannot.

In engineering implementations, this is that “famous set of eight cases”.

Strip the “eight cases” down to the skeleton and there are really only three classes.

After a black node is deleted, every path through that position is one black short. Record the deficit as “double black” and pass it down to the node that took the spot:

1. Sibling is red: rotate and recolor to send the red sibling up. The double black is not gone, but the sibling is now black — move on to the next class;
2. Sibling is black, both nephews black: color the sibling red; the “double black” merges with the sibling’s black and cancels one level at the parent. The parent either finishes (it was red, now turned black to cover the deficit) or inherits the double black and keeps moving up;
3. Sibling is black, some nephew red: one or two rotations plus recoloring directed by the red nephew’s position fill the deficit on the spot, and the repair terminates.

The “at most three rotations” bound comes from exactly this structure: class 1 does at most one (then falls into 2 or 3), class 2 is pure recoloring upward (no rotation), class 3 at most two.

Recoloring travels up the tree O(log n) times, but rotations — the expensive operation — are pressed down to a constant.

Why Red-Black Instead of AVL

AVL is strictly balanced (height difference ≤ 1) and lookup is indeed a bit faster. But its maintenance is expensive: an insertion can trigger O(log n) rotations, and deletion likewise.

The red-black tree is the other way around: lookup paths at most twice as long (still logarithmic, small constant), at most 2 rotations per insertion and at most 3 per deletion, everything else handled by recoloring.

The scales of engineering tradeoff tip toward the red-black tree because the typical workload is mixed read-write, not pure lookup.

Under frequent modification, the rotations a red-black tree saves far outweigh the loss from longer lookup paths.

Add implementations polished over decades (deletion’s case handling is highly standardized), and it becomes the standard library’s default: C++‘s map/set, Java’s TreeMap, the Linux kernel’s CFS scheduler data structure — all red-black trees.

If you want to implement one yourself, it is worth a look at the left-leaning red-black tree (LLRB): add “red edges always lean left” to the invariant, and insertion shrinks to about twenty lines while deletion’s cases contract sharply.

It is essentially the B-tree viewpoint above pushed to its extreme (simulating only 2-3 trees).

Standard libraries don’t use it more out of history and path dependence than technical rejection.

The two families’ ledger fits into one table, sparing the empty back-and-forth over “which is better”:

On the tradeoff, AVL leans read-optimized and the red-black tree stays balanced between reads and writes.

The same engineering wisdom as databases choosing B+ trees rather than perfectly balanced trees for indexes.

Two implementation conventions are also worth knowing.

First, the sentinel NIL: rather than give every leaf two null pointers and test “is it null” everywhere, use one shared black NIL node in place of all null pointers. Every leaf’s children point at it, the coloring logic unifies, the branch tests halve, and the cost is one resident object.

Second, the parent pointer cannot be skipped: insertion and deletion repairs both walk upward from the current position to find father, grandfather and uncle; without parent pointers you would have to carry a search-path stack yourself.

Standard library implementations all carry parent pointers, which is where the textbook’s “three pointer fields” comes from.

A Glance at Alternatives

Balanced trees are not the only answer to the “ordered dictionary”.

The skip list reaches the same complexity by a completely different route: the bottom layer is a sorted linked list, and progressively sparser “express lanes” are drawn above it; lookup starts at the top and moves sideways, dropping a level when it cannot advance.

Expected O(log n), balance maintained by probability, no rotations and no recoloring at all.

Three reasons it takes some territory from the red-black tree: far simpler to implement (no eight-case deletion taxonomy; insert and delete are just “flip a coin for the level height plus fix pointers”). Range queries come naturally (locate the start and walk the bottom list in order; a tree has to compute in-order successors). Rank queries (“the k-th smallest”) need only an added level-width field.

Redis’s sorted set (zset) chose a skip list over a red-black tree, and the publicly stated reasons are precisely implementation simplicity and handy range operations.

For that scenario, engineering elegance outranked theoretical elegance.

Look the other way at the territory the red-black tree holds: compact memory (a skip list node carries multi-level forward pointers, a larger space constant), worst-case guarantees (a skip list is expected O(log n), resting on randomness, with no hard upper bound in theory), and better cache behavior.

So when you want range operations and simple implementation, go with the skip list; when you want worst-case guarantees and compact memory, go with the red-black tree.

Consistent with the theme recurring throughout this chapter: choosing a data structure is requirement matching, not ranking.

In the Red-Black Tree Rotation Visualization, do three things: insert ascending data continuously and watch how rotations keep the tree short and wide. Find one “uncle is red” insertion and watch how the conflict bubbles upward. Then find one “uncle is black” insertion and watch one or two rotations terminate it on the spot.

Once you have seen all three, the five properties are no longer doctrine to memorize but this machine’s operating log.

Summary

Sorting and the red-black tree handle the two stages of the “order” problem separately: sorting answers “how to arrange n elements in one go”, with the O(n log n) lower bound standing guard; the red-black tree answers “how to keep order from ever falling under insertions and deletions”, backstopped by the loose constraint “the longest path no more than twice the shortest”. Put the two battles side by side, and “order” turns from a one-time action into a property that can be maintained continuously — exactly the step from “algorithms” to “data structures”.

The Search Skeleton: From Traversal to Adversarial Search

The order sorting and red-black trees maintain is still static; search is the main melody of the algorithm world, and it has only one basic shape: keep a candidate container, and repeatedly “take one out, put its neighbors in”. Change the take-out order and you get a different algorithm — from traversal that “sees the whole graph”, to shortest paths that “find only the best route”, to game search where “an opponent who hits back stands at the other end”: three generations of problems, one skeleton.

Layer One: Traversal

The core problem traversal has to solve is don’t walk back the way you came.

A graph isn’t a tree: edges can form cycles, and without marking you’ll circle one forever.

So the skeleton’s first block is always the visited mark.

The second block is a candidate container: it holds the nodes that are “discovered but not yet processed”.

The whole loop is just this:

1
put the start into the container and mark it
2
while the container is not empty:
3
    take out a node v and process it
4
    put all of v's unmarked neighbors into the container and mark them

The pseudocode leaves one blank: when you “take one out”, which one?

From the head of the container it’s BFS; from the tail, DFS.

The entire difference between the algorithms hides in that take-out order.

BFS: A Queue, Spreading by Layer

When the container is a first-in-first-out queue: the start’s direct neighbors are all processed before “the neighbors’ neighbors” get a turn.

The spread proceeds one layer at a time by distance from the start, like ripples on water.

That fixes BFS’s signature property: on a graph with uniform edge weights, the first time you reach a node, the path you walked is guaranteed to use the fewest edges.

The intuition: nodes are enqueued in distance layers, and the layer at distance d+1 doesn’t dequeue at all until everything at distance d is done.

The first time you touch the target, no shorter route can still be untouched.

BFS’s home turf follows: unweighted shortest paths — fewest steps in a maze, fewest moves in checkers, degrees of separation in a social network.

A corollary comes free: record “start → who first discovered each node” and you have a shortest-path tree rooted at the start.

DFS: A Stack, Dive to the Bottom Then Backtrack

When the container is a last-in-first-out stack — which is exactly what the recursive form’s call stack is — a freshly discovered neighbor is followed immediately, diving all the way to the bottom, backing up one step to try another branch only when there is nowhere left to go.

The exploration shape is a tentacle that keeps extending and retracting.

DFS promises nothing in the superlative, but it carries structural information of its own: the moment it backtracks is the moment a subtree completes.

Stamp an entry time when the recursion enters a node and an exit time when it backs out; clamped between the two timestamps you get a pile of things BFS cannot give you:

• Topological sort: ordering by descending exit stamp is a legal execution order for a DAG (build systems and task scheduling depend on it);
• Cycle detection: hitting a node that is “still on the stack” (entered, not yet left) means a cycle exists;
• Articulation points / bridges: comparing the entry stamp against the earliest entry stamp reachable through each neighbor locates single points of failure in a network.

The division of labor is clear: BFS answers “how far”, DFS answers “what structure”.

How to Choose

• Asking “fewest steps” with uniform edge weights → BFS, no second choice;
• Asking “does a path exist” (connectivity) → either works, DFS code is shorter (three lines recursive);
• Asking “order / dependencies / cycles” → DFS, because of its timestamp structure;
• Uneven edge weights → neither is right; that’s Dijkstra’s territory. See layer two.

Complexity is identical for both: every node enters and leaves the container once, every edge is examined twice — O(V+E).

On space, BFS at worst holds an entire layer (O(V) on a dense graph), while DFS holds the current path depth (worst case also O(V), but far shallower on average).

On very large mazes that is a practical consideration.

Three Variants of the Skeleton

The same skeleton refits into a few high-frequency variants:

• Multi-source BFS. Swap the single start for an entire starting layer. Every exit of a maze, every rotten orange in the rotting-oranges problem. Enqueue them all up front and let the spread proceed as usual. The distance at which a node is first reached is its distance to the nearest source. Single-source BFS answers “how far from the start”; multi-source BFS answers “how far from the nearest source”, and the latter shows up more often in real problems;
• Bipartite coloring. As BFS spreads by layers, mark each layer’s parity along the way (or alternate red and green); the moment you scan an edge joining two same-colored nodes, the graph is not bipartite. Questions like “can this be split into two groups with no edges inside a group” (timetabling, team assignment) need no new machinery at all;
• Connected component counting. Wrap the traversal in an outer loop of “while unvisited nodes remain, run another pass” — the number of passes is the number of components. BFS or DFS, it makes no difference; the skeleton is unchanged.

One engineering-level reminder as well: DFS’s recursion depth.

On a chain-shaped graph the recursive DFS’s stack depth equals the node count, and a graph with tens of thousands of nodes is enough to blow the default stack.

Production code either switches to an explicit-stack iterative form or moves to BFS.

Deque and In-Degree Table

0-1 BFS fills the gap between BFS and Dijkstra.

When edge weights take only the values 0 and 1 (grids of the “flat ground costs a step, portals are free” kind), even a priority queue feels heavy.

Swap the plain queue for a deque: nodes reached over a 0-weight edge enter at the head, those over a 1-weight edge at the tail.

The distance difference from head to tail never exceeds 1, so the take-out order stays correct.

The complexity is still O(V+E).

With that, the genealogy of take-out strategies is complete: queue (all weights 1) → deque (weights 0/1) → priority queue (arbitrary weights) — one skeleton, three containers.

Kahn’s algorithm is the other entrance to topological sorting, and it is pure BFS skeleton.

Count each node’s in-degree, and put the nodes at zero (the ones with no prerequisites) into the queue.

Each time you take one out, decrement the in-degree of every node it points to, and enqueue whatever hits zero.

The order that comes out is a legal execution order.

It arrives where DFS’s “descending exit stamp” arrives, but throws in a bonus: if the number of processed nodes is smaller than the total, the leftovers form a cycle.

Sorting and cycle detection in one pass — which is why build systems usually reach for it when checking dependencies.

Implementation Details on Grids

Most bugs in graph problems aren’t in the algorithm, they’re in the grid translation layer:

• Direction arrays: dr = [-1, 1, 0, 0] and dc = [0, 0, -1, 1] with one loop, replacing four copy-pasted neighbor blocks. A five-line difference, an order of magnitude in error rate;
• Marking timing: BFS must mark at enqueue time. Mark only at dequeue time and the same node gets pushed in by several neighbors one after another, the queue fills with duplicates, and complexity degrades from O(V+E) to O(V·E). Recursive DFS marks on entry. Don’t mix the two timings;
• Bounds and obstacle checks in one if: first the coordinates are legal, then the cell is walkable, then it is unvisited; only after all three gates pass does it enter the queue. Missing one gate usually shows up as “the answer is occasionally one too large” or a stack overflow — hard to catch by reading code, instantly visible when you hand-trace a small grid;
• When reusing the visited array across queries, clear it, or use “timestamp marking” (each cell records the id of the query that last visited it, saving the clear). A trick common in both contests and production.

Run BFS and DFS over the same grid in the Search Visualizer: BFS’s visit order is a tidy diamond of ripples pushing ring by ring toward the target, while DFS is a writhing long snake that swallows every dead end in one direction before doubling back.

Put the two frames side by side and “by layer” versus “dive deep” never needs memorizing again.

Layer Two: Shortest Paths

Swap BFS’s queue for a priority queue (take-out ordered by known cost), leave the skeleton alone, and it becomes Dijkstra.

Single-source shortest paths with arbitrary edge weights.

But Dijkstra answers “the shortest path from the start to all nodes”, while reality often asks only for the shortest path to one node.

The problem narrowed, so the algorithm should get faster.

The whole of A* is adding to Dijkstra one piece of intuition — which direction the goal lies in — and then proving that intuition cannot lead the answer astray.

Where Dijkstra Wastes Effort on Single-Target Queries

Dijkstra’s loop takes the node u with the smallest currently known distance out of the priority queue and relaxes its neighbors with it.

That smallest-distance order guarantees that the first time the target is popped, its distance is already the final answer.

Because it spreads concentrically over the whole graph by true distance from the start.

The waste in the single-target case is plain to see: the target lies east, and Dijkstra still spends the same effort spreading west and north, relaxing an entire ring of hopeless nodes.

None of that exploration contributes anything to “the shortest path to the target”.

Adding One Piece of Intuition: f = g + h

A* changes exactly one thing: the priority queue’s sort key is no longer “the known distance g from the start”, but

g(n) is the known actual cost from the start to n, and h(n) is the estimated cost from n to the goal.

That is the heuristic.

Now the queue pops not the node nearest the start, but the node near the start and looking near the goal.

Intuitively, the exploration gets pulled into an ellipse aimed at the goal instead of concentric circles over the whole graph.

Where does h come from? It depends on the problem’s structure.

Three are most common on grid maps:

• Manhattan distance |dx| + |dy|: the natural choice for four-directional movement;
• Euclidean distance √(dx² + dy²): for movement at any angle;
• Chebyshev distance max(|dx|, |dy|): for eight-directional (diagonals included) movement when a diagonal step is priced at 1.

One rule governs the choice: h must not overestimate the true remaining cost.

If the geometric intuition is too weak (on real road networks, “straight-line distance” gets detoured absurdly by rivers and viaducts), there is one more step up: landmarks (ALT).

At preprocessing time, pick a dozen or so landmark nodes and precompute their exact distances to every node; at query time, build h from the triangle-inequality lower bound “from n through some landmark to the goal”.

It uses only exact distances, so it is admissible by construction, and the lookup is O(1).

The standard strengthening for large-scale pathfinding in map services.

The Conditions Optimality Demands

h has two progressive properties:

• Admissible: h(n) ≤ the true cost from n to the goal. Then the first path A* finds to the goal is optimal. The intuitive reason: h never overestimates, which means f is “a lower bound on total cost”. Every node on the optimal path has f no greater than the true optimum, and any “seemingly cheap” node popped early cannot offer a smaller lower bound. Formalize that and it is the standard proof; intuitively, “h never brags, so queuing by f won’t miss the true optimum”.
• Consistent: h(u) ≤ cost(u,v) + h(v), i.e. h satisfies the triangle inequality. Consistency implies admissibility, and it guarantees each node is expanded at most once. Once popped, it will not re-enter the queue with a smaller f. With geometric distance as h, all three hold naturally (Euclidean distance is itself a metric, so it satisfies the triangle inequality automatically).

The engineering trade-off to know: if h occasionally overestimates a little, A* gets faster but may return a suboptimal solution (the problem becomes “weighted A*”, f = g + ε·h, trading solution quality for speed).

Plenty of game pathfinding does this on purpose. Nobody can see that an NPC is half a cell short of “optimal”.

How Much It Actually Saves

The easiest way to understand it is to look at the explored region.

On an open grid with no obstacles:

• Dijkstra explores a circle centered on the start with radius “start-to-goal distance”, area O(d²);
• A* with perfect h (h always equal to the true remaining cost) walks straight along the optimal path, O(d);
• A realistic Euclidean h lands between the two: it explores an ellipse with the start and goal as foci, and the fewer the obstacles the narrower the ellipse.

Obstacles’ job is to “fatten” the ellipse: while detouring around a big one the heuristic goes temporarily blind (the detour segment’s h shows no reason to detour), and nodes get expanded in batches anyway.

So A*‘s payoff depends heavily on the map’s shape. Enormous on open maps, clearly degraded on maze-like ones.

Load one empty field and one maze in the A* Pathfinding demo and compare the number of colored explored cells; the difference is immediate.

By Hand: Tie-Breaking Is the Hidden Third Element

“A* with perfect h walks straight along the optimal path” actually hides an assumption: ties must be broken correctly.

Work through one 3×3 empty grid and you can see through it.

Start at the top-left, goal at the bottom-right, four-directional movement, Manhattan distance as h.

The true cost from start to goal is 4.

Compute f = g + h for every cell:

• Start (0,0): g=0, h=4, f=4;
• Any middle cell (say (1,1)): g=2, h=2, f=4;
• Goal (2,2): g=4, h=0, f=4.

All nine cells tie.

That’s no coincidence: on an empty grid Manhattan distance equals the true remaining cost exactly (h is perfect), and every cell lies on some optimal path, so every cell’s g + h equals the optimal total.

f carries no discriminating power at all, and A* degenerates into “picking arbitrarily among all the f=4 cells in queue order”.

In the worst case it still expands the entire grid.

The fix is a tie-breaking rule: when f ties, take the larger g (the node closer to the goal first).

On the same nine cells, that rule makes the search hug a straight line to the goal and expand only O(d) nodes.

Engineering conclusion: the heuristic’s quality sets the floor on f, and tie-breaking decides whether you can reach that floor.

Both are mandatory questions.

When A* Degenerates Back to Dijkstra

Let h ≡ 0 hold everywhere (admissible); then f = g and A* is Dijkstra.

That’s the anchor for understanding the two.

In practice degeneration happens when:

• h is too weak: e.g. a grid that clearly moves in four directions but uses a badly underestimated distance, so g dominates the sort key;
• h has zero directionality: the graph structure has no geometric meaning (social networks, dependency graphs) and no meaningful h can be built. What you want there is bidirectional Dijkstra or an on-demand algorithm (Dijkstra with early exit: stop as soon as the target pops, which already saves half);
• Too many targets, or repeated queries: what you want is an all-source / multi-source distance field, and Dijkstra (or BFS, when all weights are 1) is simply the right tool.

Single-target problems have one more often-overlooked weapon: bidirectional search.

Run one Dijkstra/A* from the start and one from the goal, and let them meet in the middle.

On grids the explored area roughly halves; in tree-shaped spaces with large branching factors the saving is steeper.

The cost is engineering complexity: the reverse graph needs reversed edges, the two “expanded frontiers” have to join correctly, and a crooked join yields a path that looks reasonable but is actually suboptimal.

Worth doing where the graph is static and queries are frequent (road networks). Not worth doing for a one-off graph search.

Conversely, for game scenarios that “recompute pathfinding for hundreds of units every frame”, the standard move isn’t weakening A* but caching and frame-splitting (JPS, hierarchical pathfinding HPA* and friends) — that’s another topic.

Implementation Checklist and Common Bugs

Implement A* yourself and these are the spots everyone who has stepped in them nods at:

• Allow duplicates in the priority queue, validate on pop. To lower some node’s g you needn’t edit the old entry inside the queue (most heaps don’t support it) — just push a new one; on pop, if you find it’s a stale copy (recorded g worse than the current best), discard it. This is lazy deletion, and it saves all the trouble of “decrease-key inside the heap”;
• Test the goal at pop time, not at generation time. When h is admissible but inconsistent, a node may first leave the queue with a suboptimal g and later be updated to a better one. Testing the goal at generation time locks in the suboptimal solution. Under a consistent heuristic the two forms are equivalent, but “test at pop” is always right, and not worth risking a single comparison for;
• Diagonal cost for 8-direction movement. If a diagonal step costs √2, Chebyshev distance overestimates the true remaining cost (it assumes a diagonal step costs just 1), breaking admissibility outright. Use octile distance (max(|dx|,|dy|) + (√2−1)·min(|dx|,|dy|)). Chebyshev is legal only when diagonal steps are priced at 1. “Swapped the distance formula and optimality broke” is A*‘s most insidious class of bug;
• h’s units must match the edge weights. If the grid charges by cell count, use cell-count distances; if it charges in meters, convert the distances into meters. A unit mismatch amounts to scaling h by a fixed factor, and once that scaling exceeds the true ratio, h overestimates.

Layer Three: Games

Traversal and shortest paths share one premise: the graph is dead.

An edge’s cost doesn’t change because you took a step.

But there is a class of search problems where an opponent stands at the far end of the graph, ready to hit back.

Every move you make changes the moves available.

The notion of an “optimal path” collapses, replaced by the question “even against perfect play, what can I secure?”.

Tic-tac-toe is the smallest serious game: a 3×3 board, two players alternating, at most nine moves to the end.

It is small enough to enumerate the entire game tree (fewer than 260,000 legal positions in total), yet large enough to hold every core idea of adversarial search: minimax, the evaluation function, alpha-beta pruning.

The Game Tree

Your own thinking at the board runs “I go here, he’ll most likely go there, then I go here…”.

Draw that thinking out in full and you have the game tree: each node is a position, my branches and the opponent’s alternate level by level, and the leaves are endings (I win / I lose / draw).

The rule for searching this tree is minimax:

• The layers where I decide (max layers): pick the move with the largest evaluated value;
• The layers where the opponent decides (min layers): assume the opponent is smart enough and pick the move minimizing my evaluated value.

The min layer’s pessimistic assumption is the soul of the whole method: don’t guess how the opponent will move — assume the opponent plays their best.

Only a score computed under that premise means “what I can secure even against perfect play”.

Which is also why a minimax move can never be punctured by one reply from the opponent.

The Evaluation Function

Tic-tac-toe’s evaluation can be absolutely exact: terminals are marked +1 (I win), −1 (I lose), 0 (draw).

No heuristic whatsoever.

That is tic-tac-toe’s luxury as a teaching case.

For bigger games (chess), the leaves cannot be enumerated to the end, and the evaluation function becomes the protagonist: material, controlled squares, king safety… a linear combination of weighted features.

Search is responsible for seeing far, evaluation for seeing accurately — that division of labor runs through every game AI.

Recursive Implementation

With exact evaluation in hand, minimax is a very short recursion:

1
minimax(position, my turn?):
2
    if terminal: return ±1 or 0
3
    if my turn:
4
        return max over all legal moves of minimax(position after move, false)
5
    else:
6
        return min over all legal moves of minimax(position after move, true)

At the opening’s root node take the max, then walk down the branch that achieved it — that is the perfect move.

Tic-tac-toe’s whole game tree computes in milliseconds; it doesn’t even need pruning to be fast enough.

Its significance is shrinking the algorithm until one glance takes it all in, so it can be reused on a larger board.

This tree also hides an optimization that echoes DP: the same position can be reached by different move orders (upper-left then lower-right, or lower-right then upper-left, same position).

Naive recursion searches each of them separately; give the recursion a “position → already-computed score” cache (a transposition table, in engine parlance) and repeated subtrees hit it directly.

Do the count and the deal is obviously good: there are over 250,000 legal game sequences, but only a few thousand distinct board states.

The cache cuts the search space by more than an order of magnitude.

Alpha-Beta

Minimax’s answer is exact, but plenty of branches are computed for nothing.

Alpha-beta pruning’s core observation:

At a max layer, if one move has already secured a score of α, then among its sibling branches, any branch where “the opponent can hold the result to ≤ α” need not be computed to completion. Whatever good result is hidden inside, the opponent will never let you get there.

Maintain two numbers: α is “the lower bound I can currently guarantee”, β is “the upper bound the opponent allows”.

The moment a node finds α ≥ β (this branch’s result has left the opponent’s tolerance), stop searching that branch immediately.

What gets pruned is a future the opponent would never choose, and what remains is bit-for-bit identical to full minimax.

Pruning efficiency depends strongly on move ordering: try strong moves first and the bounds tighten quickly, cutting deep.

Under ideal ordering the number of examined nodes drops from $O(b^d)$ to roughly $O(b^{d/2})$.

For the same search-depth budget, that is effectively a doubled depth.

The ordering heuristic is demonstrable even on tic-tac-toe: order moves as “center > corner > edge” (matching human chess instinct) and alpha-beta’s pruning visibly speeds up.

Chess engines maintain an entire ordering pipeline of “captures first, history heuristic, killer moves”.

Which is why every practical game engine (the search layer of any chess or Go engine) treats move ordering as a first-class optimization.

The Inevitable Draw

Exhaust tic-tac-toe and the game-theoretic result is: with both sides perfect, tic-tac-toe is always a draw, and the first player has no winning strategy either.

The makeup of random play corroborates the scale of the first-move advantage: of all 255,168 game sequences, the first player wins 131,184 (about 51%), the second wins 77,904 (about 31%), and 46,080 are draws (about 18%).

Playing at random, the first player is clearly ahead; when two “perfects” meet, that edge is canceled exactly to zero.

That makes tic-tac-toe the most legible teaching sample for “game-theoretic value”: a position’s true value is only −1, 0 or +1, and a perfect AI’s every move converges toward its own value.

So a kind of humility hides in a perfect AI’s real behavior: against your mistakes it grants nothing (you slip, it wins on the spot); against you playing equally perfectly, it has been laying out the draw since the first move.

Those seemingly passive defensive moves are minimax telling you “I’ve computed this branch: I can’t win it, and I won’t lose it either”.

Getting the AI to admit “I can’t win this one” is precisely the hardest part to build: it requires the evaluation to hold no illusions on any branch.

That is exactly where human players are weak. The illusion of advantage makes people gamble in drawn positions.

Which is also why engine analysis changed professional chess training: it stripped illusion out of the decision.

Making the AI Hungry to Win

Strict minimax has a human-interaction blemish on tic-tac-toe: to the AI, “winning on move 7” and “winning on move 5” both score +1, so it may take its time along a roundabout route.

Correct, and infuriating.

The classic fix is depth weighting: make the terminal score ±(10 − recursion depth), so winning at a shallower layer scores higher and a loss dragged to a deeper layer costs less.

Two lines of change and the AI immediately shows the survival instinct of “win as fast as possible, lose as slowly as possible”.

The game-theoretic value is unchanged (still a win, still not a loss), but the “temperament” of the play is completely different.

This is the minimal case of “an evaluation function’s accuracy and its expressiveness are two different things”: tic-tac-toe already wins with an absolutely exact ±1, but making the machine’s behavior look smart requires the evaluation to also encode things humans care about, like how fast and how safely.

When the Board Grows

Swap 3×3 for 15×15 Gomoku and copying minimax over fails on the spot: the branching factor rises from under 10 to around 200, and a depth-4 search is 200⁴ ≈ 1.6 billion positions.

Tic-tac-toe’s “enumeration privilege” is gone, and all three patches are mandatory:

1. Candidate pruning: of the 225 empty points on an empty board, the vast majority are meaningless. Consider only “empty positions adjacent to existing stones” (distance ≤ 2, say), and the legal candidates shrink from two hundred-odd to twenty or thirty. This is Gomoku AI’s first pruning, and the highest-yield one;
2. Depth-limited search + evaluation function: exhausting to the end is no longer possible, so change “seeing far” to “seeing 4–8 moves” and score the leaves by stone patterns. Threat patterns like open threes and fours each get weights (anything that completes five is infinite, an open four next…). How well the evaluation function is written directly sets the strength tier;
3. Alpha-beta + move ordering: once the branching is large, pruning shifts from “icing on the cake” to “the price of staying alive”, and ordering heuristics (try the biggest threat first) determine pruning efficiency.

Do all three and you have a respectable Gomoku AI.

Add a transposition table, iterative deepening and quiescence search (searching only captures and threats), and you are at amateur tournament level.

This “patch list” and the Deep Blue / AlphaGo evolution in the next chapter are the same road.

The skeleton stays put, the engineering ratchets up level by level — tic-tac-toe merely shrank the skeleton to its minimum.

The AI Difficulty Ladder

When you put an AI in a game, minimax is not the first rung, and needn’t be the only rung.

A full ladder by playing strength:

1. Random AI: uniformly pick a legal cell. For the easiest difficulty tier, and as a sparring partner for newcomers learning the rules;
2. Rule-based AI: hand-written priorities. Win if you can, block if you must, take the center first and a corner second. Thirty to fifty lines of code, already strong enough to beat most inexperienced humans, but every trick is played with open cards;
3. Minimax (+ alpha-beta): perfect strength — unbeatable, but forceable into a draw;
4. Depth-limited minimax: cap the search depth at 2–3 layers with a shallow evaluation function. Between rule-based and perfect, the most natural “medium difficulty”.

Worth a separate mention is tic-tac-toe’s role in reinforcement learning: it is Q-learning’s classic first lesson.

A Q-table of a few thousand cells stores value by position; the AI self-plays tens of thousands of games, nudging each entry by “actual outcome vs expected value” every time, and converges to near-minimax strength.

The whole training run finishes in a browser in seconds, which is why tic-tac-toe is also the smallest sandbox for “watching reinforcement learning learn to play for the first time”.

While we’re here, the data-structure side of “small” deserves its own note, because it too is part of the teaching sample: the board is a 1D array of length 9 with a placeholder for empty; the win lines are 8 hard-coded index groups (three rows, three columns, two diagonals), and terminal detection is scanning all 8 lines once each; draw detection is “board full and no win line”.

Add minimax’s dozen-odd lines of recursion, and a complete AI comes in under a hundred lines.

Every part it ought to have is small enough to fit on an interview whiteboard, which is exactly why it has been used in teaching for sixty years.

From Tic-Tac-Toe to Deep Blue and AlphaGo

The skeleton’s later evolution is plain to see:

• Deep Blue (1997): tic-tac-toe’s architecture plus brute-force engineering. Dedicated hardware, a finely honed evaluation function, 200 million positions per second. Chess’s tree is too large to enumerate; it won by “seeing far”;
• AlphaGo (2016): Go’s branching factor is about 250, and Deep Blue-style brute force fails completely. The solution replaced minimax’s “expand everything” with policy-network move selection + value-network evaluation + Monte Carlo tree search. Search stopped being enumeration and became “smart sampling” (the methodology of the stochastic methods article enters here); the evaluation function went from hand-written features to neural-network learning.

The parts of the skeleton that didn’t change are precisely the three things tic-tac-toe teaches: the adversarial assumption (the opponent’s strongest reply), lookahead (the farther you see, the stronger), and evaluation (pricing the leaves).

Only the engineering realization of each changed.

Hands On: Forcing Its Admission

Challenge the perfect AI on Tic-Tac-Toe. The goal isn’t to beat it. You can’t.

The goal is to force its admission: play every move strictly optimally and watch how it defends all the way to the draw; then deliberately make one wrong move and watch how it tightens the noose instantly.

Put those two experiences side by side and minimax’s pessimistic assumption turns from a formula into a feel.

Against human opponents there is a practical cheat sheet, and it agrees with minimax’s conclusions: as the first player, taking a corner induces mistakes better than taking the center (the center has too many symmetric replies, while corners branch into likelier errors), and once the opponent replies wrongly you can finish in one move with a “double threat” (two lines at once).

xkcd 832’s famous map of every response draws out the optimal reply for each position — essentially a hand-drawn minimax lookup table.

Genealogy Summary

Traversal, pathfinding and games are one “candidate container” skeleton unfolded across three generations of problems. The container goes from stack to queue to priority queue, the take-out key from “who was found first” to “who is nearest” to “who looks most promising”, until the opponent enters and the key becomes “the move the opponent least wants”. A* = Dijkstra + one navigation intuition that never overestimates; minimax = tree search + one pessimistic assumption that “the opponent replies perfectly”. Memorize the framework and a new algorithm is just a new container and a new assumption.

Game AI: From Perfect Search to Sampled Approximation

Tic-tac-toe shrank the skeleton of game search to its minimum; this chapter pulls the lens back, because the four games differ widely in their skill ceilings and their fitting algorithms, and the site’s four boards happen to occupy one tier apiece — Tic-Tac-Toe, Connect Four, Gomoku, Reversi. Two-player turn-based board games are AI’s oldest testing ground, because they compress “intelligence” into a clean mathematical structure: the two sides alternate moves, information is fully public, and one side’s gain is the other’s loss. Building an opponent for this class of games is essentially answering three progressive questions: can you search to the bottom (perfect search), if you cannot, how do you estimate (evaluation functions and pruning), what if the evaluation function cannot be written at all (sampling approximation). Minimax, alpha-beta pruning, and MCTS are precisely the three answers to those three questions.

Games as Search

First, draw the boundary of this world. What is discussed here are deterministic games that are zero-sum, perfect-information, and turn-based.

No hidden information on the board (unlike Dou Dizhu), no dice (unlike backgammon), and the winner’s payoff is the loser’s loss.

This class of games has a theorem proved by Zermelo as early as 1913: as long as the game must end within finitely many moves, then from any position both players have an “optimal move”. Either one side forces a win, or both force a draw.

Note that this conclusion has nothing to do with whether humans can find it; it only guarantees existence.

What stands between “a winning strategy exists” and “knowing what the winning strategy is” is the search problem.

The organizing rule of the game tree was already set up in the previous chapter: nodes alternate between two players with opposite interests — the layer where it is my turn (the MAX layer) takes the maximum of the children’s values, the layer where it is the opponent’s turn (the MIN layer) takes the minimum. “The opponent will do their utmost to ruin your day” is not a line of psychological description; it is the min operation of the MIN layer.

Minimax

With this tree, the definition of the optimal move becomes computable at once: score every terminal position (I win +1, I lose −1, draw 0), then work bottom-up, MAX layers taking the max and MIN layers the min. The engineering version carries a depth cap:

1
function minimax(pos, depth):
2
    if terminal or depth == 0: return evaluate(pos)
3
    if my turn:
4
        best = -∞
5
        for each legal move m: best = max(best, minimax(position after m, depth-1))
6
    else:
7
        best = +∞
8
        for each legal move m: best = min(best, minimax(position after m, depth-1))
9
    return best

The complexity is the branching factor b raised to the power d. $O(b^d)$, exponential explosion.

Whether it can be used directly depends entirely on how big the game tree is.

Tic-tac-toe is the smallest case on this threshold. 9 squares and at most 9 moves; legal game paths total 255168, and distinct boards after deduplication only 5478.

These two numbers deserve a careful count, because their accounting differs. Playing every game to the full nine moves gives $9! = 362880$ sequences, but the game terminates as soon as either side connects three, so the phantom moves played afterward must all be subtracted from the total; 255168 is exactly the count of real game paths stratified by termination time. And 5478 is the portion of the $3^9 = 19683$ raw grids that is reachable through legal play (the rest are all illegal boards that could appear only after someone had already won).

This magnitude is searchable to the bottom in an instant even on a phone, so the Tic-Tac-Toe AI needs no approximation whatsoever. Every one of its moves is a perfect decision made after searching the entire tree.

Playing against it you can at best force a draw: tic-tac-toe’s Zermelo answer is “both sides force a draw”. This has been proven by exhaustive search, not conjectured.

If you can beat it, it has a bug. If you always lose, you are walking the forced-loss branches.

Alpha-Beta Pruning

The mechanism of alpha-beta pruning was already taken apart in the previous chapter: it does not change minimax’s answer; it only cuts the branches that cannot affect the answer. α is the lower bound that the MAX layers along the current path have already secured, β the upper bound the MIN layers have pressed down; the moment α ≥ β, all remaining siblings are cut. Its efficiency depends enormously on move ordering, and in the best case the complexity drops from $O(b^d)$ to about $O(b^{d/2})$ — equivalent to doubling the search depth, which is where skill gaps under the same compute budget come from. Its first big stage is Connect Four (7×6 grid, first to connect four wins).

Connect Four’s full state space is on the order of $10^{13}$; searching directly to the bottom needs crowd-scale compute.

In 1988 Victor Allis, using extremely ingenious reasoning (plus search), proved that the first player wins by simply opening in the center column. One of the most famous results in the history of game search — but for ordinary play, full-width search is still over budget. So depth-limited alpha-beta became the standard configuration, with moves sorted by static evaluation before each layer’s search (or the previous iteration’s move tried first as a “killer move”), letting good moves narrow the window early.

The site’s Reversi turns this ladder into difficulty tiers. The mid tier is pure greed (count flipped discs, plus positional bonuses for corners and edges); the high tier is minimax with alpha-beta pruning, with leaves valued by a position weight table.

Corner +100, edge +10, and squares hugging a corner −15.

That last negative score deserves its own paragraph. In Reversi a corner, once occupied, can never be flipped again — the most solid ground on the board. While the square just outside a corner, once flipped away by the opponent, hands the corner over personally.

So “flip two fewer discs but take the corner” is master play, and “flip ten more discs but give away the corner” is suicide. This inversion of disc count and positional structure is exactly why evaluation functions exist: they write down, on the search’s behalf, what counts as good in this game.

The Evaluation Function

However fast alpha-beta gets, exponential is still exponential.

Gomoku is the standard-bearer of this law. A 15×15 board where every empty square is a candidate move, with the midgame branching factor hovering around 200. Each extra ply makes the tree 200 times bigger, and ten plies is $10^{23}$.

Unable to search to the bottom, you must force a stop at some depth and then answer one question: this leaf position — how many points is it worth?

That scoring function is the evaluation function, and it is where every board-game AI’s real chess sense lives.

The evaluation function also carries an easily ignored discipline of units: its scale must align with the terminal scores.

Terminals get +∞/−∞ (or huge numbers) to signify win and loss; the scores given to intermediate positions must fall on the same ruler as “how far from winning or losing”. An open four scores 9000, an open three 500, a single stone 1 — the logic being “an open four is one step from winning and outweighs a thousand scattered stones”.

An evaluation function with broken units (material scores drowning out win/loss scores) will search out blunders like “rather lose a stone than block the opponent’s five”. That is not the search’s fault; the ruler was drawn backwards.

What a Good Evaluation Function Looks Like

Writing an evaluation function has two failure modes pointing in opposite directions. Write it too coarse, and the AI has compute but no skill. Write it too fine, and each ply slows tenfold, amputating your own depth.

The recipes that work in practice usually reduce to a few hard metrics.

Run structures. In Gomoku the values of open threes, closed fours, and open fours are not linear. An open four (four in a row with both ends empty) means the next move wins, so its valuation must outweigh any number of open twos by orders of magnitude.

The site’s Gomoku evaluation function counts runs along four directions. For each candidate point it computes “own formation score × 1.1 + blocking the opponent’s formation score”, and that 1.1 asymmetry is an interesting detail. Your own formations are worth slightly more than blocking the opponent’s, which matches the chess principle of attack first.

One-ply threat detection. Run scores alone are not enough; after simulating a placement, ask two binary questions directly. Would placing here complete five for me immediately (add 1000000), would placing here complete five for the opponent immediately (add 500000, the obligation to block).

These two large numbers lift hard threats out of the statistical scores, keeping the evaluation function from being blinded by a pile of small ones.

Positional weights. Reversi’s corners and corner-adjacent squares, Gomoku’s piece density (a new stone landing near existing pieces earns a small density bonus) — the numerification of positional play.

Connect Four’s Rule-Based AI

One counterintuitive fact deserves its own look. The site’s Connect Four AI performs zero search; it is pure rules.

First find a column where it can connect four directly, then find a column where the opponent could and block it; failing both, prefer the center columns, then pick one at random among the highest-scoring columns.

That looks shabby, yet it is quite a handful for ordinary players. The reason is that Connect Four’s threats are forcing. Only 7 choices per move, and any “wins next move” threat must be answered immediately — there is no other road to take.

Under these conditions, “finding and executing the forced move” is nearly the entire benefit of shallow search, while the compute saved is all of it.

The contrast makes the evaluation function’s boundary of applicability clear. Games with many forced moves and small branching let rules stand in for search; games with large branching and threats that need multi-move construction (Gomoku’s double open threes, three-move kills) must search honestly.

This is also why the same “greed + threat detection” recipe suffices in Gomoku’s hard tier yet loses to those three hard rules in Connect Four. The games’ combinatorial structures differ, and the value for money of the same layer of intelligence differs completely.

MCTS

The end of the evaluation-function road is Go. 19×19, branching factor around 250, and more fatally a good position simply has no writable metric. The life and death of a lone group is not settled for dozens of moves, and every local feature is unreliable.

The paradigm shift of 2010s game AI happened right here: rather than have humans write evaluation functions, let the program sample for itself.

That is Monte Carlo Tree Search (MCTS), which replaces “evaluate” with “simulate randomly to the end and see who wins”.

Selection: from the root, each node picks a child by the UCB1 formula. $\frac{w_i}{n_i} + c\sqrt{\frac{\ln N}{n_i}}$ — the first term is win-rate exploitation, the second applies curiosity scaled by visit count (exploration).

Expansion: reaching a not-fully-expanded node, add one new child.

Simulation: from the new node, play fast and randomly to the end for a win or loss.

Backpropagation: accumulate the result back along the path, updating each node’s visit count and win count.

The longer the search runs, the more visits tilt toward the good branches; the root’s most-visited child is the recommended move.

The exploration constant c in UCB1 is the personality knob of the whole method. c too small, and the algorithm bets early on the currently highest win-rate branch, easily fooled by opening appearances into inferior lines. c too large, and sampling gets spread thin by egalitarianism, slowing convergence.

What it replaces is the position minimax reserved for the evaluation function, yet it introduces no human prior whatsoever. Chess sense vanishes from the code, replaced by pure statistics.

MCTS’s beauty is that it converges to minimax while never assuming an evaluation function. For Go it is brute force without chess sense, but sampling aims the brute force where it cuts deepest.

AlphaGo’s 2016 leap stuffed a neural network into each of two stages. A policy network prunes instead of random selection, a value network estimates the win rate directly instead of terminal simulation. MCTS’s skeleton unchanged, only the precision of each stage improved.

The weakness is inherited too. Sampling has variance, and MCTS is actually less stable than a few dozen plies of alpha-beta in one-glance endgames, because it may waste samples on obviously decided branches.

Nor are the two routes strangers: stuff minimax’s win/loss propagation inside MCTS’s tree (stop sampling at proven-win nodes and backpropagate the certain value directly) and you get the hybrid called MCTS-Solver. Sampling handles the open ground, deterministic propagation handles the endgame.

This echoes the layering from the previous chapter: no single weapon covers everything; the mature approach lets perfect search handle what it can handle, and sampling handle the rest.

The Engineering Trio

For depth-limited alpha-beta search to actually sit down and play, it needs three engineering accessories. Textbooks brush past them in a sentence, yet in practice they decide the skill tier of the very same algorithm.

Iterative deepening solves the problem of how many plies to set. Rather than guess a fixed depth, search one ply, then two, then three … until the time budget runs out, then hand over the last fully completed result.

It looks as though the earlier plies were all wasted work. In fact they were not: the previous depth’s best-move ordering feeds the next depth as a try-strong-moves-first hint (pruning efficiency soars as a result), and exponential search’s node counts concentrate in the last ply anyway, so the earlier plies’ combined cost is a rounding error of the total.

Iterative deepening also throws in one freebie: interruptible at any moment. Time is up; an answer one ply shallower still beats none. Any search facing an uncertain budget that must still produce a result can use this skeleton.

Transposition tables exploit a board-game-specific fact: different move orders can reach the same position. A then B, or B then A — same board.

Hash the position and store “the value found at depth d for this position” in a table; on re-encounter, look it up and return directly.

The savings are not small change. Transpositions come in swarms in midgame search, and hit rates often exceed half.

The engineering traps concentrate here too. Hash collisions return wrong values, so position and depth must be verified together. When unwinding moves, the validity of table entries must be managed along the way.

Quiescence search patches the crack left by depth truncation.

Stopping forcibly at the depth limit to evaluate has a systematic absurdity: the cutoff lands exactly midway through “a rook is being given away for free”. The evaluation function still sees the position “the rook is there”, and only the next ply would see it vanish.

This is the horizon effect: the search depth is like a horizon, and a disaster in progress simply does not exist as long as it is pushed beyond the line.

The patch: after truncation, do not stop; keep searching only captures and checks, the forcing moves, until the position quiets down, then evaluate.

Quiescence search has an unpredictable depth but extremely narrow branching, so the actual cost is controllable. Without it, any evaluation function flinches in the face of tactical combinations. It is also the number-one source of classic incidents like “the AI suddenly gives away a piece”.

The trio’s shared temperament: the algorithm unchanged, only optimizing how the same search spends faster.

Iterative deepening manages the budget, transposition tables manage repetition, quiescence search manages truncation quality. Their relationship to alpha-beta is like caching and indexes to the database query itself.

Four Games, Each in Its Place

Aligning the three weapons with the four boards takes one table.

The pattern surfaces: the AI scheme is not chosen by game complexity but by the ratio of search budget to state space.

Tic-tac-toe is small enough to be known completely.

Connect Four’s forcing structure lets shallow reasoning substitute for deep search.

Gomoku and Reversi must evaluate, and Reversi’s branching factor is small (typically about a dozen legal moves per turn), so the same compute searches several plies deeper — alpha-beta’s payoff is therefore especially pronounced on Reversi. This matches the play experience too: the Reversi AI shows the steepest skill staircase, while the Gomoku AI occasionally misses a killing move two steps out.

Engineering Difficulty Tiers

Player-facing AI has one last design layer: difficulty is not a continuous function of compute but stairs built on purpose.

Three approaches are common, each with a different feel.

One: cut the budget. Drop the search depth from five plies to two, and the strong AI instantly turns nearsighted — though it still grabs the tactics in front of it. Fits the mid tier.

Two: dumb down the evaluation. Strip the positional weight table and keep only material counting; the AI sees far but understands nothing. Reversi’s mid tier does exactly this (counting flipped discs plus simple corner and edge scores).

Three: inject controlled randomness. Pick randomly among the top-scored moves instead of always taking the maximum. The site’s Connect Four does this with its center preference when no forcing moves exist.

Three cuts correspond to three portraits of human opponents. The one who sees near, the one who does not understand, the one who gets sloppy. Good difficulty design imitates a person’s specific flaws, rather than dumbing down uniformly.

It is also the question most worth asking yourself when debugging game AI: at my difficulty tier, does losing look like a real person losing?

Looking back, this ladder is one answer to “which problem gets which algorithm”: if you can search fully, do not estimate; if you can prune, do not search fully; if the evaluation cannot be written, sample.

Each sentence corresponds to one negotiation between compute and problem size, and the only bargaining chip at the table is the problem’s own structure: forcing moves, branching width, evaluation feasibility.

Single-player puzzles tell the same budget-for-structure story; The Math in Four Puzzles covered four examples. Two-player games add one thing it lacks — a living opponent — so every valuation must be re-weighed under the premise that the opponent responds at their worst.

The fastest way to test this taxonomy is to go lose one game on each of the four boards. The manner of your losses (stalemated by perfect search, blocked out by rules, tricked out of a corner by the evaluation function, crushed by pruning depth) will act out each weapon’s personality for you directly.

Thanks for reading! Follow me if you'd like~

Seven Algorithm Lessons from Games

Sat Apr 04 2026

25668 words · 130 minutes

Algorithms & Data StructuresAlgorithmsMathematics

---

© MuxiaoWF | CC BY-NC-SA 4.0

Share

Share this article

X (Twitter)TelegramRedditFacebookEmailQQ

Close

Close