Research
Investigating the connection between computational complexity and human enjoyment.
There is plenty of marketing research about what makes things appealing to people, and plenty of computer science research about measuring the complexity of games. Both of these are very valuable; predicting people's interest in things allows you to produce products more intriguing to the consumer, and effectively modeling games is a valuable step on the way to effectively modeling things in the non-virtual world, such as human behavior.
There is very little research, however, into comparing computational complexity with human enjoyment. The specific point of interest here is whether making a game NP-complete makes it more entertaining.
The goal is to take a specific video game and randomly generate six different levels (two levels solvable in polynomial time, two that are certainly exponential, and two that are NP-complete). Then, people will play one of each type of level (in a random order) for a few minutes each and then fill out a survey about how entertaining they found it.
Finding a link between these two things could be valuable for a few reasons. Discovering a mathematically provable quality of games that makes them more fun could be beneficial to both producers and consumers, as reliably creating enjoyable games would benefit both parties. Additionally, there are many games that have short-lived but incredibly wide-spread popularity (such as Flappy Bird or Candy Crush), and these games are often more similar to older, less successful games than they are to each other, and it is notoriously difficult to predict which games will suddenly go viral. Finding a correlation between the complexities of these games could allow developers insight about how difficult to make their games.
This repository will hold a text file of the survey to be taken after as well as the code of the levels to be played. At present, I expect Super Mario Bros. to be the game used. The levels will be generated using an instance of 3-SAT. The 3-SAT repository will be used to generate the instances.