Simulated annealing [1] is mentioned but not explained in the list of modifications to hill climbing. The technique roughly is: accept modifications to the board which decrease the score, with a probability inversely related to the magnitude of the decrease, and which decreases as the search progresses. This helps avoid getting stuck in local maximae.
[1] https://en.wikipedia.org/wiki/Simulated_annealing
EDIT: Somehow I didn't see that simulated annealing was mentioned by name (but not explained), ha!