¿Se pueden escribir algoritmos que evolucionen por si mismos? (Algoritmos genéticos/evolutivos)

Introducción

Todo empezó cuando quisimos hacer un videojuego, la idea era simple, al mejor estilo D&D o sword and sandals, creabas un personaje el cual le dabas distintos puntos de habilidad en varias categorías (fuerza, defensa, inteligencia, etc.). A partir de eso, peleabas contra distintos contrincantes y dependiendo de los stats de cada uno se obtenía el vencedor.

Hasta ese punto parecía sencillo pero, surgió un problema, en todo videojuego de bien, la dificultad es creciente y por lo tanto... ¿Como hacemos para crear peleadores cada vez mejores?

Lo logramos gracias a Darwin y su teoría de la evolución (en honor a él los peleadores serán monos) pero antes de explicarles de que va el juego, vamos con un pequeño espacio publicitario (del juego que hicimos y del que vamos a hablar :D)

Si quieres jugar a nuestro juego antes de leer la publicación (recomendado) puedes hacer click AQUI.

En la intersección entre la fascinante naturaleza de los algoritmos genéticos y la vertiginosa adrenalina de los videojuegos de peleas, para esta ocasión, nos adentramos en un sorprendente mundo virtual donde monos inteligentes se enfrentan en una batalla épica, todo gracias a la genialidad y al legado científico de Charles Darwin.

En este apasionante juego, vas a poder ver como una serie de monos evolutivos, cada uno con habilidades y características únicas, se enfrentan en una pelea a muerte. Pero, ¿cómo se logra esta sorprendente evolución de los personajes? La respuesta radica en la implementación de algoritmos genéticos, un concepto científico que encuentra su inspiración en la teoría de la evolución de Darwin.

Al igual que Darwin describió en su famosa teoría de la evolución, solo los más aptos sobreviven. Los monos más prometedores son sometidos a procesos de reproducción, mutación y selección artificial. Con cada enfrentamiento, los monos aprenden, se adaptan y evolucionan, mejorando sus habilidades de combate y convirtiéndose en guerreros imparables.

El espíritu de Darwin vive a través de los monos luchadores y nos recuerda que en la batalla por la supervivencia, solo los más fuertes y adaptados pueden triunfar.

*Imagenes solo a modo ilustrativo, no se decepcione después

Luego de esta emocionante introducción, procederemos a mostrar paso a paso como logramos esto.

Darwin y los algoritmos genéticos

¿Como podemos explicar que de un universo tan caótico, surjan seres con sistemas tan complejos como los humanos? Darwin encontró la solución, planteando una especie de "juego" (El nuestro esta mejor ;) ).

Para Darwin, los participantes son los distintos seres vivos (bacterias, animales, humanos, plantas, etc...) el objetivo es poder reproducirse, para lo cual, necesitarán: llegar a una edad determinada, alimentarse lo suficiente, NO MORIRSE ANTES, etc... . Hasta ahí todo bien, los perdedores como "jugaron mal", se van del juego para siempre, en cambio, los ganadores logran que replicas parecidas a sí mismos permanezcan en el tablero del juego (el mundo).

Pero hay un detalle importante más, los hijos de los "ganadores" no son perfectamente iguales a sus padres, sino que, pueden tener algún rasgo distinto (una mutación). Al fin de cuentas, esto hace que si el rasgo distinto ayuda a ganar, el rasgo quedará en sus generaciones que siguen, si no, desaparece. Este mecanismo lo describió en su libro "El origen de las especies" y lo llamo evolución.

Pero... ¿Qué son los algoritmos genéticos? La idea fundamental detrás de los algoritmos genéticos es simular al proceso de evolución biológica para encontrar soluciones óptimas a través de generaciones sucesivas. En lugar de trabajar con organismos vivos, los algoritmos genéticos operan con una población de posibles soluciones llamadas "individuos" o "cromosomas", estos algoritmos se utilizan para encontrar soluciones óptimas o aproximadas en situaciones complejas y se basan en principios evolutivos. Por lo tanto, a través de ellos, se pueden moldear las habilidades y características de los monos combatientes en función de su rendimiento y desempeño en el campo de batalla virtual.

