[HN Gopher] I was terrible at crosswords so I built an AI to do ...
___________________________________________________________________
I was terrible at crosswords so I built an AI to do them
Author : ColinWright
Score : 66 points
Date : 2021-05-03 09:19 UTC (13 hours ago)
(HTM) web link (www.bbc.co.uk)
(TXT) w3m dump (www.bbc.co.uk)
| thrower123 wrote:
| I did the NY Times crossword for several years, and got to the
| point that it was pretty easy. The key is that all of their junk
| fill words come from the same bank of words and clues. Sometimes
| you'd see the same clue three out of five days.
|
| You combine that with the Jeopardy-level trivia clues, that are
| hard if you aren't familiar at all but obvious if you are, and
| that just leaves the gimmick.
|
| Usually the gimmick isn't that tricky, if you get one, and can
| see the pattern. Except the damned rebuses. Those are always hard
| because they feel like they are breaking the rules.
| Tycho wrote:
| I have toyed with the idea of training an AI system to help solve
| UK cryptic crosswords.
|
| In these crosswords, found in newspapers such as _The Times_ of
| London, the answers to clues are defined by words or phrases at
| the start or end of the clue (for the vast majority of clues -
| occasionally it's both, a double definition, or the whole clue is
| the definition).
|
| Half the battle is guessing which part of the clue is the
| definition (the rest of it bring some kind of hint, such as an
| anagram). I bet an AI system could learn some rules that would
| help you decide if you should be focusing on the start or the
| end. There's a blog called _Times for the Times_ where people
| helpfully upload annotated answers, underlining the part of the
| clue that is the definition.
|
| Point would be to learn new strategies to use as a human, not
| just to create an AI solver.
| [deleted]
| rm445 wrote:
| Not seen that name in a while. Matt Ginsberg is a man of many
| accomplishments, but I had heard of him due to his contributions
| to computer contract bridge - his 90s-era world computer bridge
| champion program Gib (Ginsberg's Intelligent Bridgeplayer). In
| bridge, a game of imperfect information, it used the approach of
| dealing thousands of hands that opponents potentially could have,
| analysing them with perfect information, and taking the action
| that was statistically favoured. Interestingly, bridge programs
| seem to have somewhat stalled since. No doubt they've been
| improved but they can't beat world-class players even today.
| Though that might be lack of resources thrown at the problem.
|
| https://en.wikipedia.org/wiki/Computer_bridge
| Agentlien wrote:
| It would be interesting to hear more about this from someone
| whose field this is.
|
| My first naive thought was that surely it's lack of eyes on the
| problem. After all, we have AlphaGo. Then again, I can't say
| I've heard much about AI in games with imperfect information.
| There's StarCraft 2, but there AI has not quite surpassed
| humans.
| oscardssmith wrote:
| One thing that makes bridge very difficult is you need to be
| able to explain your partner's bids to your opponents. This
| means you either have to hard-code a bidding system (lame) or
| make a ton of progress in explainable ai.
| onceiwasthere wrote:
| Something you might be interested in is the OpenAI group's
| attempt at making a Dota 2 playing AI which, if you're
| unfamiliar, is a 5v5 imperfect information computer game. The
| AI they made was able to take games off of many top
| players/teams. The interesting factor on top of all that is
| that it isn't a single AI playing as 5 players, its 5 AIs
| acting independently without communication. Really
| interesting stuff given how complex a game Dota 2 is.
| oneeyedpigeon wrote:
| This might relate to the UK/US differences, but:
|
| > American-style crosswords, on the other hand, require both
| knowledge and a degree of lateral thinking.
|
| > One question that Prof Klein is particularly proud that Dr Fill
| got right was: "Pasta dish at the centre of a murder mystery."
|
| > The answer was poisoned penne.
|
| Does "poisoned penne" actually mean anything as a complete
| phrase? This clue is very different from a UK cryptic crossword -
| wordplay features heavily, but answers still have a coherent
| meaning. Maybe this is why the US crosswords are more complicated
| for an AI.
| BenFrantzDale wrote:
| NYT crosswords have a theme. I would imagine "poison penne" is
| one of the theme answers along with other pasta-based
| alliterations. Once you know that's the game, then it's not a
| weirdly meaningless pun but wordplay that builds as you first
| figure out the theme and then figure out the theme answers.
| jeffwass wrote:
| I've been doing the NYT crossword regularly the past year or
| so.
|
| NYT crosswords often have tricks, either in the clues
| themselves or patterns in the puzzle. Will Shortz commented on
| one of his favourite clues Q: "It may turn into another story"
| A: Spiral Staircase.
|
| There are others I've found sneaky, eg Q: Greek Leader. A:
| Alpha
|
| Today's puzzle had for example Q: Whopper Junior A: Fib
|
| 2. Some puzzles have rebus answers, where more than one letter
| will fill a single square. It's not obvious when this is the
| case
|
| 3. Sometimes there is an overall pattern to the puzzle. One
| recent example was a rebus where several squares had double O
| rebuses in single square. If you connected these squares
| together they formed the shape of a 7, ie 007. A few clues on
| the puzzle related to James Bond and would be meaningless
| without this context, eg the clue would mention a range of
| years and the answers were Sean Connery or Daniel Craig.
| dnautics wrote:
| IIRC when I was doing NYT the super tricky rebuses (the one I
| remember was "bell" being the rebus and you could draw a bell
| in the square) are only allowed to be on one day of the week.
| Sunday, was it?
| markelliot wrote:
| They're most common on Thursdays but increasingly appear on
| Wednesdays, too. Sunday is typically the "big" puzzle day,
| and has a titled theme that usually provides a hint to at
| least some of the clues, or the puzzle aspect.
| tzs wrote:
| > Some puzzles have rebus answers, where more than one letter
| will fill a single square. It's not obvious when this is the
| case.
|
| Another deviation from the "one letter per square, all in a
| line" that they sometimes have is the bent answer. I recall
| one for instance where there were several isolated black
| squares, and some answers that ran into these continued after
| a 90 degree turn. So you might have 5 spaces to the left of
| the black square, but the answer was actually 9 letters with
| the last 4 written upward from the black square.
|
| As with rebuses, they don't tell you that a puzzle has this
| sort of thing. You are left to figure it out on your own. For
| that 90 degree turn example, you'd probably get it by filling
| in enough of the words that cross it to notice that the 5
| space section matches the start of a 9 letter word that would
| work, and notice that the 4 letters that would complete that
| word are going up from the black square. That seems unlikely
| to be a coincidence, and then you'd go look at other places
| where the answers seemed to short and see that same trick
| works there.
|
| I don't think I've seen any the have both rebuses and non-
| linear answers. That would be a nightmare.
| Zenst wrote:
| One UK crossword that always stuck in my mind and captures a
| form of word play was: Clue: Scrambled Eggs Answer: Gegs
|
| That without working out the other clues would make that alone
| very hard to work out and be interesting how an AI would work
| that one.
| mangamadaiyan wrote:
| Gegs is usually cited as an example of a _bad_ clue in
| cryptic crossword circles.
| hencq wrote:
| UK crosswords also have patterns though. Words like scrambled
| in this case often indicate you're looking for an anagram.
| mjw1007 wrote:
| I think the basic idea would be OK in a UK cryptic, but you'd
| clue the pun explicitly.
|
| You might have something like << Pasta dish at the centre of a
| murder mystery and a spiteful reviewer on the radio. >>
|
| Though you'd really want the surface reading to come out a bit
| smoother (and I don't think "penne" and "pen" are pronounced
| exactly the same).
| oneeyedpigeon wrote:
| I genuinely can't think of an example of a broadsheet cryptic
| crossword that would do so. Maybe other sources, though.
| wccrawford wrote:
| I haven't done a ton of crosswords in the US (because I don't
| really enjoy them) but I haven't experienced "pun" clues like
| that very often. They're usually in crosswords that think
| themselves special somehow. You can tell because it'll be a
| famous source, or the description will tell you way too much
| about the author of the puzzle and how awesome they are.
|
| The majority of the crosswords just had plain clues that
| weren't confusing. (And didn't require "lateral thinking".)
| zem wrote:
| to expand on other answers, a themed NYT crossword often has
| four or so entries that involve some sort of punnery or
| wordplay, and are not actual words or phrases but can be
| deduced from a combination of a real word/phrase and the theme.
| so in this case there might have been other entries like
|
| Pasta dish served at a burger joint: BIG MACARONI
|
| Lose your temper at some pasta: BLOW A FUSILLI
|
| etc.
| GrumpyNl wrote:
| We call them anagram puzzles, crosswords puzzles are for us
| other words with the same meaning.
| alisonkisk wrote:
| It's not an anagram, it was portmanteau (in this case, but
| other wordplay is seen too).
|
| Also, folks in the thread are ignoring Henry Hook, a famous
| UK constructor who used plenty of "non-standard" wordplay.
| zem wrote:
| henry hook was american (and wrote american style
| cryptics, which are very similar to uk cryptics but have
| a few stylistic differences)
|
| also i'd say portmanteau clues (and rebuses) are standard
| wordplay for an nyt crossword, they just unfamiliar to
| people who don't do that kind.
| throwaway287391 wrote:
| It's likely from a NYTimes (or maybe LATimes or WaPo) crossword
| where all 4-10 of the longest answers followed the same punny
| format. But yes, it's intentionally left up to the person
| solving to figure out the theme, usually by filling many of the
| easier/shorter non-theme answers first. This style makes these
| prestige hand-crafted crosswords (like those in the NYT and a
| couple other outlets) particularly satisfying/rewarding to
| solve. The themes can be amazingly creative and original on a
| daily/weekly basis.
| Ensorceled wrote:
| It's a pun ... a terrible, terrible pun.
| oneeyedpigeon wrote:
| Sure, I get that "poisoned penne" is a pun on "poisoned pen",
| I was just wondering if there was a real meaning to the
| complete phrase. In a UK crossword, the answers all have to
| be legitimate words/phrases.
| DoomHotel wrote:
| Penne is a type of pasta, so the phrase does make sense on
| its own. Does "poisoned spaghetti" mean anything to you?
| oneeyedpigeon wrote:
| It doesn't make sense outside of the pun. "Poisoned
| spaghetti" makes as much sense as "poisoned penne", in
| those terms.
| austinjp wrote:
| (Not arguing, just adding some perspective.)
|
| Penne is pronounced "pennay" in the UK in my experience,
| making this pun kinda dysfunctional.
|
| Also as pointed out, UK cryptic crossword answers are
| phrases in actual use, not new word combinations.
|
| Edit to add relevant example:
|
| See 9 across ("Rotten people sin to produce malicious
| missive") here: https://www.fifteensquared.net/2021/03/08
| /independent-10733-...
|
| I also noticed that "poisoned pen" isn't a phrase in
| British English, instead it's "poison pen" or more
| typically "poison pen letter".
| StavrosK wrote:
| Is it pronounced "pen" anywhere? That sounds very wrong
| to me.
| austinjp wrote:
| Indeed... it seems that the consensus is tending towards
| this being so bad a pun that it isn't even a pun :)
| StavrosK wrote:
| It's a poisoned punne.
| whoisburbansky wrote:
| Leads right into a clue hinting at Canadian origins, a la
| "poisoned pen, eh?"
| boffinism wrote:
| So in the UK 'poisoned spaghetti' would not be acceptable
| as a cryptic crossword answer, because it's not a
| _recognisable_ standalone phrase, even if it's a thing
| that could exist.
| bryanrasmussen wrote:
| penne is a type of pasta, so yes it means a poisoned pasta of
| type penne.
| Tycho wrote:
| the phrase is meaningful, but it's not a recognised phrase
| like "on a roll"
|
| UK cryptics feature answers which are words or phrases you'd
| find in a dictionary
| imgabe wrote:
| A poison pen is any maliciously written letter. I've always
| heard it in relation to an overly harsh, negative review. So,
| this is a terrible pun on that.
|
| https://www.merriam-webster.com/dictionary/poison-pen
| boffinism wrote:
| In the UK, terrible puns are de rigeur, but the answer has to
| be a recognisable standalone word or phrase. So 'poisoned
| pen' could be an answer, and the clue could conceivably
| contain a pasta-based pun on that, but 'poisoned penne' could
| not.
| bl0b wrote:
| In the US, at least (TIL there's a different style across
| the pond, so fun), a 'pun-based' clue like that would need
| a question mark at the end of the clue.
|
| Additionally, I would say that that, because the answer
| isn't a coherent standalone word/phrase, that particular
| clue/answer combo would only be found in a puzzle as part
| of a hidden theme shared by a number of 'special clues'
| throughout the crossword, with some kind of rule uniting
| the answers (add 'ne' to the end of a common phrase, for
| example).
| mcphage wrote:
| So the puns need to be in the clue, and not the answer?
| oneeyedpigeon wrote:
| You could have a pun in the answer - although I think
| that's pretty rare - but the answer itself would still
| need to be a recognized word/phrase.
| mcphage wrote:
| That's really interesting--I'm not much of a crosswords
| fan, but I had never even considered the idea that there
| are "dialects" in what crosswords clues & answers could
| be.
| Zanni wrote:
| "Poison pen" (or poisoned pen) is the phrase the answer is
| punning on.
| rovek wrote:
| I don't know if this is a cultural difference with cryptic
| crosswords in general or if it's specific to NYT crosswords, I
| used to do NYT crosswords with my American partner (I'm
| British) and the wordplay never made sense to me. Answers often
| seemed to be made up of words which could literally relate to
| the clue but combined made no sense as a term or phrase, even
| as a pun.
|
| Edit: Don't want to sound like I'm deriding their style too
| much, my partner always got the wordplay so clearly there was a
| learnable style to it
| zem wrote:
| yep, the thematic entries are nothing like cryptics; the only
| similarity is that they both involve wordplay. the wordplay
| here is closer to jokes like "what fruit wanted to conquer
| the world?" "alexander the grape!" - that is, while the
| answer will not be a real word or phrase as would be required
| in a cryptic, it will be logically derivable from the theme
| and the clue.
|
| one interesting thing about the _non-thematic_ entries in an
| american crossword is that the only form of wordplay they
| allow is what in cryptic parlance would be called a "cryptic
| definition", that is, a clue which is a straight definition
| in which the words need to be read laterally. the nyt cryptic
| definitions are as good as any i've seen in the guardian,
| particularly my all-time favourite,
|
| John, to Ringo (3)
|
| for LOO
| whoisburbansky wrote:
| I don't actually get how "John, to Ringo" translates to
| LOO, would you mind explaining?
|
| [Edit]: Ah, totally missed the toilet connotation, thanks
| folks!
| zem wrote:
| specifically, 'john' is american slang for a toilet; the
| corresponding british slang is 'loo'. 'ringo' is an
| example of a very well known englishman, so 'to ringo' is
| an acceptable indicator to clue 'to an englishman'.
| SlickNik wrote:
| I suspect - John is slang for the toilet, and Ringo here
| would be an Englishman - so what would an Englishman call
| a toilet? A loo. _groan_
| simondw wrote:
| "John" is another word for bathroom. So is "loo", at
| least in the variety of English that Ringo speaks.
| Normille wrote:
| >I used to do NYT crosswords with my American partner (I'm
| British) and the wordplay never made sense to me
|
| Can't say I've ever tried an American cryptic [I regularly do
| the UK Guardian and Telegraph ones] but the ones quoted above
| don't make sense to me either: >Q: "It may
| turn into another story" A: Spiral Staircase.
|
| Would be "...turn into another storey". In a UK cryptic
| there'd have to be an indication that there was a homonym
| involved story/storey. >"Pasta dish at the
| centre of a murder mystery...The answer was poisoned penne.
|
| Ditto. UK version would need to indicate a homonym was
| involved pen/penne. And, as someone else points out, a
| 'Poisoned Pen' is a letter, not a murder mystery. Very
| strange clues indeed.
|
| Some freely available UK cryptics:
|
| * Guardian Quiptic:
| https://www.theguardian.com/crosswords/series/quiptic/latest
|
| * Guardian Everyman:
| https://www.theguardian.com/crosswords/series/everyman
|
| * Chambers: https://chambers.co.uk/puzzles/cryptic-
| crosswords/
|
| RANDOM ASIDE: My favourite anagram, which has been involved a
| couple of times in UK cryptic clues is:
|
| VINDALOO AND RICE which is an anagram of LEONARDO DA VINCI
| mcphage wrote:
| > In a UK cryptic there'd have to be an indication that
| there was a homonym involved story/storey.
|
| Well, that one can be chalked up to US/UK spelling
| differences--"storey" is not correct US spelling.
| hoppyhoppy2 wrote:
| I'm just a casual, very infrequent crossworder, but I've
| noticed that many of the more punny or clever clues for NYT
| Crossword end in a question mark. If you see "It may turn
| into another story?" as a clue in a NYT crossword you know
| from the question mark that there's probably some wordplay
| or a pun involved in the answer.
| tzs wrote:
| Yup. There are several rules for how clues relate to
| answers in the NYT puzzle, and that's an import one. Here
| are some more [1].
|
| Another thing casual or infrequent solvers should be
| aware of: day of week matters. NYT puzzles are easiest on
| Monday, getting progressively harder throughout the week
| reaching a peak on Saturday. The Sunday puzzle is midweek
| difficulty, but bigger.
|
| This article [2] gives an example of how the same 4
| letter word might be clued on Monday and Saturday:
|
| Monday: "Nabisco cookie", "Cookie with creme filling", or
| "'Twist, Lick, Dunk' cookie"
|
| Saturday: "Snack since 1912", "It has 12 flowers on each
| side", or "Sandwich often given a twist"
|
| [1] https://www.nytimes.com/crosswords/tips-and-tricks
|
| [2] https://www.nytimes.com/guides/crosswords/how-to-
| solve-a-cro...
| ellipsisfrog wrote:
| From the perspective of this UK cruciverbalist that's a
| terrible clue. You can't just clue anything you like and call
| it a cryptic definition. I would argue there isn't even a
| proper definition component to the clue since 'poisoned penne'
| isn't a 'pasta dish' in any normal usage. A fair way to clue
| this would be to indicate the pun and use normal composite
| clueing (e.g. anagrams).
| simondw wrote:
| Well, from the perspective of a Ruby programmer, Python is
| terrible Ruby code. There are different rules and conventions
| in American crosswords; you might actually learn to enjoy
| them once you got past your initial "This is different! And
| therefore terrible!" reaction.
| tzs wrote:
| I wonder how it would handle a puzzle where letters are written
| out of order?
|
| I remember a NYT puzzle sometime within the last 2 or 3 years
| with a 15 character vertical answer spanning the puzzle from top
| to bottom right down the center with a clue related to Alice in
| Wonderland. The answer was "the looking glass".
|
| Everything entirely to the left of the looking glass was normal.
| Horizontal answers entirely to the right of the looking glass
| were reversed. Horizontal answers that crossed the looking glass
| were all palindromes centered on the looking glass.
|
| BTW, for those interested in the NYT puzzle but not interested in
| the newspaper, here's a trick to save some money.
|
| The puzzle and the paper are sold as separate products. The print
| editions are always bundled together, but the digital editions
| are separate. The puzzle is about $40/year. However, if you also
| subscribe to the digital newspaper, you get a 50% discount on a
| puzzle subscription.
|
| Here's the trick: if you have the puzzle subscription set to
| automatically renew it continues to renew at the 50% discount
| rate even if you have cancelled the newspaper subscription.
| riveducha wrote:
| They have a very aggressive retention team to try to discourage
| you from cancelling. If you subscribe to (just) the crossword
| and tell them you want to cancel, they will offer you a lower
| monthly rate. Not sure if this violates California law
| requiring easy cancellation, but it's another way to subscribe
| for less.
| agumonkey wrote:
| side note: I found doing crosswords in a foreign language a
| superb and powerful way to increase knowledge of it at the
| vocabulary and idiom level. It's more fun than repetitive
| remembering technique IMO.
| 6gvONxR4sf7o wrote:
| That sounds incredibly hard. I have trouble with them in my
| native language!
| pncnmnp wrote:
| For fun, a while back, I built a small-scale crossword solver. It
| used Moby's thesaurus, pre-trained word vectors, and Wordnet to
| guess probable solutions and used an SMT solver to arrange those
| solutions on the grid.
|
| Github: https://github.com/pncnmnp/Crossword-Solver
|
| Blog-post: https://pncnmnp.github.io/blogs/crossword-1.html
| 082349872349872 wrote:
| As an etude, problem 99 of the "Ninety-nine Prolog Problems" is a
| "crossword puzzle" that's much more approachable than the subject
| of TFA.
| 11235813213455 wrote:
| I had same approach for 2048, ruzzle and a few others things
| https://caub.github.io/misc/#some-scripts (marked [AI])
| crocsarecool wrote:
| This is really cool! I am terrible at crosswords also, but I
| still do them. I have a rule that if I get stuck, I can look at
| the answer, but I have to read the Wikipedia page about it.
___________________________________________________________________
(page generated 2021-05-03 23:01 UTC)