Computadora Go

El primer programa de Go fue escrito por Albert Lindsey Zobrist en 1968 como parte de su tesis sobre reconocimiento de patrones . ^{[ 9 ]} Introdujo una función de influencia para estimar el territorio y el hash de Zobrist para detectar ko .

En abril de 1981, Jonathan K Millen publicó un artículo en Byte donde hablaba de Wally, un programa de Go con un tablero de 15x15 que cabía en la RAM de 1K del microordenador KIM-1 . ^{[ 10 ]} Bruce F. Webster publicó un artículo en la revista en noviembre de 1984 donde hablaba de un programa de Go que había escrito para el Apple Macintosh , incluyendo el código fuente MacFORTH . ^{[ 11 ]} Los programas de Go eran débiles; un artículo de 1983 estimó que, en el mejor de los casos, eran equivalentes a 20 kyu , la calificación de un jugador novato ingenuo, y a menudo se limitaban a tableros más pequeños. ^{[ 12 ]} Las IA que jugaban en el Internet Go Server (IGS) en tableros de 19x19 tenían una fuerza de alrededor de 20-15 kyu en 2003, después de mejoras sustanciales en el hardware. ^{[ 13 ]}

En 1998, jugadores muy fuertes lograron vencer a programas de computadora con hándicaps de 25 a 30 piedras, un hándicap enorme que pocos jugadores humanos aceptarían. Hubo un caso en el Campeonato Mundial de Go por Computadora de 1994 donde el programa ganador, Go Intellect, perdió las tres partidas contra los jugadores jóvenes con un hándicap de 15 piedras. ^{[ 14 ]} En general, los jugadores que comprendían y explotaban las debilidades de un programa podían ganar incluso con grandes hándicaps. ^{[ 15 ]}

En 2006 (con un artículo publicado en 2007), Rémi Coulom creó un nuevo algoritmo que denominó búsqueda en árbol de Monte Carlo . ^{[ 16 ]} En él, se crea un árbol de juego como de costumbre con futuros potenciales que se ramifican con cada movimiento. Sin embargo, las computadoras "puntúan" una hoja terminal del árbol mediante repetidas simulaciones aleatorias (similares a las estrategias de Monte Carlo para otros problemas). La ventaja es que dichas simulaciones aleatorias se pueden realizar muy rápidamente. La objeción intuitiva —que las simulaciones aleatorias no corresponden al valor real de una posición— resultó no ser tan fatal para el procedimiento como se esperaba; la parte de "búsqueda en árbol" del algoritmo se corrigió lo suficientemente bien como para encontrar árboles de juego futuros razonables para explorar. Los programas basados ​​en este método, como MoGo y Fuego, obtuvieron mejores resultados que las IA clásicas anteriores. Los mejores programas podían funcionar especialmente bien en el tablero pequeño de 9x9, que tenía menos posibilidades para explorar. En 2009, aparecieron los primeros programas de este tipo que podían alcanzar y mantener rangos bajos de nivel dan en el servidor KGS Go en el tablero de 19x19.

En 2010, en el Congreso Europeo de Go de 2010 en Finlandia, MogoTW jugó una partida de Go de 19x19 contra Catalin Taranu (5p). MogoTW recibió una ventaja de siete piedras y ganó. ^{[ 17 ]}

En 2011, Zen alcanzó el 5.º dan en el servidor KGS, jugando partidas de 15 segundos por movimiento. La cuenta que alcanzó ese rango utiliza una versión en clúster de Zen que se ejecuta en una máquina de 26 núcleos. ^{[ 18 ]}

En 2012, Zen venció a Takemiya Masaki (9p) por 11 puntos con un hándicap de cinco piedras, seguido de una victoria por 20 puntos con un hándicap de cuatro piedras. ^{[ 19 ]}

En 2013, Crazy Stone venció a Yoshio Ishida (9p) en una partida de 19×19 con un hándicap de cuatro piedras. ^{[ 20 ]}

El Codecentric Go Challenge de 2014, un encuentro al mejor de cinco partidas en un tablero par 19x19, se disputó entre Crazy Stone y Franz-Jozef Dickhut (6d). Ningún jugador más fuerte había aceptado antes jugar una competición seria contra un programa de go en igualdad de condiciones. Franz-Jozef Dickhut ganó, aunque Crazy Stone se impuso en la primera partida por 1,5 puntos. ^{[ 21 ]}

