Introduction

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.

Climb the Landscape

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">Step</button>
  <button id="btnRun" type="button">Run</button>
  <button id="btnRestart" type="button">Random Restart</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<canvas id="canvas" width="560" height="280"></canvas>
<div class="info" id="info">Press Step or Run to start climbing.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Hill climbing on a 1-D bumpy landscape.
// The landscape is a fixed sum-of-sines with several local maxima.
// The climber moves in discrete steps of size STEP across [0,1].
// "Random restart" picks a new random start and climbs again.

const W = 560, H = 280;
const MARGIN = { top: 20, right: 20, bottom: 30, left: 44 };
const PLOT_W = W - MARGIN.left - MARGIN.right;
const PLOT_H = H - MARGIN.top - MARGIN.bottom;
const STEP = 0.01;   // neighborhood step size (±1 step)
const POINTS = 300;  // landscape resolution

// Landscape: sum of sines — bumpy but deterministic.
// Designed so the global max is near x≈0.46, with clear local maxima
// near x≈0.08, x≈0.17, x≈0.37, x≈0.65, x≈0.77 so any start on the
// left half (e.g. 0.05) gets visibly trapped well below the global peak.
function landscape(x) {
  return (
    0.45 * Math.sin(Math.PI * x) +
    0.35 * Math.sin(5.5 * Math.PI * x + 0.3) +
    0.20 * Math.sin(13 * Math.PI * x + 1.1) +
    0.10 * Math.cos(21 * Math.PI * x + 0.7)
  );
}

// Pre-compute y values and global max.
const xs = Array.from({ length: POINTS }, (_, i) => i / (POINTS - 1));
const ys = xs.map(landscape);
const yMin = Math.min(...ys);
const yMax = Math.max(...ys);
const globalMaxX = xs[ys.indexOf(yMax)];

// Map data coords -> canvas coords.
function cx(x) { return MARGIN.left + x * PLOT_W; }
function cy(y) { return MARGIN.top + PLOT_H - ((y - yMin) / (yMax - yMin)) * PLOT_H; }

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

// Climber state.
let pos = 0.1;   // x in [0,1]
let stuck = false;
let bestX = pos;
let bestY = landscape(pos);
let restarts = 0;
let runTimer = null;

function drawLandscape() {
  ctx.clearRect(0, 0, W, H);
  // Axes.
  ctx.strokeStyle = '#adb1b8';
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(MARGIN.left, MARGIN.top);
  ctx.lineTo(MARGIN.left, MARGIN.top + PLOT_H);
  ctx.lineTo(MARGIN.left + PLOT_W, MARGIN.top + PLOT_H);
  ctx.stroke();
  // Y tick labels.
  ctx.fillStyle = '#666';
  ctx.font = '11px system-ui';
  ctx.textAlign = 'right';
  for (let t = 0; t <= 4; t++) {
    const v = yMin + (t / 4) * (yMax - yMin);
    const py = cy(v);
    ctx.fillText(v.toFixed(1), MARGIN.left - 4, py + 3.5);
    ctx.strokeStyle = '#e8eef3';
    ctx.lineWidth = 0.8;
    ctx.beginPath(); ctx.moveTo(MARGIN.left, py); ctx.lineTo(MARGIN.left + PLOT_W, py); ctx.stroke();
  }
  // Landscape curve.
  ctx.beginPath();
  ctx.strokeStyle = '#1d3557';
  ctx.lineWidth = 2.2;
  xs.forEach((x, i) => {
    const px = cx(x), py = cy(ys[i]);
    i === 0 ? ctx.moveTo(px, py) : ctx.lineTo(px, py);
  });
  ctx.stroke();
  // Global max marker (dashed vertical).
  ctx.setLineDash([4, 3]);
  ctx.strokeStyle = '#0a7d33';
  ctx.lineWidth = 1.2;
  ctx.beginPath();
  ctx.moveTo(cx(globalMaxX), MARGIN.top);
  ctx.lineTo(cx(globalMaxX), MARGIN.top + PLOT_H);
  ctx.stroke();
  ctx.setLineDash([]);
  // Global max label.
  ctx.fillStyle = '#0a7d33';
  ctx.font = '11px system-ui';
  ctx.textAlign = 'left';
  ctx.fillText('global max', cx(globalMaxX) + 4, MARGIN.top + 14);
  // Best-found dot (outline).
  const bpx = cx(bestX), bpy = cy(bestY);
  ctx.beginPath();
  ctx.arc(bpx, bpy, 7, 0, 2 * Math.PI);
  ctx.fillStyle = 'rgba(10,125,51,0.20)';
  ctx.fill();
  // Current climber dot.
  const ppx = cx(pos), ppy = cy(landscape(pos));
  ctx.beginPath();
  ctx.arc(ppx, ppy, 7, 0, 2 * Math.PI);
  ctx.fillStyle = '#e63946';
  ctx.fill();
}

function setInfo(msg, cls) {
  const el = document.getElementById('info');
  el.textContent = msg;
  el.className = 'info' + (cls ? ' ' + cls : '');
}

function clamp(x) { return Math.max(0, Math.min(1, x)); }

function step() {
  if (stuck) return false;
  const cur = landscape(pos);
  const left = landscape(clamp(pos - STEP));
  const right = landscape(clamp(pos + STEP));
  const best = Math.max(left, right);
  if (best <= cur) {
    stuck = true;
    const y = landscape(pos);
    if (y > bestY) { bestY = y; bestX = pos; }
    const isGlobal = Math.abs(pos - globalMaxX) < 0.05;
    drawLandscape();
    if (isGlobal) {
      setInfo(fmt('Reached the global maximum! x = %pos%, y = %y%', { pos: pos.toFixed(2), y: y.toFixed(3) }), 'global');
    } else {
      setInfo(fmt('Stuck on a local maximum. x = %pos%, y = %y%. Try a Random Restart.', { pos: pos.toFixed(2), y: y.toFixed(3) }), 'stuck');
    }
    return false;
  }
  if (right >= left) pos = clamp(pos + STEP);
  else pos = clamp(pos - STEP);
  const y = landscape(pos);
  if (y > bestY) { bestY = y; bestX = pos; }
  drawLandscape();
  setInfo(fmt('Climbing… x = %pos%, y = %y%', { pos: pos.toFixed(2), y: y.toFixed(3) }));
  return true;
}

function stopRun() {
  if (runTimer !== null) { clearInterval(runTimer); runTimer = null; }
}

document.getElementById('btnStep').addEventListener('click', () => {
  stopRun();
  step();
});
document.getElementById('btnRun').addEventListener('click', () => {
  stopRun();
  if (stuck) return;
  runTimer = setInterval(() => { if (!step()) stopRun(); }, 60);
});
document.getElementById('btnRestart').addEventListener('click', () => {
  stopRun();
  pos = Math.random();
  stuck = false;
  restarts++;
  drawLandscape();
  setInfo(fmt('New random start at x = %pos%. Press Run.', { pos: pos.toFixed(2) }));
});
document.getElementById('btnReset').addEventListener('click', () => {
  stopRun();
  pos = 0.1;
  stuck = false;
  restarts = 0;
  bestX = pos;
  bestY = landscape(pos);
  drawLandscape();
  setInfo('Press Step or Run to start climbing.');
});

// Initial draw.
drawLandscape();
setInfo('Press Step or Run to start climbing.');
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/hill-climbing/Content licensed under CC BY-NC 4.0.