Upload
pablo-garcia
View
1.537
Download
1
Embed Size (px)
Citation preview
Optimización evolutiva de bots para el juego Planet Wars
A. Fernández-Ares, A.M. Mora, J.J. Merelo,P. García-Sánchez, y C.M. Fernandes
viernes 10 de febrero de 2012
Índice
Introducción
Descripción del problema
Baseline: GoogleBot
Primera aproximación: AresBot
Segunda aproximación: GeneBot
Conclusiones
viernes 10 de febrero de 2012
Introducción
Google AI Challenge
Planet Wars
viernes 10 de febrero de 2012
viernes 10 de febrero de 2012
Descripción del problema
Restricciones
RTS->Juego basado en turnos. 1 turno = 1 sec
No se puede usar memoria para guardar estado del juego
Estado actual: planetas y flotas
Acciones: un archivo de texto con acciones leído por el juego
Estado actual
Bot Acciones a realizar
viernes 10 de febrero de 2012
Baseline: GoogleBot
Incluido en el kit como base de comparación
Cómo funciona:
Busca el planeta que contiene más naves (base)
El planeta objetivo se calcula usando la relación entre la tasa de crecimiento y el número de naves
Espera hasta que la flota llegue al planeta
viernes 10 de febrero de 2012
Primera versión: AresBot
En cada turno:
Selecciona la base de acuerdo a una puntuación (el resto se denominan colonias)
Seleccionar un planeta objetivo a atacar
Por cada colonia:
Reforzar la base (tithe) ó
Ayudar al ataque
viernes 10 de febrero de 2012
Parámetros de AresBot
titheperc y titheprob: porcentaje de naves que el bot envía a la base/probabilidad de que ocurra.
ωNS−DIS y ωGR: pesos del número de naves y distancia y tasa de crecimiento (usada en la función de puntuación para planeta objetivo)
poolperc y supportperc: porcentaje de naves que el bot envía desde la base o colonias al planeta objetivo.
supportprob: probabilidad de enviar naves extra desde las colonias al planeta objetivo
viernes 10 de febrero de 2012
Operation GeneBot
Usando técnicas intergalácticas (un GA) se mejora a AresBot para crear al poderoso GeneBot.
Gen: array de parámetros
2-Tournament
BLX-alpha crossover
Re-evaluación
viernes 10 de febrero de 2012
Función Fitness
Cada individuo se enfrenta a GoogleBot en 5 mapas distintos
Un individuo es mejor que otro si:
Gana en más mapas
Necesita menos turnos, en caso de empate
viernes 10 de febrero de 2012
Experimentos
Población de 200 individuos, 100 generaciones
40 segundos para evaluar cada uno, por lo que cada ejecución dura dos días. ->(sí, paralelismo en el futuro...)
Se obtuvieron 15 bots distintos
viernes 10 de febrero de 2012
Resultados
titheperc titheprob ωNS−DIS ωGR poolperc supportperc supportprob
AresBot 0,1 0,5 1 1 0,25 0,5 0,9
GeneBot 0,0179 0,00823 0,50954 0,23273 0,73321 0,58946 0,97405
Media 0,17386 0,09702 0,47252 0,36409 0,65732 0,59987 0,59987
viernes 10 de febrero de 2012
viernes 10 de febrero de 2012
viernes 10 de febrero de 2012
viernes 10 de febrero de 2012
viernes 10 de febrero de 2012
viernes 10 de febrero de 2012
Conclusiones y Trabajo futuro
El primer GeneBot terminó en la posición 1454 en la competición (36%), pero sólo se ejecutó una vez para conseguirlo. 1000 posiciones mejor que AresBot
El fitness define bien al individuo
Más cosas que hacer:
Paralelismo (obviamente)
Multi-objetivo
Co-evolución
Programación genética
Parar cuando el bot tenga conciencia propia, claro.
viernes 10 de febrero de 2012
¡Gracias! (y preguntas, me temo)
viernes 10 de febrero de 2012