A Computational Proof of the Highest-Scoring Boggle Board

Summary

Exciting news! This is the best possible Boggle board: Boggle is a word search game. You form words by connecting adjacent letters, including along diagonals. Longer words score more points. Good words on this board include STRANGERS and PLASTERING. After you spend three minutes trying to find as many words as you can, you’ll be struck by just how good computers are at this. Using the ENABLE2K word list, this board has 3,625 points on it coming from 1,045 words. This board has more points than any other. Try any other combination of letters and you’ll get a lower score. While I’ve long suspected this board was the winner, I’ve now proven it via exhaustive search. Many people have searched for high-scoring boards before, but no one has ever constructed a computational proof that they’ve found the best one. This is a new, first of its kind result for Boggle. To see why this is interesting, let’s go back to the 1980s. High-Scoring Boggle and Local Optima With the release of the Apple II (1977) and IBM PC (1981), computers become accessible to hobbyists, including word game enthusiasts. In 1982, Alan Frank published a short article in Word Ways magazine called High-Scoring Boggle. It’s the earliest work I’ve found on Boggle maximization, and it’s instructive on why this is a hard problem. Here’s what he wrote: The article goes on to list the 769 words that add up to 2,047 points. You can browse the words on that board using the fifth edition of OSPD here: gnisetrpseacdbls. (Thanks to the addition of new words, it’s increased to 2,226 points.) The article doesn’t explain how Alan and Steve came up with this particular board, but I suspect they used a hill climbing procedure. The idea is simple: start with a random board and find its score. Tweak a letter and see if the score improves. If so, keep it. If not, discard the change. Repeat until you stall out. You’ll eventually wind up with a high-scoring board. Writing a Boggle solver and finding this board was a real achiev...