Comment by colanderman
5 days ago
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!
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...
Somehow my eyes missed that! Edited my comment.
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!
The article does indeed mention simulated annealing though?
Somehow I didn't see that, good catch! (It's mentioned but not explained.) Edited my comment.
oh that's very interesting. I've used this idea before in solvers but did not know that this is what it's called!