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 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?
I hear girls like smart men.
What planet are you from? You should come see Earth.
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.
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"?
Girls do like smart men, just not to the exclusion of other characteristics such as social skills and appearance.
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.
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.
Girls do like smart men, just not to the exclusion of other characteristics such as social skills and appearance.
It's hard to like someone you don't even know about because they don't come out of the basement long enough to talk to 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.
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]