[HN Gopher] A Computational Proof of the Highest-Scoring Boggle ...
___________________________________________________________________
A Computational Proof of the Highest-Scoring Boggle Board
Author : danvk
Score : 60 points
Date : 2025-04-23 17:45 UTC (5 hours ago)
(HTM) web link (www.danvk.org)
(TXT) w3m dump (www.danvk.org)
| LPisGood wrote:
| My 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.
| danvk wrote:
| 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.
| LPisGood wrote:
| 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.
| danvk wrote:
| If you want to give it a try, I'd love to hear if that's
| the case! It's deleted in the repo now, but here's code to
| generate a spec for an ILP solver:
| https://github.com/danvk/hybrid-
| boggle/blob/62d3f01aed802734...
|
| One interesting thing about Boggle is that the number of
| variables (16 cells) is very small compared to the number
| of coefficients on how they combine (the number of possible
| words).
| LPisGood wrote:
| I am very intrigued by this. I'll do something thinking
| this evening about how a tight Boggle model may look.
| danvk wrote:
| Great! Feel free to reach out -- my email isn't hard to
| find.
| colanderman wrote:
| 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!
| redfern314 wrote:
| 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 wrote:
| The article does indeed mention simulated annealing though?
| colanderman wrote:
| Somehow I didn't see that, good catch! (It's mentioned but
| not explained.) Edited my comment.
| danvk wrote:
| 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 wrote:
| Somehow my eyes missed that! Edited my comment.
| tibbar wrote:
| oh that's very interesting. I've used this idea before in
| solvers but did not know that this is what it's called!
| oliwary wrote:
| Fun, love word game computations! Reminds me a bit of the
| challenge to place the challenge to place all letters in the
| alphabet in as small a grid as possible, with valid words:
| https://gamepuzzles.com/alphabest.htm
|
| I made a word game based on a similar concept, featuring
| different letters every day: https://spaceword.org
| pavel_lishin wrote:
| My favorite part of the write-up is the first sentence after the
| "What if there's a bug?" section.
| 1024core wrote:
| Where can I find the wordlist that they used?
|
| Edit: Found it here:
| https://coursera.cs.princeton.edu/algs4/assignments/boggle/f...
| danvk wrote:
| You can see all the wordlists I used here:
| https://github.com/danvk/hybrid-boggle/tree/main/wordlists
|
| The proof used ENABLE2K -- repeating it for other wordlists
| would require another ~23,000 CPU hours each.
___________________________________________________________________
(page generated 2025-04-23 23:00 UTC)