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

UNIVERSIDAD CATÓLICA ANDRÉS BELLO

FACULTAD DE INGENIERÍA

ESCUELA DE INGENIERÍA INFORMÁTICA





DDDeeesssaaarrrrrrooollllllooo dddeee uuunnn jjjuuugggaaadddooorrr
aaarrrtttiiifffiiiccciiiaaalll dddeee GGOOO bbbaaasssaaadddooo eeennn
rrreeedddeeesss nnneeeuuurrraaallleeesss eeevvvooollluuutttiiivvvaaasss

G





TRABAJO ESPECIAL DE GRADO

presentado ante la

UNIVERSIDAD CATÓLICA ANDRÉS BELLO

como parte de los requisitos para optar al título de

I N G E N I E R O E N I N F O R M Á T I C A



REALIZADO POR:

Luján Toro, Alejandro.

PROFESOR GUIA:

Pereira, Wilmer.

FECHA:





Octubre de 2004.

Dedicatoria

A mis padres, por impulsar constantemente mi desarrollo personal

y profesional. Les debo todo lo que he logrado, lo que estoy

logrando y lo que lograré.

A Dani, porque junto a ti y gracias a ti estoy encontrando el camino

a la sabiduría infinita. Hoy es sólo el comienzo de una larga vida

juntos de retos y victorias.



i

Agradecimientos

A Alex Lubberts, cuya investigación fue parte importante de la

inspiración para este trabajo, y quien ofreció un valioso aporte en

las diferentes fases del proyecto.

A Alexis Hernández por ofrecer sus valiosísimos conocimientos en el

ámbito de GO y apoyar de forma entusiasta el proyecto desde su

inicio.

A Carola, por haberme apoyado en los momentos mas complicados

de este trabajo, y de mi carrera. Por siempre estar ahí, gracias

infinitas.

A mis compañeros de estudio y de trabajo, especialmente a Carlos,

Dennis, Guillermo y Hernán, quienes han sabido apoyarme y

compartir mis esfuerzos cuando lo he necesitado.





ii

Índice de contenidos

Dedicatoria ............................................................................. i

Agradecimientos..................................................................... ii

Índice de contenidos .............................................................. iii

Índice de tablas.....................................................................vii

Índice de figuras...................................................................viii

Resumen .............................................................................. ix

Capitulo I .............................................................................. 1

I.1 Introducción................................................................... 1

I.2 Planteamiento del problema ............................................. 2

I.3 Objetivos ....................................................................... 3

Objetivo general ............................................................... 3

Objetivos específicos ......................................................... 3

I.4 Limitaciones y alcances.................................................... 4

Capitulo II: Marco teórico ........................................................ 5

II.1 El juego de GO .............................................................. 5

Reglas de juego ................................................................ 6

Suicidio ........................................................................... 6

Regla de KO ..................................................................... 7

Fases del GO .................................................................... 7

II.2 Redes Neurales.............................................................. 9



iii

II.3 ¿Por qué redes neurales para GO?.................................. 11

II.4 Algoritmos Evolutivos ................................................... 12

II.5 SANE ......................................................................... 14

Evolución Simbiótica........................................................ 14

SANE: Poblaciones paralelas ............................................. 15

Coevolución competitiva................................................... 16

Fitness Sharing ............................................................... 18

Shared Sampling............................................................. 19

Hall of Fame ................................................................... 20

Algoritmo evolutivo definitivo............................................ 22

Capitulo III: Metodología ....................................................... 23

Capitulo IV: Desarrollo .......................................................... 24

IV.1 Investigación.............................................................. 24

IV.2 Decisiones de diseño ................................................... 24

Conexiones .................................................................... 24

Estructura a tres segmentos ............................................. 26

IV.3 Diseño....................................................................... 27

IV.4 Implementación .......................................................... 29

Paquete CoCoSane: ...................................................... 29

Paquete GoCoCoSane.................................................... 29

Paquete NeoGo ............................................................ 30

Paquete GO ................................................................. 30



iv

Detalles de implementación .............................................. 30

Pesos de las conexiones ................................................ 30

Selección de jugada: mejor jugada válida ........................ 30

Regla de KO ................................................................ 31

Sistema de Puntuación .................................................. 31

Configuración dinámica ................................................. 32

Protocolo de comunicación GTP ...................................... 33

IV.5 Corridas..................................................................... 33

IV.6 Pruebas ..................................................................... 35

Capitulo V: Resultados .......................................................... 36

V.1 Tablero 5x5 ................................................................. 36

CoCo_100 ...................................................................... 37

CoCo_200 ...................................................................... 38

Neo_343434................................................................... 39

Neo_206020................................................................... 40

Neo_666666................................................................... 41

Neo_4012040 ................................................................. 42

V.2 Tablero 9x9 ................................................................. 43

V.3 Estrategias desarrolladas............................................... 43

Ojos ........................................................................... 43

Separación de grupos ................................................... 43

Captura....................................................................... 44



v

Capitulo VI: Conclusiones y Recomendaciones .......................... 45

VI.1 Conclusiones .............................................................. 45

Tablero 9x9.................................................................... 45

Tablero 5x5.................................................................... 45

Cantidad de neuronas ................................................... 45

Estructura a tres segmentos .......................................... 45

Framework SANE.......................................................... 46

VI.2 Recomendaciones........................................................ 46

Paralelización............................................................... 46

Estructura a tres segmentos .......................................... 46

Particularización ........................................................... 47

Bibliografía .......................................................................... 49

Apéndice 1: Glosario de términos de GO .................................. 51

Apéndice 2: Juegos ............................................................... 54

Juego #1 .......................................................................... 55

Juego #2 .......................................................................... 56

Juego #3 .......................................................................... 57





vi

Índice de tablas

Tabla 4.1: Configuraciones de corridas evolutivas...................... 34







vii

Índice de figuras

Figura 2.1: Suicidio................................................................. 6

Figura 2.2: KO ....................................................................... 7

Figura 2.3: Red neural “feed forward”........................................ 9

Figura 2.4: Ojos ................................................................... 11

Figura 4.1: Evolución de redes con numero fijo de conexiones. ... 25

Figura 4.2: Evolución de redes completamente conexas. ............ 25

Figura 4.3 Resultados de corrida evolutiva utilizando puntuación de
GnuGo. ............................................................................... 32

Figura 4.4 Resultados de corrida evolutiva utilizando cálculo interno
de puntuación. ..................................................................... 32

Figura A1.1: Escalera ............................................................ 51

Figura A1.2: Ojos. ................................................................ 53





viii

Resumen

En este trabajo especial de grado se exploraron una serie de

técnicas del área de las redes neurales evolutivas, utilizando como

experimento la implementación de un jugador artificial de GO. Las

técnicas exp