¿Y nuestro juego como será?

Utilizamos la tecnica "arte ascii" para las visuales del juego

Por una parte, tenemos los participantes, monos peleadores y, por otro lado, tendremos una forma de pelea entre estos participantes.

Para los rivales de uno aplicaremos algoritmos genéticos de una manera muy sencilla:

Generaremos muchos monos al azar.
Los haremos pelear entre si.
Los que mueren en las peleas, se descartan, a los que la ganan los guardamos
Luego, creamos monos parecidos a los ganadores, los cuales pelarán contra ellos para sacar la "segunda generación" y así sucesivamente.
Mientras van pasando las generaciones, quedaran monos cada vez mas fuertes.

Aclaración: Nosotros siempre ponemos los códigos que usamos en nuestros blogs, pero si no sabes programar, o simplemente no te interesa, podes pasarlos de largo y aun así entenderás de lo que hablamos.

En otras palabras, en cada generación haremos esto:



def Evolucion(iniciales):

  Monos_Mutados = []
  Monos_Aleatorios = []
  nuevos_monos = []

  nuevos_monos.append(iniciales[0])

  # Un cuarto de los monos seran un poco mutados, otro cuarto seran mutados mucho
  for i in iniciales:
      monito = Mono("Mutuado_poco",Mutacion_Mono(i))
      Monos_Mutados.append(monito)

      monito = Mono("Mutuado_mucho",Mutacion_Mono(i,True))
      Monos_Mutados.append(monito)

  # El resto de de los monos seran completamente aleatorios
  Monos_Aleatorios = Creacion_Aleatoria(31-len(iniciales)-len(Monos_Mutados))

  # Agregamos monos a las listas
  nuevos_monos.extend(iniciales)
  nuevos_monos.extend(Monos_Mutados)
  nuevos_monos.extend(Monos_Aleatorios)

  # Re-ordenamos aleatoriamente la lista, ya que en caso contrario no podrian pelear entre todos los monos
  ran.shuffle(nuevos_monos)

  return nuevos_monos

Mas información, en nuestro código al final...

Definición de monos y peleas

Una vez que ya sabemos de que tratara el juego, hay que llevar la narrativa a las matemáticas, por lo que tendremos que definir que será un mono y como serán las peleas entre ellos.

Cada mono tendrá distintos parámetros de identidad que nos ayudarán a conocer como fue la evolución que lo llevo hasta ahí y, de lucha, que serían los parámetros que los ayudan a pelear:

Parámetros de identidad:

Nombre
DNI
Generación
Nombre completo

Parámetros de lucha:

Fuerza
Agilidad
Inteligencia
Salud
Resistencia

Algo asi...


class Mono():

  # En un principio genera sus stats aleatoriamente
  def __init__(self,name="titi",stats = [0,0,0,0,0]):
    global semilla
    global DNI
    global Generacion

    self.name = name
    self.DNI = DNI
    DNI +=1
    self.generacion = Generacion
    self.nombre_Completo = name + "_" + str(Generacion) +"_" + str(DNI)

    if stats == [0,0,0,0,0]:
      for i in stats:
        stats[i] = ran.randint(1,100)

    # Nos aseguramos de que no hayan numeros negativos (pueden aparecer en las mutaciones)
    for i in range(0,5):
      if stats[i] < 0 : stats[i] = 0

    # Dividiendo por el total nos aseguramos de la suma de todos los stats de el mismo numero

    total = (stats[0] + stats[1] + stats[2] + stats[3] + stats[4])/100

    self.Fuerza = stats[0] / total
    self.Agilidad = stats[1] / total
    self.Inteligencia = stats[2] / total
    self.Salud = stats[3] / total
    self.Resistencia = stats[4] / total

Una vez que tenemos el mono, debemos definir una manera para que luchen, para eso definiremos primero lo que sera un golpe...

