Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What a crossword AI reveals about humans' way with words

wired.com

Post reply on HN
Print view View original

21–30 of 50 posts

Re: What a crossword AI reveals about humans' way with words

#21

Post by tsimionescu »

djrockstar1 wrote: post #4
isolli wrote: post #3

"But, unlike more than 200 human solvers, it wasn’t perfect on all of the puzzles: It got waylaid on two of them and finished with errors." I'm curious, what kind of error are we talking about? Words that don't exist, or another solution to a problem that may not have a unique solution?

Also, as a novice to crosswords, how do puzzle makers ensure that they have a unique solution?

In a crossword puzzle, each word shares letters with at least two other words, likely many more. So, without any effort from the puzzle desogner, it is very unlikely to actually have all of the words have ambiguous enough solutions that match the letter count etc. Even a crossword where half the clues are 'any word' will have a good chance of having a unique solution overall.

Of course, people don't like to play crosswords like sudoku, blindly matching letters, so there does have to be some skill to the clue design to have a relatively small amount of plausible answers, if not being entirely unique.

Re: What a crossword AI reveals about humans' way with words

#22

Post by SamBam »

bvm wrote: post #9

> The crossword solver is a closed system—it can’t just Google the answers. yet from the wiki: > Probabilities for individual words or phrases in the puzzle are computed using relatively simple statistical techniques based on features such as previous appearances of the clue, number of Google hits for the fill. https://en.wikipedia.org/wiki/Dr.Fill I don't think it's fair to describe it as a closed-system if it's Goo…

It's not googling stuff live, it's using a pre-computed database.

Re: What a crossword AI reveals about humans' way with words

#23

Post by SamBam »

tsimionescu wrote: post #19
tasogare wrote: post #16

Earlier quoted context omitted.

> Non-existent words should be easy to check for. I'm interested in your magical solution because this is a hard problem.

You should have given more detail on why this problem is deceptively hard. I am guessing that the simple solution of looking up the word in the dictionary seems to work ok (especially in the context of an artificial competition, which doesn't have to accept uncommon spellings, words in other languages etc), but still breaks down hard because of proper names, which are common in cross-words.

I think the point is that "Non-existent words should be easy to check for" is a useless metric, because plenty of answers are non-existent words. Proper names and things like that, many of which the computer may not have in its database.

So it can't simply blindly reject answers that are non-existent words.

An example of how this computer could make a mistake: Sometimes two proper names are crossing at a vowel. If you don't know either name, you sometimes have to guess blindly at the answer. (This exact scenario is rare in crosswords like the Times, but do occasionally come up, and similar scenarios exist.)

Re: What a crossword AI reveals about humans' way with words

#25

Post by tzs »

isolli wrote: post #3

"But, unlike more than 200 human solvers, it wasn’t perfect on all of the puzzles: It got waylaid on two of them and finished with errors." I'm curious, what kind of error are we talking about? Words that don't exist, or another solution to a problem that may not have a unique solution?

I wonder how it does on puzzles where the answers need to be written in unusual ways? Some examples from the New York Times puzzles.

- There was one with a name that suggested an Alice in Wonderland connection, and it had an answer "THE LOOKING GLASS" (no spaces) running vertically down the full length of the center of the grid.

Every across answer that was entirely to the left of that was written normally. Every across answer entirely to the right was written backwards. Every across answer that crossed the center was a palindrome centered on the center.

- There was one where several answers were triple Spoonerisms of well known phrases.

For example, the answer "THE STUCK HOPS BEER" for the clue "Tagline in an ad for Elmer's Glue-Ale". Rotate the ST from STUCK, the H from HOPS, and the B from BEER and you get "THE BUCK STOPS HERE".

- I remember one that had a few isolated black squares, and a theme that suggested the puzzle had something to do with roundabouts.

Those black squares were roundabouts. Answers would hit the roundabout and continue after a 90 degree turn.

- I remember one where the theme was something like "What goes up must come down". That had several answers that, like the roundabout one above, would take a 90 degree turn from across but it was a left turn so after the turn they went up. Then there would be a down answer whose start was the reversed end of that across answer that would come down, also make a left tern, and continue across to the right.

Re: What a crossword AI reveals about humans' way with words

#26

Post by jameshart »

sweezyjeezy wrote: post #12
bvm wrote: post #7

I would be interested to see how they perform on UK-style cryptic crosswords ( https://en.wikipedia.org/wiki/Cryptic_crossword ) where there's much more play/subversion/meta-approach to the "rules".

I think it's pretty unlikely you'll be able to learn the UK rules to a human level using brute force ML - take a fairly easy clue like ‘Drunken men are more despicable' - you need to split this as (wordplay = drunken (anagram of) "men are") / (meaning = "more despicable") = "MEANER" This is really hard for supervised learning - the reward is quite sparse (e.g. did you get it right / how many characters did you get ri…

You might not need to codify the rules; you could create a tagged training set which includes additional information, like a ‘parts of speech’ breakdown of how a clue relates to an answer (anagramSignifier - anagramMaterial - association, etc.)

An unsupervised learner could probably do reasonably well at picking up on those patterns, even to the point of considering that a word it hasn’t seen used as an anagram signifier before might be doing that job in a particular clue.

On the other hand, machine translation learning has moved away from using tagged parts of speech as far as I’m aware, and it has nonetheless managed to develop sufficient internal modeling that it is as if it has learned parts-of-speech tagging; it’s possible that an ML on a cryptic clue corpus could develop those same hidden models.

Re: What a crossword AI reveals about humans' way with words

#27

Post by EGreg »

SamBam wrote: post #22
bvm wrote: post #9

> The crossword solver is a closed system—it can’t just Google the answers. yet from the wiki: > Probabilities for individual words or phrases in the puzzle are computed using relatively simple statistical techniques based on features such as previous appearances of the clue, number of Google hits for the fill. https://en.wikipedia.org/wiki/Dr.Fill I don't think it's fair to describe it as a closed-system if it's Goo…

It's not googling stuff live, it's using a pre-computed database.

Sounds like how AlphaGo beat Stockfish or Rybka… massive precomputing vs alphabeta search in real time

Re: What a crossword AI reveals about humans' way with words

#29

Post by bvm »

SamBam wrote: post #20
sweezyjeezy wrote: post #15

Earlier quoted context omitted.

Very cool - the fact that it explains the solution makes me almost certain they have codified the rules here.

Actually, one of the interesting things about cryptic crosswords is that, in some ways, the rules are far more codified. The specifics definitely depend on the paper, of course, but basics like the fact that the majority of the clues are actually two halves, clueing the word two different ways, and that anagrams are always explicitly clues using words such as "scrambled," "drunken," "off" or whatever could actually m…

well yes, but the beautiful thing about UK cryptics at least is that they regularly intentionally misdirect the user, so you spend some time going down a rabbit hole and realise that you're on a hiding to nothing. I think that kind of game play is what makes a rules-based approach more challenging. I'll have to check out Crossword Genius though.

Re: What a crossword AI reveals about humans' way with words

#30

Post by sillysaurusx »

EGreg wrote: post #27
SamBam wrote: post #22

Earlier quoted context omitted.

It's not googling stuff live, it's using a pre-computed database.

Sounds like how AlphaGo beat Stockfish or Rybka… massive precomputing vs alphabeta search in real time

Hmm. AlphaGo and AlphaZero were trained using self play. I don't think there was any precomputing, unless you count training as precomputation.
Post reply on HN