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

41–50 of 50 posts

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

#41

Post by pessimizer »

weeblewobble wrote: post #38

A few years back I wrote a program that, given a blank or partially-filled in (NYT-style) crossword grid (with black squares already inserted), could fill out the rest of the grid with valid words/phrases both across and down. It had no relation to clues though, you had to write the clues yourself after the grid was filled out. I wrote it because I wanted to make my dad (a huge nyt crossword fan) a custom crossword f…

Don't use that as a final product, use it as a crossword book generator. Selling the books would be a lot more lucrative (or selling the actual puzzles to someone who already prints crosswords.)

Especially if you can generate them from arbitrary lists of of clues:words.

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

#42

Post by xkeysc0re »

weeblewobble wrote: post #38

A few years back I wrote a program that, given a blank or partially-filled in (NYT-style) crossword grid (with black squares already inserted), could fill out the rest of the grid with valid words/phrases both across and down. It had no relation to clues though, you had to write the clues yourself after the grid was filled out. I wrote it because I wanted to make my dad (a huge nyt crossword fan) a custom crossword f…

There is Phil, the free crossword maker http://www.keiranking.com/apps/phil/ but I haven't had the best luck with its automated fill. Lately I've been using Crossfire http://beekeeperlabs.com/crossfire/ to make puzzles and its auto fill is quite versatile, even if some of the choices can be iffy (but easily fixed with some manual tweaking). You can even provide your own custom dictionary for it to use in the fill.

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

#43

Post by peab »

weeblewobble wrote: post #38

A few years back I wrote a program that, given a blank or partially-filled in (NYT-style) crossword grid (with black squares already inserted), could fill out the rest of the grid with valid words/phrases both across and down. It had no relation to clues though, you had to write the clues yourself after the grid was filled out. I wrote it because I wanted to make my dad (a huge nyt crossword fan) a custom crossword f…

I did the same thing, as a side project when covid first hit. It's a fun and difficult problem to solve efficiently. I remember seeing some videos on YouTube of algorithms that could do it as well.

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

#44

Post by EGreg »

sillysaurusx wrote: post #30
EGreg wrote: post #27

Earlier quoted context omitted.

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.

Precomputation on a huge cluster for a long time

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

#45

Post by weeblewobble »

peab wrote: post #43
weeblewobble wrote: post #38

A few years back I wrote a program that, given a blank or partially-filled in (NYT-style) crossword grid (with black squares already inserted), could fill out the rest of the grid with valid words/phrases both across and down. It had no relation to clues though, you had to write the clues yourself after the grid was filled out. I wrote it because I wanted to make my dad (a huge nyt crossword fan) a custom crossword f…

I did the same thing, as a side project when covid first hit. It's a fun and difficult problem to solve efficiently. I remember seeing some videos on YouTube of algorithms that could do it as well.

nice, what did you end up going with? I built a "scoring" function for candidates based on how many other words can intersect each letter (based on grid layout and squares already filled) plus a backtracking system. ended up working pretty well, although each grid took >1 minute. I used an NYT historical word list as the dictionary

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

#46

Post by weeblewobble »

xkeysc0re wrote: post #42
weeblewobble wrote: post #38

A few years back I wrote a program that, given a blank or partially-filled in (NYT-style) crossword grid (with black squares already inserted), could fill out the rest of the grid with valid words/phrases both across and down. It had no relation to clues though, you had to write the clues yourself after the grid was filled out. I wrote it because I wanted to make my dad (a huge nyt crossword fan) a custom crossword f…

There is Phil, the free crossword maker http://www.keiranking.com/apps/phil/ but I haven't had the best luck with its automated fill. Lately I've been using Crossfire http://beekeeperlabs.com/crossfire/ to make puzzles and its auto fill is quite versatile, even if some of the choices can be iffy (but easily fixed with some manual tweaking). You can even provide your own custom dictionary for it to use in the fill.

The Phil auto-fill button doesn't do anything for me. Crossfire looks like it has this feature though, and it's probably a lot faster than mine

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

#47

Post by peab »

weeblewobble wrote: post #45
peab wrote: post #43

Earlier quoted context omitted.

I did the same thing, as a side project when covid first hit. It's a fun and difficult problem to solve efficiently. I remember seeing some videos on YouTube of algorithms that could do it as well.

nice, what did you end up going with? I built a "scoring" function for candidates based on how many other words can intersect each letter (based on grid layout and squares already filled) plus a backtracking system. ended up working pretty well, although each grid took >1 minute. I used an NYT historical word list as the dictionary

interesting - I was trying to think of a backtracking system as well, but wasn't able to create something efficient. Did it work well for large dense crosswords?

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

#48

Post by pwdisswordfish0 »

weeblewobble wrote: post #38

A few years back I wrote a program that, given a blank or partially-filled in (NYT-style) crossword grid (with black squares already inserted), could fill out the rest of the grid with valid words/phrases both across and down. It had no relation to clues though, you had to write the clues yourself after the grid was filled out. I wrote it because I wanted to make my dad (a huge nyt crossword fan) a custom crossword f…

I’ve used QXW very successfully.

The trick is to have a good word list… I’m working on one for German, but it’s a bit of an undertaking and I guess pretty subjective.

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

#49

Post by tsimionescu »

tasogare wrote: post #32
tsimionescu wrote: post #19

Earlier quoted context omitted.

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.

There is no dictionary that contains "all existing words" for any giving language.

It depends a lot on what you mean by a language. Iglf you define 'the English language' as 'all of the words that some amount of people who identify as speaking English would understand', then of course there is no dictionary that would cover that (but by this definition, many words in the English language are Indian, Chinese, Romanian, Russian, etc, and would be completely incomprehensible to the vast majority of people in the USA or England). On the other hand, many people define the concept of a 'correct English word' as 'any word with a definition in the OED or Merriam Webster (ignoring proper nouns)', and leave other words as being 'wrong/foreign language'.

Either way, this is all moot when discussing a crossword puzzle contest, which explicitly limits itself to words in a specific dictionary + proper nouns. The problem of proper nouns is still extreme, and brings down the whole idea, but at least the problem of recognizing 'all possible common nouns that could be present in the crossword contest' is simple.

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

#50

Post by eutectic »

peab wrote: post #47
weeblewobble wrote: post #45

Earlier quoted context omitted.

nice, what did you end up going with? I built a "scoring" function for candidates based on how many other words can intersect each letter (based on grid layout and squares already filled) plus a backtracking system. ended up working pretty well, although each grid took >1 minute. I used an NYT historical word list as the dictionary

interesting - I was trying to think of a backtracking system as well, but wasn't able to create something efficient. Did it work well for large dense crosswords?

I had good success using a DAWG for pruning, and letter-wise (rather than word-wise) branching, picking the letter with fewest options. If you want to get fancy, you can use back-jumping instead of backtracking.
Post reply on HN