3 ms·
Simulated annealing [1] is mentioned but not explained in the list of modifications to hill climbing. The technique roughly is: accept modifications to the boa
by colanderman 1y 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 https://en.wikipedia.org/wiki/Simulated_annealing
EDIT: Somehow I didn't see that simulated annealing was mentioned by name (but not explained), ha!
- redfern314 1y agoThe 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 1y agoThe article does indeed mention simulated annealing though?
- colanderman 1y agoSomehow I didn't see that, good catch! (It's mentioned but not explained.) Edited my comment.
- danvk 1y agoAnnealing 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/hillclimb.py https://github.com/danvk/hybrid-boggle/blob/main/boggle/hill...
- colanderman 1y agoSomehow my eyes missed that! Edited my comment.
- deleted 1y ago[deleted]
- tibbar 1y agooh that's very interesting. I've used this idea before in solvers but did not know that this is what it's called!