9 ms·

Lone coder cracks 50-year puzzle to find Boggle's top-scoring board

176 points by DavidSJ 1y ago

smcin 1y ago
His blog post announcing it: https://www.danvk.org/2025/04/23/boggle-solved.html https://www.danvk.org/2025/04/23/boggle-solved.html FT article: https://archive.ph/siaAO https://archive.ph/siaAO His blog: https://www.danvk.org/blog.html https://www.danvk.org/blog.html > Driven “by the thrill of discovery”, Vanderkam has searched for this board, essentially alone, since 2004. He would scrape together computing time on Google’s hardware for heavy Boggle computation, all along documenting his efforts on his blog. > “As far as I can tell, I’m the only person who is actually interested in this problem,” Vanderkam said.
- danvk 1y ago
  > “As far as I can tell, I’m the only person who is actually interested in this problem,” Vanderkam said. For context, many people are interested in finding high-scoring Boggle boards, usually via simulated annealing, hillclimbing, or genetic algorithms. But so far as I can tell, I'm the only one interested in _proving_ that a particular board is best. Doing that was the new result here.
  - hamburglar 1y ago
    I once spent a little time writing code to find the longest possible boggle word and found there were a few candidates. Interesting things I noted that weren’t entirely obvious: the longest word is actually 17 characters, not 16, because of the “Qu” side, and there are actually lots of words that are impossible, because for example there is only one J and only one B and they are on the same die. I don’t remember all the longest words but sesquicentennials was one of them.
    - danvk 1y ago
      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-boards-containing-a-16--or-17-letter-word 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.
      - smcin 1y ago
        Ok so English max is 3,625 points from 1,045 words (with ENABLE2K word list). Why not compute the max possible Boggle board for other languages: French, Spanish, German, Italian, Portuguese, Czech... they each have a different set of 16 dice x 6 faces [], and of course totally different wordlists: [boardgames.SE] "What is the dice configuration for Boggle in various languages?" https://boardgames.stackexchange.com/questions/29264/boggle-what-is-the-dice-configuration-for-boggle-in-various-languages https://boardgames.stackexchange.com/questions/29264/boggle-... [] some languages' Boggle dice sets have 25x6 faces
        danvk 1y ago
        It's open source, take a crack at it! Or file an issue requesting it. This analysis doesn't make use of the Boggle dice. It assumes that any cell can be any letter. In practice, all high-scoring boards can be rolled with the Boggle dice. My code does assume the letters are A-Z, though, so the Ñ die in Spanish Boggle would require some code changes.
        smcin 1y ago
        Ok, but then a) we'd need to refine the issue to "enhance request to handle every non-ASCII character/digram that could occur in other Boggle languages": - Spanish: ñ - Czech: no extra characters (e.g. 'E' can be used in words as E, É and Ì) - Danish/Norwegian: do Boggle dice use æ,å,ø ? I searched but couldn't find out. - Swedish: do Boggle dice use å,ä,ö ? - Turkish: do Boggle dice use ç,ı,ğ,ş,ö,ü ? - Bosnian: see https://boardgames.stackexchange.com/a/51289/2358 https://boardgames.stackexchange.com/a/51289/2358 - Filipino: ñ . And separately in some wordgames (e.g. Scrabble knockoffs), I see 'ng' treated as a single digraph. Apparently it's officially a separate digraph, so the Tagalog alphabet ('abakada') has 28 letters. And b) if we have rare characters on a few dice (esp. the unofficial Bosnian one proposed), that imposes restrictions on your assumption that any cell can be any letter. So you'd have to postprocess to cull a few words that couldn't legally be made with that dice-set.
matt3210 1y ago
[flagged]
- haxton 1y ago
  > The former Google employee It's literally like the 3rd sentence...
robinhouston 1y ago
It was a fun surprise to see this story on the front page of this morning's Financial Times. It's very unusual in my experience for this sort of thing to be picked up by the mainstream media before it's on HN or similar. I wonder how the FT reporter came across the story.
- wdumaresq 1y ago
  This was posted on HN about a month ago: https://news.ycombinator.com/item?id=43774702 https://news.ycombinator.com/item?id=43774702
  - robinhouston 1y ago
    Thanks. What's particularly embarrassing is that I found that submission this morning, and read the comments on it, and then somehow forgot about its existence until you reminded me of it just now.
  - jonplackett 1y ago
    Thank you. I felt something must have been seriously wrong in the world that the FT knew this before any HN contributor.
    - noitpmeder 1y ago
      The author himself was the original submitter.
  - dang 1y ago
    Thanks! Macroexpanded: After 20 years, the globally optimal Boggle board - https://news.ycombinator.com/item?id=43774702 https://news.ycombinator.com/item?id=43774702 - April 2025 (23 comments) How did that spend only 6 hours on HN's frontpage? I'm gonna email danvk right now
