Humans best crossword-puzzling computer

Dr Fill is no Deep Blue or Watson – yet

Officially, humans are the only ones who can enter the American Crossword Puzzle Tournament, which was held in Brooklyn, New York over the weekend. But this time artificial intelligence expert Matt Ginsberg of On Time Systems has put his Dr Fill crossword solver to the test. As the results show, you don't have to throw out your pencil just yet.

This week, the puzzle masters at the ACPT put the hurt on Dr Fill, who according to a report in the New York Times, did terribly on two out of the five crossword puzzles and would have only ranked 141st among the 600 people that took the test. The program has done better in the past, and in simulated runs among fifteen former tournaments, Dr Fill came out on top three times.

"I'll be back next year," Ginsberg told the Times.

Ginsberg's company, located in Eugene, Oregon, is a niche player in industrial optimization. Among other things, On Time Systems has created algorithms behind the Green Driver application used in the cities of Eugene and Portland to anticipate red lights and to route around them, which can cut commute times by 5 per cent.

The company has also created the algorithms for routing the US Air Force's fleet of cargo aircraft around weather while still obeying air traffic rules. The Worldwide Aeronautical Route Planner was created to run on mainframes and its being modernized to run on laptops. The optimized routing saves the Air Force something on the order of 1 to 2 per cent on its fuel bill each year, which works out to $35m to $90m.

In his spare time, in addition to actually creating crossword puzzles for the Times, Ginsberg has been working on the Dr Fill program. Ginsberg submitted a paper describing Dr Fill to the Journal of Artificial Intelligence Research, which was published (PDF) in December 2011. Based on its past performance, Ginsberg reckons that Dr Fill ranks among the top 50 puzzle solvers in the world, even though it did not have a very good day on Sunday.

The Watson Jeopardy! question-answer system built by IBM that took on the two human champs (perhaps chimps or chumps might be more appropriate, given how badly Watson spanked Ken Jennings and Brad Rutter) did terribly at first, too, but with tweaks and tuning and algorithm changes, it got better.

So there's no question that Ginsberg will be back, and it might even turn out that he gets some help. The Gray Lady is Big Blue's hometown rag, so some collaboration might be in order. The puzzles that threw Dr Fill through a loop had words spelled backwards and some that had words diagonally as well as horizontally and vertically.

As with the Watson QA machine, Dr Fill is not actually understanding what it is doing, but using statistical probabilities to calculate its answers. Technically, what Dr Fill does is convert a crossword puzzle into a singly weighed constraint satisfaction problem. The constraints, of course, are the clues. Otherwise, you could just use a vast dictionary and try to cram every word of every length into every appropriate spot and then create a cross index of where letters match up where words cross.

Such an unconstrained problem is very tough to solve, so if you can "understand" the clues, then you can limit the possible answers and therefore the size of the dictionary you need to rifle through. The clues have all kinds of other cues that people process, such as a clue that ends in a question is usually tricky in some fashion.

Behind the Dr Fill program, Ginsberg has amassed a database of over 47,000 crossword puzzles and their solutions, with almost 1.9 million unique clues. The system also makes use of a dictionary with over six million words and a smaller dictionary with 8,542 common words.

The answers to all of these puzzles were then rated in a number of ways, including hand scoring them by 100 volunteers and cross-checking them for the number of Google hits, their Scrabble score if you were playing that word game, their length, and other criteria. Based on the 50,000 words, scoring was done for the remaining clues in the 47,000 puzzles.

The Dr Fill database also includes a database of Wikipedia titles, grammatical information about 154,000 words that tells Dr Fill their part of speech, and 1.2 million synonyms.

Armed with all this data and super-secret algorithms, Dr Fill solves crossword puzzles. Watson needed a rack of IBM Power 750 servers with 2,880 cores and 16TB of memory in a high-speed cluster, but Ginsberg says you can run Dr Fill on a notebook with two x86 cores and 8GB of memory with a compressed database that weighs in at 300MB.

Like many others, Ginsberg thinks that Watson cheated a bit. Humans did beat Watson in a dry run, and then IBM sped up the button pushing a bit for the real showdown.

"Watson, too, outperforms humans easily in terms of speed; its much-ballyhooed victory against human Jeopardy! competitors was probably due far more to Watson's mastery of button pushing than to its question-answering ability," writes Ginsberg in his JAIR paper. "In terms of the underlying cognitive task, Watson appears to not yet be a match for the best Jeopardy players, who are in general capable of answering virtually all of the questions without error."

Ginsberg says that the task for Dr Fill is a lot harder, because you can't decline to answer or bet to boost your earnings as you can on Jeopardy!. You have to find the right answers, period. And perhaps more significantly, Ginsberg is having a harder time as Dr Fill gets better and better of figuring out why the program is not working.

Perhaps we need to create Stallman? ®

