7 ms·
An AI system for solving crossword puzzles that outperforms the best humans
- ericwallace_ucb 4y agoHi, I am the first author of this paper and I am happy to answer any questions. You can find a link to the technical paper here https://arxiv.org/abs/2205.09665 https://arxiv.org/abs/2205.09665.
- avrionov 4y agoDo you think your approach can be applied to other problems?
- Imnimo 4y agoFor handling cross-reference clues, do you think it would be feasible in the future to feed the QA model a representation of the partially-filled puzzle (perhaps only in the refinement step - hard to do for the first step before you have any answers!), in order to give it a shot at answering clues that require looking at other answers? It feels like the challenges might be that most clues are not cross-referential, and even for those that are, most information in the puzzle is irrelevant - you only care about one answer among many, so it could be difficult to learn to find the information you need. But maybe this sort of thing would also be helpful for theme puzzles, where answers might be united by the theme even if their clues are not directly cross-referential, and could give enough signal to teach the model to look at the puzzle context?
- mikeryan 4y agoHey this is cool, I do the NYT Crossword every day. A few questions. 1. You mention an 82% solve rate. The NYT puzzle gets "harder" each day Monday through Saturday. Do you track the days separately? If so I'd be curious how much of the 18% unsolved end up on Fridays and Saturday. (for anyone who doesn't know the Sunday puzzle is outside of the M-Sat range since its a bigger puzzle). 2. Related to the above Thursday puzzles usually have "tricks" (skipped letters and what not) in them or require a Rebus (multiple letters in one space) - do you handle these at all? 3. Is this building an ongoing model and getting better at solving? Or did you have to seed it with a set of solved puzzles and clues? Sorry didn't have time to read the whole paper.
- nickatomlin 4y agoHi! I'm another author on this paper. To answer your questions: 1. Monday puzzles are the easiest for our model, and Thursdays are the most difficult. You can see a graph of day-by-day performance here: https://twitter.com/albertxu__/status/1527704535912787968 https://twitter.com/albertxu__/status/1527704535912787968 2. Our current system doesn't have any handling for rebuses or similar tricks, although Dr. Fill does. I think this is part of why Thursday is the hardest day for us, even though Saturday is usually considered the most difficult. 3. We trained it with 6.4M clues. As new crosswords get published, we could theoretically retrain our model with more data, but we aren't currently planning to do that.
- sp332 4y agoI don't suppose you gave more weight to more recent puzzles? Is there a time period or puzzle setter that was harder to solve because they favored an unusual clue type?
- nickatomlin 4y agoWe didn't give more weight to recent puzzles. In fact, we trained on pre-2020 data, validated on data from 2020, and evaluated on post-2020 data. Our model seems to perform well despite this "time generalization" split, but there are a couple instances where it struggled with new words. For example, we got the answer "FAUCI" wrong in a puzzle from May 2021. Even though Fauci was in the news before 2020, I guess he wasn't famous enough to show up in crosswords, and therefore his name wasn't in our training data. I think evaluating performance by constructor would be really interesting! But we haven't done that.
- twright0 4y agoThis is super interesting work! One thing I was curious about - the ACPT is a crossword speed-solving competition, with time spent solving a major aspect of total score. How did you approach leveling the playing field between the human and computer competitors?
- mikeryan 4y agoOh also do you use the puzzle Author as a data point? I wonder if there are patterns to be gleaned there.
- thom 4y agoNote for Brits that this isn’t cryptic (dare I say ‘real’) crosswords, but I assume it could be retooled for that.
- dane-pgp 4y agoI'm reminded of an article I read about an AI that competed in a crossword competition and one particularly difficult clue it faced was "Apollo 11 and 12 [180 degrees]". I don't know if it would be allowed as part of a cryptic crossword, but the number of letters in the (words of the) answer were 8, 4. The answer to that clue is included here: https://www.uh.edu/engines/epi2783.htm https://www.uh.edu/engines/epi2783.htm
- nilstycho 4y agoThat would usually be considered an invalid cryptic clue.
- tialaramex 4y agoAmerican Crosswords are different in two key ways as I understand it: Firstly, all "serious" British crosswords are "Cryptic" ie once you figure out what the answer is, it's apparent why that's the correct clue, but figuring out the answer from the clue involves lateral thinking and some skills learned from years of staring at such clues. e.g. Private Eye's crossword 726 (back in April), clue 23 down, "He finally gets to penetrate agreeable person (relatively) (5)" The correct answer is "Niece". "Nice" can mean agreeable, the final letter of "He" is E, and so by having the letter E "penetrate" the word nice you produce "niece", a person who is a relative. [ and yes, Private Eye is a satirical magazine, the crossword clues are, likewise, intended to make you a little uncomfortable while you laugh ] Secondly, British crosswords are arranged with black "dead" squares between letters to produce more of a lattice, in which many letters only take part in one word, as a result longer answers are common e.g. same crossword, clue 26 across is "Figure on getting your teeth into our statistical revelations (6,9)" The answer was "Number Crunching".
- jen729w 4y ago
- cinntaile 4y agoNow automatically send in the answers to the various weekly magazine and newspaper competitions to get a passive prize income.
- gardenfelder 4y agohttps://github.com/albertkx/berkeley-crossword-solver https://github.com/albertkx/berkeley-crossword-solver
- zwieback 4y agoMy dad was a big crossword puzzler. I asked him if he thought that if you pick one of two possible answers to the first clue whether it would be possible to solve the entire puzzle one way or another way. He sat down and created a series of puzzles with "themes", e.g. "north", "south" or "Schiller", "Goethe", where all the major words were from one or the other theme. Anyway, it would be interesting what the AI would do with this, would there be two hotspots in the solution space, one for each variant?
- mcherm 4y agoAlso famously the November 5 1996 NYT puzzle where a clue about the newly elected president could be solved either CLINTON or BOBDOLE and all the crossing words had two solutions. If they trained the AI on the NYT archive then they would have the results of testing it on this one.
- evanb 4y agoI do the puzzle every day. I've been collecting clues that have caused me trouble, a wrong answer. I hope someday to be able to construct such a puzzle with one set of clues and two complete but incompatible solutions. A thesaurus will get you far, but will never get you OREOCOOKIE and CHESSBOARD as answers for "It's all black and white" (from today's puzzle).
- mnd999 4y agoAnyone else getting a bit bored with all these AI does some super specialised task better than humans after enormous amounts of training. It’s not very interesting anymore. Sure, it can do crosswords well but the average human that does crosswords well can also do a zillion other things and this type of AI is not getting us any closer to that.
- DantesKite 4y agoIf you skim the paper, you’ll realize what’s most interesting are the new techniques they developed to accomplish this, advancing the field of machine learning in the process.
- JHonaker 4y agoConstraint propagation and search are hardly new techniques. In fact they're both from or from before the previous "AI winter." It's a shame they've been left out of so many of the deep learning generation's wheelhouses. They were considered fundamentals by the field a very short time ago. Also, I'm not knocking this paper at all. I think it's a great applied paper! Stitching together techniques to actually do something is a Herculean task. Hell, it's mostly what I do too.
- joshcryer 4y agoBut every specialized model like this is getting us closer to "doing a zillion other things." By logic it is exactly one step closer. The general AI agent will be composed of many such models.
- PeterisP 4y ago> The general AI agent will be composed of many such models. Not necessarily, there is good evidence that a single model can work for many tasks - for example, the recent Gato system https://www.deepmind.com/publications/a-generalist-agent https://www.deepmind.com/publications/a-generalist-agent is a good example. It's just that we usually don't do that because for most practical purposes we want an agent for a specific purpose, and for most research experiments we want a simpler experiment to isolate some factor, so we usually train single-task models and don't try to make general systems.
- interestica 4y agoIf you want to use two brains, 'partner mode' for the New Yorker's crossword has been great. Two persons can work on a single puzzle in real time. There may be other sites that allow it -- the software seems to power a few diff crossword sites (with certain features enabled/disabled).
- r0b05 4y agoMind blowing stuff.