Network Game

Author: Jens Jakob Sørensen

Contact person: Carrie Weidner cweidner@phys.au.dk

• Solving the most complex computational problems.
• Understanding how human intuition can provide new solution strategies

In the Network Game, you can help us find out how humans approach solving some of the most difficult computational problems. However, wait a minute! What does it mean for something to be difficult? Most of us would probably find the multiplication 1337*42 quite impossible (it’s 56154), but it can easily be performed by a computer. Some problems cannot be easily performed even by a computer—such as making a non-conflicting schedule for university courses. These problems are known as NP-hard problems. In these problems, finding good enough solutions often requires creative leaps, which computers are terrible at doing; unlike humans. In the Network Game, you must help us solving such NP-hard problems and see if you can find the necessary creative leaps.

In this game, you must find the shapes which fit the network the best. The network is defined by cyan and white connections. White connections give points when they connect shapes of the same type and the opposite way goes for cyan connections. However, for large networks, you cannot satisfy all connections!

An easy example is the following: take magnets that prefer to be anti-aligned (like in the game) and place three of them in a triangle. Then there is no configuration that makes all of the magnets happy.

In the game we introduce one extra complication which is characteristic of some of the most mysterious and potentially interesting frustrated systems, called spin glasses. Here, across the system there will be patches where magnets prefer to be aligned and others where they prefer to be anti-aligned. In the game we have frozen in these pairwise preferences, and then the players job is to search for the magnet combination that satisfies as many of the conditions as possible. The player must find the best trade-off between all the connections, and this trade-off is what makes the problem very difficult.

This game is currently an early demo of a project we might pursue further in the future.