Computer tries crossword puzzles
Poll
 | 8 votes (30.76%) | ||
| | 18 votes (69.23%) |
26 members have voted
Quote: YoDiceRoll11Running.....eating........and crosswords? Where do I sign up?
Check out the thread 'Wizards Challenge'... David attempted to run 2 miles, do 2 New York Times Crossword puzzles, and eat 100 Chicken McNuggets in less than 1 hour. Alas, he made it to 88 Mcnuggets and had to abort the attempt, resulting in a loss. I believe the Wiz will accept a challenge from you if you think you can do it.
Quote: SOOPOOAs some might remember, my son competed in the Wizard's challenge, which included running, eating, and crossword puzzling. He is the current World Champion in crossword puzzling in the under age 25 division, and came in 11th place overall in 2011. He will be defending his under 25 title next month and trying to move into the overall top 10 next month. Of note, this year there will be a computer, named Fill, competing. The inventor of the computer program named Fill has stated that his program would have won the competition many times in the past if it had been competing. Will the computer beat the humans? David, my son, says he is up to the challenge. Wiz- with the limited information you have, what do you make the morning line?
I don't think computers can eat Chicken McNuggets so the Wizard's Challenge is safe for now. However, my instinct says a heuristic software algorithm should be able to crush a human in a crossword competition.
Here's the paper on Dr. Fill, the crossword solver. It is apparently in the top 50 crossword solvers in the world, and since this paper was published less than a year ago, I expect that within short order humans will be a distant second to machines in this field.
http://en.wikipedia.org/wiki/Cybernetic_revolt
http://www.robotapocalypse.net/
Quote: MathExtremistI don't think computers can eat Chicken McNuggets so the Wizard's Challenge is safe for now. However, my instinct says a heuristic software algorithm should be able to crush a human in a crossword competition.
Here's the paper on Dr. Fill, the crossword solver. It is apparently in the top 50 crossword solvers in the world, and since this paper was published less than a year ago, I expect that within short order humans will be a distant second to machines in this field.
Perhaps..... but David thinks he can beat Fill this March at the New York Times Crossword Competition (also referred to as the world championship). Since David does not think he will have improved enough to crack the top 3 in the world this year, his goal is to beat Fill. I'm still waiting for the Wiz to chime in on a betting line.
Really, this is mostly comprehension and data retrieval. So long as the machine understands the clue, it can solve the puzzle. Better yet, it can also try a brute force approach if it knows one or two letters in a word. How long would it take a computer to run all, say, six-letter words containing "r" as the third letter and meaning something specific?
But then I do quite badly at crossword puzzles.
Quote: DocI haven't read the article and don't know the approach to programming the computer. I suspect that the computer would be at some disadvantage on those clues which involve puns or other mis-direction clues where a human would be expected to use some lateral thinking. It is particularly tricky when it is not at all obvious that the clues are some kind of twist or play. Are computers any good at figuring that out? I often finally understand a clue only after having filled in the word from other directions.
That is why I think the top humans, my son included, might have an advantage. The puzzles they do in the competition are filled with nuances and double entendres. Its not like the USA today puzzle with questions like... 3rd US president...
One example question might be.... 'Musical' gambling guru--- the answer ----- WizardofOdds
Or "junk" food- the answer------ testicles
I don't know how a computer can be programmed to get those answers..... But I am no expert on artificial intelligence.......
I admire your son's entrance into the world of " man versus machine" challenges. But I fear the outcome will not be one he enjoys.
SIGH
Quote: buzzpaff" John Henry's prowess as a steel-driver was measured in a race against a steam powered hammer, which he won only to die in victory with his hammer in his hand. "
I admire your son's entrance into the world of " man versus machine" challenges. But I fear the outcome will not be one he enjoys.
SIGH
This thread has been up for a while... and I know who the only forum member (me) that voted for him is! I'm still waiting for a betting line....
Quote: DocI haven't read the article and don't know the approach to programming the computer. I suspect that the computer would be at some disadvantage on those clues which involve puns or other mis-direction clues where a human would be expected to use some lateral thinking. It is particularly tricky when it is not at all obvious that the clues are some kind of twist or play. Are computers any good at figuring that out? I often finally understand a clue only after having filled in the word from other directions.
I did scan the paper and you are correct that the software problems with those kinds of clues (puns and especially themed clues.) However it does have a very large library of puzzles. Crossword authors tend to reuse clues quite frequently. It also uses some clever tricks like using a clue to narrow down the answer to a specific part of speech. There are some words it will never be able to fill from the clues but as you know, sometimes you just find the only word that will fit. A surprisingly small number of clues with a sure answer are enough to constrain the problem to where the software can search for valid solutions to all the crossings.
Given that David is an elite level crossword solver he would probably beat the version of Dr. Fill described in the paper. I voted the computer would win assuming that the software developers have spent the last year working on improvements.
If a computer could beat straight-up Jeopardy, a computer can beat a crossword puzzle with its known word length and letter clues.
There is any number of crossword puzzle solving tools already. Not sure how far they go. But you don't even need a very powerful computer, it has been done over a decade ago already - http://www.oneacross.com/proverb/press/newsstory8.html
Quote: P90Duh.
If a computer could beat straight-up Jeopardy, a computer can beat a crossword puzzle with its known word length and letter clues.
There is any number of crossword puzzle solving tools already. Not sure how far they go. But you don't even need a very powerful computer, it has been done over a decade ago already - http://www.oneacross.com/proverb/press/newsstory8.html
So what odds would you be willing to lay that David can't beat Fill?
Quote: P90Duh.
If a computer could beat straight-up Jeopardy, a computer can beat a crossword puzzle with its known word length and letter clues.
It's not the same computer.
Quote: NareedIt's not the same computer.
Indeed, it's not at *all* the same computer. The paper admits that the algorithms used in Dr. Fill are reasonably unpolished. On the other hand, IBM spent over $1B (yes, BILLION) on Watson. Not even in the same ballpark.
I'd bet that if IBM applied Watson and the associated research team to crossword puzzles, it'd crush everybody. Including Dr. Fill, which was written by a single researcher without a 9- or 10-figure budget. I'd expect sub-60-second solutions to basically any puzzle, and that's faster than most people can even write (vis-a-vis filling in the letters in the puzzle).
Try just writing the letter "A" in each square of a crossword puzzle and see how long it takes you.
Edit: there's actually a good discussion of the differences between Watson and Dr. Fill at the end of the Dr. Fill paper. Worth reading.
Quote: SOOPOOI'm still waiting for a forum member to establish a line against my boy. There has not been a single poster who thinks he can do it. But not a single poster who would establish a betting line. Remember, guys, this is a gambling forum.
Based on what I know of software and computer capabilities, I would bet on Dr. Fill at -500 to beat your son. However, I am actually reading the paper now, so the line may change as I gain knowledge :)
Quote: SOOPOOI'm still waiting for a forum member to establish a line against my boy. There has not been a single poster who thinks he can do it. But not a single poster who would establish a betting line.
There's good reason for that:
1) too many unkowns like
2) how do you even determine a betting line?
Quote: Nareed
how do you even determine a betting line?
There are some general concepts to use when making a betting line. If you are charging a vig, and want zero variance, then you pick a line where you think half of the money will be on one side and half on the other. If you plan on betting one side, then you will give your side the most odds, or points, such that there will still be action against you. Amongst friends, you would use all the information you have, and determine what the likelihood of an event happening is, obviously a guess. Acesand Eights thinks David has around a 17% chance of beating Fill, so he made the odds 5-1 against David.
Quote: SOOPOOBut not a single poster who would establish a betting line. Remember, guys, this is a gambling forum.
We just have very little idea WTF this Fill thing is. Other than it's some sort of a computer.
Quote: P90We just have very little idea WTF this Fill thing is. Other than it's some sort of a computer.
mathExtremist has posted a link. You can read it if you want. But of course anyone making a 'line' on this type of event is using lots of conjecture. Thats what makes it fun.
Quote: SOOPOOThere are some general concepts to use when making a betting line. If you are charging a vig, and want zero variance, then you pick a line where you think half of the money will be on one side and half on the other. If you plan on betting one side, then you will give your side the most odds, or points, such that there will still be action against you.
Sure. That's easy for you to say. You understand what you're talking about ;P
No, please, don't bother to explain further. There's a reason why I don't bet in sports.
Quote: SOOPOOI see a second person clicked on that David will beat Fill. Aces and Eights has made Fill a 5- 1 favorite. I am now ready to take low level action, if anyone wants to bet against David. The preliminary rounds are March 17, and the final round is March 18. The competition takes place at the Brooklyn Marriott.
I need to finish reading the paper, and then perhaps I will make a wager with you. Although maybe we should just use the poll to establish the line. Currently running 4-1 against your son, which would make the line -400 now. Of course this is advantageous to me betting against him :).
What's "low-level"? I would be willing to bet 40 or 50 bucks with you. Only $10 risk to your gambling bankroll! I would bet more, except for all of the uncertainties.
Quote: AyecarumbaLike Watson, does Fill have the distinct advantage of having the clues pre-typed for entry?
I haven't the slightest idea of how it will work. David says that the computer will surely finish the puzzles quicker than a human, just he expects it (or hopes it) makes more mistakes. Each letter that is wrong costs a minute, I think. Last year David was one of a dozen or so competitors that made zero mistakes over the course of the seven puzzle gauntlet.
David Wins +350
Fill wins -500
As bets are placed then the odds are altered to reflect the market. When the market becomes more accurate then so does the vig reduce - so you may have (after a week of betting):-
David Wins +325
Fill Wins -400
Showing that more wagers have been placed on David - however, the vig has been reduced in the process.
Quote: AyecarumbaLike Watson, does Fill have the distinct advantage of having the clues pre-typed for entry?
Quote: SOOPOOI haven't the slightest idea of how it will work. David says that the computer will surely finish the puzzles quicker than a human, just he expects it (or hopes it) makes more mistakes. Each letter that is wrong costs a minute, I think. Last year David was one of a dozen or so competitors that made zero mistakes over the course of the seven puzzle gauntlet.
If the footing were even (the computer had to "read" the clues autonomously, and use a stylus to record results,) it might be fairer. Having the clues pre-loaded is akin to allowing the humans to scan the clues for a few minutes before the competition begins. The advantage for the computer seems to me, really the speed in reporting results, not developing solutions.
Quote: SwitchNot sure about the US betting market but normally, when the outcomes are not easy to determine, the bookies may set a higher vig until the betting settles down. So, in this case for example, it may start out at:-
David Wins +350
Fill wins -500
As bets are placed then the odds are altered to reflect the market. When the market becomes more accurate then so does the vig reduce - so you may have (after a week of betting):-
David Wins +325
Fill Wins -400
Showing that more wagers have been placed on David - however, the vig has been reduced in the process.
Sure, but there's no 3rd party to take a vig here. In a friendly bet between two individuals, the important part is agreeing on a line where both parties believe they will win. So I'm making a bet at -500 (e.g.) and SOOPOO is making a bet at +500, much like in the HB challenge. HB is betting at +900 that she can do it, the rest of us are laying -900 against her (well except for the couple of special cases where they volunteered to pay her for succeeding but not take any winnings if she fails).
Quote: AyecarumbaIf the footing were even (the computer had to "read" the clues autonomously, and use a stylus to record results,) it might be fairer. Having the clues pre-loaded is akin to allowing the humans to scan the clues for a few minutes before the competition begins. The advantage for the computer seems to me, really the speed in reporting results, not developing solutions.
I suspect it's also pretty damn fast at working out solutions, but it does seem unfair that it gets to compete at an unfair I/O advantage. We know machines are better at input/output processing than a human being even with a keyboard and mouse. I just proved that while typing this, as I some test cases at work in 1/10th the time I could do it manually.
I think FILL is a big favorite. SOOPOO himself told me that lots of clues are repeated and experienced puzzlers see them over and over. I would imagine FILL has a memory of thousands, perhaps over a million, crossword clues in its memory. Where it may get stumped is on something new. Then again, Watson (what that it's name) won the Jeopardy challenge, so clearly there is some "thinking" ability is possible.
The lines Switch posted about looked pretty solid to me, based on my limited knowledge. I'd be happy to lay 2 to 1 on FILL if anyone is interested.
Quote: WizardI think FILL is a big favorite. SOOPOO himself told me that lots of clues are repeated and experienced puzzlers see them over and over. I would imagine FILL has a memory of thousands, perhaps over a million, crossword clues in its memory. Where it may get stumped is on something new. Then again, Watson (what that it's name) won the Jeopardy challenge, so clearly there is some "thinking" ability is possible.
I suppose it depends on the rules. I've seen NY times crossword puzzles where a symbol is part of the answer (in this case a "Rose")
In order to solve it, you would need a broad cultural background, including recognizing the century old poem by Gertrude Stein where she writes the line Rose is a rose is a rose is a rose .
.
I would assume that Dr FILL would have a huge advantage over any human in doing the TV Guide crossword puzzle, where it's sheer computing power would easily overwhelm any human. But very subjective thinking is much harder to reproduce.
Quote: WizardI'm late to the party, so forgive me if what I'm about to say has already been said.
I think FILL is a big favorite. SOOPOO himself told me that lots of clues are repeated and experienced puzzlers see them over and over. I would imagine FILL has a memory of thousands, perhaps over a million, crossword clues in its memory. Where it may get stumped is on something new. Then again, Watson (what that it's name) won the Jeopardy challenge, so clearly there is some "thinking" ability is possible.
The lines Switch posted about looked pretty solid to me, based on my limited knowledge. I'd be happy to lay 2 to 1 on FILL if anyone is interested.
I'll offer 3 to 1 on FILL if anyone wants to bet against me on SOOPOO's kid. Woooo capitalism!
This is how it works right?
I have encountered similar out-of-the-ordinary puzzles. One had a question mark appearing in numerous answer cells. One that appeared in an airline magazine took me almost the entire flight to solve because of the time it took me to recognize that there were a dozen cells that each were to contain three letters, with each three-letter sequence to appear in both the across and down answers that crossed at those cells. Could a computer ever figure out such a shift?Quote: pacomartinI've seen NY times crossword puzzles where a symbol is part of the answer (in this case a "Rose").
Earlier I suggested that humans might have an advantage on clues that are puns or that seem to misdirect. Here are a few clues and answers from the two puzzles I worked this morning:
It covers all the bases. (tarp)
Register for Tiny Tim. (falsetto)
Words before coming or out. (hasit)
SOS card. (sevenofspades)
Coil in the yard (hose)
Bavarian carp (ach)
Ability to detect a certain orientation. (gaydar)
Now, neither of the two puzzles and none of those answers was very hard for a person to come up with, but unless the computer has those particular clues/answers stored in memory, I think it would be difficult to have a program that would figure them out, unless it's just a matter of looking for all the letter sequences that might be words and that might fit in both directions.
Quote: AcesAndEightsI'll offer 3 to 1 on FILL if anyone wants to bet against me on SOOPOO's kid. Woooo capitalism!
This is how it works right?
Now we're starting to make a book :-)
Aces, you are giving a line of -300 on FILL, am I correct? Or are you giving +300 on SOOPOO?
Quote: Wizard
The lines Switch posted about looked pretty solid to me, based on my limited knowledge. I'd be happy to lay 2 to 1 on FILL if anyone is interested.
FILL -200? I'm very tempted by that offer - wish I knew more about this :-)
Quote: SwitchNow we're starting to make a book :-)
Aces, you are giving a line of -300 on FILL, am I correct? Or are you giving +300 on SOOPOO?
I'm not sure what the terminology is for personal betting like this where you don't offer both sides of the wager. I guess I'm offering +300 on SOOPOO's kid, as in I will take a bet from someone where if the computer wins, I win $100, and if SOOPOO's kid wins, I pay them $300. I want to say it the other way around (-300 on Mr. Fill) because that's my side of the wager.
Quote: DocI have encountered similar out-of-the-ordinary puzzles. One had a question mark appearing in numerous answer cells. One that appeared in an airline magazine took me almost the entire flight to solve because of the time it took me to recognize that there were a dozen cells that each were to contain three letters, with each three-letter sequence to appear in both the across and down answers that crossed at those cells. Could a computer ever figure out such a shift?
Earlier I suggested that humans might have an advantage on clues that are puns or that seem to misdirect. Here are a few clues and answers from the two puzzles I worked this morning:
It covers all the bases. (tarp)
Register for Tiny Tim. (falsetto)
Words before coming or out. (hasit)
SOS card. (sevenofspades)
Coil in the yard (hose)
Bavarian carp (ach)
Ability to detect a certain orientation. (gaydar)
Now, neither of the two puzzles and none of those answers was very hard for a person to come up with, but unless the computer has those particular clues/answers stored in memory, I think it would be difficult to have a program that would figure them out, unless it's just a matter of looking for all the letter sequences that might be words and that might fit in both directions.
This is why David thinks he will win. There are 7 puzzles that Fill will compete in against the humans. Generally, six of them tend to be 'easy', and Fill will be a big favorite in those. For those of you who haven't seen david do a puzzle, there is a link on this site called 'Wizards Challenge', where david polished off 2 'easy' puzzles about as fast as you can write. The hardest puzzle, which often the best human's make errors on, has many of the clues like Doc has listed. The penalty for incorrect answers is greater than the bonus for being faster.
For those interested, they made a movie ("Wordplay") about the whole crossword 'scene', and it focused on Tyler Hinman, who was a multiple time champion. When Tyler turned 26 David became the champion 25 and under.
I will be checking my bankroll and getting back to those who want to bet against David.
Quote: ewjones080Man oh man, Crossword Championships, Scrabble Tournaments, Cup Stacking Competition.... What's next? Bad Movie Marathons?
I would say that amongst most competitions that we are aware of, crossword puzzling is done recreationally by a very large percentage of the population, certainly moreso than any major sport (football, ice hockey, tennis, etc..). To be amongst the very best in the world, and be THE BEST in your age group, I think is quite a feat! (Proud dad talking) David has told me that Fill 'competed' against the same puzzles David did 2 years ago, and Fill's score would not have beaten David's. So, I am now more confident in David's chances. The least favorable odds to me mentioned were making Fill a 2 to 1 favorite, so I am now willing to book bets on Fill, with me taking David. So any member willing to risk $20 to win $10 can make it known on this thread. The Wiz will be granted the option of betting $100 to win $50 if he so chooses.
Quote: SOOPOOI would say that amongst most competitions that we are aware of, crossword puzzling is done recreationally by a very large percentage of the population, certainly moreso than any major sport (football, ice hockey, tennis, etc..). To be amongst the very best in the world, and be THE BEST in your age group, I think is quite a feat! (Proud dad talking) David has told me that Fill 'competed' against the same puzzles David did 2 years ago, and Fill's score would not have beaten David's. So, I am now more confident in David's chances. The least favorable odds to me mentioned were making Fill a 2 to 1 favorite, so I am now willing to book bets on Fill, with me taking David. So any member willing to risk $20 to win $10 can make it known on this thread. The Wiz will be granted the option of betting $100 to win $50 if he so chooses.
I'm going to pass on betting on this, although I do enjoy the intellectual challenge of trying to make "fair" lines on stuff. Good luck to your kid!
