Hill Climbing

Imagine you are dropped onto a hilly landscape in thick fog. You can feel the slope under your feet but you cannot see the terrain ahead. Your goal: reach the highest point. The simplest strategy — always step in the direction that goes most steeply upward — is called hill climbing.

As an algorithm, hill climbing is just as literal. You start at some solution, look at all its neighbors (small changes you could make), and move to whichever neighbor improves your score the most. Repeat until no neighbor is better than where you are. At that point the algorithm stops — it has found a local maximum.

The strategy is fast, needs almost no memory, and works surprisingly well in practice. It underpins everything from early AI game-playing to modern neural-network training. But it carries a fundamental weakness: a local maximum is not necessarily the global maximum. The hill you climb might be a molehill next to a mountain you never even see.

That gap between "good enough nearby" and "best overall" is not a bug you can fix with more code. It reflects something deep about the structure of optimization itself.

The bumpy curve below is your landscape — the horizontal axis is a solution, the vertical axis is its quality (higher = better). The red dot is the current position of the climber.

<div class="controls">
  <button id="btnStep" type="button">{{btn_step}}</button>
  <button id="btnRun" type="button">{{btn_run}}</button>
  <button id="btnRestart" type="button">{{btn_restart}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="560" height="280"></canvas>
<div class="info" id="info">{{prompt_start}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; background: #fff; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; width: 100%; max-width: 560px; height: auto;
         border: 1px solid #cdd9e3; border-radius: 8px; }
.info { margin-top: .55rem; font-size: .92rem; font-weight: 600; min-height: 1.4em; color: #1d3557; }
.info.stuck { color: #c92f3c; }
.info.global { color: #0a7d33; }

// Code not found

Press Step to move one step uphill. Press Run to let the climber ascend until it gets stuck. Then press Random Restart to drop the climber at a new random position and try again. Notice how the first run often lands on a local peak — a bump that looks like the top from nearby but is nowhere near the global maximum. Multiple restarts explore different basins of attraction and improve the odds of finding the true summit.

Hill climbing is fast by design: each step scans the neighborhood and moves to the best neighbor — polynomial time per step, linear space. The problem is completeness.

• Local vs global: a local maximum is a point where every neighbor is worse. Finding one is easy; knowing whether it is the global maximum is hard. On most real landscapes there are exponentially many local maxima.
• No global guarantee: hill climbing can stop at any local maximum and declare victory. For NP-hard problems like P vs NP instances — the Travelling Salesman Problem, graph coloring, bin packing — the landscape is rugged and the best local peak may be far from optimal.
• Variants that help: random restarts run hill climbing many times from random starts and keep the best result. Simulated annealing occasionally accepts a worse move early on, letting the algorithm escape local traps by cooling the acceptance probability over time. Genetic algorithms maintain a population of solutions and combine them. None of these guarantees optimality, but they dramatically improve results in practice.
• The landscape metaphor is literal: the difficulty of optimization corresponds directly to how rugged the fitness landscape is. Smooth unimodal landscapes are solved by a single hill climb; jagged multimodal ones require population-based or stochastic methods.

The status of hill climbing is therefore: solved in the sense of being fully understood — its convergence to a local optimum is guaranteed, its failure to find the global optimum is also guaranteed on adversarial inputs. The interesting question is not whether it gets trapped, but how often and how badly on real-world problem instances.

Despite its limitations, hill climbing is arguably the most widely used optimization idea in all of computer science:

• Neural network training: gradient descent is hill climbing on a smooth, high-dimensional landscape. Stochastic gradient descent (SGD) adds noise that doubles as a random-restart mechanism, helping escape sharp local minima.
• Chip placement: placing millions of transistors on a die to minimize wire length is a classic combinatorial problem. Google's 2021 paper used reinforcement learning — a form of hill climbing in policy space — to beat human experts.
• Robotics and control: a robot learning to walk optimizes a reward function over motion parameters. Hill climbing in parameter space often finds good gaits faster than model-based planning.
• Scheduling and logistics: employee timetables, truck routes, and satellite task assignments are all optimized with local-search variants of hill climbing (tabu search, large neighbourhood search).
• Game AI: early chess programs used iterative deepening with hill climbing in the evaluation function. Modern engines like Stockfish still tune their weights with gradient-free local search.

Wherever brute-force enumeration is impossible and gradient information is absent, some form of hill climbing fills the gap. Understanding when it works — and when the landscape is too rugged — is a core skill in algorithm design. See also non-convex optimization for the machine-learning angle.

Hill climbing captures a beautiful tension in algorithm design: the simplest reasonable strategy — always move to the best neighbor — is both remarkably effective and provably incomplete. It runs fast, uses almost no memory, and often finds solutions good enough for practice. Yet it can be defeated by any landscape with more than one peak.

Random restarts, simulated annealing, and evolutionary algorithms all extend hill climbing with different ways of escaping local traps. But none of them eliminate the core challenge: hard optimization landscapes are hard. The local maxima are not an artifact of naive code — they are a structural property of the problem.

Next time an algorithm seems stuck or a machine-learning model stops improving, you are probably watching hill climbing hit a local maximum. The question is never whether local optima exist — they always do — but whether the ones you find are good enough for what you need.