Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:

 

Game Utilizes Human Intuition to Help Computers Solve Complex Problems

30.07.2009
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 computer science 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 http://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."

For more information:

Valeria Bertacco: http://www.eecs.umich.edu/~valeria/

FunSAT: http://funsat.eecs.umich.edu

Michigan Engineering:
The University of Michigan College of Engineering is ranked among the top engineering schools in the country. At more than $130 million annually, its engineering research budget is one of largest of any public university. Michigan Engineering is home to 11 academic departments and a National Science Foundation Engineering Research Center. The college plays a leading role in the Michigan Memorial Phoenix Energy Institute and hosts the world class Lurie Nanofabrication Facility. Find out more at http://www.engin.umich.edu/.

Nicole Casal Moore | Newswise Science News
Further information:
http://www.umich.edu

More articles from Information Technology:

nachricht Smart Computers
21.08.2017 | Albert-Ludwigs-Universität Freiburg im Breisgau

nachricht AI implications: Engineer's model lays groundwork for machine-learning device
18.08.2017 | Washington University in St. Louis

All articles from Information Technology >>>

The most recent press releases about innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Fizzy soda water could be key to clean manufacture of flat wonder material: Graphene

Whether you call it effervescent, fizzy, or sparkling, carbonated water is making a comeback as a beverage. Aside from quenching thirst, researchers at the University of Illinois at Urbana-Champaign have discovered a new use for these "bubbly" concoctions that will have major impact on the manufacturer of the world's thinnest, flattest, and one most useful materials -- graphene.

As graphene's popularity grows as an advanced "wonder" material, the speed and quality at which it can be manufactured will be paramount. With that in mind,...

Im Focus: Exotic quantum states made from light: Physicists create optical “wells” for a super-photon

Physicists at the University of Bonn have managed to create optical hollows and more complex patterns into which the light of a Bose-Einstein condensate flows. The creation of such highly low-loss structures for light is a prerequisite for complex light circuits, such as for quantum information processing for a new generation of computers. The researchers are now presenting their results in the journal Nature Photonics.

Light particles (photons) occur as tiny, indivisible portions. Many thousands of these light portions can be merged to form a single super-photon if they are...

Im Focus: Circular RNA linked to brain function

For the first time, scientists have shown that circular RNA is linked to brain function. When a RNA molecule called Cdr1as was deleted from the genome of mice, the animals had problems filtering out unnecessary information – like patients suffering from neuropsychiatric disorders.

While hundreds of circular RNAs (circRNAs) are abundant in mammalian brains, one big question has remained unanswered: What are they actually good for? In the...

Im Focus: RAVAN CubeSat measures Earth's outgoing energy

An experimental small satellite has successfully collected and delivered data on a key measurement for predicting changes in Earth's climate.

The Radiometer Assessment using Vertically Aligned Nanotubes (RAVAN) CubeSat was launched into low-Earth orbit on Nov. 11, 2016, in order to test new...

Im Focus: Scientists shine new light on the “other high temperature superconductor”

A study led by scientists of the Max Planck Institute for the Structure and Dynamics of Matter (MPSD) at the Center for Free-Electron Laser Science in Hamburg presents evidence of the coexistence of superconductivity and “charge-density-waves” in compounds of the poorly-studied family of bismuthates. This observation opens up new perspectives for a deeper understanding of the phenomenon of high-temperature superconductivity, a topic which is at the core of condensed matter research since more than 30 years. The paper by Nicoletti et al has been published in the PNAS.

Since the beginning of the 20th century, superconductivity had been observed in some metals at temperatures only a few degrees above the absolute zero (minus...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

Event News

Call for Papers – ICNFT 2018, 5th International Conference on New Forming Technology

16.08.2017 | Event News

Sustainability is the business model of tomorrow

04.08.2017 | Event News

Clash of Realities 2017: Registration now open. International Conference at TH Köln

26.07.2017 | Event News

 
Latest News

Nagoya physicists resolve long-standing mystery of structure-less transition

21.08.2017 | Materials Sciences

Chronic stress induces fatal organ dysfunctions via a new neural circuit

21.08.2017 | Health and Medicine

Scientists from the MSU studied new liquid-crystalline photochrom

21.08.2017 | Materials Sciences

VideoLinks
B2B-VideoLinks
More VideoLinks >>>