def golpe(Mono_Golpeador, Mono_Golpeado, turno, multiplicador = 1):
  # El daño que un mono le hace al otro depende tanto de las estadisticas de uno como las del otro
  Ataque_Mono_golpeador=(Mono_Golpeador.Fuerza*(Mono_Golpeador.Agilidad/100)*Multiplicador_Golpe(Mono_Golpeador)*(cansancio(Mono_Golpeador,turno,ataque="ataque"))-(Mono_Golpeado.Resistencia*(Mono_Golpeado.Inteligencia/100)))
  Defensa_Mono_golpeado=(Mono_Golpeado.Resistencia*(0.8*pow(Mono_Golpeado.Salud,1.8)/100))+(Mono_Golpeado.Inteligencia*(Mono_Golpeado.Agilidad/100))

  Daño = Ataque_Mono_golpeador - Defensa_Mono_golpeado

  # Necesitamos que los golpes sean positivos mayores a cero.
  if Daño < 7 : Daño = ran.randint(4,10)

  return Daño * multiplicador

Luego definiremos una pelea, la cual no es mas que muchos golpes seguidos hasta que uno palme...

def Peleas(mono_1 , mono_2,jugable=False,Titulo = " "):
  # Definimos la salud al principio de la pelea
  Vida_mono_1 = 100
  Vida_mono_2 = 100

  Turno = 1

  # Hacemos que se peguen hasta que alguno pierda toda la salud o se completen una cantidad de golpes maximos
  while Turno < Maximos_Turnos_por_pelea :
    Turno += 1
    # print(Turno)

    Vida_mono_1 = Vida_mono_1 - golpe(mono_2 , mono_1 , Turno)
    Vida_mono_2 = Vida_mono_2 - golpe(mono_1 , mono_2 , Turno)

    # Si es "jugable" le hacemos la animacion
    if jugable:On_Game(mono_1,mono_2,Vida_mono_1,Vida_mono_2,Titulo)

    # Una vez que uno pierde toda la salud, el ganador es el que mas salud tiene
    if (Vida_mono_1 <= 0 or Vida_mono_2 <= 0):  break

  # Revisamos quien gano la pelea
  if Vida_mono_1 >= Vida_mono_2:
    return mono_1

  else:
    return mono_2

Evaluación de resultados

Es importante saber si los monos realmente están evolucionando, con lo cual, debemos analizar los gráficos de las variables (stats) de cada generación en particular. Como pudimos ver, estos resultados convergen a unas stats especificas, lo que indica que encontró un optimo (se genera un límite imaginario impuesto por el mismo algoritmo).

Las primeras generaciones, al ser aleatorias, toman todo tipo de formas en su grafico

En cambio los monos de generaciones superiores como los siguientes (generación N°50) están más evolucionado que sus ancestros. de a poco van tomando formas, por mas que cada tanto aparece alguna forma extraña

Podiamos decir que en esta ocación, el algoritmo está buscando su óptimo para sobrevivir a generaciones futuras .

Los monos viven en la misma generación pero, no significa que en ellos se encuentren los mismos stats. Como podemos ver las gráficas, existen dos tipos de monos dentro de la misma generación, aquel que fue mutado poco y otro mutado mucho, significa que el porcentaje de variación de mutación de uno con el otro difiere.

Finalmente, podemos observar monos de generaciones futuras que han logrado converger a valores similares.

¿Final?

Antes de sacar esta publicación, presentamos en algunos lugares el juego y tuvo mejor recepción del que esperábamos, por lo que estamos pensando sacar "Monos y trompadas 2". La idea es experimentar (como absolutamente todo lo que hacemos en noAIData) y lanzarlo con un sistema de historias procedurales, con mas gráficos y muchas cosas más en alguna plataforma de videojuegos, y como siempre explicar los porqués en este blog así que, como dice el cliché, se vienen cositas...

Si querés estar al tanto de lo que hacemos, te invitamos a nuestro grupo de difusión de whatsapp, solamente lo usamos para contar nuevas publicaciones, no haremos spam ni seremos una molestia de todas las semanas.

Canal de difusion de whatsapp

Fuentes

- Repositorio de la Beta del juego

¿Necesitas ayuda?
Podes hacer preguntas aca abajo en los comentarios o en nuestros perfiles de linkedin que puedes encontrar en este link. Si estas buscando ayuda en proyectos grandes, nos podes contratar por medio de nuestra consultora haciendo click en este link . Hacemos ingenieria electromecanica, civil, desarrollo de software y varias cosas mas.

Buscar este blog

noAIData