Stuck at local Maxima: Hill-climbing strategies have a tendency to become stuck at local maxima. If they reach a state that has a better evaluation than any of its children, the algorithm halts.

If this state is not a goal, but just a local maximum, the algorithm may fail to find the best solution.

That is, performance might well improve in a limited setting, but because of the shape of the entire space, it may never reach the overall best.

An example of local maxima in games occurs in the 8-puzzle. Often, in order to move a particular tile to its destination, other tiles already in goal position need be moved out. This is necessary to solve the puzzle but temporarily worsens the board state. Because "better" need not be "best" in an absolute sense, search methods without backtracking or some other recovery mechanism are unable to distinguish between local and global maxima.

Multiple Local Maxima: hill-climbing functions can have multiple local maxima, which frustrates hill-climbing methods. For example, in 8-puzzle problem consider the goal state & initial state as below

Any applicable rule applied to the initial state description lowers value of our hill-climbing function. In this case the initial state description is a local (but not a global) maximum of the function.

Stuck on plateaus & ridges: The hill climbing algorithm may get the problem stuck on plateaus & ridges

End-bunching: Instant insanity problem where the goal of the puzzle is to arrange the cubes one on top of the other in such a way that they form a stack four cubes high, with each of the four sides having exactly one red, one blue, one green, & one white cubes.

The goal state could be characterized exactly as having each of the four colours represented on each of the four vertical sides. Hence, we may consider the beginning state to have the evaluation vector (4, 4, 4, 4). The four dimensions could rather naturally be combined into a one-dimensional evaluation function simply by summing the four components. In obtaining this sum, it seems natural to give equal weight to each component, since each dimension has the same range of values and an analogous meaning. Hill climbing here greatly reduces the search space, but the method still leaves a very large number of alternatives to investigate. There are many equivalent options at each of the four nonterminal nodes of the state-action tree for Instant Insanity, so hill climbing with this evaluation function hardly yields the answer with a single series of four choices. The difficulty with this state evaluation function applied to this problem is that it is much harder to increase the evaluation function by the required amount at the last (fourth) choice node than at earlier nodes. At most of the last nodes, no action will achieve the goal, even though the solver is currently at a node that has the evaluation (3, 3, 3, 3). Whether or not you can solve the problem is determined by existence of such an action at the fourth node, but the evaluation function for the states that could be achieved at earlier nodes gives very inadequate information concerning the “correct” fourth node at which to be. That is, there are many fourth nodes with the evaluation (3, 3, 3, 3), and very few of these have any action that leads to a terminal node with the evaluation (4, 4, 4, 4). There are many problems like this, where the restrictions bunch up at the end of the problem. It is as if you had many easy trails to climb most of the way up a mountain, but the summit was attainable from only a few of these trails, with the rest running into unscalable precipices. Hill climbing is often not a very good method to use in such cases, though it may considerably reduce the amount of trail-and-error search.

The end-bunching of restrictions is a difficulty with hill climbing that is somewhat analogous to the local maximum difficulty.

Detours and Circling: Problems with multiple equivalently valued paths at the early nodes can be difficult to solve with hill climbing, but perhaps the greatest frustration in using the method comes in detour problems, where at some node you must actually choose an action that decreases the evaluation. Somewhat less difficulty is encountered in what might be called circling problems, where at one or more nodes you must take actions that do not increase the evaluations. If the nodes where you must detour or circle have no better choices (that is, no choices that increase the evaluation), then you are more likely to try detouring or circling than if the critical nodes have better choices. When better choices are available, you tend to just choose them and go on without considering the possibility of detouring or circling. If the path you choose does not lead to the goal, you might go back and investigate alternative paths, but the first ones to be investigated will be those that were equivalent or almost equivalent at some previous node. Only after all of this fails should you try detouring – that is, choosing an action at some node that produces a state that has a lower evaluation than the previous state had.

The missionaries-and-cannibals problem is a famous example of the difficulties encountered by hill climbing in detour problem.

Inference Problems: The description of the problem state must generally be considered to include the entire set of expressions given or derived up to that point. Since the goal isusually asingleexpression, it is generally much more difficult todefine an evaluation function that isuseful for hill climbing that compares the current state with the goalstate. Another reason for the greater difficulty in using hill climbing in inference problems is that the non-destructive operations frequently found in such problems are often not one-to-one operations-that is, operations that take one expression as input and produce one expression as output. There are such one-to-one operations, of course. However, in addition, inference problems usually contain a variety of two-to-one, and three-to-one, or even more complex operations-that is, operations that take two or three or more expressions as input and produce one expression as the output (the inferred expression).