It’s a regrettable reality that there is never enough time to cover all the interesting scientific stories we come across each month. In the past, we’ve featured year-end roundups of cool science stories we (almost) missed. This year, we’re experimenting with a monthly collection. October’s list includes the microstructural differences between regular and gluten-free spaghetti, capturing striking snakes in action, the mystery behind the formation of Martian gullies, and—for all you word game enthusiasts—an intriguing computational proof of the highest possible scoring Boggle board.
Highest-scoring Boggle board
Sometimes we get handy story tips from readers about quirkily interesting research projects. Sometimes those projects involve classic games like Boggle, in which players find as many words as they can from a 4×4 grid of 16 lettered cubic dice, within a given time limit. Software engineer Dan Vanderkam alerted us to a a preprint he posted to the physics arXiv, detailing his quest to find the Boggle board configuration that yields the highest possible score. It’s pictured above, with a total score of 3,625 points, according to Vanderkam’s first-ever computational proof. There are more than 1000 possible words, with “replastering” being the longest.
Vanderkam has documented his quest and its resolution (including the code he used) extensively on his blog, admitting to the Financial Times that, “As far as I can tell, I’m the only person who is actually interested in this problem.” That’s not entirely true: there was an attempt in 1982 that found an optimal board yielding 2,195 points. Vanderkam’s board was known as possibly being the highest scoring, it was just very difficult to prove using standard heuristic search methods. Vanderkam’s solution involved grouping board configurations with similar patterns into classes, and then finding upper bounds to discard clear losers, rather than trying to tally scores for each board individually—i.e., an old school “branch and bound” technique.