After 20 years, the globally optimal Boggle board
1–10 of 25 posts
Re: After 20 years, the globally optimal Boggle board
#2My first thought is that there is surely an Integer Linear Programming approach that can solve this within a few seconds using some very advanced solver like Gurobi.
These solvers can very often find the globally optimal solution - and prove that this solution is optimal - much faster than exhaustive search.
Of course they do use a smart exhaustive search by applying branch-and-bound as described in this article, but advanced solvers use, among other things, branch-and-cut where cutting planes in the solution space are generated, as well as a variety of other approaches.
One interesting thing however is that GPUs are still not particularly applicable for solvings Mixed Integer Linear Programs to sufficient accuracy. There are things like PDLP that can use GPUs to solve these problems, but they are restricted to something like 1e-4 accuracy whereas the state of the art is more like 1e-9.
Re: After 20 years, the globally optimal Boggle board
#3Simulated 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!
Re: After 20 years, the globally optimal Boggle board
#4My first thought is that there is surely an Integer Linear Programming approach that can solve this within a few seconds using some very advanced solver like Gurobi. These solvers can very often find the globally optimal solution - and prove that this solution is optimal - much faster than exhaustive search. Of course they do use a smart exhaustive search by applying branch-and-bound as described in this article, but…
I actually did try ILP, see https://stackoverflow.com/questions/79422270/why-is-my-z3-an...
I tried Z3 and OR Tools. I didn't try Gurobi. But this was enough to make me think ILP was a dead end. (There were a lot of dead ends in this project.)
I don't know much about integer programming, though, and I'd love to be proven wrong.
Re: After 20 years, the globally optimal Boggle board
#5Simulated 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: Someho…
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!
Re: After 20 years, the globally optimal Boggle board
#6Simulated 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: Someho…
The article does indeed mention simulated annealing though?
Re: After 20 years, the globally optimal Boggle board
#7My first thought is that there is surely an Integer Linear Programming approach that can solve this within a few seconds using some very advanced solver like Gurobi. These solvers can very often find the globally optimal solution - and prove that this solution is optimal - much faster than exhaustive search. Of course they do use a smart exhaustive search by applying branch-and-bound as described in this article, but…
I actually did try ILP, see https://stackoverflow.com/questions/79422270/why-is-my-z3-an... I tried Z3 and OR Tools. I didn't try Gurobi. But this was enough to make me think ILP was a dead end. (There were a lot of dead ends in this project.) I don't know much about integer programming, though, and I'd love to be proven wrong.
I saw that! In my experience, problems that seem completely intractable using open source tools often get solved in seconds using state of the art commercial approaches.
Re: After 20 years, the globally optimal Boggle board
#8Simulated 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: Someho…
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...
Re: After 20 years, the globally optimal Boggle board
#9Simulated 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: Someho…
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.
Re: After 20 years, the globally optimal Boggle board
#10Simulated 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: Someho…
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.