Local Search: Hill Climbing

Hill-Climbing Search

The simplest local search. Always move to the best neighboring state.

function HILL-CLIMBING(problem) returns a state that is a local maximum
    current ← INITIAL-STATE(problem)
    loop do
        neighbor ← highest-valued successor of current
        if VALUE(neighbor) ≤ VALUE(current) then return current
        current ← neighbor

• O(1) memory — no frontier
• No backtracking
• Returns when no neighbor improves on current state

Three Failure Modes

1. Local Maxima

A state better than all neighbors but not the global maximum. The algorithm terminates here — stuck.

2. Ridges

A sequence of states each of which is a local maximum viewed from the sides, but where the path along the ridge keeps improving. Standard hill climbing picks an arbitrary move direction and gets stuck.

3. Plateaus

A flat region where multiple neighbors have equal value. Two variants: - Flat local maximum: no uphill exit — truly stuck - Shoulder: plateau with an uphill edge reachable eventually

Statistic: For the 8-queens problem, steepest-ascent hill climbing gets stuck ~86% of the time. But restarts solve it quickly — median ~4 steps from good starts.

Variants

Stochastic Hill Climbing

Choose randomly among all uphill moves (not the steepest). Explores more of the uphill space. Slower but sometimes finds better local optima.

First-Choice Hill Climbing

Generate successors randomly; take the first one that improves current. Good when branching factor is large (generating all successors is expensive).

Random-Restart Hill Climbing

Repeat from random initial states until goal found.

If each hill climb succeeds with probability p, expected restarts = 1/p.

Key insight: For 8-queens, random restart is very effective — average ~21 steps (7 steps of climbing + 14 wasted on failures). Complete in the limit (asymptotically).

Sideways Moves

Allow moves to neighbors with equal value (escape flat local maxima / shoulders):

if VALUE(neighbor) < VALUE(current) then return current
# allow == case

• Risk: infinite loop on flat local maxima
• Fix: limit number of consecutive sideways moves (e.g., max 100)
• Effect for 8-queens: success rate 94% → 100% (with sideways limit)

Properties

Connection to DynamICCL

• NCCL parameter tuning (buffer size, chunk size, algorithm) = optimization over a discrete landscape
• Hill climbing can quickly find good parameter configurations without exhaustive search
• Random-restart hill climbing suits situations where multiple locally good configs exist (different network topologies)