A Computational Proof of the Highest-Scoring Boggle Board

Exciting news! This is the best possible Boggle board: Boggle is a word search game where 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.

We used the ENABLE2K word list to calculate a score of 3,625 points on this board from 1,045 words. This board has more points than any other board we’ve tested, and it's likely the global optimum. But how did we get here?

The Problem

Boggle is a classic word game that has been around for decades. The objective is to find as many words as possible in a grid of letters. The score of each word depends on its length, with longer words scoring more points. However, finding the optimal solution – the board with the highest total score – is a challenging problem.

The problem is made even harder by the fact that there are an enormous number of possible boards to test. With 4x4 and larger grids, the number of possible boards grows exponentially, making it impractical to test every single one. This is where our solution comes in.

Branch and Bound

We used a technique called Branch and Bound to tackle this problem. B&B is an algorithm that works by grouping boards into classes based on their properties (e.g., consonant/vowel patterns). We then calculate an upper bound for the highest-scoring board in each class, and if it's lower than our current best score, we can eliminate the entire class without testing any individual boards.

This approach is more efficient than a naive brute-force search because it allows us to prune branches of the search tree that are unlikely to contain the optimal solution. By focusing on a smaller set of promising classes, we can reduce the number of boards we need to test, making the problem more tractable.

Sum/Choice Trees

We also developed a custom tree structure called "sum/choice trees" that is optimized for Boggle. These trees allow us to efficiently calculate upper bounds and split board classes into smaller, more manageable pieces.

The sum/choice tree data structure works by representing each node in the tree as a combination of two operations: SUM (calculate the total score) and CHOICE (split the class into sub-classes). By traversing this tree, we can efficiently explore the search space and find promising classes to test further.

The Results

After running our algorithm on 4x4 Boggle, we found a list of all boards that score at least 3,500 points using the ENABLE2K word list. There were 32 such boards, with the top five being:

  • sepesdsracietilmanesligdr
  • xraydilnesdresapiesps
  • rrexdyspesedrsei
  • esesipsdedrxsey
  • sepesedsracietilsig

We're thrilled to have found these top-scoring boards, and we believe that they represent the global optimum for 4x4 Boggle. However, there's still more work to be done – we need to formalize our results in a paper and explore other word lists, including those from Hasbro's 5x5 and 6x6 versions of Boggle.

Conclusion

This project demonstrates the power of algorithmic thinking and computational proof. By breaking down a complex problem into smaller, more manageable pieces, we can develop efficient solutions that tackle challenges that would be impossible to solve through brute force alone.

We hope that our work will inspire others to explore the fascinating world of word games and algorithms. And who knows? Maybe one day we'll find the optimal solution for 5x5 Boggle!