AlphaGo , desarrollado por Google DeepMind , representó un avance significativo en la potencia informática en comparación con los programas de Go anteriores. Utilizaba técnicas que combinaban el aprendizaje profundo y la búsqueda en árbol de Monte Carlo . ^{[ 22 ]} En octubre de 2015, derrotó a Fan Hui , el campeón europeo de Go, cinco veces de cinco en condiciones de torneo. ^{[ 23 ]} En marzo de 2016, AlphaGo venció a Lee Sedol en los tres primeros de cinco encuentros. ^{[ 24 ]} Esta fue la primera vez que un maestro de 9 dan jugó una partida profesional contra una computadora sin hándicap. ^{[ 25 ]} Lee ganó el cuarto encuentro, describiendo su victoria como "invaluable". ^{[ 26 ]} AlphaGo ganó el encuentro final dos días después. ^{[ 27 ] [ 28 ]} Con esta victoria, AlphaGo se convirtió en el primer programa en vencer a un profesional humano de 9 dan en una partida sin hándicap en un tablero de tamaño completo.

En mayo de 2017, AlphaGo venció a Ke Jie , quien en ese momento ocupaba el primer puesto en el ranking mundial, ^{[ 29 ] [ 30 ]} en un encuentro de tres partidas durante la Cumbre del Futuro del Go . ^{[ 31 ]}

En octubre de 2017, DeepMind reveló una nueva versión de AlphaGo, entrenada únicamente mediante autoaprendizaje, que había superado a todas las versiones anteriores, venciendo a la versión de Ke Jie en 89 de cada 100 partidas. ^{[ 32 ]}

Tras la publicación de los principios básicos de AlphaGo en la revista Nature , otros equipos lograron desarrollar programas de alto nivel. Desde entonces, el trabajo en IA para Go se ha centrado principalmente en emular las técnicas utilizadas para crear AlphaGo, que demostró ser muy superior a cualquier otro sistema. Para 2017, tanto Zen como el proyecto Fine Art de Tencent eran capaces de derrotar a profesionales de altísimo nivel en algunas ocasiones. También se creó el motor de código abierto Leela Zero .

Una técnica tradicional de IA para crear software de juegos es usar una búsqueda en árbol minimax . Esto implica ejecutar todos los movimientos hipotéticos en el tablero hasta cierto punto, y luego usar una función de evaluación para estimar el valor de esa posición para el jugador actual. Se selecciona el movimiento que conduce al mejor tablero hipotético, y el proceso se repite en cada turno. Si bien las búsquedas en árbol han sido muy efectivas en el ajedrez computarizado , han tenido menos éxito en los programas de Go computarizado. Esto se debe en parte a que tradicionalmente ha sido difícil crear una función de evaluación efectiva para un tablero de Go, y en parte a que la gran cantidad de movimientos posibles que cada bando puede realizar da como resultado un alto factor de ramificación . Esto hace que esta técnica sea muy costosa computacionalmente. Debido a esto, muchos programas que usan árboles de búsqueda extensamente solo pueden jugar en el tablero más pequeño de 9×9, en lugar de los completos de 19×19.

Existen varias técnicas que pueden mejorar considerablemente el rendimiento de los árboles de búsqueda en términos de velocidad y memoria. Las técnicas de poda, como la poda alfa-beta , la búsqueda de variación principal y MTD(f) , pueden reducir el factor de ramificación efectivo sin pérdida de fuerza. En áreas tácticas como la vida y la muerte, el Go es particularmente adecuado para técnicas de almacenamiento en caché, como las tablas de transposición . Estas pueden reducir la cantidad de esfuerzo repetitivo, especialmente cuando se combinan con un enfoque de profundización iterativa . Para almacenar rápidamente un tablero de Go de tamaño completo en una tabla de transposición, generalmente es necesaria una técnica de hash para resumir matemáticamente. El hash Zobrist es muy popular en los programas de Go porque tiene bajas tasas de colisión y se puede actualizar iterativamente en cada movimiento con solo dos XOR , en lugar de calcularse desde cero. Incluso utilizando estas técnicas de mejora del rendimiento, las búsquedas de árboles completos en un tablero de tamaño completo siguen siendo prohibitivamente lentas. Las búsquedas pueden acelerarse mediante el uso de técnicas de poda específicas del dominio, como no considerar movimientos donde el oponente ya tiene ventaja, y extensiones selectivas como considerar siempre los movimientos junto a grupos de piedras que están a punto de ser capturadas . Sin embargo, ambas opciones conllevan un riesgo significativo de no considerar un movimiento vital que habría cambiado el curso de la partida.

