Forgot your password?
typodupeerror
Games Entertainment Hardware

Making a Game of Hardware Design 60

Posted by Soulskill
from the sim-cpu dept.
no-life-guy writes "Researchers at the University of Michigan have developed a web-game to harness the natural human abilities for electronic design automation (EDA). Arguing that people are still much better than computers in games of strategy and visualization, and that we'll do anything as long as it's fun, a group created FunSAT — a game where an average Joe gets to solve a Boolean satisfiability problem. Known as SAT, this problem is an important component in various hardware design tools from formal verification to IC layout to scheduling. The pilot version is a puzzle-like single-player Java app (akin to those addictive web-games), but the researchers envision that it can be extended to a multi-player (and, perhaps, replace WoW as the favorite past-time of the millions), so anybody can be a hardware designer. If anything, this is definitely a great learning tool."
This discussion has been archived. No new comments can be posted.

Making a Game of Hardware Design

Comments Filter:
  • I hear girls like smart men. Now intellectualism can be combined with everyone's favorite pastime, video games-- bonus!!
  • by Hammer (14284)

    Cool toy :-)

  • Not so fun (Score:5, Insightful)

    by pmontra (738736) on Thursday July 30, 2009 @03:39AM (#28878607) Homepage

    I solved the first three levels of the 3SAT game turning all rectangles yellow and deselecting them in turn until all circles turned green. Basically I didn't understand what was going on and I played in a mechanical way, so I quickly lost interest. I think that any computer can do than faster than me (and that made me loose interest too): was I really helping the design of new hardware or slowing it down?

    By the way, can anybody estimate how many million people playing this game they need to create ICs faster than a single computer can?

    • Re: (Score:1, Informative)

      by Anonymous Coward

      Yes, I made it to level 3 and decided that the computer could enumerate (and evaluate) all choices faster than I could ever figure out the interactions.

      • Re: (Score:3, Informative)

        by sopssa (1498795) *

        Exactly, and also taking into account that boolean operations are really, really, really fast on computers. All of those levels would had been solved faster than blink of an eye by computer, and you couldn't compete even if every person on this planet would play that game all the time.

        • by riegel (980896)

          I disagree. I played for quite a bit and was at a level that had 70 of those little rectangles. So at 3 choices per rectangle that is 3^70

          3^70 = 2.5031555*10^33

          So thats a 10 with 33 little zeros behind it. I solved it in less than 5 minutes. I am not sure I understand what 10 with 33 zeros behind it is but thats a very large number. Could somone tell me how long it would take a computer to loop through that many numbers

          a=systime

          for x=1 to 1000000000000000000000000000000000

          noop

          /for

          print a-systime

          • by cstdenis (1118589)

            More than 5 minutes.

            I threw a quick php script to test, and let it run for 10 minutes. It didn't finish.

            C or asm would be faster, but still not enough to matter here. Regardless the answer is long.

    • by mwvdlee (775178)

      I had the same idea. A simple brute force approach should be able to outperform a human by atleast a factor of millions.

      • by noundi (1044080)

        I had the same idea. A simple brute force approach should be able to outperform a human by atleast a factor of millions.

        Or a much more preferred algorithm.

      • Re:Not so fun (Score:4, Interesting)

        by Jurily (900488) <jurily@[ ]il.com ['gma' in gap]> on Thursday July 30, 2009 @05:25AM (#28879089)

        A simple brute force approach should be able to outperform a human by atleast a factor of millions.

        Till level 5, at least, yes. But I imagine that's only the tutorial. As the levels advance, the puzzles get increasingly interconnected, and I imagine it'll take some real intuition to get past the bigger levels.

        Brute force definitely won't cut it. The goal here might be to figure out an algorithm that behaves like a skilled human, only millions of times faster.

        • Re: (Score:3, Interesting)

          by Jurily (900488)

          Stopped playing at level 10, because of UI issues [photobucket.com], and because it takes over half a second to update the screen after each click.

          However, this game could be much more interesting if it had a scripting interface.

    • Re:Not so fun (Score:4, Insightful)

      by Pyrion (525584) * on Thursday July 30, 2009 @04:00AM (#28878709) Homepage

      Same. Finished the second level without having the slightest clue what I was trying to accomplish. It doesn't help that the instructions are so vague that no thought is given to strategy. It's like putting a chessboard in front of somebody who has never played the game and tell them to "just move shit around until you win."

    • Re: (Score:2, Informative)

      by psyph3r (785014)
      I did the "anysat" set and they became very complex after several levels. the first ones may just be "tutorial" levels.
    • by cgomezr (1074699)

      I haven't tried TFG (this is Slashdot, after all); but perhaps the thing is that they are not looking from direct input from the users to design specific ICs, but rather to gather data about how humans approach this problem so as to be able to develop new heuristics. We humans are quite good at finding decent solutions to NP-complete problems in limited time, so trying to find out which heuristics and rules-of-thumb be use to imitate them in algorithms can be an interesting approach.

    • Re:Not so fun (Score:4, Interesting)

      by wagnerrp (1305589) on Thursday July 30, 2009 @04:59AM (#28878943)
      The puzzles get larger and more complex quickly, but can still be solved in a largely mechanical manner. The bigger issue is that these hardware designers know nothing of software design. Ten minutes in and eight levels passed, I notice the 'game' getting very sluggish. I pull up task manager and find 'java.exe' bouncing between 95-98% CPU usage.
      • Same here. Found it kind of interesting, but the further I went, the slower my machine got. Shame too, I was close to finishing the level!
  • doubts (Score:2, Informative)

    by Anonymous Coward

    I have my doubts that humans can solve these puzzles better than computers.

    I myself have programmed several SAT solvers, which can solve problems with thousands of variables and constraints in seconds. And that was with just a little bit of hobby programming in python. Really good solvers like MINISAT (Google it if you're interested) can solve problems with hundreds of thousands of constraints in milliseconds.

    Humans do have better visual pattern recognition skills than computers, but this helps us only if t

  • Your hardware better be Open Source if I'm going to help you make it.
  • There are certainly things that humans are still better at than computers, but solving SAT problems is not one of them. I would be surprised if the collective efforts of several thousand humans solving SAT problems were faster than one regular desktop running a decent modern algorithm.

    • Actually SAT problems are usually solved quite easily. You just have to turn your dish until you get a reasonable signal. :-)

  • by Fry-kun (619632) on Thursday July 30, 2009 @04:29AM (#28878827)

    Though it doesn't serve a useful purpose (other than entertainment)

    http://www.zachtronicsindustries.com/pivot/entry.php?id=79 [zachtronic...stries.com]

    • I love that game. It's very challenging on the later puzzles. And really does teach some fundamentals of EDA. In my opinion the person/people that made that should win some sort of award.

      • Re: (Score:3, Interesting)

        by MarkGriz (520778)

        It's pretty interesting, though the tutorial video with the inverter completely ignores the fact that you need to also drive the outputs to ground when the inputs are high. Not exactly the EDA fundamentals you want to teach people.

    • by easyTree (1042254)

      Thanks for the link. kohctpyktop *is* fun...

  • Thats not a game (Score:2, Insightful)

    by dublindan (1558489)
    I'm just randomly clicking. A computer can do that better than I can. A genetic algorithm should be unbeatably fast vs a human and even brute force probably would be too. If they explained the rules a little bit maybe.. I was greatly disappointed and thought it was a stupid and unfun game. Clicking randomly is not fun.
    • Maybe in truth it's an psychology experiment to find out how long it takes people to get bored :-)

      • You're probably right. In a few days they'll publish the results haha. I gave up during the second one anyway. Since I didn't know the rules, I felt like I had no real chance and I gave up. I don't enjoy mindlessly clicking in order to figure out why.
    • Re: (Score:2, Insightful)

      Clicking randomly is not fun.

      Attention: Lucas Arts, Sierra Entertainment, et al.

    • Turn on Highlight on Hover under the game window. Then you can see what spots the buttons change, what color the button has to be to change the spot, and hover over spots to see what button can change it - makes it pretty simple.

  • by dido (9125) <dido@@@imperium...ph> on Thursday July 30, 2009 @04:59AM (#28878945)

    If I'm not mistaken, the boolean satisfiability problem is NP-complete. In fact, in 1971, Stephen Cook established a direct proof of its NP-completeness [wikipedia.org], which basically introduced the whole idea of NP-complete problems to theoretical computer science. Well, Sudoku is yet another game that is basically NP-complete as well [u-tokyo.ac.jp] (PDF link), and as might expected from their both being NP-complete, Sudoku problems are reducible to SAT problems (see here [umass.edu], also a PDF link), and presumably vice-versa. My guess is that perhaps the same people who get kicks out of solving Sudoku puzzles might have almost as much fun with this game as well.

    • by pzs (857406)

      I guess you could convert a SAT problem into a Sudoku. However, I think a crucial pre-condition for Sudoku people is that the puzzle is solvable with the given information. Nobody is going to spend hours plugging away at a Sudoko in order to try to return an "it can't be solved" answer.

      • by dido (9125)

        Well, I wouldn't be so quick to say that. As a counterexample, people routinely plug away at solitaire card games without any kind of assurance that the game they're playing can even be won. In fact, it seems that empirical results show that a fifth or even more of all Klondike solitaire games are unwinnable, and no true theoretical results on the winnability of Klondike solitaire are available. That hasn't deterred the game from becoming popular.

    • by ezzzD55J (697465)

      SAT is more than any old NPC problem. SAT is THE canonical NPC problem as it was the first to be proved so, by constructing a SAT problem from any given turing machine.

      Pretty much *by definition* of NPC can sudoku problems be 'reduced' to a SAT problem. That more a property of SAT than it is of sudoku.

  • If this is something a human should be able to do better then an AI, I am not human.

    I could only solve the first level of 3SAT and none of anySAT. I also did not try really hard as it got bored pretty fast and was thinking: why not write a program to do it. That would be so much easier.

    I just randomly clicked.

  • Foldit (Score:3, Insightful)

    by Frans Faase (648933) on Thursday July 30, 2009 @08:03AM (#28880109) Homepage
    Another example of a game used for science is Foldit [fold.it] where you have to fold a protein. I find this example more interesting than SAT.
  • The tutorial looks a lot more like a lecture than a "how to" play a game. I bailed.
  • http://www.warrenrobinett.com/rockysboots/ [warrenrobinett.com]

    I always wondered if/when they'd ever have a robotic peripheral that would link in (via rs232 I suppose) and would carry your logic creations out of the computer?

  • This IS awesome. (Score:3, Interesting)

    by BlueKitties (1541613) <bluekitties616@gmail.com> on Thursday July 30, 2009 @10:23AM (#28881819)
    I opened the game in one tab (Chrome) and the article in another. According to the article, the larger the bubble is the more buttons control its color -- by pressing the button tied to the bubble, the color will change accordingly. The smaller the bubble, the more buttons control it. Once all bubbles become green, you've won the game.

    If a bubble only has "one" button tied to it, that we know for a FACT that button must set that bubble to green -- we now don't have to worry about that button! Using similar tactics, this becomes an interesting cat-and-mouse game of whack-the-bubble. If you didn't enjoy the game or felt it's mechanical, give it a second chance and try to figure out how to use strategy -- it's actually really damn fun, and requires a lot of thought and careful reasoning. Don't worry, if it seemed hard at first, you're not a dunce, you're probably just not looking at things the right way.
    • by riegel (980896)
      This game is amazing. I wonder what would happen if each little rectangle were only controlled by one person. I wonder how long it would take a group to "cooperatively" solve the puzzle. If everyone could see the whole but only control their button. It seems like a 3^80 problem could probably be solved in seconds with 80 people on it.
  • It seems that the designers of the game are attempting to harness a form of "human computation" that has been popularized in other areas of computer science (e.g., the ESP game [wikipedia.org] for image labeling, Amazon's Mechanical Turk [mturk.com] for various tasks, etc.)

    Regrettably, this particular application of the concept is (IMHO) flawed. It is hard to argue that humans are more adept than machines for solving a problem like SAT (at least manually) and as many have pointed out, the dimensionality of the space is too grand for

  • on anySAT I stopped at level 12.

Cobol programmers are down in the dumps.

Working...