Unlock the Editor’s Digest for free
Roula Khalaf, Editor of the FT, selects her favourite stories in this weekly newsletter.
The summit of the word game Boggle has finally been reached — and it spells “replastering”.
Dan Vanderkam, a freelance software engineer, has discovered the game’s highest-scoring board, solving a puzzle unanswered since Boggle was introduced more than 50 years ago.
The former Google employee, who lives in New York state, used some 23,000 hours of computing power to identify the winning grid of 16 letters, which contains more than 1,000 words with “replastering” the longest of all.
“The appeal of the problem is that at first it just seems so overwhelmingly impossible,” Vanderkam told the Financial Times.
Vanderkam himself is no great Boggle player, having dabbled in college with friends. But he was enchanted by the game’s underlying structure and mathematics, which is the stuff of rich analysis: data, algorithms, tree diagrams and powers of 10.
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.
Boggle is played using a four-by-four grid of lettered cubes, which are loudly shaken to randomise their faces and locations. Players then race against the clock to find as many words as they can, winding horizontally, vertically and diagonally through the grid. Longer words are worth more points.
From this modest equipment emerges arithmetic and architecture of cosmological proportion.
The maximal board contains 1,045 words worth 3,625 points. (The average board contains about 100 words worth 140 points.) Alongside “replastering”, there are six other words with 10 or more letters, and colourful shorter entries including “eateries”, “gesneria”, “strangers” and “integrals”.
Your chances of encountering this board after shaking the cubes at home are about one in 10 quintillion.
An early search for the richest Boggle board dates to a 1982 article in Word Ways magazine. The author “with the aid of a computer” identified what he considered “very likely the highest scoring one”. Adjudicating with a modern word list, it contains a relatively modest 2,195 points.
Vanderkam suspects the deficit — and a central difficulty of the project — lies with an optimisation method called “hill climbing”.
If a hiker, for instance, tries to locate a summit on hilly terrain, they could reasonably decide to only walk uphill and never down. This would ensure they would arrive at a peak but there is no guarantee that it would be the highest peak of all.
The same is true of certain computer algorithms that would take a Boggle board, change one letter, check if it scores higher, and repeat until it can improve the board no further. While the board would be better, there is no guarantee that it would be the best.
While Vanderkam and others were aware of the promising “replastering” board, there had been no sure proof of its universal dominance.
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.
Vanderkam relied on a pair of tricks to shrink a geological aeon into a few days.
First, rather than consider boards individually, he grouped them into classes — such as those that share a particular vowel-consonant pattern.
Second, rather than scoring them individually and painstakingly, he found upper bounds and discarded inadequate classes. These methods in combination swept away vast, inferior swaths of the Boggle cosmos.
The final flash of insight, about tree structures, came one night while Vanderkam was driving home. Together these tools are a relatively old technique known as “branch and bound”.
Vanderkam noted the entire project is “remarkably old-school”, and free from reliance on artificial intelligence. His work has yet to be peer reviewed, but for the computationally Boggle-minded, Vanderkam posted his code online.
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.
“It’s satisfying to solve a problem like that,” he said. “But also a little sad to lose it.”
Graphics by Jana Tauschinski in London
Read the full article here