Slashdot Mirror
Data Mining the Web Reveals What Makes Puzzles Hard For Humans
KentuckyFC (1144503) writes "The question of what makes puzzles hard for humans is deceptively tricky. One possibility is that puzzles that are hard for computers must also be hard for people. That's undoubtedly true and in recent years computational complexity theorists have spent some time trying to classify the games people play in this way (Pac Man is NP hard, by the way). But humans don't always solve problems in the same way as computers because they don't necessarily pick the best method or even a good way to do it. And that makes it hard to predict the difficulty of a puzzle in advance. Cognitive psychologists have attempted to tease this apart by measuring how long it takes people to solve puzzles and then creating a model of the problem solving process that explains the data.
But the datasets gathered in this way have been tiny — typically 20 people playing a handful of puzzles. Now one researcher has taken a different approach by mining the data from websites in which people can play games such as Sudoku. That's given him data on the way hundreds of players solve over 2000 puzzles, a vast increase over previous datasets and this has allowed him to plot the average time it takes to finish different puzzles. One way to assess the difficulty of Sudoku puzzle is in the complexity of each step required to solve it. But the new work suggests that another factor is important too — whether the steps are independent and so can be attempted in parallel or whether the steps are dependent and so must be tried in sequence, one after the other. A new model of this puzzle-solving process accurately reproduces the time it takes real humans to finish the problems and that makes it possible to accurately predict the difficulty of a puzzle in advance for the first time. It also opens the way for other studies of human problem solving using the vast datasets that have been collected over the web. Indeed work has already begun on the Sudoku-like puzzle game, Nurikabe."
But the datasets gathered in this way have been tiny — typically 20 people playing a handful of puzzles. Now one researcher has taken a different approach by mining the data from websites in which people can play games such as Sudoku. That's given him data on the way hundreds of players solve over 2000 puzzles, a vast increase over previous datasets and this has allowed him to plot the average time it takes to finish different puzzles. One way to assess the difficulty of Sudoku puzzle is in the complexity of each step required to solve it. But the new work suggests that another factor is important too — whether the steps are independent and so can be attempted in parallel or whether the steps are dependent and so must be tried in sequence, one after the other. A new model of this puzzle-solving process accurately reproduces the time it takes real humans to finish the problems and that makes it possible to accurately predict the difficulty of a puzzle in advance for the first time. It also opens the way for other studies of human problem solving using the vast datasets that have been collected over the web. Indeed work has already begun on the Sudoku-like puzzle game, Nurikabe."
Isn't sudoku extraordinarily easy for a computer? I think it would be more interesting to investigate human problem solving strategies in opposite scenarios, games that humans are really good at but that are nearly intractable for computers.
But humans don't always solve problems in the same way as computers because they don't necessarily pick the best method or even a good way to do it.
And here's where I knew the summary (probably the root story and maybe even the research) is trash. Computers are fed algorithms designed by humans to solve problems. The only time the computer 'picks' a method is when you are using a genetic algorithm (a human-sculpted algorithm to randomly create an algorithm), and those take a lot of time before they get up to the 'button-masher' skill level.
Ok, so I read the second paragraph also, and it looks like the actual research behind this is a bit less trash than the reporter's ignorance of it. Still, 'more useless options harder than more viable options' is not the kind of intuitively obvious hypothesis that I would waste money testing. If (as is the case in Sudoku, the one game these guys analyzed) you have 50 empty boxes, but only the information to know one of them, the puzzle will be harder than if you have 50 empty boxes and the information to know 5 of them. If we get a bit meta and consider guess-chains, the puzzle is easier the shorter chain of guessing is needed to disprove a bad first-guess.
While I find this very interesting, there are chess puzzles which have been categorized for a long time now in different levels. Of course chess is a 'dependent' puzzle where each move must be made in sequence. I imagine there are many other puzzles which have different (accurate) difficulty levels. I may be missing something here.
Some people die at 25 and aren't buried until 75. -Benjamin Franklin
Somewhere I read an article by a guy who makes and sells Sudoku puzzles to newspapers. He explained that the value of providing the puzzle was near zero, since anyone with a computer could easily generate thousands of them, and anyone without a computer could get them from any number of sources. The value of his service, and the reason newspapers paid him to provide the puzzle, he said, was that he provided an accurate difficulty estimate to the puzzle. People attempting, and failing to solve, a difficult puzzle rated "easy", and people quickly solving an easy puzzle rated "difficult", were dissatisfied, and complained. People that had the experience they expected -- easy puzzles quickly solved, hard puzzles solved only with difficulty -- were much more satisfied.
The result was, newspaper editors got fewer complaints using his puzzles than they did from his competitors, so they bought from him.
He said he spent far more time tweaking his difficulty-rating algorithm than he did his software that generated the puzzles themselves -- since that was what kept him in business.
Psychology is such a dismal science, making overarching, over-generalising conclusions which help nobody but the mythical lowest common denominator, yet it's managed to interfere with almost every aspect of academic and commercial life with its simplistic measures.
I would argue that nothing has done more to contribute toward the dumbing down of the West than its obsession with statistics over logic.
Indeed work has already begun on the Sudoku-like puzzle game, Nurikabe."
Great. Another time-consuming addictive game I have to play. Thanks, slashdot!
Tic-Tac-Toe, Global Thermonuclear War, and relationships all have the same winning move.
Due to the lack of enough (or any?) use of a random-event-generator, some early versions of the original Pac-Man arcade game had "canned solutions" that worked for every level. After the hardest level, the hardest level just repeated itself forever. One version ended at the "5th key" and another at the "9th key."
I say "some early versions" - it might be "all versions." I don't know if there were any other versions of the official Pac Man arcade game back in its heyday.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
I like this research area but the researchers need to dramatically improve their definitions and measures of 'difficulty'
parallel steps, by the researchers definition, increase ***complexity*** which is incorrect
parallel steps increase the length of time required, b/c you must use **trial and error** but that is **not more complex**
making a game more difficult by making it more tedious is bad game design...the challenges must increase in complexity as the player progresses
tedious games are like homework...no one plays them
Thank you Dave Raggett
People do not do well with recursive. People do well with hidden simple pattern recognition. Give us a simple pattern, and we can recognize it everywhere. The simplest example of this is optical character recognition, i.e. recognizing letters in a picture. In part because there are infinite number of fonts, but humans can recognize them all, because we look for the pattern. Computers have major issues with this - and to get any real accuracy, do it slower than people do.
excitingthingstodo.blogspot.com
Once in a great while, I drag it out and try yet again to solve it. (Sigh)
PS Yeah I know there are books that tell how to do it. That's not what I'm after.
In theory, theory and practice are the same; in practice they're different. (Yogi Berra & A. Einstein)
Pac Man is NP hard, by the way
So you mean each time a level is passed, a NP hard problem is solved. I'm a genius!
Slashdot, fix the reply notifications... You won't get away with it...
Considering the information in TFA, can we infer anything about what type of puzzles would be easy for humans, but hard for computers? Traditional captchas were an attempt at that, but they don't work that well.
So far, I've come up with only one puzzle our wetware does much better than software - spotting attractive members of the opposite sex. That's what we use in our captchasystem.
I have to wonder how/if this research translates into the games arena. Recently, there have been several attempts to make games playable by humans but which negate the computer's advantage of massive search. These games include Arimaa, Octi, and Havannah. One speculates whether it would be possible to design a game that is equally difficult, and a fair contest, between humans and computers.
I would think crossword puzzles, especially the kind that uses puns, etc.
Not really. I would imagine something like a riddle would be easier for a human than a computer. On a more mundane level, computers, even with robotic bodies, so far can't interact with the world we live in as easily as humans do. Yes, they can do some things we can't but the reverse is also true.
Has anybody tried to hook Watson up to a crossword puzzle? Its Jeopardy-answering skills should give it a substantial jump on the puzzle, and combined with the combinatorial crunching power of a computer should be able to narrow down a lot of places to the point where it can just plain guess. Which is what a lot of human players have to do when faced with overly "clever" clues anyway.
Some puzzles have extra thematic elements that would make it tricky for a computer (such as misspellings), though a lot of these are really just a matter of practice for humans as well: "Oh, this is the kind of language game you're allowed to play." A computer might not be able to induce that kind of rule, but if you code for it it can probably take some fine guesses.
Tinfoil hat time :-)
Different humans use different approaches. I knew a physics professor when rubric's cube first came out. He looked at it without touching it, wrote some stuff on paper, then picked it up and solved it instantly. Some humans will know the "key" to a puzzle, others won't.
work in progress
>Pac-Man
They should have tried Touhou Project for the tests too...
https://www.youtube.com/watch?v=BQLIaZUOnBU