Other stories you might like

  • Chip shortage forces temporary Raspberry Pi 4 price rise for the first time

    Ten-buck increase for 2GB model 'not here to stay' says Upton

    The price of a 2GB Raspberry Pi 4 single-board computer is going up $10, and its supply is expected to be capped at seven million devices this year due to the ongoing global chip shortage.

    Demand for components is outstripping manufacturing capacity at the moment; pre-pandemic, assembly lines were being red-lined as cloud giants and others snapped up parts fresh out of the fabs, and the COVID-19 coronavirus outbreak really threw a spanner in the works, so to speak, exacerbating the situation.

    Everything from cars to smartphones have been affected by semiconductor supply constraints, including Raspberry Pis, it appears. Stock is especially tight for the Raspberry Pi Zero and the 2GB Raspberry Pi 4 models, we're told. As the semiconductor crunch shows no signs of letting up, the Raspberry Pi project is going to bump up the price for one particular model.

    Continue reading
  • Uncle Sam to clip wings of Pegasus-like spyware – sorry, 'intrusion software' – with proposed export controls

    Surveillance tech faces trade limits as America syncs policy with treaty obligations

    More than six years after proposing export restrictions on "intrusion software," the US Commerce Department's Bureau of Industry and Security (BIS) has formulated a rule that it believes balances the latitude required to investigate cyber threats with the need to limit dangerous code.

    The BIS on Wednesday announced an interim final rule that defines when an export license will be required to distribute what is basically commercial spyware, in order to align US policy with the 1996 Wassenaar Arrangement, an international arms control regime.

    The rule [PDF] – which spans 65 pages – aims to prevent the distribution of surveillance tools, like NSO Group's Pegasus, to countries subject to arms controls, like China and Russia, while allowing legitimate security research and transactions to continue. Made available for public comment over the next 45 days, the rule is scheduled to be finalized in 90 days.

    Continue reading
  • Global IT spending to hit $4.5 trillion in 2022, says Gartner

    The future's bright, and expensive

    Corporate technology soothsayer Gartner is forecasting worldwide IT spending will hit $4.5tr in 2022, up 5.5 per cent from 2021.

    The strongest growth is set to come from enterprise software, which the analyst firm expects to increase by 11.5 per cent in 2022 to reach a global spending level of £670bn. Growth has fallen slightly, though. In 2021 it was 13.6 per cent for this market segment. The increase was driven by infrastructure software spending, which outpaced application software spending.

    The largest chunk of IT spending is set to remain communication services, which will reach £1.48tr next year, after modest growth of 2.1 per cent. The next largest category is IT services, which is set to grow by 8.9 per cent to reach $1.29tr over the next year, according to the analysts.

    Continue reading
  • Memory maker Micron moots $150bn mega manufacturing moneybag

    AI and 5G to fuel demand for new plants and R&D

    Chip giant Micron has announced a $150bn global investment plan designed to support manufacturing and research over the next decade.

    The memory maker said it would include expansion of its fabrication facilities to help meet demand.

    As well as chip shortages due to COVID-19 disruption, the $21bn-revenue company said it wanted to take advantage of the fact memory and storage accounts for around 30 per cent of the global semiconductor industry today.

    Continue reading
  • China to allow overseas investment in VPNs but Beijing keeps control of the generally discouraged tech

    Foreign ownership capped at 50%

    After years of restricting the use and ownership of VPNs, Beijing has agreed to let foreign entities hold up to a 50 per cent stake in domestic VPN companies.

    China has simultaneously a huge market and strict rules for VPNs as the country's Great Firewall attempts to keep its residents out of what it deems undesirable content and influence, such as Facebook or international news outlets.

    And while VPN technology is not illegal per se (it's just not practical for multinationals and other entities), users need a licence to operate one.

    Continue reading
  • Microsoft unveils Android apps for Windows 11 (for US users only)

    Windows Insiders get their hands on the Windows Subsystem for Android

    Microsoft has further teased the arrival of the Windows Subsystem for Android by detailing how the platform will work via a newly published document for Windows Insiders.

    The document, spotted by inveterate Microsoft prodder "WalkingCat" makes for interesting reading for developers keen to make their applications work in the Windows Subsystem for Android (WSA).

    WSA itself comprises the Android OS based on the Android Open Source Project 1.1 and, like the Windows Subsystem for Linux, runs in a virtual machine.

    Continue reading
  • Software Freedom Conservancy sues TV maker Vizio for GPL infringement

    Companies using GPL software should meet their obligations, lawsuit says

    The Software Freedom Conservancy (SFC), a non-profit which supports and defends free software, has taken legal action against Californian TV manufacturer Vizio Inc, claiming "repeated failures to fulfill even the basic requirements of the General Public License (GPL)."

    Member projects of the SFC include the Debian Copyright Aggregation Project, BusyBox, Git, GPL Compliance Project for Linux Developers, Homebrew, Mercurial, OpenWrt, phpMyAdmin, QEMU, Samba, Selenium, Wine, and many more.

    The GPL Compliance Project is described as "comprised of copyright holders in the kernel, Linux, who have contributed to Linux under its license, the GPLv2. These copyright holders have formally asked Conservancy to engage in compliance efforts for their copyrights in the Linux kernel."

    Continue reading
  • DRAM, it stacks up: SK hynix rolls out 819GB/s HBM3 tech

    Kit using the chips to appear next year at the earliest

    Korean DRAM fabber SK hynix has developed an HBM3 DRAM chip operating at 819GB/sec.

    HBM3 (High Bandwidth Memory 3) is a third generation of the HBM architecture which stacks DRAM chips one above another, connects them by vertical current-carrying holes called Through Silicon Vias (TSVs) to a base interposer board, via connecting micro-bumps, upon which is fastened a processor that accesses the data in the DRAM chip faster than it would through the traditional CPU socket interface.

    Seon-yong Cha, SK hynix's senior vice president for DRAM development, said: "Since its launch of the world's first HBM DRAM, SK hynix has succeeded in developing the industry's first HBM3 after leading the HBM2E market. We will continue our efforts to solidify our leadership in the premium memory market."

    Continue reading

Biting the hand that feeds IT © 1998–2021