05 de septiembre, 2014
Dev Lavde 18# – Algoritmos genéticos

«Mi padre tenía razón, no importaba cuanto mintiera en mi informe. Mi verdadero informe estaba en mis células. […] Por supuesto discriminar es ilegal, se denomina genoísmo. Pero nadie se toma la ley en serio» La controversia que rodea la ética de la modificación genética ha dado de beber muchísimo a la ciencia ficción, y uno de sus máximos exponentes es la película Gattacca (Andrew Niccol, 1997), centrada en la posible discriminación hacia seres humanos que no han sido genéticamente seleccionados en un hipotético futuro cercano. No obstante, cuando la genética se utiliza como referente para un algoritmo de computación, la discriminación es, precisamente, la clave. Ni los creacionistas podrán negar las ventajas de numerosas iteraciones de un proceso evolutivo simulado. Spoiler: Esto no tiene nada que ver con la forma de generar retoños en Los Sims.

Cuando se habla de inteligencia artificial en videojuegos, lo más corriente es hacerlo en referencia a al comportamiento de personajes autónomos y tratando de que estos resulten, a los ojos del jugador, más realistas e inteligentes (o estúpidos). Sin embargo, la inteligencia artificial no siempre se usa para lo mismo. Hay muchas aplicaciones distintas, y algunas de ellas tienen más sentido durante el desarrollo que durante la ejecución del juego. Es el caso de los algoritmos genéticos, técnica poco común pero con interesantes aplicaciones.

Heurística

Algunos lectores habrán escuchado a menudo esta expresión, sin saber muy bien qué significa. Muchos problemas, como la búsqueda de rutas, son difíciles o ineficientes de solucionar por métodos de computación clásica. Un algoritmo heurístico es cualquiera que, sin garantías de éxito ni eficiencia, se encarga de encontrar una solución a ese problema que de otra forma sería imposible, o mucho más difícil. Normalmente incluyen un ensayo y error automatizado, repitiendo el mismo proceso hasta encontrar una solución factible que se acerque lo suficiente al objetivo final.

Suelen partir de ideas muchas veces inspiradas en procesos o patrones que se pueden encontrar en la naturaleza. Por ello están muy relacionados con la inteligencia artificial, tomando ésta como cualquier forma de computación que intente imitar o mejorar algún aspecto humano. Ningún algoritmo heurístico intentará dominar el mundo, pero ya podemos hacernos la idea de cómo los que sí que lo dominan buscan la palabra «Bomba» en las comunicaciones globales.

¿Qué es un algoritmo genético?

Con el transcurso del tiempo, una población de individuos sufre infinidad de mutaciones y cruces, y aquellos individuos que, fortuitamente, reciben una cierta ventaja, tienden a reproducirse más, dominando sobre el resto y eventualmente reemplazándolos. A este fenómeno se le llama selección natural, y su resultado es la evolución de las especies.

Los algoritmos genéticos son una forma de heurística que trata de reproducir ese proceso de selección y evolución con el objetivo de refinar una serie de parámetros y encontrar la combinación que más se adecue a un determinado propósito. Para ello, hay que describir la solución del problema en base a una serie de valores numéricos que constituyen el genotipo. Este genotipo puede codificar parámetros como apariencia, comportamiento, cualidades físicas… Sobre ellos actuará el algoritmo, y decidirlos puede no ser sencillo según el problema que se quiera resolver.

Una vez implementado el genotipo, el algoritmo se resume en los siguientes pasos:

  1. Mezcla inicial
    Es necesaria una población de individuos inicial que se genera dando valores aleatorios a los parámetros. También pueden inicializarse con valores escogidos en base a algún criterio o con resultados de anteriores usos del algoritmo.
  2. Selección
    Para seleccionar los mejores candidatos entra en juego la función de fitness. Esta función obtendrá una “nota” a partir del genotipo de cada individuo, indicando lo cerca que se está de la solución al problema. La función de fitness es la clave del proceso. Tiene ir a la par con el propósito final del algoritmo, además de ser lo más rápida posible en términos computacionales, por lo que su diseño y ajuste es complicado, y es a lo que más tiempo se suele dedicar.
  3. Cruce y/o mutación
    Seleccionados los mejores candidatos, se cruzan sus parámetros y se realizan pequeñas variaciones aleatorias (mutaciones) sobre ellos, para obtener una nueva generación con la que volver a alimentar el algoritmo. Se suelen usar índices o porcentajes para controlar los cruces y mutaciones, de forma que ocurran de forma regulada.

La ejecución del algoritmo se repite un número determinado de veces, o hasta que se encuentre una solución satisfactoria.

En resumen

Los algoritmos genéticos son costosos en términos de CPU, por lo que no es aconsejable usarlos durante la ejecución del juego, pero son una herramienta potente a la hora de ajustar y equilibrar parámetros del juego durante el desarrollo o para generar contenido procedural. Pueden servir con bastante provecho para encargarse de tareas tediosas de ajuste para las cuales un ser humano emplearía mucho tiempo. Como toda heurística, no garantizan una solución óptima, pero podrían encontrar soluciones novedosas o imprevistas en las que una persona rara vez llegue a pensar.

Generalmente es poco común la necesidad de algoritmos genéticos en el desarrollo de un juego, sin embargo, nunca está de más conocer su existencia y sus principios básicos. Como poco, es otra técnica más que añadir a ese kit de supervivencia indie, a la espera de ser utilizada en algún momento.

Acerca de Enrique Hervás


Humano Nivel 32. Diseñador y Programador de videojuegos Nivel 6. De esos a los que sus padres prohibieron jugar a "las maquinitas" por estar demasiado enganchados. No sabían lo que les esperaba. Actualmente trabajo como Game Designer en Exient, e intento no olvidarme de mi pasado indie de Game Jams y jueguitos con Join2 Games

No hay comentarios