Game utilizes human intuition to help computers solve complex problems

Jul 27, 2009

(PhysOrg.com) -- A new computer game prototype combines work and play to help solve a fundamental problem underlying many computer hardware design tasks.

The online logic puzzle is called FunSAT, and it could help integrated circuit designers select and arrange transistors and their connections on silicon microchips, among other applications.

Designing chip architecture for the best performance and smallest size is an exceedingly difficult task that's outsourced to computers these days. But computers simply flip through possible arrangements in their search. They lack the human capacities for intuition and visual pattern recognition that could yield a better or even optimal design. That's where FunSAT comes in.

Developed by University of Michigan researchers Valeria Bertacco and Andrew DeOrio, FunSAT is designed to harness humans' abilities to strategize, visualize and understand complex systems.

"Computer games can be more than a fun diversion," said Bertacco, an associate professor in computer science and engineering. "Humans are good at playing games and they enjoy dedicating time to it. We hope that we can use their strengths to improve chip designs, databases and even robotics."

DeOrio, a doctoral student in Computer Science and Engineering, will present a paper on the research on July 30 at the Design Automation Conference in San Francisco.

A single-player prototype exists at funsat.eecs.umich.edu , implemented in Java by U-M undergraduate Erica Christensen. Bertacco and DeOrio are working on growing it to a multi-player game, which would allow more complicated problems to be solved.

By solving challenging problems on the FunSAT board, players can contribute to the design of complex computer systems, but you don't have to be a computer scientist to play. The game is a sort of puzzle that might appeal to Sudoku fans.

The board consists of rows and columns of green, red and gray bubbles in various sizes. Around the perimeter are buttons that players can turn yellow or blue with the click of a mouse. The buttons' color determines the color of bubbles on the board. The goal of the game is to use the perimeter buttons to toggle all the bubbles green.

Right-clicking on a bubble tells you which buttons control its color, giving the player a hint of what to do next. The larger a bubble is, the more buttons control it. The game may be challenging because each button affects many bubbles at the same time and in different ways. A button that turns several bubbles green will also turn others from green to red or gray.

The game actually unravels so-called satisfiability problems—classic and highly complicated mathematical questions that involve selecting the best arrangement of options. In such quandaries, the solver must assign a set of variables to the right true or false categories so to fulfill all the constraints of the problem.

In the game, the bubbles represent constraints. They become green when they are satisfied. The perimeter buttons represent the variables. They are assigned to true or false when players click the mouse to make them yellow (true) or blue (false).

Once the puzzle is solved and all the bubbles are green, a computer scientist could simply look at the color of each button to gather the solution of that particular problem.

Satisfiability problems arise not only in complex chip design, but in many other areas such as packing a backpack with as many items as possible, or searching for the shortest postal route to deliver mail in a neighborhood.

"When solving these problems, humans can use their intuition and visualization skills. For instance, by just glancing at the neighborhood map they can gain an intuition of where to begin in the case of the postal route," Bertacco said. "FunSAT can leverage these human skills that computer-based solvers do not have."

The paper is called "Human Computing for EDA."

Provided by University of Michigan (news : web)

Explore further: Big data may be fashion industry's next must-have accessory

add to favorites email to friend print save as pdf

Related Stories

New computer program automates chip debugging

Nov 02, 2007

Fixing design bugs and wrong wire connections in computer chips after they've been fabricated in silicon is a tedious, trial-and-error process that often costs companies millions of dollars and months of time-to-market.

An unbeatable computer game?

Aug 30, 2007

Researchers have come up with an idea to design a computer game that knows a player’s move about two seconds before the move is made. Using measurements of players’ skin conductance, the computer’s sensors ...

Color sudoku puzzle demonstrates new vision for computing

Dec 18, 2007

Researchers at the University of Warwick’s Department of Computer Science have developed a colour based Sudoku Puzzle that will help Sudoku players solve traditional Sudoku puzzles but also helps demonstrate ...

Recommended for you

Cloud computing helps make sense of cloud forests

Dec 17, 2014

The forests that surround Campos do Jordao are among the foggiest places on Earth. With a canopy shrouded in mist much of time, these are the renowned cloud forests of the Brazilian state of São Paulo. It is here that researchers ...

Teaching robots to see

Dec 15, 2014

Syed Saud Naqvi, a PhD student from Pakistan, is working on an algorithm to help computer programmes and robots to view static images in a way that is closer to how humans see.

User comments : 1

Adjust slider to filter visible comments by rank

Display comments: newest first

RayCherry
not rated yet Jul 28, 2009
Download the free game, and work for free - solving problems that experienced specialists earn a fortune for today.

Clever people exploiting markets has been a fact of life for centuries, but leveraging the Internet and Game Addiction could provide a more comercially attractive alternative ... given enough monkeys and enough typewriters ...

Taken to the extreme, addicts will solve business problems for free and pay the Internet providers for access ... product, dealer, consumer ... just like us geniuses here on PhysOrg providing public opinions, initial market uptake, left field criticism and valuable feedback - all for free.

Suddenly feeling like Scrat when the acorn turns to dust, but ... what if participation was financially rewarded according to merit and market?

SecondLife is a reward-driven end-user participation environment, with the potential to earn from the 'work' done while 'socialising' and 'playing' there.

Is this a more sustainable long-term business model?

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.