Slashdot Mirror
Making a Game of Hardware Design
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."
I hear girls like smart men. Now intellectualism can be combined with everyone's favorite pastime, video games-- bonus!!
Cool toy :-)
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?
The only winning move is not to play. How about a nice game of chess?
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 there are easily recognizable visible patterns in the puzzle. I've played with the game, but the relations between variables and constraints shown in the game are not very helpful.
I think a better approach is to use advanced visualization and exploration techniques, so humans can help simplify problems for computers to solve.
Still, the game does nicely show the difficulties in solving the SAT problem.
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.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
Though it doesn't serve a useful purpose (other than entertainment)
http://www.zachtronicsindustries.com/pivot/entry.php?id=79
Did you know that "FTW" ("for the win") is a direct translation of "Sieg Heil"?
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.
I solved the first two with this strategy:
1. Click through the 3 states of a button to find the state that has most green/least red bubbles
2. go to random next button
3. repeat
I couldn't be bothered to figure out the rules of the game. Could somebody be so kind to explain them? Is it really possible to solve these faster than a computer can?
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, 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 (PDF link), and as might expected from their both being NP-complete, Sudoku problems are reducible to SAT problems (see here, 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.
Qu'on me donne six lignes écrites de la main du plus honnête homme, j'y trouverai de quoi le faire pendre.
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.
Don't fight for your country, if your country does not fight for you.
Another example of a game used for science is Foldit 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/
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?
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.
"Sorrow is better than laughter, for by sadness of face the heart is made glad." [Ecclesiastes 7:3]
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 a suitable visualization.
In the space of VLSI design, higher-level problems grounded in physical space (such as macro floorplanning and large-block placement) would be much more amenable to this type of game.
I couldn't even try the game because I couldn't tell when it was red or green.
on anySAT I stopped at level 12.