Dr. Fill: Crosswords Aren't Just for Humans Any More
- When:
- Monday, January 30, 2012, 11:00 am - 12:00 pm
- Where:
- 11th floor large conference room
- Speaker:
- Matthew L.Ginsberg, On Time Systems
- Description:
Description of talk:
We describe and demonstrate 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.
Bio:Matthew L. Ginsberg received his doctorate in mathematics from Oxfordin 1980 at the age of 24. He remained on the faculty in Oxford until1983, doing research in mathematical physics and computer science;during this period, he wrote a program that was used successfully totrade stock and stock options on Wall Street.Ginsberg's continuing interest in artificial intelligence brought himto Stanford in late 1983, where he remained for nine years. He thenwent on to found CIRL, the computational intelligence researchlaboratory at the University of Oregon, which he directed until 1996.He remained at CIRL until 1998, when CIRL spun off On Time Systems, acommercial entity focusing on scheduling and routing technology.Ginsberg has been the CEO of the company since its formation and iscurrently its chairman as well.Ginsberg is also the chairman and CEO of Green Driver, Inc., a sistercompany to On Time Systems that focuses on using real-time traffic andsignal information to provide more fuel-efficient routes to drivers.Ginsberg's present research interests focus on constraintsatisfaction. He is the author of numerous publications in thisareas, the editor of "Readings in Nonmonotonic Reasoning," and theauthor of "Essentials of Artificial Intelligence," both published byMorgan Kaufmann. He is also the author of the bridge-playing programGIB, which made international news by finishing 12th in the worldbridge championships in Lille, France, and the author of Dr. Fill, acrossword-solving program that will be participating in the AmericanCrossword Puzzle Tournament in March of 2012.