Los resultados de las competiciones informáticas demuestran que las técnicas de reconocimiento de patrones para seleccionar un conjunto de movimientos adecuados, combinadas con búsquedas tácticas rápidas y localizadas (explicadas anteriormente), fueron suficientes en su momento para crear un programa competitivo. Por ejemplo, GNU Go fue competitivo hasta 2008.

Los principiantes humanos suelen aprender de los registros de partidas antiguas jugadas por maestros. El trabajo en IA durante la década de 1990 a menudo implicaba intentar "enseñar" a la IA heurísticas de estilo humano sobre el conocimiento del Go. En 1996, Tim Klinger y David Mechner reconocieron la fortaleza de nivel principiante de las mejores IA y argumentaron que "creemos que con mejores herramientas para representar y mantener el conocimiento del Go, será posible desarrollar programas de Go más fuertes". ^{[ 34 ]} Propusieron dos maneras: reconocer configuraciones comunes de piedras y sus posiciones, y concentrarse en batallas locales. En 2001, un artículo concluyó que "los programas de Go todavía carecen tanto de calidad como de cantidad de conocimiento", y que solucionar esto mejoraría el rendimiento de la IA en Go. ^{[ 35 ]}

En teoría, el uso del conocimiento experto mejoraría el software de Go. Cientos de directrices y reglas prácticas para un juego sólido han sido formuladas tanto por aficionados de alto nivel como por profesionales. La tarea del programador consiste en tomar estas heurísticas , formalizarlas en código informático y utilizar algoritmos de coincidencia y reconocimiento de patrones para determinar cuándo se aplican estas reglas. También es importante poder "puntuar" estas heurísticas para que, cuando ofrezcan consejos contradictorios, el sistema pueda determinar cuál es más importante y aplicable a la situación. La mayoría de los resultados relativamente exitosos provienen de las habilidades individuales de los programadores en Go y de sus conjeturas personales sobre el juego, pero no de afirmaciones matemáticas formales; intentan que el ordenador imite su forma de jugar al Go. Los programas competitivos alrededor de 2001 podían contener entre 50 y 100 módulos que abordaban diferentes aspectos y estrategias del juego, como el joseki. ^{[ 35 ]}

Algunos ejemplos de programas que se han basado en gran medida en el conocimiento experto son Handtalk (más tarde conocido como Goemate), The Many Faces of Go, Go Intellect y Go++, cada uno de los cuales ha sido considerado en algún momento el mejor programa de Go del mundo. Sin embargo, estos métodos finalmente tuvieron rendimientos decrecientes y, en el mejor de los casos, nunca avanzaron más allá de un nivel intermedio en un tablero de tamaño completo. Un problema particular era la estrategia general del juego. Incluso si un sistema experto reconoce un patrón y sabe cómo jugar una escaramuza local, puede pasar por alto un problema estratégico más profundo que se avecina. El resultado es un programa cuya fuerza es menor que la suma de sus partes; si bien los movimientos pueden ser buenos desde un punto de vista táctico individual, el programa puede ser engañado y manipulado para ceder demasiado a cambio y encontrarse en una posición general perdedora. Como lo expresó la encuesta de 2001, "un solo mal movimiento puede arruinar una buena partida. El rendimiento del programa en una partida completa puede ser mucho menor que el nivel maestro". ^{[ 35 ]}

