Desarrollo de un Jugador de GO Basado
en Redes Neurales Evolutivas.
Prof. Alejandro Luján
Prof. Wilmer Pereira
Universidad Catolica Andres Bello
Contenido de la Exposición
• Introducción
• Objetivos
• El juego de GO
• ¿Por qué Redes Neurales para GO?
• Técnicas a explorar
• Diseño
– Estructura a tres segmentos
– Diseño de conexiones neurales (fuertemente conexa)
Contenido de la Exposición
• Resultados
– Detalles de las corridas evolutivas
– Resultados de las evoluciones
– Análisis de las estrategias desarrolladas
• Conclusiones
• Recomendaciones
• Segmento de preguntas
Introducción
• La Inteligencia Artificial se ha utilizado en juegos
como ajedrez por su complejidad.
• Se desean explorar técnicas relacionadas con
las Redes Neurales Artificiales y los Algoritmos
Evolutivos.
• Se observan precedentes en el uso de estas
técnicas en tareas similares al GO.
Objetivos
• Diseñar un prototipo de Red Neural capaz de
jugar GO.
• Determinar un mecanismo evolutivo que permita
obtener mejores redes.
• Implementar este mecanismo.
• Evaluar las redes con jugadores externos.
• Analizar resultados de las evaluaciones.
Redes Neurales Artificiales
Unidades enlazadas a través de conexiones
cargadas por pesos numéricos
El aprendizaje se basa en la actualización de esos pesos que se
inicializan en la fase de entrenamiento de la red
Está formada por unidades de entrada y unidades de salida
(neuronas de entrada y neuronas de salida)
El nivel de activación de la neurona artificial (equivalente al
impulso excitatorio) es un cálculo individual en cada neurona,
sin control global
Se tiene una fase de aprendizaje, con ejemplos conocidos,
una de prueba con otros ejemplos y finalemente la puesta en
ejecucion
Redes neurales evolutivas
• Algoritmo Evolutivo SANE.
Los individuos no son soluciones en si mismos, sino
parte de una solución. Población de neuronas PN y
población de redes PR... [Moriarty, Miikkulainen]
1. Limpiar fitness de cada neurona y red de poblaciones
2. Seleccionar N neuronas de PN para una red de PR
3. Crear una red neural con las neuronas seleccionadas
4. Evaluar la red para la tarea
5. Asignar fitness de la red segun la evaluación
6. Repetir los pasos de 2 a 5 para cada individuo de PR
7. Asignar a cada neurona el fitness de las mejores 5 redes en las que participó
8. Realizar mutación y cruce a ambas poblaciones (PR yPN)
Coevolucion competitiva
• Coevolución Competitiva:
Evolucionar dos poblaciones paralelas que se enfrenten
mutuamente elevando su nivel (host y parásitos que se
intercambian los roles) [Rosin, Belew]
• Shared Sampling
Selecciona una muestra representativa, que reúna todas las
habilidades, de los parásitos.
• Fitness Sharing
–Premia individuos que derroten a parásitos dominantes aunque
pierdan con el resto de los parásitos (Fi = Σ(i,O) 1 / Nj) donde O es
el número de oponentes derrotados y Nj cantidad de derrotas de j
• Hall of Fame
Utiliza los mejores individuos de poblaciones anteriores como parte
de la muestra de evaluación, con el fin de perpetuar sus
habilidades.
Algoritmo shared sampling
Para cada oponente O de la generación anterior
o.golpe=0
Para i=0 hasta N (Tamaño de la muestra)
Para cada parásito P que no esté en la muestra
p.sample_fitness=0
Para cada oponente O derrotado por P
P.sample_fitness+=1/1+O.golpe
P2=oponente con máximo fitness
Agregar P2 a la muestra
Para cada oponente O de la generación anterior
Si P2 derrotó a O entonces O.golpe++
SANE + Coevolucion
Competitiva
En vez de evaluar con un humano o un sistema preexistente
(se estancaría y adaptaría a sólo ganar a ese contrincante) se
se evalua con una competencia entre dos poblaciones que
evolucionen en paralelo
Se combinan el algoritmo de redes neurales evolutivas con las
estrategias competitivas para obtener una mejora permanente
Algoritmo definitivo
1. Limpiar fitness de cada neurona y red de poblaciones
2. Seleccionar R de la poblacion PR
3. Seleccionar N oponentes de la población parásito,
utilizando Shared Sampling
4. Seleccionar M oponentes del Hall of Fame
5. Evaluar la red contra los N+M oponentes
6. Asignar fitness de la red R utilizando Fitness Sharing
7. Repetir los pasos de 2 a 6 para cada individuo de PR
8. Agregar el mejor individuo de PR al Hall of Fame
9. Asignar a cada neurona el fitness de las mejores 5
redes en las que participo
10. Realizar cruce y mutación en ambas poblaciones
El juego de GO
• Tablero cuadrado de 5 a 19
intersecciones.
– Grupos
– Libertades
– Capturas (ocupa ultimo grado de
libertad)
– Territorio (conteo de espacio menos
las piezas capturadas)
• Restricciones
– Interseccion vacia
– No jugada suicida
– Evitar KO
Fases del juego
Fuseki: Esboza las estrategias con contacto minimo entre los
grupos
Medio Juego: Se establecen batalals de vida o muerte por la
zonas del fuseki
Yose: fase terminal donde se cierran los ultimos grupos y se
demarca el territorio
Consideraciones importantes:
Jugadas elasticas son muy alejadas del grupo (osadas pero
arriesgadas) se debe ser elastico para conquistar territorios
Buscar patrones con al menos 2 ojos es importante
¿Por qué RN para GO?
• Han demostrado habilidades en
análisis de patrones. El GO se
basa en patrones:
– Figuras ofensivas, defensivas
– Figuras fuertes, débiles
– Ejemplo de patrón: Ojos
• Capacidad de solucion en
problemas no algorítmicos o con
complejidad inmanejable.
Diseño
• Tableros: tamaños 5x5 y 9x9
• Entradas: dos entradas por cada intersección,
indicando si esta ocupada por blanco o por
negro.
• Salidas: una para cada intersección. El valor
real de salida indica que tan conveniente es
jugar en esta intersección.
• Cantidad de neuronas: 500 neuronas para 9x9,
100 neuronas para 5x5.
Diseño
Aportes adicionales
• Organización de neuronas escondidas
– Capa escondida de forma tradicional
– Estructura a tres segmentos
• Conexiones: cada neurona de entrada está
conectada con todas las escondidas.
Las
neuronas escondidas tienen conexión con todas
las de salida.
Estructura a tres segmentos
• Fases del juego de GO:
– Fuseki
– Medio Juego
– Yose
• Cada segmento está activo en la etapa
correspondiente del juego.
• El paso a la próxima fase está definido por la
densidad del tablero.
• La función de evaluación es la de GNUGo y
protocolo GTP
Estructura a tres segmentos
Estudio de conexiones
• Otros trabajos manejan neuronas escondidas
con un número fijo de conexiones (~16%)
• ¿Por qué no tener redes completamente
conexas en la capa intermedia?
Estudio de conexiones
Numero fijo de conexiones
4
Numerode juegos ganados
3
2
1
0
0
20
40
60
Generacion
80
100
120
Estudio de conexiones
Redes completamente conexas
4
Numerode juegos ganados
3
2
1
0
0
20
40
60
Generacion
80
100
120
Implementación
• Partiendo de SANE 2.0, éste se reescribe,
corrige y rediseña.
• Se realizan evoluciones de 100 generaciones.
• Torneo cada generación: GnuGO contra las 4
mejores redes.
• Tiempos de corridas: desde 6 horas hasta 12
días.
Parámetros de Evoluciones
CoCoSane
Nombre Corrida
100
200
250
500
500A
2000
Muestra de parasitos
25
25
20
20
20
20
Muestra Hall Of Fame
3
3
3
3
3
3
Población de neuronas
2000 2000 2000 2000 4000
Población de redes
200
200
200
200
400
400
Neuronas Escondidas
100
200
250
500
500
2000
5
5
9
9
9
9
Tamaño tablero
20000
Parámetros de Evoluciones
NeoGo
Nombre Corrida
343434
206020
666666
4012040
166166166
100300100
Muestra parasitos
25
25
25
25
25
25
Muestra HOF
3
3
3
3
3
3
990
1000
1980
2000
4980
5000
startgame
330
200
660
400
1660
1000
midgame
330
600
660
1200
1660
3000
endgame
330
200
660
400
1660
1000
Población de redes
200
200
200
200
400
400
Neuronas Escondidas
99
100
198
200
498
500
startgame
33
20
66
40
166
100
midgame
33
60
66
120
166
300
endgame
33
20
66
40
166
100
5
5
5
5
9
9
Población de neuronas
Tamaño tablero
Resultados de la evolución
CoCo100
4
Númerojuegosganados
3
2
1
0
0
20
40
60
80
100
Generacion
100 neuronas en la capa intermedia fuertemente conexa
Resultados de la evolución
CoCo200
4
Númerojuegosganados
3
2
1
0
0
20
40
60
80
100
Generacion
200 neuronas en la capa intermedia fuertemente conexa
Resultados de la evolución
NeoG
o343434
4
Númerojuegosganados
3
2
1
0
0
20
40
60
80
100
Generacion
34 neuronas en cada capa de las fases de juego: fuseki, medio juego y
Resultados de la evolución
NeoG
o206020
4
Númerojuegosganados
3
2
1
0
0
20
40
60
80
100
Generacion
20, 60 y 20 neuronas en cada capa de las fases del juego
Resultados de la evolución
NeoG
o666666
4
Númerojuegosganados
3
2
1
0
0
20
40
60
Generacion
80
100
Resultados de la evolución
NeoG
o4012040
4
Númerojuegosganados
3
2
1
0
0
20
40
60
Generacion
80
100
Estrategias Desarrolladas
• Ojos: en muchos juegos se evidencia la
formación de ojos para la supervivencia de los
grupos.
• Separación de grupos del oponente.
• Captura: las redes parecen demostrar ciertas
habilidades en luchas vida o muerte.
Conclusiones
• Tableros 9x9: dadas las condiciones del
experimento, no se observaron evidencias de
aprendizaje.
• Tableros 5x5: SANE demuestra ser efectivo en
el ámbito del GO, al ser combinado con las
técnicas mencionadas.
• El aumento en la cantidad de neuronas en la
capa intermedia no parece aportar beneficios al
aprendizaje.
Conclusiones
• La estructura a tres segmentos no ofreció una
mejora en el proceso de aprendizaje, aunque
mantiene la tendencia de avance de la
estructura tradicional.
• Se obtuvo exitosamente un framework que
contiene una serie de clases, escritas en java,
que facilitan la implementación de Coevolución
Competitiva SANE para otros dominios.
Recomendaciones
• Paralelizar el proceso evolutivo, dada la carga
de procesamiento que esta exige.
• Utilizar una estrategia de cálculo de fitness
adecuada a la estructura de tres segmentos,
que evalúe cada segmento por separado.
• Neuronas de paso mas sofisticadas.
• Seguir ahondando en particularizaciones de las
Redes Neurales
¿Dudas?
¿Preguntas?
Descargar

Desarrollo de un Jugador de GO Basado en Redes Neurales