The Crossing Guard

Matthew Ginsberg could be considered a traffic cop of sorts.

Research professor at the UO’s Computational Intelligence Research Laboratory and cofounder of the spinoff company On Time Systems, Ginsberg applies artificial intelligence to create, for example, “optimization” software programs that smartly route U.S. Air Force flights—conserving some twenty million gallons of fuel per year—and steer shipbuilders efficiently through unimaginably complex jobs for the U.S. Navy. On Time Systems’ latest venture, a smartphone-based application called Green Driver, taps real-time traffic light data to show drivers the quickest of many possible routes to a destination.

And while his work involves guiding people, planes, and processes through puzzling challenges, Ginsberg’s hobby is creating challenging puzzles. As a crossword puzzle constructor—perhaps crossing guard is the better comparison here—Ginsberg shepherds words across (and down) into clever, sometimes mind-bending intersections.

Ginsberg created his first crossword puzzles in the 1970s when, as a senior at Wesleyan University, he wrote software that could fill a grid with words. “It’s basically a massive search problem,” he says, “and people then didn’t know nearly as much as they know now about that class of problem.”

For about thirty years, throughout his work in mathematics, computer science, and artificial intelligence at Oxford (where he earned his PhD in mathematics at age twenty-four), Stanford, and Oregon, Ginsberg occasionally revisited crossword design. He took it up in earnest in 2007, and in January of 2008 had his first puzzle published in that most hallowed crossword medium, The New York Times.

Ginsberg since has created some of the most original and memorable theme puzzles published by the Times in recent years.

“Every puzzle of his is based on a novel, slightly offbeat idea, involving a severe constraint of some sort, which he then brilliantly executes, with a first-rate construction to boot,” says Timescrossword editor Will Shortz. “Whatever idea he pursues, he likes to push it to its very limit. Every puzzle of his is a bit of a surprise. And I like that.”

Shortz surprised his crossword legions on Sunday, May 16, 2010, when he published a theme puzzle by Ginsberg called “Double Crossers.” Within its grid, ten squares, which typically would each be filled in with one letter, were further separated into four squares (see square 74 in photo). Puzzled puzzlers eventually discovered that each quadrant awaited four letters that would unite two overlapping, two-part down and across answers, each pair varying by two letters.

For example, one clue, “Like Enron,” yielded the answer “IN THE RED IN THE END,” with the two overlaying three-word phrases diverging only in the double-crossed square (underlined). The clue for the intersecting answer read “Knock again.” The answer: “RETRY ENTRY.”

“I especially liked how TIME WARNER became TIME WASTER by changing just two letters—and then had two other common words [CONVERSION/CONVENTION] crossing those changed letters in the other direction,” Shortz says.

(Having trouble visualizing the concept? See “Double Crossers,” along with Ginsberg’s twenty-one other puzzles published in the Times, at www.xwordinfo.com/authors.)

“Double Crossers” actually sparked a minor flap among the Times’ crossword diehards. Many solvers use Across Lite software to complete the daily puzzle, but the program couldn’t handle the quartered squares of this atypical grid. Before Ginsberg and the Times’ crossword blogger could piece together a patched electronic file, those who normally completed the puzzle onscreen had to print out the puzzle and solve it on paper.

“All of the online solvers were mad,” says Ginsberg. “There was this online brouhaha about whether I was a hero or a goat.” (Read comments and Ginsberg’s responses on the Times’ Wordplay blog at www.tinyurl.com/25r6y6v.)

Detractors aside, “Double Crossers” represented the type of technically sophisticated puzzle borne of Ginsberg’s man-machine construction methods.

“First of all, Matt has a gigantic database of potential crossword entries—one of the largest in the business—so he’s able to achieve intricate constructions other people can’t,” explains Shortz, who publishes the work of more than 100 puzzle makers each year. “He also has an excellent sense of what makes a good or great crossword entry and what doesn’t.”

Surprisingly, Ginsberg admits to being “truly horrible” at solving crosswords. “But I look at the Times puzzle pretty much every day because I’m interested in themes and I always try to do something no one has done before.”

As with his “day job” optimization work, Ginsberg’s puzzle construction begins with a problem that has myriad possible solutions. “There are many different ways of filling a grid, and you want to find the best one,” he says.

Ginsberg starts a puzzle grid by entering his theme words, which he often culls from database search results that match certain parameters. Finding the twenty pairs of slightly varied words and phrases that could unite and intersect with two others in “Double Crossers,” for example, would be a daunting task without a computer’s enormous computational power.

Similarly, man and microprocessor teamed up to concoct the portmanteau entries in “Compound Fractures,” a November 1, 2009, Times theme puzzle by Ginsberg and Pete Muller, a longtime associate and collaborator. Muller had the initial idea, and Ginsberg then wrote a program to merge words that shared sequences of several letters. Finally, the authors crafted clever definitions for the most inspired of these Frankenwords. RETROSPECTACLES became “Eyewear providing hindsight”; GUITARISTOCRAT, a “Noble Les Paul”; and SPORADICAL, an “Intermittent revolutionary.”

To help in assembling the remainder of puzzles, Ginsberg maintains a database filled with entries harvested from electronically published crosswords. This is not to make his task easier, he says, but to help him avoid overused entries. “I want to have fresh clues,” he stresses, citing “Fabled slacker” for HARE as one of his favorites.

Ginsberg uses closely supervised “auto-fill” to flesh out his puzzle grids. The computer suggests words to fill each slot, and then Ginsberg chooses the ones he likes best, revisits any trouble spots, and finally writes the clues. “I’ll gradually fill it in, usually in six to eight hours, in sort of a team effort between me and the computer,” he says.

The quality of Ginsberg’s meticulous work is apparent to Shortz.

“When I get a puzzle from Matt, I get the feeling that he’s explored all the best possibilities for the construction,” Shortz says. “I don’t have to second-guess him and ask ‘Did you try this instead?’ He already tried everything and chose the optimal result.”

Contestants at Shortz’s annual American Crossword Puzzle Tournament (chronicled in the 2006 documentary film Wordplay) also don’t have to second-guess results at the competition thanks to a program Ginsberg wrote to assist human judges in scoring and scanning puzzle forms for errors.

All of this human-computer crossword crossover raises a compelling question for Ginsberg, who in the 1990s developed GIB (Ginsberg’s Intelligent Bridgeplayer), widely regarded as the first bridge software to approach the level of expert human players. Couldn’t a program also be written to create crosswords as skillfully as the best human constructors?

Well, he says, it is easy to program a computer to design “good” crosswords unassisted. That’s why he prefers to create puzzles infused with thematic links, wordplay, wit, and subtlety—the type favored by Shortz, and the kind that can be schemed in the human mind but not (yet) in the realm of artificial intelligence.

Ginsberg devised one puzzle built on the theme of contranyms, or words that can mean one thing and the opposite. Entries included “Add to or remove from” (TRIM); “Easy to see or impossible to see” (TRANSPARENT); and “Confirmation or uncertainty” (RESERVATION).

“There is this interesting bit of emotional tension in these words that mean their opposite,” explains Ginsberg who, literally, wrote the book on the Essentials of Artificial Intelligence (Morgan Kaufmann, 1993). “Coming up with an idea like that is completely beyond what computers can do at the moment. And I work with computers eight hours a day as it is, so I always try to do something with a genesis that is entirely human.”

After all, guiding words into wondrous intersections still requires the guiding hands of a gifted crossing guard.

—By Joel Gorthy ’98