El Cercado - Go y ordenadores
El Cercado

Wei Chi

 

Go y ordenadores


Introducción

    De todos los juegos de habilidad, el Go es, tras el Ajedrez, el que más recursos de investigación y programación ha acaparado. Y, sin embargo, los programas de Go tienen un nivel mucho más bajo que sus equivalentes en cualquier otro juego. Aunque en los últimos 15 años se han producido importantes avances, esos programas pueden ser vencidos por jugadores humanos de nivel moderado.

    Si bien los programas de Go comenzaron a aparecer en los años 60, su auge se inició a mediados de los 80, con el nacimiento del PC por una parte y con la celebración de torneos dotados de importantes premios, por otra. En este sentido, el millón de dólares ofrecido por la Fundación Ing al primer programa que venciera sin handicap a un jugador humano previamente designado (galardón que expiró en 2000 sin ganador), supuso un importante acicate.

    Los primeros torneos fueron dominados por programas taiwaneses como Dragon. Entre 1989 y 1991, el vencedor en los torneos fue Goliath, de Mark Boon, seguido de Go Intellect, de Ken Chen, y de los programas Handtalk y Goemate, de Chen Zhixing. En años más recientes, los ganadores han sido The Many Faces of Go, de David Fotland, el controvertido programa norcoreano KCC Igo y Go++, del británico Michael Reiss. En total, existen unos 10 programas de primer nivel, entre los que se hallan Haruka, Wulu, FunGo, Star of Poland y Jimmy, la mayoría de los cuales han sido distribuidos comercialmente. En un segundo escalón hay en torno a 30 programas de nivel medio, normalmente escritos por investigadores universitarios o por aficionados. Entre los programadores se cuentan muchos jugadores no profesionales de nivel medio y alto. Un fenómeno a reseñar también es la aparición de programas de código abierto, como GnuGo.

    Entre los hitos en la breve historia de los programas de Go cabe reseñar los siguientes: En 1991, Goliath ganó, por primera vez, la liguilla entre el vencedor de la Copa Ing y tres jóvenes jugadores humanos, tomando una ventaja de 17 piedras. Handtalk ganó las partidas con 15 y 13 piedras de ventaja en 1995 y la de 11 en 1997. Programas como Handtalk y Go++ han tenido cierto éxito en partidas de igualdad contra jugadores humanos cercanos al nivel de dan. Sin embargo, en partidas reiteradas contra un mismo programa (una vez el jugador descubre sus debilidades), un jugador experimentado sigue venciendo, incluso con más de 11 piedras de ventaja. La Nihon Ki-in concedió sucesivamente a Handtalk los diplomas de 5, 4 y 3 kyu tras vencer éste en la Copa FOST durante los años 1995-97. KCC Igo recibió el de 2 kyu tras sus éxitos de 1999.


Un poco de historia

    Según parece, el primer programa de Go fue escrito por D. Lefkovitz en 1960 y el primer artículo científico sobre el tema se debe a H. Remus; publicado en 1963, consideraba la posibilidad de aplicar el aprendizaje de máquina al juego del Go. El primer programa que venció a un jugador humano (su víctima era un principiante absoluto en aquel momento) fue creado en 1969 por A. Zobrist, quien introdujo ya una función de influencia y más tarde propondría otros conceptos que siguen siendo de aplicación en este ámbito. El paso siguiente corrió a cargo de J. Ryder, que en 1971 añadió consideraciones estratégicas y tácticas al software, así como un análisis sistemático de movimientos futuros.

    Los primeros programas de Go se basaban exclusivamente en una función de influencia: cada piedra irradia un efecto sobre las intersecciones que la rodean (las piedras negras irradian el valor opuesto al de las piedras blancas) y esa influencia decrece con la distancia. La mayor parte de los programas actuales sigue haciendo uso de alguna función similar (por ejemplo, en Go Intellect, la influencia es proporcional a 1/2distancia, mientras que en The Many Faces of Go, lo es a 1/distancia).

    El primer programa capaz de jugar mejor que un mero principiante fue diseñado en 1972 por Bruce Wilcox. Se denominaba Interim.2 y daba inicio a una nueva generación de programas que empleaban representaciones abstractas del tablero y razonaban sobre grupos. Wilcox dividía el tablero en zonas y razonaba en torno a ellas, una aproximación que también fue adoptada por Friedenbach. Wilcox rescribiría posteriormente Interim.2, convirtiéndolo en Nemesis, el primer programa comercial.

    De entre los sub-problemas a resolver en un programa de Go, hay que citar el algoritmo desarrollado por D. Benson en 1976, que establece inequívocamente la condición de vivo o muerto de un grupo dado. La etapa siguiente en la evolución consistió en el uso intensivo de patrones para reconocer situaciones y sugerir movimientos. El primer ejemplo en este sentido lo constituyó el programa Goliath, de Mark Boon (1990).

    Los programas actuales usan una combinación de todas esas técnicas y se basan en búsquedas tácticas rápidas y masivas, así como en análisis conceptuales de grupos e incluso búsquedas globales. Emplean tanto patrones como estructuras abstractas de datos. Las líneas de trabajo más novedosas exploran paradigmas tales como la teoría combinatoria de juegos, el aprendizaje de máquina y la modelización cognitiva.

    En definitiva y, a diferencia del Ajedrez (un problema matemático que, a fecha de hoy, casi se puede considerar resuelto), el Go representa actualmente un reto en el que caben diversas aproximaciones y que se ha convertido en terreno de experimentación ideal para las ciencias de la computación.