Una alternativa importante al uso de conocimiento y búsquedas codificadas manualmente es el uso de métodos de Monte Carlo . Esto se hace generando una lista de movimientos potenciales y, para cada movimiento, jugando miles de partidas aleatorias en el tablero resultante. El movimiento que conduce al mejor conjunto de partidas aleatorias para el jugador actual se elige como el mejor movimiento. No se requiere ningún sistema basado en conocimiento potencialmente falible. Sin embargo, debido a que los movimientos utilizados para la evaluación se generan aleatoriamente, es posible que un movimiento que sería excelente excepto por una respuesta específica del oponente se evalúe erróneamente como un buen movimiento. El resultado de esto son programas que son fuertes en un sentido estratégico general, pero imperfectos tácticamente. Este problema se puede mitigar agregando algo de conocimiento del dominio en la generación de movimientos y un mayor nivel de profundidad de búsqueda sobre la evolución aleatoria. Algunos programas que utilizan técnicas de Monte Carlo son Fuego, ^{[ 36 ]} The Many Faces of Go v12, ^{[ 37 ]} Leela, ^{[ 38 ]} MoGo, ^{[ 39 ]} Crazy Stone , MyGoFriend, ^{[ 40 ]} y Zen.

En 2006, se desarrolló una nueva técnica de búsqueda, límites de confianza superiores aplicados a árboles (UCT), ^{[ 41 ]} y se aplicó a muchos programas de Go Monte-Carlo 9x9 con excelentes resultados. UCT utiliza los resultados de las jugadas recopiladas hasta el momento para guiar la búsqueda a lo largo de las líneas de juego más exitosas, al tiempo que permite explorar líneas alternativas. La técnica UCT junto con muchas otras optimizaciones para jugar en el tablero más grande de 19x19 ha llevado a MoGo a convertirse en uno de los programas de investigación más fuertes. Las primeras aplicaciones exitosas de los métodos UCT al Go 19x19 incluyen MoGo, Crazy Stone y Mango. ^{[ 42 ]} MoGo ganó la Olimpiada de Computación de 2007 y ganó una (de tres) partida blitz contra Guo Juan, 5º Dan Pro, en el Go 9x9 mucho menos complejo. The Many Faces of Go ^{[ 43 ]} ganó la Olimpiada de Computación de 2008 después de agregar la búsqueda UCT a su motor tradicional basado en el conocimiento.

Los motores de Go basados ​​en el método de Montecarlo tienen fama de ser mucho más propensos a realizar tenuki (movimientos en otras partes del tablero) que a continuar una lucha local que los jugadores humanos. Esto se percibía a menudo como una debilidad en los inicios de estos programas. ^{[ 44 ]} Dicho esto, esta tendencia ha persistido en el estilo de juego de AlphaGo con resultados dominantes, por lo que podría tratarse más de una peculiaridad que de una debilidad. ^{[ 45 ]}

El nivel de habilidad de los sistemas basados ​​en el conocimiento está estrechamente ligado al conocimiento de sus programadores y expertos en el dominio correspondiente. Esta limitación ha dificultado la programación de IA verdaderamente robustas. Una alternativa es utilizar técnicas de aprendizaje automático . En estas, lo único que los programadores deben programar son las reglas y los algoritmos de puntuación simples para analizar el valor de una posición. El software, en teoría, generará automáticamente su propio análisis de patrones, heurísticas y estrategias.

Esto generalmente se logra permitiendo que una red neuronal o un algoritmo genético revise una gran base de datos de partidas profesionales, o que juegue muchas partidas contra sí mismo o contra otras personas o programas. Estos algoritmos pueden entonces usar estos datos para mejorar su rendimiento. Las técnicas de aprendizaje automático también se pueden usar en un contexto menos ambicioso para ajustar parámetros específicos de programas que dependen principalmente de otras técnicas. Por ejemplo, Crazy Stone aprende patrones de generación de movimientos a partir de varios cientos de partidas de muestra, utilizando una generalización del sistema de clasificación Elo . ^{[ 46 ]}

El ejemplo más famoso de este enfoque es AlphaGo, que demostró ser mucho más eficaz que las IA anteriores. En su primera versión, contaba con una capa que analizaba millones de posiciones existentes para determinar los movimientos más probables que merecían un análisis más profundo, y otra capa que intentaba optimizar sus propias probabilidades de ganar utilizando los movimientos probables sugeridos por la primera capa. AlphaGo utilizaba la búsqueda en árbol de Montecarlo para puntuar las posiciones resultantes. Una versión posterior de AlphaGo, AlphaGoZero, prescindió del aprendizaje a partir de partidas de Go existentes y, en su lugar, aprendió únicamente jugando contra sí misma repetidamente. Otros programas anteriores que utilizaban redes neuronales incluyen NeuroGo y WinHonte.

