Gpbot

#Artículo

##Objetivos

Determinar cual es el método de terminación del proceso de evolución que sea capaz de dar individuos capaces de ganar de forma consistente a otros contrincantes no vistos previamente y en una cantidad de tiempo mínima en un juego en el que el que la adecuación de un individuo se define en función de la victoria frente a otros individuos.

Los objetivos tienen que ser concretos y medibles: procedimiento que sea capaz de optimizar el tiempo de obtención de un bot súper guay.

##Hipótesis: El criterio de parada de un algoritmo ruidoso basado en combates afecta al rendimiento, debido a que la calidad del bot que se obtenga dependerá de si se ha parado o no en el momento adecuado. Creemos que criterios de parada que tardan más no tienen por qué crear necesariamente mejores individuos, por lo que se puede conseguir un ahorro de tiempo de cómputo significativo eligiendo condiciones de parada apropiadas, y, en todo caso, se puede buscar una condición de parada que minimice el tiempo de ejecución con unas mínimas condiciones.

hay que hablar de convergencia. Se trata de ver cuándo el algoritmo converge a una solución buena (la mejor, a ser posible). ¿Se podría pensar en un criterio de optimalidad total? Es decir, ¿que el mejor individuo obtenido sea el mejor posible? Puede que usando una función de score, para la que se sabrá el valor máximo, se pueda resolver esto.

##Dominio general: Proponer soluciones generales a la obención de bots en juegos usando métodos offline e inteligencia computacional.

##Dominio de la solución: Trabajaremos en RTS pero en principio podría aplicarse a cualquier juego en el que el resultado sea estocástico y dependiente de un combate. En este paper, nos centramos en el juego Planet Wars porque es un RTS simplificado (un sólo tipo de ataque, un sólo tipo de unidad, un sólo tipo de recurso).

###Técnicas de parada

Se proponen a estudio dos tipos de técnicas de parada: basadas en la población actual y basadas en el propio algoritmo evolutivo:

• Basadas en la población actual:
  • Estabilidad en la diversidad de la población.
  • Condiciones basadas en "enfrentamientos" contra contrincantes externos.
  • Basadas en la edad de la población (¿qué pasa con la edad? ¿Os vais a cargar a los viejos? ¿Y si son buenos? Yo lo quitaría). No lo de la edad de la población era para intentar parar si ya llevamos varias generaciones sin mejorar, es decir, si ya tenemos un buen individuo, para qué vamos a seguir si no estamos mejorando.
• Basadas en la ejecución del algoritmo:
  • Número de simulaciones realizadas. Esto o una medida de tiempo tendrá que ponerse eventualmente si no se alcanza estabilidad. No se van a tirar toda la vida. (Maribel: Si le pones tiempo ya no será el número de simulaciones realizadas, sino el tiempo de evolución no? Supongo que te refieres a que podemos hacer un número de generaciones (simulaciones) pero cada evaluación se limitará con un tiempo no?)
  • Estabilidad del resultado promedio de las batallas: Es decir, porcentaje de victorias del jugador 1 y 2. Al principio debe ser aleatorio pero a medida que la población mejora, al mejorar los individuos a su vez, la probabilidad de que gane un jugador u otro debe tender al 50% ya que ambos individuos deben ser iguales. Depende mucho de la población inicial, pero puede ser interesante. (Maribel: Esto no lo entiendo, no entiendo qué podamos parar cuando el porcentaje de victorias sea el 50% porque eso significa que no hay un claro ganador, pero quizás no lo he entendido bien.)
  • Individuos nuevamente generados que son introducidos en la población.

Basarse sólo en las victorias no será muy indicativo, por la poca variedad de resultados posibles. Yo aplicaría la función Score. Si el Score medio de la población no mejora en X generaciones, se termina. Para eso usaría rivales externos, pero si estáis pensando en Co-Evolución, entonces se miraría si el score medio de los ganadores mejora o no. (Maribel: Yo creo que mezclar aquí la coevolución no simplifica el paper ahora mismo. Yo dejaría la coevolución para más adelante, la verdad)

##Metodología

Se realizará un número significativo de ejecuciones de un algoritmo evolutivo (por decidir) donde se implementarán distintas técnicas de parada en el propio algoritmo. Es decir, para la ejecución A se tendrán distas condiciones de parada (todas las del estudio) y una que limite a las otras (por ejemplo, basada en tiempo total de ejecución).

Así para igualdad de condiciones (misma población inicial y demás) cada condición de parada determinará cuando considera que debe detenerse el algoritmo.

Así podemos definir dos métricas para el estudio: el tiempo de ejecución y la bondad del individuo.

Sería esperable que hubiese métodos que decidiesen parar el algoritmo en menos tiempo de ejecución frente a otros que requieran más tiempo.

Se realizaría por tanto un gráfica de 2-ejes, representando el tiempo y la bondad del individuo resultante, como se suele representar los algoritmos multiobjetivos.

(En un papel lo explico mejor).

###Experimentos

Una vez obtenidos las mejores poblaciones de cada ejecución según la condición de parada, se tienen que realizar dos tipos de experimentos:

####Experimentos sobre el tiempo:

Esto es sencillo, ver que método es más prematuro y cual requiere más tiempo de ejecución.

###Experimentos sobre la bondad:

Este se divide en dos partes: La selección del mejor individuo de la población y la métrica de bondad

Hay que usar un método con función de fitness, si no nos metemos en otro embolao. Decidir quien es el mejor individuo. De modo que si esto funciona o no funciona como se espera no se podría asegurar si es debido al criterio de parada o a la elección del mejor.

####Selección del mejor individuo de la población Como carecemos de fitness al terminar la población no tenemos un "mejor individuo". En el SuBot hemos realizado un enfrentamiento todos contra todos de la población. Podemos usar ese mismo mecanismo o emplear otro.

Como digo arriba, sí debería haber fitness. Yo voto por GPBot para los experimentos, que era nuestro estado del arte.

De hecho, sería interesante para otro artículo. Para este considero que sería demasiado follón.

Eso mismo

##Métricas ####Métrica de la bondad

Propongo emplear la función Score del Suvbot enfrentándolo a varios bots de la bibliografía.

####Métrica del tiempo Tiempo de ejecución, al ser la misma ejecución con los mismos parámetros del algoritmo (población inicial, probabilidades de cruce, etc.) y siendo el único elemento distinto el criterio de parada. El tiempo máximo será X, por lo que se normaliza de 0 a 1.

##Conclusiones El criterio de parada de un algoritmo ruidoso basado en combates afecta a las soluciones obtenidas (obviamente), pero debido a las razones (medibles) X, Y y Z.