Dr Fill

[nige1]

From Georgiana Gates on BridgeWinners...

Matt Ginsberg (creator of GIB) refocuses his skills on crosswords

[kenberg]

Both fun and very instructive. From the fun part: There are a couple of clues and answers in the story. My wife becky is far better at crosswords than I am so I gave her the challenge.

“Trip to watch the big game?” It took less than five seconds for her to respond "safari"

“Pasta dish at the center of a murder mystery?” Nope. But of course with a crossword you start to get clues by finding the answers to the crosswise words.

I might buy, maybe even read, his book Factor Man. I gather that the book should be regarded as fun rather than as literature.

[FelicityR]

I had to reply to this, Nigel, even though I have resisted posting on BBO some time ago. I'm not surprised that AI has finally entered the world of crosswords and found to be better than humans.

 

I personally gave up crosswords many years ago, having been a Times, Telegraph and Guardian crossword 'attemptee' for want of a better made-up word. Occasionally I would complete one, feeling jolly pleased with myself.

 

However, the watershed moment came when I had one clue left to finish a broadsheet crossword. It was 'Old timer found in dry places'. I had a couple of letters to help me construct the word, but for the life of me I tried for about an hour, juggling the letters into the remaining spaces, thinking what it might be. In the end I consulted a thesaurus and found the word 'Clepsydra' an anagram of 'Dry Places'.

 

I studied Latin at school but not Greek, so I wasn't aware of the word until then. But what got me is that a 'Clepsydra' is actually a water clock. So it can never be found in 'dry places', or if it was in a 'dry place' it wouldn't be working :)

 

I have never done a crossword since. The AI computer programs are welcome to them. Bridge is much more fun!

[thepossum]

Very interesting but to me it fits in the category of pseudo AI. Its hardly remarkable that a dumb piece of software with all that information and data with some extremely fast hardware can outperform many humans. Anyone can look up clues on the internet if they want or look up Wikipedia. So what if it was disconnected, it had already "ingested it" whatever that means :) Don't tell me it had access to a dictionary to scan too :)

 

PS Before anyone has a go at me, I just have a rather specific view on what true AI entails or should entail. Most of what people think of as AI is in my book pseudo AI :)

[barmar]

However, the watershed moment came when I had one clue left to finish a broadsheet crossword. It was 'Old timer found in dry places'. I had a couple of letters to help me construct the word, but for the life of me I tried for about an hour, juggling the letters into the remaining spaces, thinking what it might be. In the end I consulted a thesaurus and found the word 'Clepsydra' an anagram of 'Dry Places'.

 

I studied Latin at school but not Greek, so I wasn't aware of the word until then. But what got me is that a 'Clepsydra' is actually a water clock. So it can never be found in 'dry places', or if it was in a 'dry place' it wouldn't be working :)

 

I have never done a crossword since. The AI computer programs are welcome to them. Bridge is much more fun!

That sounds like a "cryptic crossword", they make extensive use of anagrams and other wordplay, making them far harder than normal crosswords. But I think there are some common tropes, so experienced players of these games learn that "found in" suggests looking for anagrams or substrings, rather than treating it literally.

 

And I guess the machine learning part of Dr. Fill could similarly discover these patterns, although it might take many training sessions.

[pilowsky]

Here's the original reference:

MR2874817 68T35

Ginsberg, Matthew L.

Dr.Fill: crosswords and an implemented solver for singly weighted CSPs.

J. Artificial Intelligence Res. 42 (2011), 851–886.

DOI: https://doi.org/10.1613/jair.3437

 

(I think that a CSP is "communicating sequential processes" and not Concordia University St Paul, a Certified Safety Professional or Cloud Solution Provider.)

I note that Ginsberg writes "Dr.Fill" - I assume that this is also computer phraseology since Dr Fill is grammatically correct.

 

Abstract

We describe Dr.Fill, a program that solves American-style crossword puzzles. From a technical perspective, Dr.Fill works by converting crosswords to weighted CSPs, and then using a variety of novel techniques to find a solution. These techniques include generally applicable heuristics for variable and value selection, a variant of limited discrepancy search, and postprocessing and partitioning ideas. Branch and bound is not used, as it was incompatible with postprocessing and was determined experimentally to be of little practical value. Dr.Filll's performance on crosswords from the American Crossword Puzzle Tournament suggests that it ranks among the top fifty or so crossword solvers in the world.

Ginsberg is well-known for his speedy visit to the club.

[barmar]

Ginsberg was interviewed on yesterday's "Science Friday". If you download the podcast, the interview starts about 45 minutes in.

[thepossum]

Is it possible to access the puzzles for the Competition. I need to test my brain :)