¿Dónde está el problema?

    Aunque es cierto que, hasta la fecha, los recursos dedicados al Ajedrez han sido, comparativamente, mucho mayores, los aplicados al Go permiten ya afirmar que se trata de un problema mucho más complejo. (Otra forma de expresarlo es decir que el ser humano es mejor jugando al Go que al Ajedrez, comparado con las máquinas.)

    La tabla siguiente presenta una comparativa del Go con otros juegos de premisas similares: dos jugadores, información completa (ambos jugadores conocen todas las posibles jugadas) y suma nula (el total de las ganancias es igual al total de las pérdidas al acabar la partida), siendo E la complejidad del espacio de estados (número de posiciones que es posible alcanzar desde la posición de partida) y A, la complejidad del árbol de juego (número de nodos del árbol mínimo necesario para resolverlo). Los símbolos '>', '>=' y '<<' significan, respectivamente, 'más fuerte que', 'más fuerte o parejo a' y 'claramente más débil que'. log10(X) representa el 'logaritmo decimal de X'.

 

JUEGO

log10(E)

log10(A)

Ordenador (O) frente a
jugador humano (H)

Damas

17

32

O > H

Otelo

30

58

O > H

Go 9 x 9

40

85

O << H

Ajedrez

50

123

O >= H

Go-Moku 15 x 15

100

80

Juego resuelto

Go 19 x 19

160

400

O << H

     
    En el caso del Ajedrez, con el que la comparación resulta inevitable, la siguiente tabla resume algunas de las características más relevantes a la hora de abordar la implementación de un programa de juego:

 

 

CARACTERISTICA

AJEDREZ

GO

1

Tamaño del tablero

8 x 8

19 x 19

2

Jugadas por partida

~80

~300

3

Factor de ramificación

Pequeño (~35)

Grande (~200)

4

Fin de partida y resultado

Jaque mate (definición simple; fácil de identificar)

Conteo del territorio (acuerdo entre jugadores; difícil de identificar)

5

Efectos a largo plazo

Las piezas pueden moverse a grandes distancias (ej. dama, torre, alfil)

Las piezas no se mueven; sus disposiciones tienen efectos a largo plazo (ej. escalera, vida/muerte)

6

Estado del tablero

Cambia rápidamente al mover las piezas

Cambia de forma incremental (excepto en las capturas)

7

Evaluación de la posición

Buena relación con el número y calidad de las piezas en el tablero

Escasa relación con el número de piezas en el tablero

8

Enfoques utilizados

Apto para árboles de búsqueda con buenos criterios de evaluación

Demasiados árboles para búsqueda por fuerza bruta; poda difícil por falta de buenos criterios de evaluación

9

Profundidad de búsqueda humana

Típicamente, hasta 10 jugadas

Los principiantes pueden visualizar hasta 60 jugadas. Búsquedas estrechas, pero profundas (ej. escaleras)

10

Efecto horizonte

Sólo a nivel de gran maestro

A nivel de principiante (ej. escaleras)

11

Procesos humanos de agrupamiento

Agrupación jerárquica

Las piezas pertenecen a muchos grupos a la vez

12

Sistema de ventajas

No existe

