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/2^distancia, 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, 'mucho más fuerte que', 'más fuerte que' y 'más fuerte o parejo a'. La expresión log₁₀(X) representa el 'logaritmo decimal de X'.

 
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:

 
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) sí es relevante tratándose de tiempo de cálculo. Se trata de logaritmos: ¡el número de posiciones a considerar es 10¹¹⁰ 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 10¹⁸ 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 10²⁶ 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

Como curiosidad citaremos 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.

Líneas de investigación

El Go 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 habituales:
 

• 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).
• La estrategia por objetivos
• 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 Fuego

Estado actual

En marzo de 2016, el programa de inteligencia artificial AlphaGo, desarrollado por Google DeepMind, logró derrotar por 4-1 al coreano Lee Sedol, jugador profesional de Go y campeón del mundo en varias ocasiones.

Deepmind utilizó para AlphaGo un algoritmo basado en redes neuronales, que combinaba tres técnicas distintas de inteligencia artificial. En primer lugar, el aprendizaje profundo, basado en la acumulación de cantidades masivas de información sobre las que reconocer patrones: en este caso, se trató de 160.000 partidas reales. En segundo lugar, el aprendizaje por refuerzo: hacer que la máquina juegue contra sí misma para aprender ejercitándose. Finalmente, se utilizó un árbol de búsqueda de tipo Monte Carlo para seleccionar aleatoriamente las variantes más prometedoras.

Posteriormente, DeepMind ha ido lanzando sucesivas versiones del algoritmo utilizado en AlphaGo: AlphaGo Zero (2017), AlphaZero (2018) y, finalmente, MuZero (2020), en las que progresivamente se ha eliminado el conocimiento humano embebido en el programa, hasta obtener una especie de 'jugador artificial universal', capaz de aprender a jugar (y a dominar) cualquier juego, sin conocer siquiera de forma previa sus reglas.

Programas existentes

Sin pretender ser exhaustiva, se incluye a continuación una lista de los principales programas de Go 'convencionales' 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

Intelligent Go Foundation. Organización dedicada a la promoción del Go por ordenador

The Computer Go Ladder. Campeonato permanente entre programas de Go. Contiene también enlaces con las webs de los principales expertos.

Computer Go Bibliography. La mayor colección de artículos y libros sobre Go y ordenadores. Mantenida por Markus Enzenberger.

Computer-go.info. Una web reciente con todo tipo de información sobre el tema.

BGA Software Catalogue. Biblioteca de programas de Go de la British Go Association.

Senseis's Library: Computer Go. El apartado dedicado al asunto en la popular biblioteca.

UA Games Group. Departamento de Juegos de la Universidad canadiense de Alberta, una de las más activas en implementación de juegos por ordenador.

DeepMind. La empresa de software puntera en inteligencia artificial, aplicada al juego del Go.

Wikipedia. El artículo dedicado al go por ordenador en la famosa enciclopedia.

SGF File Format. Todo sobre el Smart Game Format empleado para almacenar las partidas de Go.