Stories
Slash Boxes
Comments

SoylentNews is people

posted by janrinok on Wednesday March 12 2014, @06:59PM   Printer-friendly
from the so-my-childhood-wasn't-wasted dept.

nobbis writes:

"Toby Walsh at the University of NSW Australia has, as reported in New Scientist, studied a generalized version of the popular game Candy Crush Saga and found it be an NP-hard problem, indeed he suggests 'Part of its addictiveness may be that Candy Crush is a computationally hard puzzle to solve.'

His paper shows that early rounds in the game can be modeled as a collection of 'wires' transmitting information across the board, with candies forming inputs and outputs, which can be seen as equivalent to logical statements, this reduces the game to an example of a Boolean satisfiability problem which is known to be NP-complete. A similar technique has been used to show that Super Mario Brothers and Zelda are also NP-hard.

Given that people have spent millions of hours playing the game he notes 'It would be interesting to see if we can profit from the time humans spend solving Candy Crush problems, perhaps we can put this to even better use by hiding some practical NP-hard problems within these puzzles?'"

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 5, Insightful) by slartibartfastatp on Wednesday March 12 2014, @07:19PM

    by slartibartfastatp (588) on Wednesday March 12 2014, @07:19PM (#15454) Journal

    The final statement is really interesting. Like mixing the mechanical turk with flappy bird. Plus, earning bucks from advertisement.

    • (Score: 5, Informative) by MrGuy on Wednesday March 12 2014, @07:40PM

      by MrGuy (1007) on Wednesday March 12 2014, @07:40PM (#15467)
      The question is whether we can find a polynomial formula to predict how many players we'll need to solve a known problem. Also, can predict with certainty before they start whether the players will give up before they finish the task? :)
      • (Score: 2, Informative) by slartibartfastatp on Wednesday March 12 2014, @07:51PM

        by slartibartfastatp (588) on Wednesday March 12 2014, @07:51PM (#15478) Journal

        I don't think the interesting thing here is to solve the general problem, but instances of it. You can generate a huge database of solutions, that could be used to solve other instances by approximation methods.

        • (Score: 2, Insightful) by space_in_your_face on Wednesday March 12 2014, @10:43PM

          by space_in_your_face (224) on Wednesday March 12 2014, @10:43PM (#15589)
          This idea is intersting in problems for which humans are good and computer bad (for example image recognition).

          In the case of NP-(hard|complete), humans can only solve small problems. And for those, computers are much faster. Try this game [nikoli.com] if you are not convinced (it's probably hard for you, but a computer can solve it in a fraction of a second).
      • (Score: 5, Interesting) by MrGuy on Wednesday March 12 2014, @08:21PM

        by MrGuy (1007) on Wednesday March 12 2014, @08:21PM (#15502)

        Lol. I make a bad NP joke, followed by a worse halting problem joke, and I wind up getting modded "informative."

        I need a serious rethink on what I consider funny, I guess...

        • (Score: 3, Funny) by Geotti on Wednesday March 12 2014, @08:40PM

          by Geotti (1146) on Wednesday March 12 2014, @08:40PM (#15512) Journal

          That must be, because you're One Double O Seven and we don't think you're a joke ; )

        • (Score: 1) by Nesh on Thursday March 13 2014, @08:11AM

          by Nesh (269) on Thursday March 13 2014, @08:11AM (#15759)

          Hey, I laughed! There's at least two who find this funny.

    • (Score: 3, Insightful) by davester666 on Wednesday March 12 2014, @07:43PM

      by davester666 (155) on Wednesday March 12 2014, @07:43PM (#15470)

      reverse mechanical turk...you get the privilege of paying to solve somebody else's problem via in-app purchases and viewing ads.

  • (Score: 5, Interesting) by Snotnose on Wednesday March 12 2014, @07:27PM

    by Snotnose (1623) on Wednesday March 12 2014, @07:27PM (#15458)

    Think I got up to a level in the mid-70s when the chocolate finally cheesed me off too much. The game is basically punishing you for losing.

    I didn't rage quit the thing, one day I just didn't fire it up. It's been a couple months since I've played.

    Fun game though, just get rid of the chocolate.

    --
    The dishes in the sink are giving me dirty looks again.
    • (Score: 2) by hubie on Wednesday March 12 2014, @08:00PM

      by hubie (1068) Subscriber Badge on Wednesday March 12 2014, @08:00PM (#15491) Journal

      I have never played the game, but I have played something similar where you try to line up 3 or more like-objects. Could you explain your chocolate comment, as in, what properties does it do or not do that changes the gameplay?

      • (Score: 3, Informative) by cyborg_zx on Wednesday March 12 2014, @08:06PM

        by cyborg_zx (3450) on Wednesday March 12 2014, @08:06PM (#15495)

        Basically it spreads out each turn unless you make a match next to it or otherwise destroy it. You can't swap it and it can block incoming candies so if it grows too much you can lose by default.

    • (Score: 3, Interesting) by Fluffeh on Wednesday March 12 2014, @10:38PM

      by Fluffeh (954) Subscriber Badge on Wednesday March 12 2014, @10:38PM (#15586) Journal

      Really? I thought it was a logical factor to put in to make the level more difficult. It was also innovative. That sort of thing didn't really kick in again until somewhere in the 400's where you started getting poly-colored candy (it flucuates between two colors, flipping once a move is made) but even that then generally makes for unexpected slides that generally help more than they hinder.

      The hurricanes further in the 400's were somewhat annoying though, they randomly jump to anywhere on the board, delete the candy and leave a "scar" for one move which candy cannot fall into. There are a few levels with five or ten of the buggers flying around.

      Having said that, I have been waiting for the last few weeks for another patch to come out so that I can continue past 530 where I am currently waiting.

  • (Score: 5, Interesting) by MrGuy on Wednesday March 12 2014, @07:35PM

    by MrGuy (1007) on Wednesday March 12 2014, @07:35PM (#15465)
    ...that someone's mapped a game into a class of NP-hard or NP-complete problems.

    Minesweeper, for example [bham.ac.uk] was proven to be NP-complete way back in 2000. i.e. finding a general-purpose algorithm to solve minesweeper in polynomial time would prove P !=NP.

    As I understand it (IANACS), the problem with using the game equivalent to "solve" equivalent NP-hard or NP-complete problems (for example, finding a hamiltonian path through an arbitrary connected graph) is that it's hard to "prove" the negative ("no path exists" or "this game of minesweeper is not solvable without guessing") without somehow forcing your "large array of monkeys" to try every single possibility. Proving the POSITIVE case (I solved it!) is much easier, but not guaranteed to happen.

    • (Score: 5, Interesting) by bstamour on Wednesday March 12 2014, @07:42PM

      by bstamour (3803) <bryan@bryanstamour.com> on Wednesday March 12 2014, @07:42PM (#15469) Homepage

      As I understand it (IANACS), the problem with using the game equivalent to "solve" equivalent NP-hard or NP-complete problems (for example, finding a hamiltonian path through an arbitrary connected graph) is that it's hard to "prove" the negative ("no path exists" or "this game of minesweeper is not solvable without guessing") without somehow forcing your "large array of monkeys" to try every single possibility. Proving the POSITIVE case (I solved it!) is much easier, but not guaranteed to happen.

      Sort of. By my understanding of complexity theory, it would be more like: one of your magical monkeys hands me a solution to the game, and I can verify that it is indeed a solution in polynomial time. However constructing the solution to begin with is still computationally very difficult.

      Consider minesweeper: if some oracle handed me a solution to the puzzle, I could quickly scan over it and say "yes this is a solution", or "no, you hit a bomb over there" pretty easily.

      --
      Peace, love, and Unix
      • (Score: 4, Interesting) by MrGuy on Wednesday March 12 2014, @07:49PM

        by MrGuy (1007) on Wednesday March 12 2014, @07:49PM (#15477)

        Right - get how NP-complete problems work.

        I'm referring to the suggestion in TFA/TFS that, since we've proven equivalency, if we were in a position where we had a specific instance of an NP-complete or NP-hard problem, we could construct a version of the game that was equivalent to that problem, and then use people playing the game to "solve" the NP-hard/NP-complete instance problem we care about. i.e. use humans playing a game as logical processing threads to find solutions to a more important but less fun version of the problem.

  • (Score: 4, Funny) by Anonymous Coward on Wednesday March 12 2014, @07:52PM

    by Anonymous Coward on Wednesday March 12 2014, @07:52PM (#15480)

    There is a porn star named CandyCrush, and she does the most amazing things...NP-complete

    • (Score: 5, Funny) by bstamour on Wednesday March 12 2014, @07:55PM

      by bstamour (3803) <bryan@bryanstamour.com> on Wednesday March 12 2014, @07:55PM (#15485) Homepage

      But what input does she take? Oh, wait... Nevermind.

      --
      Peace, love, and Unix
      • (Score: 0) by Anonymous Coward on Wednesday March 12 2014, @09:50PM

        by Anonymous Coward on Wednesday March 12 2014, @09:50PM (#15558)

        Like all problems, it is dependent on size of the input...

  • (Score: 0) by Anonymous Coward on Wednesday March 12 2014, @08:09PM

    by Anonymous Coward on Wednesday March 12 2014, @08:09PM (#15496)

    Heroes of Kalevala is a better game, and I know few people who have actually rage-quitted because of that bird.

    (What is with Finns and annoying birds?)

  • (Score: 5, Informative) by lhsi on Wednesday March 12 2014, @09:13PM

    by lhsi (711) on Wednesday March 12 2014, @09:13PM (#15534) Journal

    It's not solving a NP problem, but Cancer Research UK have an app to help analyse data: https://play.google.com/store/apps/details?id=com. guerillatea.elementalpha [google.com]

    It's a space game but the course plotting bit is helping analyse one of many cancer samples. The app is based around this and up front about it instead of trying to sneak it in though.

    • (Score: 1) by NezSez on Thursday March 13 2014, @06:15PM

      by NezSez (961) on Thursday March 13 2014, @06:15PM (#16019) Journal

      I heard about this project on Ted Talks. A project for mapping 3d neural pathways in the human brain by people playing a game called "Eyewire" http://blog.eyewire.org/about/ [eyewire.org]
      Links to youtube videos are on the site.

      --
      No Sig to see here, move along, move along...
  • (Score: 1) by allsorts46 on Wednesday March 12 2014, @11:07PM

    by allsorts46 (574) on Wednesday March 12 2014, @11:07PM (#15595) Homepage

    He'd better watch out, mentioning that name. Might get sued.

  • (Score: 1) by BradTheGeek on Thursday March 13 2014, @12:18AM

    by BradTheGeek (450) on Thursday March 13 2014, @12:18AM (#15630)

    King, the publishers of said game are trademark trolls. Google Candy crush / candy swipe and banner saga. The creator of Candy Swipe has taken down his open letter, but you can find out enough to be distasteful. I will not touch king's products with a 10 foot pole. And I used to play candy crush. I fought my way to around level 150 without spending on unlocks or boosts.

  • (Score: 1) by Subsentient on Thursday March 13 2014, @04:32AM

    by Subsentient (1111) Subscriber Badge on Thursday March 13 2014, @04:32AM (#15691) Homepage Journal

    Am I the only one that finds the fact that grown men are playing candy crush living proof that smartphones and tablets dumb people down?

    --
    "It is no measure of health to be well adjusted to a profoundly sick society." -Jiddu Krishnamurti