hybrid-boggle

Finding the highest-scoring board with a 16- or 17-letter word is a fun, but very different problem. There are few enough "Hamiltonian paths" through the all the letters on a 4x4 Boggle board (~68,000) and few enough 16 letter words (~2,000) that you can enumerate all pairs in an hour or two. Depending on wordlist and whether you want a 16 or 17 letter word, you get "charitablenesses", "supernaturalised" (British spelling), "quadricentennials" or "quartermistresses". These boards all score considerably lower than the REPLASTERING board. Full results here: https://github.com/danvk/hybrid-boggle/#highest-scoring-boar... I hadn't realized until I did this "side quest" that most wordlists top out at 15 letter words. That makes sense for a Scrabble dictionary, but it's not great for Boggle.

There are simpler ways to calculate a bound that don’t involve trees. You can read about the sum and max bounds in the WIP paper: https://github.com/danvk/hybrid-boggle/blob/main/paper There are some examples in these old posts: - https://www.danvk.org/wp/2009-08-08/breaking-3x3-boggle/inde... - https://www.danvk.org/wp/2009-08-11/a-few-more-boggle-exampl... These bounds are pretty effective at finding the global max for 3x3 Boggle, but 4x4 is a lot bigger. There is a mapping from Boggle optimization to ILP, but I’ve seen no evidence that this is an efficient way to solve it. I’ve been told that branch and cut is usually better than branch and bound, but I don’t know whether it’s applicable to Boggle.

You might find the answer in the README: https://github.com/danvk/hybrid-boggle/blob/main/paper%2FREA... Scroll down to 'Sum/Choice trees' or Ctrl+F max_bound

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.

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).

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...