Class of searching algorithms which try to improve a single option until no longer possible. Unlike tree search, these algorithms do not keep track of unexplored alternatives, meaning completeness and optimality are traded for speed and memory efficiency.
Informed searching algorithm which starts at an arbitrary state and moves to the best successor state (as determined by a heuristic) until no such improvement can be made.
Hill Climbing (**problem**) -> **solution state**:
**current** <- choose a state from **problem**
**loop do:
neighbor** <- highest-valued successor of **current**
if value[**neighbor**] <= ****value[**current**]:
return **current**.state
else:
**current** <- **neighbor**
Probabilistic searching algorithm which escapes local maxima by allowing downhill moves which become rarer as time goes on.
Temperature $T$. Proportional with how likely we are to move on to a suboptimal successor state. This fluctuates according to a scheduler.
Change in Free Energy $\Delta E$. This is the change in value, as assigned by a heuristic or objective function, between the current state and the successor state.
The algorithm proceeds by arbitrarily choosing an initial state, randomly selecting a successor variable, and, if it is suboptimal, we move to that state with probability $e^{\frac{\Delta E}{T}}$. If $T$ is decreased slowly enough, then the algorithm reaches the global maximum with probability approaching 1.
Simulated Annealing (**problem**, **scheduler**) -> **solution state**:
**current** <- choose a state from **problem**
for **t** = 1 : ∞:
**T** <- **scheduler**[t]
if **T** = 0:
return **current**
**next** <- choose a random successor of **current**
Δ**E** <- value[**next**] - value[**current**]
if Δ**E** > 0:
**current** <- **next**
else:
**current** <- **next** with probability e^(Δ**E**⁄**T**)
Games are environments involving more than 1 agent, where the goal is to find a policy $S \rightarrow A$ which recommends an action to take at a given state. They can be formulated in a very similar way as search problems, hence they are sometimes referred to as adversarial search problems.