La primera competición de Go por ordenador fue patrocinada por Acornsoft , ^{[ 62 ]} y las primeras competiciones regulares por USENIX . Se celebraron entre 1984 y 1988. Estas competiciones introdujeron Nemesis, el primer programa competitivo de Go de Bruce Wilcox , y G2.5 de David Fotland, que más tarde evolucionaría en Cosmos y The Many Faces of Go.

Uno de los primeros impulsores de la investigación en Go computarizado fue el Premio Ing, un premio en metálico relativamente grande patrocinado por el banquero taiwanés Ing Chang-ki , que se ofrecía anualmente entre 1985 y 2000 en el Congreso Mundial de Go Computarizado (o Copa Ing). El ganador de este torneo podía desafiar a jugadores jóvenes con hándicap en una partida corta. Si la computadora ganaba la partida, se le otorgaba el premio y se anunciaba un nuevo premio: un premio mayor para quien venciera a los jugadores con un hándicap menor. La serie de premios Ing estaba programada para expirar 1) en el año 2000 o 2) cuando un programa pudiera vencer a un profesional de 1 dan sin hándicap por 40.000.000 de dólares taiwaneses . El último ganador fue Handtalk en 1997, quien se llevó 250.000 dólares taiwaneses por ganar una partida con hándicap de 11 piedras contra tres aficionados de 11 a 13 años con 2 a 6 dan. Cuando el premio expiró en 2000, el premio no reclamado era de 400.000 dólares NT por ganar un partido con hándicap de nueve piedras. ^{[ 63 ]}

Muchos otros grandes torneos regionales de Go ("congresos") incluían un evento de Go por computadora. El Congreso Europeo de Go ha patrocinado un torneo por computadora desde 1987, y el evento USENIX evolucionó hasta convertirse en el Campeonato de Go por Computadora de EE. UU./Norteamérica, que se celebró anualmente desde 1988 hasta 2000 en el Congreso de Go de EE. UU.

Japón comenzó a patrocinar competiciones de Go por ordenador en 1995. La Copa FOST se celebró anualmente entre 1995 y 1999 en Tokio. Este torneo fue sustituido por el Gifu Challenge, que se celebró anualmente entre 2003 y 2006 en Ogaki, Gifu. La Copa UEC de Go por Ordenador se celebra anualmente desde 2007.

Cuando dos ordenadores juegan al Go, lo ideal es tratar el juego como si fueran dos humanos, evitando cualquier intervención humana. Sin embargo, esto puede resultar difícil durante la fase final de la partida. El principal problema es que el software de Go, que normalmente se comunica mediante el Protocolo de Texto de Go (GTP), no siempre coincide en cuanto al estado de las piedras (vivas o muertas).

Aunque no existe una forma general para que dos programas diferentes "dialoguen" y resuelvan el conflicto, este problema se evita en gran medida utilizando las reglas chinas , de Tromp-Taylor o de la Asociación Americana de Go (AGA), en las que se requiere continuar el juego (sin penalización) hasta que no haya más desacuerdo sobre el estado de las piedras en el tablero. En la práctica, como en el servidor de Go KGS, el servidor puede mediar en una disputa enviando un comando GTP especial a los dos programas cliente indicándoles que deben continuar colocando piedras hasta que no haya dudas sobre el estado de ningún grupo en particular (todas las piedras muertas han sido capturadas). El servidor de Go CGOS suele ver que los programas se rinden antes de que una partida haya llegado a la fase de puntuación, pero aun así admite una versión modificada de las reglas de Tromp-Taylor que requiere que se juegue la partida completa.

Estas reglas implican que un programa que se encontraba en una posición ganadora al final del juego según las reglas japonesas (cuando ambos jugadores han pasado) podría, en teoría, perder debido a un mal juego en la fase de resolución, pero esto es muy improbable y se considera una parte normal del juego según todas las reglas de cada área.

El principal inconveniente del sistema anterior es que algunos conjuntos de reglas (como las reglas tradicionales japonesas) penalizan a los jugadores por realizar estos movimientos adicionales, lo que impide el uso de la opción de juego adicional para dos ordenadores. No obstante, la mayoría de los programas modernos de Go admiten las reglas japonesas contra humanos.

Históricamente, otro método para resolver este problema consistía en que un experto humano evaluara el tablero final. Sin embargo, esto introduce subjetividad en los resultados y el riesgo de que el experto pase por alto algo que el programa sí detectó.