A Video Game-Crowdsourcing Approach to Discover a Player’s Strategy for Problem Solution to Facility Location

Abstract

In recent times, there has been a growing interest in the domain of computationally challenging problem solving within both scientific and organizational contexts. This study is primarily concerned with the extraction and comprehension of the methodologies and strategies employed by individuals when confronted with intricate problems, specifically those falling under the purview of NP-hard problems. The Facility Location Problem (FLP) serves as a prominent exemplar within this study’s framework. Traditionally, the handling of such complex problems has leaned upon intuitive reasoning and visual perception as the primary tools. However, these conventional approaches tend to provide only limited insight into the underlying processes employed in solving such problems. The present research seeks to bridge this knowledge gap through the utilization of advanced machine learning techniques for the purpose of categorizing and scrutinizing the strategies deployed by individuals in their attempts to tackle computationally challenging problems. The analysis conducted as part of this study unveils discernible and well-defined patterns and strategies that are employed by participants, some of whom have achieved notable levels of success. Remarkably, in certain instances, the outcomes achieved by these individuals have demonstrated a competitive edge when compared to the results produced by sophisticated computational methods, such as genetic algorithms. A fundamental component of our research methodology involves the application of heatmaps and clustering techniques. Through the normalization of results, our findings distinctly delineate two primary categories of games: those characterized by uniform player strategies and those characterized by a multitude of diverse and individualized tactics. Furthermore, our research employs a systematic approach to represent games by clustering them based on inherent similarities, utilizing cosine similarity as a metric for this purpose. By computing the averages of vectors within each cluster, we derive centroids that encapsulate the central tendencies exhibited by games belonging to that cluster. These centroids are then visually presented in a three-dimensional format, complemented by proportional spheres. These visual representations serve to vividly illustrate the dispersion and influence associated with each cluster. Our research significantly contributes to the understanding of human problem-solving strategies when confronted with computationally challenging problems. It unearths valuable insights regarding the potential for harnessing human intuition and expertise in addressing complex computational challenges. Through the integration of machine learning methodologies and intuitive visualizations, this work advances our comprehension of the approaches individuals employ to excel in solving computationally intricate problems.

Keywords

• Facility location problem (FLP)
• crowdsourcing
• machine learning
• video game
• clustering
• strategy