Arts
INDY Week's arts blog

Archives | RSS | Follow on

Thursday, March 22, 2012

Man vs. Machine at the American Crossword Puzzle Tournament

Posted by on Thu, Mar 22, 2012 at 11:55 AM

There were some surprise winners at the American Crossword Puzzle Tournament last weekend in Brooklyn, even as last year's victor, Dan Feyer, won his second straight championship. Filling in answers to a very difficult puzzle with a dry erase marker on a whiteboard before a crowd of 600 vanquished contestants, Feyer defended his title in rather anticlimactic fashion, beating the runner-up by more than three minutes. (Finishing second was none other than Tyler Hinman, whom viewers of the 2006 documentary Wordplay would recognize as the red-haired wunderkind who became the tournament's youngest champion. Hinman went on to win the next four competitions before being deposed by Feyer).

No, the surprise winner wasn't Feyer, but the 140 entrants—about a quarter of the total—who bested Dr. Fill, a ruthless competitor with a novel approach to solving and with a realistic shot at finishing first, despite having never competed at the tournament before.

Allow me to explain.

Dr. Fill is a computer algorithm created by Matthew Ginsberg, an AI expert and crossword constructor. It's not the first of its kind—a team of computer scientists from Duke brought a cyber-solver called Proverb to the tournament in 1999—but it's undoubtedly the best: While Proverb limped to a bottom-half finish, in simulations of the previous 34 tournaments, Dr. Fill would've won three outright.

The name "Dr. Fill" is a pun on Dr. Phil McGraw, and in crossword lingo, "fill" also refers to the words in the grid (the "entries") collectively. Not coincidentally, fill is one facet of crossword puzzles that computers have already mastered, not in the solving but in the making: While it takes human ingenuity to come up with lively themes and tricky clues, computers have proven adept at generating interlocking words to fill in the white squares.

That's a pretty straightforward task for a machine: Draw from a database of kosher character strings and fit them into a grid. It's a math problem. But finding answers to clues like "Late riser?" (GHOST) or "Turn left, say?" (RADICALIZE)—that's a taller order.

Even more difficult for the computer are the devious tricks and gimmicks constructors will throw in, the solving of which demands mental flexibility and thinking outside the box. Experienced solvers learn to look for these curveballs, such as multiple letters in a square or entries that extend outside the grid. But they're extremely hard to account for in a linear set of instructions. Of the eight tournament puzzles, two in particular—#2 and #5, traditionally the hardest—grievously tripped up Dr. Fill.

Puzzle #2, by Patrick Merrell, was titled "Boustrophedon," with a helpful definition below the title: "adj. (and n.): having alternate lines running from left to right and right to left." Crossword veterans figured out the gimmick in short order, noticing that the words were to be entered forward and backward in alternating rows. (Entries such as PLOWING A FIELD, MOWING THE LAWN and ONE WAY OR ANOTHER compounded the theme.)

Much more fiendish was Puzzle #5, "Going Underground," by Patrick Blindauer. "Follow the tunnels made by five creatures to complete this pesky puzzle," read the directions, and the first thing you noticed was that five across entries had blank clues. It didn't make sense until, midway through filling a confusing grid, it dawned on you that some of the answers, like LIEUTENANT COLONEL for "North, e.g." and INSTANT PUDDING for "Jell-O specialty," didn't fit in their designated slots but rather zigzagged through the grid, taking a downward diagonal turn with the letters ANT (the "creatures" who tunneled "underground").

Which was all too much for Dr. Fill. In a presentation on Saturday night, Ginsberg demonstrated his brainchild to the curious crowd. We watched it solve the puzzles in real time, using different colors for the letters depending on its confidence in the answers. Readers, I won't lie: Much of the hooting and guffawing at Dr. Fill's awkwardness with Puzzles #2 and #5 was pure schadenfreude. At least we knew we weren't hurting its feelings.

But the speed with which it solved the easier puzzles was awe-inspiring. Puzzle #4, a themer with two-word entries made up of pairs of one-word movie titles (CHICAGO SEVEN, SPEED UP, BIG HAIR, TRAFFIC SIGNS), fell in about 10 seconds, eliciting oohs and ahs. "That's what you guys are up against," said Ginsberg. "And it's only going to get better."

For these puzzles, at least, Dr. Fill lived up to its hype. On the morning of the tournament, Ginsberg and his cruciverbal Frankenstein had landed on the cover of The New York Times, with an article below the fold that alluded to Deep Blue and name-checked Watson, the computers that knocked off human champions in chess and Jeopardy, respectively. In his presentation, Ginsberg reinforced the scale of his program's achievement, pointing out the many ways that, compared to Watson, Dr. Fill was competing with one hand behind its back. Whereas Watson, he noted, was created by a staff of 25, ran in a room, and was powered by 2880 "cores" with 16 terabytes of memory, Dr. Fill was created by a "staff of one ... who has a job," and takes up only four gigabytes of memory on his notebook computer.

Ginsberg also pointed out that "Jeopardy questions are fair," while "crossword constructors cheat." Though his presentation was, on the whole, upbeat and good-natured, you couldn't help but notice a slight tone of pique. "I've probably put in 100 hours on this in the past week alone," he said.

In the end, though, a roomful of word nerds defended the pride of humankind against the advance of the machines for at least another year. Not a bad achievement for a weekend's worth of idle scribbling.

Pin It
AI expert Matthew Ginsberg's "Dr. Fill" had its fill of troubles in New York when going up against the creative humans who design crossword puzzles.

Comments

Showing 1-1 of 1

Add a comment

 
Subscribe to this thread:
Showing 1-1 of 1

Add a comment

INDY Week publishes all kinds of comments, but we don't publish everything.

  • Comments that are not contributing to the conversation will be removed.
  • Comments that include ad hominem attacks will also be removed.
  • Please do not copy and paste the full text of a press release.

Permitted HTML:
  • To create paragraphs in your comment, type <p> at the start of a paragraph and </p> at the end of each paragraph.
  • To create bold text, type <b>bolded text</b> (please note the closing tag, </b>).
  • To create italicized text, type <i>italicized text</i> (please note the closing tag, </i>).
  • Proper web addresses will automatically become links.

Latest in Arts

Facebook Activity

Twitter Activity

Comments

Just as the Heisman Trophy stands for a level of excellence in playing college football, so the position of poet …

by Heather McGehee on Opinion: McCrory’s mean joke, a poet laureate who’s barely a poet (Arts)

Indeed, some "elitist" writing in this article alone.Would you call Wallace Stevens a hobbyist?

Yes- The great American Poet …

by Mic Mac on Opinion: McCrory’s mean joke, a poet laureate who’s barely a poet (Arts)

Most Read

© 2014 Indy Week • 201 W. Main St., Suite 101, Durham, NC 27701 • phone 919-286-1972 • fax 919-286-4274
RSS Feeds | Powered by Foundation