An Empirical Study on Collective Intelligence Algorithms for Video Games Problem-Solving

Authors

  • Antonio Gonzalez-Pardo Basque Center for Applied Mathematics (BCAM), Bilbao & TECNALIA, OPTIMA Unit, Derio
  • Fernando Palero Escuela Politecnica Superior, Universidad Autonoma de Madrid, Madrid
  • David Camacho Escuela Politecnica Superior, Universidad Autonoma de Madrid, Madrid

Keywords:

Collective intelligence, ant colony optimization, genetic algorithms, video games solving algorithms, Lemmings video game

Abstract

Computational intelligence (CI), such as evolutionary computation or swarm intelligence methods, is a set of bio-inspired algorithms that have been widely used to solve problems in areas like planning, scheduling or constraint satisfaction problems. Constrained satisfaction problems (CSP) have taken an important attention from the research community due to their applicability to real problems. Any CSP problem is usually modelled as a constrained graph where the edges represent a set of restrictions that must be verified by the variables (represented as nodes in the graph) which will define the solution of the problem. This paper studies the performance of two particular CI algorithms, ant colony optimization (ACO) and genetic algorithms (GA), when dealing with graph-constrained models in video games problems. As an application domain, the "Lemmings" video game has been selected, where a set of lemmings must reach the exit point of each level. In order to do that, each level is represented as a graph where the edges store the allowed movements inside the world. The goal of the algorithms is to assign the best skills in each position on a particular level, to guide the lemmings to reach the exit. The paper describes how the ACO and GA algorithms have been modelled and applied to the selected video game. Finally, a complete experimental comparison between both algorithms, based on the number of solutions found and the levels solved, is analysed to study the behaviour of those algorithms in the proposed domain.

Downloads

Download data is not yet available.

Downloads

Published

2015-06-19

How to Cite

Gonzalez-Pardo, A., Palero, F., & Camacho, D. (2015). An Empirical Study on Collective Intelligence Algorithms for Video Games Problem-Solving. COMPUTING AND INFORMATICS, 34(1), 233–253. Retrieved from http://www.cai.sk/ojs/index.php/cai/article/view/2058

Issue

Section

Special Section Articles