Buen sistema de ventajas

     
    El problema es que esa diferencia de 50 frente a 160 en el espacio de estados (y de 123 frente a 400 en el árbol de juego) es relevante tratándose de tiempo de cálculo. Se trata de logaritmos: ¡el número de posiciones a considerar es 10110 veces - un uno seguido de 110 ceros - mayor en el caso del Go! (Para dar una idea de la magnitud de esa cifra, baste considerar que han transcurrido menos de 1018 segundos desde el comienzo del universo y que Deep Blue, el programa que venció a Kasparov, calculaba 300 millones de posiciones por segundo, con lo que "apenas" llevaría analizadas 1026 de haber estado trabajando desde el Big Bang.) Como consecuencia de ello, el Go es especialmente rebelde a los métodos computacionales basados en la "fuerza bruta".

    Los programas de Ajedrez suelen emplear una búsqueda heurística junto a una técnica de evaluación. Los árboles de búsqueda se generan hasta una profundidad preestablecida y se hace una "poda" heurística basada en una función de mérito de la posición. El método funciona bien en Ajedrez porque el tamaño del tablero es suficientemente pequeño y el Ajedrez es más táctico que estratégico.

    La evaluación de una posición de Go presenta problemas nuevos. El Go tiene un carácter mucho más estratégico que el Ajedrez. A diferencia de éste, el Go no se centra en la captura de una única pieza. Las ventajas posicionales se van consiguiendo poco a poco, supeditadas al objetivo global de obtener más territorio que el oponente, y hay muchas maneras, directas e indirectas, de alcanzar ese objetivo: rodear territorio, crear áreas de influencia, atacar grupos enemigos débiles, asegurar grupos propios, destruir territorios del oponente... Una diferencia de una intersección en la ubicación de una única pieza puede afectar al estado - vivo o muerto - de grupos enteros y tener un enorme impacto sobre la puntuación resultante.

    Debido al gran tamaño del tablero, una partida de Go se compone de muchas escaramuzas locales. Si describimos el Ajedrez como una batalla, el Go representaría toda una guerra. Muchas jugadas tácticas buenas a nivel local deben competir, a la hora de ser seleccionadas, en un contexto de consideraciones estratégicas globales.

    Tomando el Ajedrez como referencia, los dos factores que, hoy por hoy, hacen del Go un problema intratable para los métodos computacionales clásicos son, pues:
     

    • El alto factor de ramificación
    • La enorme dificultad para establecer una función de evaluación fiable

    Curiosamente, hay que citar que, en 2002 y en el marco de su tesis doctoral, el holandés Erik van der Werf encontró la estrategia óptima para un tablero de 5 x 5.


Elementos de un programa de Go

    Los programas de Go actuales son, en esencia, sistemas expertos cuidadosamente ajustados, basados fundamentalmente en métodos heurísticos, búsquedas selectivas, reglas dictadas por la experiencia y algoritmos de reconocimiento de patrones. Los módulos que los constituyen son, conceptualmente, comunes a los de otros programas de juegos (en particular, a los de Ajedrez), si bien su implementación puede ser radicalmente distinta

Representación del tablero

    Típicamente, una matriz unidimensional o multidimensional registra en todo momento la situación actual del tablero. Aparte de consignar si una intersección está ocupada o no y por qué bando, se suele llevar la cuenta, para cada piedra, de la pertenencia real o potencial a un grupo, del número de libertades, del estado - vivo o muerto - del grupo en cuestión, etc. En el caso del Go, tiene especial importancia elegir si se mantiene un histórico de tales informaciones (lo que exige más memoria) o se recalculan cada vez (lo que requiere más tiempo).

Generador de jugadas

    Al igual que un jugador humano, los programas de Go generan jugadas candidatas empleando una combinación de criterios o basándose en una serie de objetivos (si es éste el enfoque adoptado). Por ejemplo, The Many Faces of Go genera jugadas que:
     

    • Ocupen los puntos estratégicos en la apertura (fuseki), siguiendo la práctica de los grandes maestros
    • Sigan las secuencias estándar de apertura (joseki) (para lo cual dispone de una biblioteca de tales aperturas)
    • Concuerden con patrones óptimos de forma (para lo cual alberga una biblioteca de patrones)
    • Favorezcan la vida de los grupos propios o cooperen a evitar la de algún grupo oponente
    • Estabilicen grupos propios o desestabilicen los del contrario
    • Defiendan un grupo propio o ataquen uno contrario
    • Sirvan como amenaza de ko
    • Amplíen o reduzcan territorios

    Casi todos los programas de Go, como los de Ajedrez, incluyen bibliotecas de aperturas. Pero, a diferencia de lo que sucede en estos últimos, las aperturas de Go dependen en gran medida de la posición global del tablero. Asimismo, el concepto exclusivo del Go de vida y muerte requiere normalmente un módulo específico capaz de procesarlo.

