Making a Game of Hardware Design 60
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... (Score:1)
Re: (Score:3, Funny)
I hear girls like smart men.
What planet are you from? You should come see Earth.
Re: (Score:2)
No. No, you should not. If you know what's good for you, you will stay as far away from Earth as you can.
Re: (Score:1, Offtopic)
Earth:The Milky Way::Alabama:USA
Re: (Score:1)
Re:I hear... (Score:4, Insightful)
Re: (Score:3, Funny)
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.
Re: (Score:1)
Fun (Score:1)
Cool toy :-)
Not so fun (Score:5, Insightful)
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)
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)
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.
Re: (Score:1)
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
Re: (Score:2)
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.
Re: (Score:2)
I had the same idea. A simple brute force approach should be able to outperform a human by atleast a factor of millions.
Re: (Score:2)
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)
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)
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: (Score:2)
Lol, WowEmuHacker v5 :-)
Re: (Score:2)
If not, change the visualization so that the user can infer the function of each button and reason over them, or give up and resume doing brute force computation or logic proofs.
They do that. It just takes a while to figure out the rules.
Re:Not so fun (Score:4, Insightful)
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)
Re: (Score:1)
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)
Re: (Score:2)
Re: (Score:1)
There's a bug in many keyboards which every time you type the key sequence "[L] [O] [S] [E]" appends the key presses "[<-] [<-] [O] [->] [->]" afterwards.
That's why many people love old (non-enhanced) versions of vi: Old vi doesn't know the arrow keys.
Re: (Score:1)
Why is it that no one online can spell the term 'lose' correctly?
godammit u dont have to be such a gramar nazi!!!!11onecos(0)
doubts (Score:2, Informative)
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
If I help you make hardware... (Score:2)
SAT, really? (Score:2)
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.
Re: (Score:1)
Actually SAT problems are usually solved quite easily. You just have to turn your dish until you get a reasonable signal. :-)
KOHCTPYKTOP is more fun (Score:4, Interesting)
Though it doesn't serve a useful purpose (other than entertainment)
http://www.zachtronicsindustries.com/pivot/entry.php?id=79 [zachtronic...stries.com]
Re: (Score:2)
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)
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.
Re: (Score:2)
the puzzles would be a jumbled mess if you had to do them properly.
Re: (Score:1)
Thanks for the link. kohctpyktop *is* fun...
Thats not a game (Score:2, Insightful)
Re: (Score:1)
Maybe in truth it's an psychology experiment to find out how long it takes people to get bored :-)
Re: (Score:1)
Re: (Score:2, Insightful)
Clicking randomly is not fun.
Attention: Lucas Arts, Sierra Entertainment, et al.
Re: (Score:1)
Re: (Score:1)
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.
Satisfiability, Sudoku, and NP-completeness (Score:3, Informative)
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.
Re: (Score:2)
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.
Re: (Score:2)
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.
Re: (Score:2)
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.
Re: (Score:2)
Foldit (Score:3, Insightful)
This is a game? (Score:1)
Rocky's Boots? (Score:1)
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)
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.
Re: (Score:1)
Abuse of Human Computation (Score:1)
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
What level did you stop at? (Score:1)
on anySAT I stopped at level 12.