Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

After 20 years, the globally optimal Boggle board

danvk.org

Post reply on HN
Print view View original

11–20 of 25 posts

Re: After 20 years, the globally optimal Boggle board

#11

Post by danvk »

LPisGood wrote: post #7
danvk wrote: post #4

Earlier quoted context omitted.

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.

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

Re: After 20 years, the globally optimal Boggle board

#12

Post by LPisGood »

danvk wrote: post #11
LPisGood wrote: post #7

Earlier quoted context omitted.

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.

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

I am very intrigued by this. I’ll do something thinking this evening about how a tight Boggle model may look.

Re: After 20 years, the globally optimal Boggle board

#13

Post by [deleted] »

colanderman wrote: post #3

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: Someho…

[deleted]

Re: After 20 years, the globally optimal Boggle board

#14

Post by danvk »

LPisGood wrote: post #12
danvk wrote: post #11

Earlier quoted context omitted.

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

I am very intrigued by this. I’ll do something thinking this evening about how a tight Boggle model may look.

Great! Feel free to reach out -- my email isn't hard to find.

Re: After 20 years, the globally optimal Boggle board

#15

Post by oliwary »

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

Re: After 20 years, the globally optimal Boggle board

#18

Post by danvk »

1024core wrote: post #17

Where can I find the wordlist that they used? Edit: Found it here: https://coursera.cs.princeton.edu/algs4/assignments/boggle/f...

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.

Re: After 20 years, the globally optimal Boggle board

#19

Post by tibbar »

colanderman wrote: post #3

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: Someho…

oh that's very interesting. I've used this idea before in solvers but did not know that this is what it's called!

Re: After 20 years, the globally optimal Boggle board

#20

Post by joefkelley »

This reminded me of one of my high school computer science assignments- simply to find all words in a single boggle board. And try to optimize your solution a bit. The point was to teach about recursion/backtracking and data structures. The intended solution was roughly: start at a square, check if your current prefix is a valid prefix, move to a neighbor recursively, and emit any words you find. Trying to optimize naturally motivates a trie data structure.

I found it to be at least an order of magnitude faster, though, to invert the solution: loop through each word in the dictionary and check whether it exists in the grid! The dictionary is small compared to the number of grid paths, and checking whether a word exists in the grid is very very fast, requiring not much backtracking, and lends itself well to heuristic filtering.

Post reply on HN