Evaluador

    Una vez generadas las jugadas candidatas, la decisión sobre cuál adoptar se suele tomar evaluando la posición resultante tras cada una de ellas y ordenando de menor a mayor el valor de esa configuración del tablero. En el caso del Go, la función de evaluación es uno de los puntos más conflictivos. Evaluar significa estimar, para cada intersección, la probabilidad de que se convierta en territorio propio o ajeno. Ello, entre otras cosas, requiere saber qué piedras están vivas y cuáles muertas, lo que, a su vez, exige conocer la conectividad de las piezas (no sólo si ya están conectadas o no, sino, mediante algún tipo de búsqueda rápida, cuántas jugadas harían falta para que llegasen a estar conectadas). Go++, por ejemplo, hace uso de probabilidades para determinar este punto. Seguidamente, el programa procede a analizar los ojos y el estado - vivo o muerto - de los grupos. Para las zonas del tablero todavía sin ocupar, se suele emplear una función de influencia, en la que las piedras existentes "irradian" un efecto decreciente sobre las intersecciones vecinas.

    En los programas modernos, la función de evaluación combina pues, la "evaluación concreta" - mediante la que se asignan puntos a las intersecciones del tablero en una posición dada - y la "evaluación conceptual" - que considera términos como conectividad, áreas de influencia, interacción, etc, más próximos a la forma de trabajar de un jugador humano.

Búsqueda en árbol

    Aparte de su factor de ramificación más elevado, el Go presenta, respecto al Ajedrez, un factor adicional que dificulta el problema: En Ajedrez, dada una posición de partida, la búsqueda en árbol da lugar a las posiciones finales que se evalúan de forma estática. En Go, llegados a una posición, la propia función de evaluación requiere a veces una búsqueda posterior para puntuar el resultado.

    De ahí la gran importancia de optimizar mediante estrategias de búsqueda, algoritmos de "poda", bases de datos de patrones, etc, un análisis que arrojaría tiempos de proceso inviables para que un programa sea capaz de jugar en tiempo real.


Nuevas líneas de investigación

    Se podría decir que, respecto a los ordenadores, el Go se encuentra hoy en una situación similar a la del Ajedrez en la década de 1960. Dista de ser un problema resuelto con los conocimientos y medios técnicos actuales y, por lo tanto, da pie a múltiples e interesantes aproximaciones, desde el recocido simulado a la teoría fractal, pasando por la lógica difusa. En particular, se ha convertido en reto y campo de experimentación para los estudiosos de la inteligencia artificial. Su carácter eminentemente visual (reconocimiento de formas) y su complejidad (árbol de posibilidades gigantesco), unidos a la paradójica simplicidad de sus elementos (piezas de un solo tipo y que no se mueven, a diferencia del Ajedrez) y a su escalabilidad (es posible emplear tableros de cualquier tamaño) permiten reproducir "en condiciones de laboratorio" algunos de los fascinantes procesos de la mente humana.

    En este ámbito cabe citar tres líneas de investigación actualmente en curso:
     

    • El aprendizaje máquina, basado en redes neuronales artificiales capaces de evolucionar su respuesta frente algunos de los problemas que plantea el juego (por ejemplo, el reconocimiento de formas). El principal experto en este apartado es Markus Enzenberger, autor del programa NeuroGo
    • La estrategia por objetivos, cuyo principal valedor es Steven Willmott
    • La teoría combinatoria de juegos, que descompone un juego en una suma de sub-juegos y trata de encontrar la jugada óptima en cada uno de ellos para, a partir de ahí, encontrar la mejor jugada global. El líder en este campo es Martin Müller, creador del programa Explorer


Programas existentes

    Sin pretender ser exhaustiva, se incluye a continuación una lista de los principales programas de Go existentes en la actualidad, agrupados en tres categorías:
     

    • Programas comerciales. Programas a la venta, generalmente dotados de numerosas características de juego y resolución de problemas. Todos ellos juegan, al menos, en tablero de 19 x 19
       
    • Programas gratuitos y experimentales. Software en versión limitada (tamaño de tablero o prestaciones) o creado por investigadores de nuevos conceptos aplicables al juego y puesto a disposición del público
       
    • Applets. Programas "incrustados" en páginas web, contra los que es posible jugar sin que requieran instalación alguna.

    En Computer-go.info se puede encontrar una lista de todos los programas existentes.


Recursos en Internet

anteriorsubir 1 nivelsiguiente © 2004 Luis E. Juan Powered by Interspire.com