- danvk 1y ago
  "Lone coder" here. I reached out to Ollie (the FT reporter) because he'd written a book (Seven Games) about computers and games, so I thought the Boggle story might interest him. It did!
cgreerrun 1y ago
> The code is a mixture of C++ for performance-critical parts and Python for everything else. They’re glued together using pybind11, which I’m a big fan of. Nice, I'm a big fan of this combo! Hits the right balance of prototype speed plus performance.
everyone 1y ago
I love scrabble and boggle, but to me there is tension between just playing for points according to a certain set of rules, and playing to form nice satisfying words.. eg. in scrabble you could use all sorts of bullshit scrabble words that are in SOWPODS like "za" and "qi", but imo its sort of undignified and cheesy to do so.
- pretzellogician 1y ago
  I used to agree with you. But there's a slippery slope. At what point is a word "bullshit"? What if you simply have a better vocabulary than other players? Our family compromise has always been, if it's valid and you know its definition (like "qi" and "za"), you can play it.
  - aabhay 1y ago
    Easier rule is just to exclude two letter words, or make two letter words zero points (so you can get rid of your Qs and Zs if you wish
    - Sesse__ 1y ago
      If you exclude two-letter words, you are also excluding nearly all overlaps and parallel plays.
- throwaway81523 1y ago
  Like this person, I also remembered the Notre Dame Scrabble Team fight song. I found this post by web search on the words. https://mudcat.org/thread.cfm?threadid=45390#671943 https://mudcat.org/thread.cfm?threadid=45390#671943 Added: I think s/he got some of the words slightly wrong!
- npteljes 1y ago
  This is the same thing I realized when being a "game master" of the shooter matches we used to hold on my previous project. The end goal of that play was fun, not to determine who has the most technical skill. After realizing this in my head, and also implementing it as additional rules for the game, the game sessions became much more enjoyable for everyone, participation, enjoyment, and desire to return for another session was through the roof. That said, both kinds of play has its place, in my life at least. Staying on the topic of shooters, when I play online in ranked, it's all out for me, and I enjoy that as well, in a different way. But when playing with my wife, it's never all out, always friendly.
Clood5 1y ago
[dead]
38 1y ago
Mirror?
- sphars 1y ago
  Posted above: https://archive.ph/siaAO https://archive.ph/siaAO
jebarker 1y ago
> "As far as I can tell, I’m the only person who is actually interested in this problem" I think this is a really interesting problem but I have to admit that if I'd heard it stated I would have guessed the answer was already known. I love the persistence on display here in spite of it being a "low status" problem. Reminds me of the recent discovery of a new largest (Mersenne?) prime, just someone getting nerd sniped and willing to spend their time and money.
sphars 1y ago
> The problem is hard because examining every possible Boggle board is unfeasible. There are something like a 20-digit number of them and scoring every one — even at Vanderkam’s pacy 200,000 boards a second — would take 800mn years. > It took 23,000 CPU hours on a high-end 192-core machine in the cloud — time worth about $1,200, across five human days. Pardon the pun but the sheer amount of possible boards is mind boggling. Impressive how he managed to cut it down by magnitudes.
throwaway81523 1y ago
The 192 core Google Cloud server is likely running at a fairly low frequency for power efficiency. So 5 days on it might be comparable to 1 or 2 months on a 16 core Ryzen 5950X that you can rent at hetzner.com/sb for around $100 a month. You can alternatively get an Epyc 7502P there (32 cores) for around the same price. I don't know how the speed would compare.
- danvk 1y ago
  I have been surprised that the Boggle code runs about 4x slower on the GCP machine than on my M2 MacBook. I don’t have enough experience running CPU- and RAM-intensive cloud jobs to know whether this is normal.
  - Aachen 1y ago
    Similar experience at DigitalOcean where, in 2023, I rented a VPS with dedicated cores to compute on some decent-sized dataset and it turned out to be slower than the 2012 laptop CPU that I use as my main server! That laptop has an i7-3630qm iirc, not sure what DO claimed they give you but it was slower The storage i/o speeds were also crap (quoting myself here from the notes I made at the time) compared to what I got soon after when I bought a 70€ TLC SSD as upgrade for the laptop-server. They claim it runs on SSDs but, if it does, they're the world's cheapest bulk data SSDs or they have a bottleneck in ferrying data between the SAN and the VPS host, even for sequential r/w (that it has higher iops latency, I could understand) At work, we sometimes use AWS GPUs for password cracking (we do security audits and sometimes find hashes). The GPUs that employees have just to play some games are faster than these and cost a lot less to operate, but we can't put customer data on private systems For occasional problems that can be parallelised, sure, rent a hundred temporary systems at a cloud farm for two days; but in general I just can't recommend it to anyone. It costs an arm and a leg compared to cheaper providers or buying hardware yourself (if you're into being the sysadmin). The "we have a fleet of systems on stand-by for you" (so you can scale on demand) is a big premium that most seem to be unaware of that they're paying implicitly
    - throwaway81523 1y ago
sireat 1y ago
Fantastic and fun achievement danvk! Solving Boggle would be a welcome addition to my Branch and Bound examples. I teach Algorithms course and my Branch and Bound lecture usually involves solving integer linear optimization problems. Those are quite dry. Now for the Branch and Bound to work you need what I informally call "cheat code". That is we need a way of solving a relaxed - easier version of the problem quickly . Quickly meaning with less time complexity. So what is the approach / key insight to calculate upper and lower bound estimates in Boggle?
- rahimnathwani 1y ago
  You might find the answer in the README: https://github.com/danvk/hybrid-boggle/blob/main/paper%2FREADME.md https://github.com/danvk/hybrid-boggle/blob/main/paper%2FREA... Scroll down to 'Sum/Choice trees' or Ctrl+F max_bound
- danvk 1y ago
  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 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/index.html https://www.danvk.org/wp/2009-08-08/breaking-3x3-boggle/inde... - https://www.danvk.org/wp/2009-08-11/a-few-more-boggle-examples/index.html 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.
lowbloodsugar 1y ago
Quibble: There’s only 6^16 possible sets, not 26^16.
- amiga386 1y ago
  That would only be if the dice order didn't matter. Multiply by 16! for the number of ways you can place your rolled dice in the grid. Then you find that 26^16 is less than 6^16*16! https://www.danvk.org/wp/2007-08-02/how-many-boggle-boards-are-there/ https://www.danvk.org/wp/2007-08-02/how-many-boggle-boards-a...

176 points by DavidSJ 1y ago

His blog post announcing it: https://www.danvk.org/2025/04/23/boggle-solved.html https://www.danvk.org/2025/04/23/boggle-solved.html FT article: https://archive.ph/siaAO https://archive.ph/siaAO His blog: https://www.danvk.org/blog.html https://www.danvk.org/blog.html > Driven “by the thrill of discovery”, Vanderkam has searched for this board, essentially alone, since 2004. He would scrape together computing time on Google’s hardware for heavy Boggle computation, all along documenting his efforts on his blog. > “As far as I can tell, I’m the only person who is actually interested in this problem,” Vanderkam said.

danvk 1y ago
> “As far as I can tell, I’m the only person who is actually interested in this problem,” Vanderkam said. For context, many people are interested in finding high-scoring Boggle boards, usually via simulated annealing, hillclimbing, or genetic algorithms. But so far as I can tell, I'm the only one interested in _proving_ that a particular board is best. Doing that was the new result here.
- hamburglar 1y ago
  I once spent a little time writing code to find the longest possible boggle word and found there were a few candidates. Interesting things I noted that weren’t entirely obvious: the longest word is actually 17 characters, not 16, because of the “Qu” side, and there are actually lots of words that are impossible, because for example there is only one J and only one B and they are on the same die. I don’t remember all the longest words but sesquicentennials was one of them.
  - danvk 1y ago
    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-boards-containing-a-16--or-17-letter-word 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.
    - smcin 1y ago
      Ok so English max is 3,625 points from 1,045 words (with ENABLE2K word list). Why not compute the max possible Boggle board for other languages: French, Spanish, German, Italian, Portuguese, Czech... they each have a different set of 16 dice x 6 faces [], and of course totally different wordlists: [boardgames.SE] "What is the dice configuration for Boggle in various languages?" https://boardgames.stackexchange.com/questions/29264/boggle-what-is-the-dice-configuration-for-boggle-in-various-languages https://boardgames.stackexchange.com/questions/29264/boggle-... [] some languages' Boggle dice sets have 25x6 faces
      - danvk 1y ago
        It's open source, take a crack at it! Or file an issue requesting it. This analysis doesn't make use of the Boggle dice. It assumes that any cell can be any letter. In practice, all high-scoring boards can be rolled with the Boggle dice. My code does assume the letters are A-Z, though, so the Ñ die in Spanish Boggle would require some code changes.
        smcin 1y ago
        Ok, but then a) we'd need to refine the issue to "enhance request to handle every non-ASCII character/digram that could occur in other Boggle languages": - Spanish: ñ - Czech: no extra characters (e.g. 'E' can be used in words as E, É and Ì) - Danish/Norwegian: do Boggle dice use æ,å,ø ? I searched but couldn't find out. - Swedish: do Boggle dice use å,ä,ö ? - Turkish: do Boggle dice use ç,ı,ğ,ş,ö,ü ? - Bosnian: see https://boardgames.stackexchange.com/a/51289/2358 https://boardgames.stackexchange.com/a/51289/2358 - Filipino: ñ . And separately in some wordgames (e.g. Scrabble knockoffs), I see 'ng' treated as a single digraph. Apparently it's officially a separate digraph, so the Tagalog alphabet ('abakada') has 28 letters. And b) if we have rare characters on a few dice (esp. the unofficial Bosnian one proposed), that imposes restrictions on your assumption that any cell can be any letter. So you'd have to postprocess to cull a few words that couldn't legally be made with that dice-set.

matt3210 1y ago

[flagged]

haxton 1y ago
> The former Google employee It's literally like the 3rd sentence...

robinhouston 1y ago

It was a fun surprise to see this story on the front page of this morning's Financial Times. It's very unusual in my experience for this sort of thing to be picked up by the mainstream media before it's on HN or similar. I wonder how the FT reporter came across the story.

wdumaresq 1y ago
This was posted on HN about a month ago: https://news.ycombinator.com/item?id=43774702 https://news.ycombinator.com/item?id=43774702
- robinhouston 1y ago
  Thanks. What's particularly embarrassing is that I found that submission this morning, and read the comments on it, and then somehow forgot about its existence until you reminded me of it just now.
- jonplackett 1y ago
  Thank you. I felt something must have been seriously wrong in the world that the FT knew this before any HN contributor.
  - noitpmeder 1y ago
    The author himself was the original submitter.
- dang 1y ago
  Thanks! Macroexpanded: After 20 years, the globally optimal Boggle board - https://news.ycombinator.com/item?id=43774702 https://news.ycombinator.com/item?id=43774702 - April 2025 (23 comments) How did that spend only 6 hours on HN's frontpage? I'm gonna email danvk right now
danvk 1y ago
"Lone coder" here. I reached out to Ollie (the FT reporter) because he'd written a book (Seven Games) about computers and games, so I thought the Boggle story might interest him. It did!

cgreerrun 1y ago

> The code is a mixture of C++ for performance-critical parts and Python for everything else. They’re glued together using pybind11, which I’m a big fan of. Nice, I'm a big fan of this combo! Hits the right balance of prototype speed plus performance.

everyone 1y ago

I love scrabble and boggle, but to me there is tension between just playing for points according to a certain set of rules, and playing to form nice satisfying words.. eg. in scrabble you could use all sorts of bullshit scrabble words that are in SOWPODS like "za" and "qi", but imo its sort of undignified and cheesy to do so.

pretzellogician 1y ago
I used to agree with you. But there's a slippery slope. At what point is a word "bullshit"? What if you simply have a better vocabulary than other players? Our family compromise has always been, if it's valid and you know its definition (like "qi" and "za"), you can play it.
- aabhay 1y ago
  Easier rule is just to exclude two letter words, or make two letter words zero points (so you can get rid of your Qs and Zs if you wish
  - Sesse__ 1y ago
    If you exclude two-letter words, you are also excluding nearly all overlaps and parallel plays.
throwaway81523 1y ago
Like this person, I also remembered the Notre Dame Scrabble Team fight song. I found this post by web search on the words. https://mudcat.org/thread.cfm?threadid=45390#671943 https://mudcat.org/thread.cfm?threadid=45390#671943 Added: I think s/he got some of the words slightly wrong!
npteljes 1y ago
This is the same thing I realized when being a "game master" of the shooter matches we used to hold on my previous project. The end goal of that play was fun, not to determine who has the most technical skill. After realizing this in my head, and also implementing it as additional rules for the game, the game sessions became much more enjoyable for everyone, participation, enjoyment, and desire to return for another session was through the roof. That said, both kinds of play has its place, in my life at least. Staying on the topic of shooters, when I play online in ranked, it's all out for me, and I enjoy that as well, in a different way. But when playing with my wife, it's never all out, always friendly.

Clood5 1y ago

[dead]

38 1y ago

Mirror?

sphars 1y ago
Posted above: https://archive.ph/siaAO https://archive.ph/siaAO

jebarker 1y ago

> "As far as I can tell, I’m the only person who is actually interested in this problem" I think this is a really interesting problem but I have to admit that if I'd heard it stated I would have guessed the answer was already known. I love the persistence on display here in spite of it being a "low status" problem. Reminds me of the recent discovery of a new largest (Mersenne?) prime, just someone getting nerd sniped and willing to spend their time and money.

sphars 1y ago

> The problem is hard because examining every possible Boggle board is unfeasible. There are something like a 20-digit number of them and scoring every one — even at Vanderkam’s pacy 200,000 boards a second — would take 800mn years. > It took 23,000 CPU hours on a high-end 192-core machine in the cloud — time worth about $1,200, across five human days. Pardon the pun but the sheer amount of possible boards is mind boggling. Impressive how he managed to cut it down by magnitudes.

throwaway81523 1y ago

The 192 core Google Cloud server is likely running at a fairly low frequency for power efficiency. So 5 days on it might be comparable to 1 or 2 months on a 16 core Ryzen 5950X that you can rent at hetzner.com/sb for around $100 a month. You can alternatively get an Epyc 7502P there (32 cores) for around the same price. I don't know how the speed would compare.

danvk 1y ago
I have been surprised that the Boggle code runs about 4x slower on the GCP machine than on my M2 MacBook. I don’t have enough experience running CPU- and RAM-intensive cloud jobs to know whether this is normal.
- Aachen 1y ago
  Similar experience at DigitalOcean where, in 2023, I rented a VPS with dedicated cores to compute on some decent-sized dataset and it turned out to be slower than the 2012 laptop CPU that I use as my main server! That laptop has an i7-3630qm iirc, not sure what DO claimed they give you but it was slower The storage i/o speeds were also crap (quoting myself here from the notes I made at the time) compared to what I got soon after when I bought a 70€ TLC SSD as upgrade for the laptop-server. They claim it runs on SSDs but, if it does, they're the world's cheapest bulk data SSDs or they have a bottleneck in ferrying data between the SAN and the VPS host, even for sequential r/w (that it has higher iops latency, I could understand) At work, we sometimes use AWS GPUs for password cracking (we do security audits and sometimes find hashes). The GPUs that employees have just to play some games are faster than these and cost a lot less to operate, but we can't put customer data on private systems For occasional problems that can be parallelised, sure, rent a hundred temporary systems at a cloud farm for two days; but in general I just can't recommend it to anyone. It costs an arm and a leg compared to cheaper providers or buying hardware yourself (if you're into being the sysadmin). The "we have a fleet of systems on stand-by for you" (so you can scale on demand) is a big premium that most seem to be unaware of that they're paying implicitly
  - throwaway81523 1y ago

sireat 1y ago

Fantastic and fun achievement danvk! Solving Boggle would be a welcome addition to my Branch and Bound examples. I teach Algorithms course and my Branch and Bound lecture usually involves solving integer linear optimization problems. Those are quite dry. Now for the Branch and Bound to work you need what I informally call "cheat code". That is we need a way of solving a relaxed - easier version of the problem quickly . Quickly meaning with less time complexity. So what is the approach / key insight to calculate upper and lower bound estimates in Boggle?

rahimnathwani 1y ago
You might find the answer in the README: https://github.com/danvk/hybrid-boggle/blob/main/paper%2FREADME.md https://github.com/danvk/hybrid-boggle/blob/main/paper%2FREA... Scroll down to 'Sum/Choice trees' or Ctrl+F max_bound
danvk 1y ago
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 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/index.html https://www.danvk.org/wp/2009-08-08/breaking-3x3-boggle/inde... - https://www.danvk.org/wp/2009-08-11/a-few-more-boggle-examples/index.html 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.

lowbloodsugar 1y ago

Quibble: There’s only 6^16 possible sets, not 26^16.

amiga386 1y ago
That would only be if the dice order didn't matter. Multiply by 16! for the number of ways you can place your rolled dice in the grid. Then you find that 26^16 is less than 6^16*16! https://www.danvk.org/wp/2007-08-02/how-many-boggle-boards-are-there/ https://www.danvk.org/wp/2007-08-02/how-many-boggle-boards-a...