[colanderman]

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!

[danvk]

Annealing is mentioned a few times in the post but not discussed in any detail. I found that hill climbing with an expanded "pool" of boards and exhaustive search of neighbors was the most reliable way to get from a random starting point to the highest-scoring board: https://github.com/danvk/hybrid-boggle/blob/main/boggle/hill...

[colanderman]

Somehow my eyes missed that! Edited my comment.

[redfern314]

The article actually does mention using this technique, though it doesn't explain it, so thanks for the background from someone who isn't familiar with this space!

[athorax]

The article does indeed mention simulated annealing though?

[colanderman]

Somehow I didn't see that, good catch! (It's mentioned but not explained.) Edited my comment.

[tibbar]

oh that's very interesting. I've used this idea before in solvers but did not know that this is what it's called!