Videogame Crowdsourcing Approach to Find Strategies Using Repeated Sub-Sequences

Abstract

Crowdsourcing surged as a new problem-solving model to better knowledge on how to solve a specific problem. The procedure starts by externalizing the problem from the group that is trying to solve it. Then, people with a variety of skills can help design solutions. The motivation for persons to participate is the key that makes the model work. From giving money to socialization, many options exist to encourage people to contribute to a crowdsourcing model. Studies tested the use of videogames to motivate people to participate in the solution to problems from different domains. These studies report that people can provide competitive solutions, against the experts, even for complex problems. Until now, Videogame Crowdsourcing helped to complement the solution space, but mining the strategies from the users is an area of opportunity. This thesis studies the application of Videogame Crowdsourcing for mining strategies from players’ solutions for a problem. It focuses on a specific one: the Housing Development Problem; it is of interest to the architecture community. It is a single objective problem that consists of placing as many houses as possible, given the land, subject to restrictions of connectivity (from the entrance of the land to all houses). We represented a match of our videogame as a sequence of movements. Each move consists of placing a house on a square of the land, represented as a grid, followed by displacement to another square in which the player puts the next one. This representation abstracts out two types of plays: the ones made to fulfill the restrictions of connectivity and the ones that belong to a correction of a previous one. Our underlying hypothesis is that a player strategy lies within a grammar expression; in particular, it is embedded in the recurrent sub-sequences of the expression. We used the videogame to collect 113 matches. With Sequitur, we found recurrent sub-sequences for each match, a larger sequence. Analyzing the sub-sequences, we have successfully identified the following strategies: Bottom-Left, Top-Right, Top-Left, and others that are not found as heuristics for optimization problems like the one on the videogame. Our results show that the strategy of a player is in the grammar expression of his/her movements. They encourage us to think that recurrent sub-sequences can build the strategies people use for the Housing Development Problem and lead to new algorithms.