Announcing: Slashdot Deals - Explore geek apps, games, gadgets and more. (what is this?)

Thank you!

We are sorry to see you leave - Beta is different and we value the time you took to try it out. Before you decide to go, please take a look at some value-adds for Beta and learn more about it. Thank you for reading Slashdot, and for making the site better!

Making a Game of Hardware Design

Soulskill posted more than 5 years ago | from the sim-cpu dept.

Games 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."

Sorry! There are no comments related to the filter you selected.

I hear... (1)

wasmoke (1055116) | more than 5 years ago | (#28878577)

I hear girls like smart men. Now intellectualism can be combined with everyone's favorite pastime, video games-- bonus!!

Re:I hear... (2, Funny)

sopssa (1498795) | more than 5 years ago | (#28878697)

I hear girls like smart men.

What planet are you from? You should come see Earth.

Re:I hear... (1)

Pyrion (525584) | more than 5 years ago | (#28878737)

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:I hear... (0, Offtopic)

geminidomino (614729) | more than 5 years ago | (#28881577)

Earth:The Milky Way::Alabama:USA

Re:I hear... (4, Insightful)

Procasinator (1173621) | more than 5 years ago | (#28878829)

Girls do like smart men, just not to the exclusion of other characteristics such as social skills and appearance.

Re:I hear... (2, Funny)

Jurily (900488) | more than 5 years ago | (#28878987)

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:I hear... (1)

Procasinator (1173621) | more than 5 years ago | (#28879297)

That player is just being mysterious and playing hard to get... chicks dig that!

Re:I hear... (-1, Offtopic)

Anonymous Coward | more than 5 years ago | (#28878875)

"I hereby sentence you to a term of no less than 6 years and not exceeding 12 years" bellowed the Judge at my court case. You could tell in the sterness of his voice and his general demeanor that he took delight in sending scum like me up the river. A fucking DUI that ended up killing some black kid in Detroit was all it took to sealed my fate for the next decade. I had thoughts of appeal but I figured it wouldn't be worth the little savings I had left and my sentence would probably stand. To this day I still believe had the kid been white, my life would have been much easier, inside and outside of prison.

Now, don't believe what you see on Televison about prison, it is a far worse place than any 32" screen could every conjure up. Imagine watching an MSNBC special on jail or an episode of OZ and take that experience and double it. That's about the wretched hell I have come to know for the past 3 1/2 years. Sometimes I don't know who is worse and my already fazed and battered mind, the prison guards or the inmates. It really takes a certain type of psychopath to want to work around this place, 8 hours a day or longer and that's exactly the type of labor pool this place picks from.

I can't say my first week was the worst week of my life, but I can certainly say it was the scariest, most horrifying change change in lifestyle I can remember. The dynamic between my old life as a software developer with a modest 1 bedroom downtime, to sharing a tiny cell with a sexual deviant is enough to make anyone go insane. But anyway let me talk about my first day of 12 long years here.

As I was escorted on to the prison bound bus with the day's newly convicted felons, it was already starting. I was chained next to this black man named Napps. I am sure this wasn't his real name but you can't tell these days with the way these people are named. Now Napps was a pretty built man, and I could tell by the excess amount of tattos and his attitude, that this wasn't the first time he was getting bussed off to a stint in the State Penetentary. Napps upon being forced to sit next to me had given me a look that you would imagine a wolf would give towards their defenseless prey. That was what I officially was now, defensless prey for Napps and God knows who else now. Napps, with a smug and deviously look in his eye asked me "What's a white boy like yourself doing going to the shit?". "Pardon?", I said uneasily almost choking on my words. "This white boy dinks we at da country club.", he said to the rest of the bus, while the bus started roaring in laughter. Now all eyes and ears on the bus were tuned in to me. "I says, wat a tender cracka like you doing here wit the rest of us?", he said in a more pointed fashion. "I'm here...for drunk driving. I killed someone in Brightmore", I shamefully admitted. "So you the motherfucka who killed dat black kid!", now furious with me. The rest of the bus, still focused on me began roaring again loudly as if my crime is more terrible than raping and killing a white woman in the suburbs (I eventually find this out later on). "You lucky da guards are here bitch, you hear me? When we get down to the shit, your ass belongs to the blacks, you got it cracker?". My heart jumped, not even in prison yet, and I am already targeted for what I am sure is to be a stabbing. Shit.

The bus finally turned into the outer gate, which seemed to stretch on for ever, Napps was still from time to time threatening me. I didn't think I would even make it into prison alive. "So you kill one of ours, huh?", he uttered with extreme hatred. "Well, I took one of yours too bitch ass. 4 of my boys went to your white part of town and and took a bitch. We ran a train on dat fo 8 hours, den we pours acid on that cunt", he must have enjoyed the thought as he laughed sadisticly while telling me his crime. As we got manhandled off of the bus one by one, Napps turned around and said "watch yo ass, lit'ry!", before being forced face first by the guard.

By now I was too much in shock from being scared to even be scared. I went through the motions of "processing" before I was escorted to my cell. The bunk was already occupied with an inmate, reading some sort of hip-hop magazine. I was pushed into my cell, and my new roommate eyed me and said "So you the nigga killer?". "It's gonna be you and me tonight", he threatened as I already had my fill of being threatened by prison niggers. It was already about 8:30 and since our bus got delayed coming in, and I knew that in a half an hour it was going to be 'me and him'.

"Lights out! Lights fucking out!" Yelled from the distance as the boom of the dimming lights started my first night. "You and me time, cracker" the hulking voice from the top of the bunk whispered. He came down from his bunk getting about 6 inches away from me and must have been 6 foot five. I started panicking, believing he had a shank or was going to choke me to death but it was too dark to tell. He moved his hands down around his crotch and made several 'manuveurs'. Before I knew it, still being dark, he had his cock out in front of me, which must have been at least 8 inches but probably 10 if I could see. "Yo want to ack like a bitch, you gonna suck like one too". His giant hands pushed me into my knees while he began putting his already erect cock up towards my face. By now his throbbing cock was hitting me on the side of my ear as he kept commanding me to open my mouth. "Put this shit down yo throat bitch", he commanded again while I still resisted. "Boy, I will cut yo throat if I gots to say it another time", he responded to my reluctance.

I finally gave in, thinking that this was probably still better than death. I opened my mouth and began feeding his nigger cock into my mouth. This was not enough for him and he grabbed my hair while he forced the rest of what was probably 5 inches more down my throat. I almost gagged but maintained composure, while he started skull fucking me more and more. I figured this would soon be over and I would be able to go cry myself to sleep very soon. He then pulled out and I thought the worst was over. "Bitches need a good fuck now too", he said while he threw me in my bunk and made me get on my hands and knees. He forced my pants down and kept me in place even while I tried my best to squirm out of there and go...nowhere. His cock still hard and wet with my mouth, he pushed his cock into my virgin asshole. I swear, between his cock size and my clenching reaction, this was the most painful experience I have can remember. The car accident that brought me here didn't even hurt half as bad. He kept going at it while he pulled my hair and pinned me down with his giant body. I tried to scream for help but nothing would even coming out. The only sounds now coming out of my cell was the cyclic screeching of springs and the "Hmm! Hmm! Hmm!" of my new found rapist. When it was finally over, he had deposited a gigantic load of semen on my ass, and with his cock still in my ass whispered in my ear "Wait till the rest of the niggers break you in tomorrow". He kissed me on the cheek and left my limp body in my own bed as he climbed back up to his bunk.

3 sphincter surgeries and an HIV positive diagnosis later, I am 3 year into my prison sentence, and worth about a pack of Pall Malls. I constantly think of killing myself but I know I don't have the guts to do so. Napps, Tbone, and Shades are back and I have little time now before I get traded on the nigger exchange. I thought I would share my experiences on Slashdot and let people know how prison reall

Fun (1)

Hammer (14284) | more than 5 years ago | (#28878585)

Cool toy :-)

Not so fun (4, Insightful)

pmontra (738736) | more than 5 years ago | (#28878607)

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:Not so fun (1, Informative)

Anonymous Coward | more than 5 years ago | (#28878649)

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:Not so fun (2, Informative)

sopssa (1498795) | more than 5 years ago | (#28878721)

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:Not so fun (1)

riegel (980896) | more than 5 years ago | (#28887135)

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


for x=1 to 1000000000000000000000000000000000



print a-systime

Re:Not so fun (1)

cstdenis (1118589) | more than 5 years ago | (#28887515)

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:Not so fun (1)

mwvdlee (775178) | more than 5 years ago | (#28878681)

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

Re:Not so fun (1)

noundi (1044080) | more than 5 years ago | (#28878753)

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 (3, Interesting)

Jurily (900488) | more than 5 years ago | (#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:Not so fun (2, Interesting)

Jurily (900488) | more than 5 years ago | (#28879313)

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 (2)

easyTree (1042254) | more than 5 years ago | (#28880555)

Lol, WowEmuHacker v5 :-)

Re:Not so fun (0)

Anonymous Coward | more than 5 years ago | (#28882363)

To build an intelligent algorithm from human performance data, one needs intelligent human performance. The authors should test whether humans are, in fact, performing intelligently, i.e., with any strategy that is not (1) random (i.e., click any button) or (2) systematic but with random effects (e.g., clicking each button in counterclockwise rotation). IFF humans are acting intelligently, then sic machine learning on the data. 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.

Re:Not so fun (1)

Jurily (900488) | more than 5 years ago | (#28882641)

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 (3, Insightful)

Pyrion (525584) | more than 5 years ago | (#28878709)

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:Not so fun (2, Informative)

psyph3r (785014) | more than 5 years ago | (#28878865)

I did the "anysat" set and they became very complex after several levels. the first ones may just be "tutorial" levels.

Re:Not so fun (1)

cgomezr (1074699) | more than 5 years ago | (#28878877)

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 (3, Interesting)

wagnerrp (1305589) | more than 5 years ago | (#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.

Re:Not so fun (1)

religious freak (1005821) | more than 5 years ago | (#28891049)

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!

Re:Not so fun (0)

Anonymous Coward | more than 5 years ago | (#28882305)

Why is it that no one online can spell the term 'lose' correctly?

Re:Not so fun (1)

maxwell demon (590494) | more than 5 years ago | (#28882879)

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:Not so fun (1)

SilverEyes (822768) | more than 5 years ago | (#28882927)

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)

A strange game. (0)

Anonymous Coward | more than 5 years ago | (#28878729)

The only winning move is not to play. How about a nice game of chess?

doubts (2, Informative)

Anonymous Coward | more than 5 years ago | (#28878749)

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.

If I help you make hardware... (1)

PhrostyMcByte (589271) | more than 5 years ago | (#28878793)

Your hardware better be Open Source if I'm going to help you make it.

SAT, really? (1)

Trepidity (597) | more than 5 years ago | (#28878821)

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:SAT, really? (1)

maxwell demon (590494) | more than 5 years ago | (#28878907)

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 (3, Interesting)

Fry-kun (619632) | more than 5 years ago | (#28878827)

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

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

Re:KOHCTPYKTOP is more fun (1)

OrangeTide (124937) | more than 5 years ago | (#28878989)

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:KOHCTPYKTOP is more fun (2, Interesting)

MarkGriz (520778) | more than 5 years ago | (#28883089)

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:KOHCTPYKTOP is more fun (1)

OrangeTide (124937) | more than 5 years ago | (#28883665)

the puzzles would be a jumbled mess if you had to do them properly.

Re:KOHCTPYKTOP is more fun (1)

easyTree (1042254) | more than 5 years ago | (#28886961)

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

Thats not a game (2, Insightful)

dublindan (1558489) | more than 5 years ago | (#28878859)

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.

Re:Thats not a game (1)

maxwell demon (590494) | more than 5 years ago | (#28878911)

Maybe in truth it's an psychology experiment to find out how long it takes people to get bored :-)

Re:Thats not a game (1)

dublindan (1558489) | more than 5 years ago | (#28879045)

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:Thats not a game (2, Insightful)

not-enough-info (526586) | more than 5 years ago | (#28879155)

Clicking randomly is not fun.

Attention: Lucas Arts, Sierra Entertainment, et al.

Re:Thats not a game (1)

SilverEyes (822768) | more than 5 years ago | (#28882957)

Science is fun once you know the secret!

Re:Thats not a game (1)

Pranadevil2k (687232) | more than 5 years ago | (#28879411)

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.

What are the rules? (0)

Anonymous Coward | more than 5 years ago | (#28878895)

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?

Satisfiability, Sudoku, and NP-completeness (2, Informative)

dido (9125) | more than 5 years ago | (#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.

Re:Satisfiability, Sudoku, and NP-completeness (1)

pzs (857406) | more than 5 years ago | (#28879877)

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:Satisfiability, Sudoku, and NP-completeness (1)

dido (9125) | more than 5 years ago | (#28884973)

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:Satisfiability, Sudoku, and NP-completeness (1)

ezzzD55J (697465) | more than 5 years ago | (#28880953)

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.

I am not human (1)

houghi (78078) | more than 5 years ago | (#28879099)

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 (2, Insightful)

Frans Faase (648933) | more than 5 years ago | (#28880109)

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.

This is a game? (1)

methano (519830) | more than 5 years ago | (#28880579)

The tutorial looks a lot more like a lecture than a "how to" play a game. I bailed.

Rocky's Boots? (1)

otis wildflower (4889) | more than 5 years ago | (#28880689)

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. (3, Interesting)

BlueKitties (1541613) | more than 5 years ago | (#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.

Re:This IS awesome. (1)

riegel (980896) | more than 5 years ago | (#28887297)

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.

Abuse of Human Computation (1)

domulys (1431537) | more than 5 years ago | (#28882247)

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 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.

Red Green Color Blind (0)

Anonymous Coward | more than 5 years ago | (#28886017)

I couldn't even try the game because I couldn't tell when it was red or green.

What level did you stop at? (1)

angelbunny (1501333) | more than 5 years ago | (#28891539)

on anySAT I stopped at level 12.

Check for New Comments
Slashdot Login

Need an Account?

Forgot your password?