Data Mining the Web Reveals What Makes Puzzles Hard For Humans 44
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."
Value (Score:5, Interesting)
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.
Some Pac-Man ROMs had clear solutions (Score:5, Interesting)
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.
Re:Sudoku's complexity (Score:5, Interesting)
> Isn't sudoku extraordinarily easy for a computer?
Yes, "solving" sudoku is extremely trivial. Few years back wrote less then 100 lines of C/C++ code to solve any Sudoku using back tracking. Solves any 9x9 sudoku in less then a second.
The more interesting question is how players use the advanced deduction / induction such as x-wing, swordfish, etc.
> games that humans are really good at but that are nearly intractable for computers.
You mean like asking a person to identity the movie / actors / plot from a 5 or 10 second movie clip?? ;-)
Computers completely suck at meta-searching through large amounts of "noise".
They are _extremely_ good when you have tons of "signal" and want to find that 1 special entry.
Re:Sudoku's complexity (Score:5, Interesting)
Generalized (NxN) sudoku is NP-complete. That's the only sense in which any puzzle is computationally intractable.
This is very fascinating work, but I am skeptical. I design puzzles like this, with computer assistance, and automatically gauging how difficult a puzzle is seems to be basically impossible. The fundamental problem is that the logical structure of a puzzle is not in itself sufficient to gauge difficulty. A huge amount of it is in the presentation, and how the player conceptualizes the puzzle, and how much of the problem can be handled automatically by visual processes. There are puzzles with trivial game trees that I have watched players get totally lost in, because the game tree is not apparent in the puzzle manifestation.
If this research addresses this problem, I will be very impressed.
Extension to games... (Score:4, Interesting)
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 [boardgamegeek.com], Octi [boardgamegeek.com], and Havannah [boardgamegeek.com]. One speculates whether it would be possible to design a game that is equally difficult, and a fair contest, between humans and computers.
Re:Sudoku's complexity (Score:4, Interesting)
It's not just that. The puzzle solvers essentially adopt their own rules for what consistutes a valid solution step.
Once I started completing most five stars puzzles in twelve minutes or less, I started to mainly work the "insane" category. My preferred method is to logically eliminate a single digit placement: this digit can't go here in this box. In the insane puzzles, one often gets to a place where are few digit placements one can reasonably crack with an inference chain without going more than three levels deep.
At that point, it's pretty easy to get completely stuck for ten minutes looking in all the wrong places. That same situation can often be "solved" in under a minute with a four colour pen and the willingness to posit and backtrack. Normally this is against my personal code.
Once upon a time I compiled Knuth's dancing links and threw some "hardest ever" puzzles at it that came up in a quick Google search. One of the first such puzzles I tried solved without a single backtrack step: at each point where the algorithm made a guess, it happened to guess right. There were only three or four or five such junctures of valence 2 or 3. I think I had slightly modified how it sorts the list based on my own intuition about the potency of guesswork, but still, it made a completely mockery of the whole "difficulty" notion. Purportedly one of the hardest of all puzzles (by a certain metric) and Dancing Links goes Rain Man without so much as scuffing its eraser.
When I challenged myself to solve five star puzzles in under ten minutes, there was a complex dance inside my mind to keep track of where I'd shaken the tree already, and what part of the tree needed to be revisited based on recently completed digits. At the slightly faster pace, my mistake production would skyrocket: somehow my double-checking circuit and my "what next" circuit became competitive.
Also, the critical junctures became too thin on the ground, and the punishment for my errors too great, so I lost interest in pushing it any further. It was always for me an excercise in observing my own solution strategies and mental capacities/incapacities.
I think the only way a puzzle-setter can get consistent solution times for a hardness category is by patiently training the puzzle solvers to appoach the task in a certain way, rather than just doing their own thing. I certainly knew with each puzzle setter that I could exploit my familiarity with previous puzzles set at that level of difficulty if I followed the main sequence.
From time to time I would spot an advanced inference early, and then the puzzle would melt away posing no further difficulty whatsoever.