Videogame Crowdsourcing Approach to Find Strategies Using Repeated Sub-Sequences
Export citation
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.