Beta

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Data Mining the Web Reveals What Makes Puzzles Hard For Humans

Unknown Lamer posted about 4 months ago | from the sticking-to-breakout dept.

Puzzle Games (Games) 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."

cancel ×

44 comments

Sorry! There are no comments related to the filter you selected.

Sudoku's complexity (1)

kruach aum (1934852) | about 4 months ago | (#46639243)

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.

Re:Sudoku's complexity (5, Interesting)

UnknownSoldier (67820) | about 4 months ago | (#46639631)

> 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 (0)

Anonymous Coward | about 4 months ago | (#46647049)

You mean like asking a person to identity the movie / actors / plot from a 5 or 10 second movie clip?? ;-)

Shazam could do this by indexing the audio and then giving you the plot synopsis and cast list from IMDB.

Computers are actually very good at meta-searching through large amounts of noise. They can use the same Bayesian techniques the brain does, with improved reliability over wetware, and vastly larger backend datasets.

Re:Sudoku's complexity (5, Interesting)

Bob Hearn (61879) | about 4 months ago | (#46639665)

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.

Re:Sudoku's complexity (1)

harrkev (623093) | about 4 months ago | (#46640147)

Well, the ARE right about Sudoku. I can tell you from experience that, sometimes, just looking at a board is not enough. For some configurations of some types of puzzles (sudoku being a great example), you just have to mentally go through the possibilities until you find one that takes you a little further along. If there are 10 possible next steps instead of just one, you only have to search, on average, 1/10 the solution space to get your next move. These results are actually quite obvious once you think about it for a moment.

On the other hand, there are classes of problems where intuition (fuzzy heuristics?) is of some use. In these cases, if you can narrow your search of the state space to get your next move without an exhaustive search, the fact that there is only one next possible move is much less of a handicap.

Re:Sudoku's complexity (3, Insightful)

Wycliffe (116160) | about 4 months ago | (#46640475)

He's looking at both complexity of the move and how many possible moves there are at each step.
It is much easier to find a valid move and solve a puzzle if there are 10 opening moves.
It is much harder if there is only a single path of 20 moves in a particular sequence.
A puzzle with 20 steps that must be done in order is much much harder than a puzzle with 20
steps that can be done in any order just like it would be much harder to solve a word search if
you had to find the words in order.
This should be pretty accurate as a truly serial puzzle would be the sum of time to solve each
step while a puzzle with parallel steps would be the average time to discover one of the possible
next moves. On average if there is more than one solution on a step then finding one of the
many solutions should be faster than finding the one solution.

Re:Sudoku's complexity (3, Interesting)

epine (68316) | about 4 months ago | (#46642455)

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.

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.

Re:Sudoku's complexity (2)

oneandoneis2 (777721) | about 4 months ago | (#46640315)

Yup, see http://perl.abigail.be/Talks/S... [abigail.be] for an interesting example of how a Sudoku puzzle can be solved via Regex :)

Idiotic summary (0)

Anonymous Coward | about 4 months ago | (#46639289)

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.

Re:Idiotic summary (2)

dtmos (447842) | about 4 months ago | (#46639347)

The "they" in the quoted line refers to people, not computers. It's the people picking the method (poorly).

The issue with Sudoku is that easy and difficult puzzles can have the same number of boxes to fill.

chess (1)

schneidafunk (795759) | about 4 months ago | (#46639299)

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.

Value (5, Interesting)

dtmos (447842) | about 4 months ago | (#46639311)

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.

Re:Value (2)

dr_blurb (676176) | about 4 months ago | (#46646863)

Absolutely spot on.

I wrote a Calcudoku generator/solver a while ago (now in heavy use at http://www.calcudoku.org/ [calcudoku.org] and spent a _lot_ of effort on the difficulty rating bits (and still know there is room for improvement).

One idea that isn't in there yet is to somehow incorporate the distance between the solving steps: if the next logical step is in a cell very near the previous one, you see it more quickly, hence the puzzle is easier.

Yawn. (0)

Anonymous Coward | about 4 months ago | (#46639321)

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.

Re:Yawn. (1)

Jmc23 (2353706) | about 4 months ago | (#46640415)

Medicine 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.

FTFY.

'cause really psych hasn't made any sweeping changes to anything, but 'medical science' has been fucking with our food and drug intake for the past century and created some of the worst changes in the global economy.

Re:Yawn. (0)

Anonymous Coward | about 4 months ago | (#46641685)

Yes, but with better PR. So be prepared for downmodding.

Re:Yawn. (0)

Anonymous Coward | about 4 months ago | (#46647063)

Way to take an off-topic comment and move it even further off-topic. Go grind your ax somewhere it's relevant. An article on the difficulty of solving Sudoku has fuck all to do with your "look how iconoclastic I am" opinion on medical science.

Nurikabe (2)

oodaloop (1229816) | about 4 months ago | (#46639361)

Indeed work has already begun on the Sudoku-like puzzle game, Nurikabe."

Great. Another time-consuming addictive game I have to play. Thanks, slashdot!

Re:Nurikabe (1)

K. S. Kyosuke (729550) | about 4 months ago | (#46640519)

The nurikabe is a Yokai, or spirit, from Japanese folklore. It manifests as a wall that impedes or misdirects walking travelers at night.

Well, the name sounds apt to me! ;)

Re:Nurikabe (1)

jpvlsmv (583001) | about 4 months ago | (#46641309)

Don't worry, there's 2048 [github.io] other games to consume your time.

Some Pac-Man ROMs had clear solutions (5, Interesting)

davidwr (791652) | about 4 months ago | (#46639369)

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:Some Pac-Man ROMs had clear solutions (3, Informative)

L1mewater (557442) | about 4 months ago | (#46639555)

I believe it is "all versions." Pac-Man does have a perfect solution, and the maximum possible score has been achieved. Several people have done this, but Billy Mitchell is credited with being the first.

Tedious != Difficult (2)

globaljustin (574257) | about 4 months ago | (#46639557)

I like this research area but the researchers need to dramatically improve their definitions and measures of 'difficulty'

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,

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

Re:Tedious != Difficult (2)

Carewolf (581105) | about 4 months ago | (#46639603)

I read it the other way if applied to video games. A sequence of steps is a linear game and boring and not really a game as much as a movie with grind. Parallel steps are sandbox, open world.

Re:Tedious != Difficult (1)

globaljustin (574257) | about 4 months ago | (#46639957)

hi Carewolf...interesting...

"trial and error" is only relevant when there **is a goal to try for**

by definition, a "sandbox" game isn't programmed to have accomplishments (of course you can have both in one game ex: GTA)

so a "sandbox" game *cant* have goals...or it wouldn't be "sandbox"

part of this is, gaming became so reductive with the introduction of the "cut scene"...and just lazy game design

Re:Tedious != Difficult (1)

mikael (484) | about 4 months ago | (#46640179)

I though the Nintendo games (Super Mario 64, Ocarina of Time) started off in parallel steps as you explored each level to find keys and unlock other levels. But eventually after figuring out the optimum sequence of completing levels (get the flying hat first, then get the invisibility hat, get the ten keys, get the skulltulas), then the game becomes linear.

Re:Tedious != Difficult (0)

Anonymous Coward | about 4 months ago | (#46649105)

I think it's actually the other way. It would seem that actually sequencing steps increase difficulty and not parallel steps. The article is not explicit about this, but it would appear the most logical.

Take an easy Sudoku puzzle, in which the first step has 10 first legal moves. If you take one, the other 9 moves are still just as applicable because they are independent of one another. This means that all those 10 steps could be executed in parallel, without regard for execution order. Enlarging the amount of legal moves makes a puzzle easier, because the puzzler just has to find any one of them. Having only one sequence of legal moves, i.e. everytime there is only 1 legal move, should make the puzzle harder.

Now your argument on tedious puzzles still holds, in the sense that you don't want too long easy puzzles. But the difficulty of a puzzle does increase with lengthening the puzzle, as long as you make it so that everytime there is only a limit set of legal moves. Choosing one legal move out of 64 should appear to be harder than choosing the one legal move out of 16, despite making the puzzles arguably also more tedious.

Human vs computer (4, Insightful)

gurps_npc (621217) | about 4 months ago | (#46639573)

Computers do certain things very very well - in depth repetition, aka recursive.

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.

Re:Human vs computer (0)

Anonymous Coward | about 4 months ago | (#46640207)

In other words, flat and associative memory models have different advantages and characteristics.

Re:Human vs computer (0)

Anonymous Coward | about 4 months ago | (#46647089)

Well that's not what was just said at all, nor is it really a model that explains what was just said. Saying the brain does this using "associative memory" is just handwaving, and any form of associative memory used by the brain can be simulated by a computer anyway.

The real reason OCR is hard is because the same class of system is used to discriminate letters that is used to design fonts. In other words, humans design an A so that it looks like an A to other humans. That's a far more complex criteria than just "it has this topology" or "it has these spatial moments", and to read all As the computer has to simulate the exact criteria used by humans, which is basically unknown (e.g. look at some gothic font). OCR on fixed fonts is, by contrast, a completely solved problem, and has been for decades, with readers handling thousands of characters per second, which is way in excess of human performance.

I can't believe how many people who work with computers still fall into this "computers are bad at X" nonsense. If computers can do a task slower than humans, someday they will do it faster, and if computers can't do a task, that's because we don't know how to write the software, not because the computer could never do that task.

Where does Rubik's Cube fit in all of this? (1)

shoor (33382) | about 4 months ago | (#46639589)

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.

Re:Where does Rubik's Cube fit in all of this? (1)

captjc (453680) | about 4 months ago | (#46640013)

I prefer the engineer's method. It involves a screwdriver.

Re:Where does Rubik's Cube fit in all of this? (2)

narcc (412956) | about 4 months ago | (#46642361)

It's not too bad until you get close to the end. That's where it takes the longest to work out a set of useful moves. (e.g. sequences which ultimately affects just a few cubes while leaving the others in place) for the end-game. Keep at it, make lots of notes, and you'll work out your own solution in no time.

Pac Man (1)

hcs_$reboot (1536101) | about 4 months ago | (#46639903)

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!

what can we infer about puzzles easy for humans, h (1)

raymorris (2726007) | about 4 months ago | (#46640063)

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.

Re:what can we infer about puzzles easy for humans (1)

bws111 (1216812) | about 4 months ago | (#46640193)

I would think crossword puzzles, especially the kind that uses puns, etc.

Re:what can we infer about puzzles easy for humans (1)

jfengel (409917) | about 4 months ago | (#46641429)

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.

Extension to games... (3, Interesting)

braindrainbahrain (874202) | about 4 months ago | (#46640151)

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.

modR Up (-1)

Anonymous Coward | about 4 months ago | (#46640803)

I doubt it. (1)

darkwing_bmf (178021) | about 4 months ago | (#46640897)

One possibility is that puzzles that are hard for computers must also be hard for people. That's undoubtedly true...

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.

Data Mining Sudoku Websites (1)

ComputersKai (3499237) | about 4 months ago | (#46642115)

Tinfoil hat time :-)

Depends on the human (2)

mynamestolen (2566945) | about 4 months ago | (#46642885)

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.

Lunatic (0)

Anonymous Coward | about 4 months ago | (#46644443)

>Pac-Man
They should have tried Touhou Project for the tests too...
https://www.youtube.com/watch?v=BQLIaZUOnBU

Check for New Comments
Slashdot Login

Need an Account?

Forgot your password?
or Connect with...

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>