PDF de programación - Desarrollo de un Jugador de GO Basado en Redes Neurales Evolutivas

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.

El juego de GO

• Tablero cuadrado de 5 a 19

intersecciones.
– Grupos
– Libertades
– Capturas
– Territorio

• Restricciones

– Interseccion vacia
– No jugada suicida
– Evitar KO

¿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.

Técnicas a explorar

• Algoritmo Evolutivo SANE.

Los individuos no son soluciones en si mismos, sino
parte de una solución. Población de neuronas y
población de redes... [Moriarty, Miikkulainen]

• 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.

Técnicas a explorar

• Fitness Sharing

Premia individuos que derroten a parásitos dominantes
aunque pierdan con el resto de los parásitos

• 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.

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

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

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

s
o
d
a
n
a
g


s
o
g
e
u

j




e
d
o
r
e
m
u
N

4

3

2

1

0

0

20

40

60

Generacion

80

100

120

Estudio de conexiones

Redes completamente conexas

s
o
d
a
n
a
g



s
o
g
e
u

j




e
d
o
r
e
m
u
N

4

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

Muestra
Muestra HOF

Población de neuronas
Población de redes
Neuronas Escondidas
Tamaño tablero

100
25
3

2000
200
100
5

200
25
3

2000
200
200
5

250
20
3

2000
200
250
9

500
20
3

2000
200
500
9

500A
20
3

4000
400
500
9

2000
20
3

20000
400
2000

9

Parámetros de Evoluciones

NeoGo

Nombre Corrida

343434

206020

666666

4012040

166166166

100300100

Muestra
Muestra HOF

Población de neuronas

startgame
midgame
endgame

Población de redes
Neuronas Escondidas

startgame
midgame
endgame

Tamaño tablero

25
3

990
330
330
330
200
99
33
33
33
5

25
3

1000
200
600
200
200
100
20
60
20
5

25
3

1980
660
660
660
200
198
66
66
66
5

25
3

2000
400
1200
400
200
200
40
120
40
5

25
3

4980
1660
1660
1660
400
498
166
166
166
9

25
3

5000
1000
3000
1000
400
500
100
300
100
9

Resultados de la evolución

CoCo100

s
o
d
a
n
a
g

s
o
g
e
u
j

o
r
e
m
ú
N

4

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

3

2

1

0

s
o
d
a
n
a
g

s
o
g
e
u

j


o
r
e
m
ú
N

0

20

40

60

80

100

Generacion

200 neuronas en la capa intermedia fuertemente conexa

Resultados de la evolución

NeoGo 343434



s
o
d
a
n
a
g

s
o
g
e
u

j


o
r
e
m
ú
N

4

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

NeoGo 206020



4

3

2

1

0

s
o
d
a
n
a
g

s
o
g
e
u

j


o
r
e
m
ú
N

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

NeoGo 666666



4

3

2

1

0

s
o
d
a
n
a
g

s
o
g
e
u

j


o
r
e
m
ú
N

0

20

40

60

80

100

Generacion

Resultados de la evolución

NeoGo 4012040



4

3

2

1

0

s
o
d
a
n
a
g

s
o
g
e
u

j


o
r
e
m
ú
N

0

20

40

60

80

100

Generacion

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?