El Go informático es el campo de la inteligencia artificial (IA) dedicado a crear un programa informático que juegue al tradicional juego de mesa Go . El campo está claramente dividido en dos eras. Antes de 2015, los programas de la época eran débiles. Los mejores esfuerzos de los años 1980 y 1990 produjeron solo IA que podían ser derrotadas por principiantes, y las IA de principios de la década de 2000 eran de nivel intermedio en el mejor de los casos. Los profesionales podían derrotar a estos programas incluso con handicaps de 10+ piedras a favor de la IA. Muchos de los algoritmos como alpha-beta minimax que funcionaron bien como IA para damas y ajedrez se desmoronaron en el tablero de 19x19 de Go, ya que había demasiadas posibilidades de ramificación para considerar. La creación de un programa de calidad profesional humana con las técnicas y el hardware de la época estaba fuera de alcance. Algunos investigadores de IA especularon que el problema era irresoluble sin la creación de una IA similar a la humana .
La aplicación de la búsqueda de árbol de Monte Carlo a los algoritmos de Go proporcionó una mejora notable a fines de la década de 2000 , con programas finalmente capaces de alcanzar un nivel de dan bajo : el de un aficionado avanzado. Los aficionados y profesionales de alto dan aún podían explotar las debilidades de estos programas y ganar de manera consistente, pero el rendimiento de la computadora había avanzado más allá del nivel intermedio ( kyu de un solo dígito ). El tentador objetivo incumplido de derrotar a los mejores jugadores humanos sin un hándicap, que durante mucho tiempo se creyó inalcanzable, provocó una explosión de renovado interés. La idea clave resultó ser una aplicación del aprendizaje automático y el aprendizaje profundo . DeepMind , una adquisición de Google dedicada a la investigación de IA, produjo AlphaGo en 2015 y lo anunció al mundo en 2016. AlphaGo derrotó a Lee Sedol , un profesional de 9 dan, en un partido sin hándicap en 2016, luego derrotó a Ke Jie en 2017 , quien en ese momento mantuvo continuamente el ranking mundial No. 1 durante dos años. De la misma forma que las damas habían caído ante las máquinas en 1995 y el ajedrez en 1997 , los programas informáticos finalmente conquistaron a los mayores campeones de Go de la humanidad en 2016-2017. DeepMind no lanzó AlphaGo para uso público, pero desde entonces se han creado varios programas basados en los artículos de revistas que DeepMind publicó que describen AlphaGo y sus variantes.
Los jugadores profesionales de Go consideran que el juego requiere intuición, pensamiento creativo y estratégico. [1] [2] Durante mucho tiempo se ha considerado un desafío difícil en el campo de la inteligencia artificial (IA) y es considerablemente más difícil de resolver que el ajedrez . [3] Muchos en el campo consideraron que el Go requiere más elementos que imitan el pensamiento humano que el ajedrez. [4] El matemático IJ Good escribió en 1965: [5]
¿Go en un ordenador? – Para programar un ordenador para que juegue una partida razonable de Go, en lugar de una partida meramente legal, es necesario formalizar los principios de una buena estrategia o diseñar un programa de aprendizaje. Los principios son más cualitativos y misteriosos que en el ajedrez, y dependen más del criterio. Por eso creo que será aún más difícil programar un ordenador para que juegue una partida razonable de Go que de ajedrez.
Antes de 2015, los mejores programas de Go solo conseguían alcanzar el nivel de dan amateur . [6] [7] En el pequeño tablero de 9x9, la computadora se desempeñaba mejor y algunos programas lograron ganar una fracción de sus partidas de 9x9 contra jugadores profesionales. Antes de AlphaGo, algunos investigadores habían afirmado que las computadoras nunca derrotarían a los mejores humanos en Go. [8]
El primer programa 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 Zobrist para detectar ko .
En abril de 1981, Jonathan K Millen publicó un artículo en Byte en el que se hablaba de Wally, un programa de Go con una placa de 15x15 que encajaba en la memoria RAM de 1K del microordenador KIM-1 . [10] Bruce F. Webster publicó un artículo en la revista en noviembre de 1984 en el que se hablaba de un programa de Go que había escrito para Apple Macintosh , incluida la fuente de MacFORTH . [11] Los programas para 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 placas más pequeñas. [12] Las IA que jugaban en el servidor de Go de Internet (IGS) en placas de tamaño 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 fueron capaces de vencer a programas informáticos con hándicaps de 25 a 30 piedras, un hándicap enorme que pocos jugadores humanos podrían aceptar. Hubo un caso en el Campeonato Mundial de Go por Computadora de 1994 en el que 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 hándicaps altos. [15]
En 2006 (con un artículo publicado en 2007), Rémi Coulom produjo un nuevo algoritmo al que llamó Monte Carlo tree search . [16] En él, se crea un árbol de juego como siempre de futuros potenciales que se ramifican con cada movimiento. Sin embargo, las computadoras "puntúan" una hoja terminal del árbol mediante repetidas jugadas aleatorias (similar a las estrategias de Monte Carlo para otros problemas). La ventaja es que tales jugadas aleatorias se pueden hacer muy rápidamente. La objeción intuitiva - que las jugadas aleatorias no corresponden al valor real de una posición - resultó no ser tan fatal para el procedimiento como se esperaba; el lado de "búsqueda de árbol" del algoritmo 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 un mejor rendimiento que las IA clásicas de antes. Los mejores programas podían hacerlo especialmente bien en el pequeño tablero 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 de nivel dan bajo en el servidor KGS Go en el tablero 19x19.
En 2010, en el Congreso Europeo de Go de 2010 en Finlandia, MogoTW jugó al Go 19x19 contra Catalin Taranu (5p). MogoTW recibió un hándicap 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 por una victoria de 20 puntos con un hándicap de cuatro piedras. [19]
En 2013, Crazy Stone venció a Yoshio Ishida (9p) en un juego de 19×19 con un hándicap de cuatro piedras. [20]
El Codecentric Go Challenge 2014, una partida al mejor de cinco en un formato de 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 ganó la primera partida por 1,5 puntos. [21]
AlphaGo , desarrollado por Google DeepMind , fue un avance significativo en la fortaleza de la computadora en comparación con los programas Go anteriores. Utilizaba técnicas que combinaban el aprendizaje profundo y la búsqueda de árboles 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 primeros tres de cinco partidos. [24] Esta fue la primera vez que un maestro de 9 dan había jugado una partida profesional contra una computadora sin hándicap. [25] Lee ganó el cuarto partido, describiendo su victoria como "invaluable". [26] AlphaGo ganó el partido 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 un juego sin hándicaps en un tablero de tamaño completo.
En mayo de 2017, AlphaGo venció a Ke Jie , quien en ese momento estaba clasificado como el mejor del mundo, [29] [30] en un partido de tres juegos durante la Cumbre del Futuro del Go . [31]
En octubre de 2017, DeepMind reveló una nueva versión de AlphaGo, entrenada solo a través del juego propio, que había superado todas las versiones anteriores, superando a la versión Ke Jie en 89 de 100 juegos. [32]
Después de que los principios básicos de AlphaGo se publicaran en la revista Nature , otros equipos han sido capaces de producir programas de alto nivel. El trabajo en Go AI desde entonces ha consistido en gran medida en emular las técnicas utilizadas para crear AlphaGo, que demostró ser mucho más fuerte que todo lo demás. En 2017, tanto Zen como el proyecto Fine Art de Tencent eran capaces de derrotar a profesionales de muy alto nivel en algunas ocasiones. También se creó el motor de código abierto Leela Zero .
Durante mucho tiempo, la opinión generalizada fue que el Go por ordenador planteaba un problema fundamentalmente diferente al del ajedrez por ordenador . Muchos consideraban que un programa capaz de jugar al Go era algo que solo se podría conseguir en un futuro lejano, como resultado de avances fundamentales en la tecnología de inteligencia artificial en general. Quienes pensaban que el problema era factible creían que se necesitaría conocimiento del dominio para ser eficaz contra expertos humanos. Por lo tanto, una gran parte del esfuerzo de desarrollo del Go por ordenador durante estos tiempos se centró en formas de representar el conocimiento experto similar al humano y combinarlo con la búsqueda local para responder a preguntas de naturaleza táctica. El resultado de esto fueron programas que manejaban bien muchas situaciones específicas pero que tenían debilidades muy pronunciadas en su manejo general del juego. Además, estos programas clásicos no ganaron casi nada con los aumentos en la potencia de cálculo disponible. El progreso en el campo fue generalmente lento.
El gran tamaño del tablero (19×19, 361 intersecciones) suele considerarse una de las principales razones por las que es difícil crear un programa sólido. El gran tamaño del tablero impide que un buscador alfa-beta logre una mirada profunda hacia adelante sin extensiones de búsqueda significativas o heurísticas de poda .
En 2002, un programa informático llamado MIGOS (MIni GO Solver) resolvió por completo el juego de Go para el tablero de 5×5. Las negras ganan y se quedan con todo el tablero. [33]
Siguiendo con la comparación con el ajedrez, los movimientos del Go no están tan limitados por las reglas del juego. Para el primer movimiento en ajedrez, el jugador tiene veinte opciones. Los jugadores de Go comienzan con una elección de 55 movimientos legales distintos, teniendo en cuenta la simetría. Este número aumenta rápidamente a medida que se rompe la simetría, y pronto deben evaluarse casi todos los 361 puntos del tablero.
Una de las tareas más básicas de una partida es evaluar la posición del tablero: ¿qué bando es el favorito y por cuánto? En ajedrez, muchas posiciones futuras en un árbol son victorias directas para un bando, y los tableros tienen una heurística razonable para la evaluación en el conteo simple de material, así como ciertos factores posicionales como la estructura de peones. Un futuro en el que un bando ha perdido su reina sin ningún beneficio claramente favorece al otro bando. Este tipo de reglas de evaluación posicional no se pueden aplicar de manera eficiente al Go. El valor de una posición de Go depende de un análisis complejo para determinar si el grupo está vivo o no, qué piedras se pueden conectar entre sí y de heurísticas en torno al grado en que una posición fuerte tiene influencia, o el grado en que una posición débil puede ser atacada. Una piedra colocada puede no tener una influencia inmediata, pero después de muchos movimientos podría volverse muy importante en retrospectiva a medida que otras áreas del tablero toman forma.
Una mala evaluación de los estados del tablero hará que la IA trabaje hacia posiciones que cree incorrectamente que la favorecen, pero que en realidad no es así.
Una de las principales preocupaciones de un jugador de Go es qué grupos de piedras pueden mantenerse con vida y cuáles pueden ser capturados. Esta clase general de problemas se conoce como vida o muerte . Los sistemas de IA basados en el conocimiento a veces intentaron comprender el estado de vida o muerte de los grupos en el tablero. El enfoque más directo es realizar una búsqueda en árbol sobre los movimientos que potencialmente afectan a las piedras en cuestión y luego registrar el estado de las piedras al final de la línea principal de juego. Sin embargo, dentro de las limitaciones de tiempo y memoria, generalmente no es posible determinar con total precisión qué movimientos podrían afectar la "vida" de un grupo de piedras. Esto implica que se debe aplicar alguna heurística para seleccionar qué movimientos considerar. El efecto neto es que para cualquier programa dado, existe una compensación entre la velocidad de juego y las habilidades de lectura de vida o muerte.
Un problema que todos los programas de Go deben abordar es cómo representar el estado actual del juego. La forma más directa de representar un tablero es como una matriz unidimensional o bidimensional, donde los elementos de la matriz representan puntos en el tablero y pueden tomar un valor correspondiente a una piedra blanca, una piedra negra o una intersección vacía. Se necesitan datos adicionales para almacenar cuántas piedras se han capturado, de quién es el turno y qué intersecciones son ilegales debido a la regla Ko . En general, los programas de aprendizaje automático se detienen en esta forma más simple y dejan que las IA orgánicas lleguen a su propia comprensión del significado del tablero, probablemente simplemente usando jugadas de Monte Carlo para "puntuar" un tablero como bueno o malo para un jugador. Sin embargo, los programas de IA "clásicos" que intentaron modelar directamente la estrategia de un humano podrían ir más allá, como por ejemplo superponiendo datos como piedras que se cree que están muertas, piedras que están incondicionalmente vivas, piedras en un estado seki de vida mutua, etc. en su representación del estado del juego.
Históricamente, se han utilizado técnicas de inteligencia artificial simbólica para abordar el problema de la IA de Go. Las redes neuronales comenzaron a probarse como un enfoque alternativo en la década de 2000, ya que requerían una inmensa potencia de procesamiento que era costosa o imposible de alcanzar en décadas anteriores. Estos enfoques intentan mitigar los problemas del juego de Go, que tiene un alto factor de ramificación y muchas otras dificultades.
La única elección que debe hacer un programa es dónde colocar su próxima piedra. Sin embargo, esta decisión se dificulta debido a la amplia gama de impactos que una sola piedra puede tener en todo el tablero y las complejas interacciones que pueden tener entre sí los distintos grupos de piedras. Han surgido varias arquitecturas para abordar este problema. Las técnicas y filosofías de diseño más populares incluyen:
Una técnica tradicional de IA para crear software de juegos es utilizar una búsqueda de árbol minimax . Esto implica jugar todos los movimientos hipotéticos en el tablero hasta un cierto punto, 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 lleva al mejor tablero hipotético y el proceso se repite en cada turno. Si bien las búsquedas de árbol han sido muy efectivas en ajedrez por computadora , han tenido menos éxito en programas de Go por computadora. 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 lado puede hacer cada uno conduce a 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 extensivamente 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 en gran medida 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 o la muerte, Go es particularmente susceptible a técnicas de almacenamiento en caché como las tablas de transposición . Estas pueden reducir la cantidad de esfuerzo repetido, 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 se pueden acelerar utilizando una gran cantidad de técnicas de poda específicas de dominio, como no considerar movimientos en los que el oponente ya es fuerte y extensiones selectivas como considerar siempre movimientos junto a grupos de piedras que están a punto de ser capturadas . Sin embargo, ambas opciones introducen un riesgo significativo de no considerar un movimiento vital que habría cambiado el curso del juego.
Los resultados de las competiciones informáticas muestran que las técnicas de comparación de patrones para elegir un puñado de movimientos apropiados combinadas con búsquedas tácticas localizadas rápidas (explicadas anteriormente) eran suficientes en el pasado para producir un programa competitivo. Por ejemplo, GNU Go fue competitivo hasta 2008.
Los principiantes humanos suelen aprender de los registros de partidas antiguas jugadas por jugadores expertos. El trabajo de IA en la década de 1990 a menudo implicaba intentar "enseñar" a la IA las heurísticas de conocimiento de Go al estilo humano. 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 de Go, será posible desarrollar programas de Go más fuertes". [34] Propusieron dos formas: reconocer configuraciones comunes de piedras y sus posiciones y concentrarse en batallas locales. En 2001, un artículo concluyó que "los programas de Go aún carecen tanto de calidad como de cantidad de conocimiento", y que solucionar esto mejoraría el rendimiento de la IA de Go. [35]
En teoría, el uso de conocimientos de expertos mejoraría el software de Go. Tanto aficionados como profesionales de alto nivel han formulado cientos de pautas y reglas generales para un juego fuerte. La tarea del programador es tomar estas heurísticas , formalizarlas en código informático y utilizar algoritmos de coincidencia y reconocimiento de patrones para reconocer cuándo se aplican estas reglas. También es importante poder "puntuar" estas heurísticas de modo que, cuando ofrezcan consejos contradictorios, el sistema tenga formas de determinar qué heurística 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 Go, pero no de afirmaciones matemáticas formales; están tratando de hacer que la computadora imite la forma en que juegan al Go. Los programas competitivos alrededor de 2001 podían contener entre 50 y 100 módulos que trataban diferentes aspectos y estrategias del juego, como joseki. [35]
Algunos ejemplos de programas que han dependido en gran medida del conocimiento experto son Handtalk (más tarde conocido como Goemate), The Many Faces of Go, Go Intellect y Go++, cada uno de los cuales en algún momento ha sido considerado el mejor programa de Go del mundo. Sin embargo, estos métodos finalmente tuvieron rendimientos decrecientes y nunca avanzaron realmente más allá de un nivel intermedio en el mejor de los casos en un tablero de tamaño completo. Un problema particular fue 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 en el futuro. El resultado es un programa cuya fuerza es menor que la suma de sus partes; si bien los movimientos pueden ser buenos en una base táctica individual, el programa puede ser engañado y maniobrado para ceder demasiado a cambio, y encontrarse en una posición general perdedora. Como lo expresó la encuesta de 2001, "solo un mal movimiento puede arruinar una buena partida. El rendimiento del programa durante una partida completa puede ser mucho menor que el nivel de maestro". [35]
Una alternativa importante al uso de búsquedas y conocimiento codificados a mano 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 juegos al azar en el tablero resultante. El movimiento que conduce al mejor conjunto de juegos aleatorios 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 al azar, 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 son imperfectos tácticamente. [ cita requerida ] 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 mismo 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 sólidos. Las primeras aplicaciones exitosas de los métodos UCT al Go 19x19 incluyen MoGo, Crazy Stone y Mango. [42] MoGo ganó la Olimpiada de Computadoras de 2007 y ganó una (de tres) partidas blitz contra Guo Juan, 5º Dan Pro, en el mucho menos complejo Go 9x9. The Many Faces of Go [43] ganó la Olimpiada de Computadoras de 2008 después de agregar la búsqueda UCT a su motor tradicional basado en el conocimiento.
Los motores de Go basados en Montecarlo tienen la reputación de estar mucho más dispuestos a jugar tenuki , movimientos en otras partes del tablero, en lugar de continuar una pelea local que los jugadores humanos. Esto a menudo se percibía como una debilidad al principio de la existencia de estos programas. [44] Dicho esto, esta tendencia ha persistido en el estilo de juego de AlphaGo con resultados dominantes, por lo que esto puede ser más una "peculiaridad" que una "debilidad". [45]
El nivel de habilidad de los sistemas basados en el conocimiento está estrechamente vinculado al conocimiento de sus programadores y de los expertos en el dominio asociado. Esta limitación ha dificultado la programación de IA verdaderamente fuertes. Un camino diferente es utilizar técnicas de aprendizaje automático . En estas, lo único que los programadores necesitan programar son las reglas y los algoritmos de puntuación simples sobre cómo analizar el valor de una posición. El software generará automáticamente su propio sentido de patrones, heurísticas y estrategias, en teoría.
Esto se hace generalmente permitiendo que una red neuronal o un algoritmo genético revise una gran base de datos de juegos profesionales o juegue muchos juegos contra sí mismo o contra otras personas o programas. Estos algoritmos pueden entonces utilizar estos datos como un medio para mejorar su rendimiento. Las técnicas de aprendizaje automático también se pueden utilizar 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 de varios cientos de juegos de muestra, utilizando una generalización del sistema de calificació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, tenía una capa que analizaba millones de posiciones existentes para determinar los movimientos probables que se priorizarían como dignos de un análisis más profundo, y otra capa que intentaba optimizar sus propias posibilidades de ganar utilizando los movimientos probables sugeridos por la primera capa. AlphaGo utilizó la búsqueda de árbol de Monte Carlo para puntuar las posiciones resultantes. Una versión posterior de AlphaGo, AlphaGoZero, evitó aprender de los juegos de Go existentes y, en su lugar, aprendió solo de jugarse a sí mismo repetidamente. Otros programas anteriores que utilizaban redes neuronales incluyen NeuroGo y WinHonte.
Los resultados de la investigación sobre Go por computadora se están aplicando a otros campos similares, como la ciencia cognitiva , el reconocimiento de patrones y el aprendizaje automático . [47] La teoría de juegos combinatorios , una rama de las matemáticas aplicadas , es un tema relevante para el Go por computadora. [35]
John H. Conway sugirió aplicar números surrealistas al análisis de finales de Go. Esta idea ha sido desarrollada más a fondo por Elwyn R. Berlekamp y David Wolfe en su libro Mathematical Go . [48] Se ha demostrado que los finales de Go son difíciles de resolver si se debe calcular el mejor movimiento absoluto en un tablero arbitrario casi lleno. Ciertas situaciones complicadas como Triple Ko, Quadruple Ko, Molasses Ko y Moonshine Life hacen que este problema sea difícil. [49] (En la práctica, los algoritmos de Monte Carlo fuertes aún pueden manejar situaciones normales de finales de Go bastante bien, y es poco probable que surjan las clases más complicadas de problemas de finales de vida o muerte en un juego de alto nivel). [50]
Varios problemas combinatorios difíciles (cualquier problema NP-completo ) pueden convertirse en problemas tipo Go en un tablero suficientemente grande; sin embargo, lo mismo es cierto para otros juegos de mesa abstractos, incluidos el ajedrez y el buscaminas , cuando se generalizan adecuadamente a un tablero de tamaño arbitrario. Los problemas NP-completos no tienden en su caso general a ser más fáciles para humanos sin ayuda que para computadoras adecuadamente programadas: los humanos sin ayuda son mucho peores que las computadoras a la hora de resolver, por ejemplo, instancias del problema de suma de subconjuntos . [51] [52]
Se llevan a cabo varias competiciones anuales entre programas informáticos de Go, incluidos eventos de Go en la Olimpiada de Computadoras . Las competiciones regulares, menos formales, entre programas solían tener lugar en el servidor Go de KGS [60] (mensualmente) y en el servidor Go de Computadora [61] (continuamente).
Hay muchos programas disponibles que permiten que los motores Go de computadora jueguen entre sí; casi siempre se comunican a través del Protocolo de Texto Go (GTP).
La primera competición de Go por ordenador fue patrocinada por Acornsoft , [62] y las primeras regulares por USENIX . Se celebraron entre 1984 y 1988. En estas competiciones se presentaron Nemesis, el primer programa de Go competitivo de Bruce Wilcox , y G2.5 de David Fotland, que más tarde evolucionaría hasta convertirse en Cosmos y The Many Faces of Go.
Uno de los primeros impulsores de la investigación del Go por ordenador fue el Premio Ing, un premio en metálico relativamente grande patrocinado por el banquero taiwanés Ing Chang-ki , ofrecido anualmente entre 1985 y 2000 en el Congreso Mundial de Go por Ordenador (o Copa Ing). Al ganador de este torneo se le permitía desafiar a jugadores jóvenes con un hándicap en un partido corto. Si el ordenador ganaba el partido, se otorgaba el premio y se anunciaba un nuevo premio: un premio mayor por vencer a los jugadores con un hándicap menor. La serie de premios Ing iba a 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 NT . El último ganador fue Handtalk en 1997, que se llevó 250.000 dólares NT por ganar un partido con un hándicap de 11 piedras contra tres aficionados de 2 a 6 dan de entre 11 y 13 años. Cuando el premio expiró en 2000, el premio no reclamado era de 400.000 dólares NT por ganar un partido con handicap de nueve piedras. [63]
Muchos otros grandes torneos regionales de Go ("congresos") tenían un evento de Go por computadora adjunto. 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 empezó a patrocinar competiciones de Go por ordenador en 1995. La Copa FOST se celebró anualmente entre 1995 y 1999 en Tokio. Ese 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 computadoras juegan una partida de Go una contra la otra, lo ideal es tratar el juego de manera idéntica a como lo harían dos personas jugando, evitando cualquier intervención de personas reales. Sin embargo, esto puede resultar difícil durante la puntuación final de la partida. El problema principal es que el software de juego de Go, que normalmente se comunica mediante el Protocolo de Texto Go (GTP) estandarizado, no siempre estará de acuerdo con respecto al estado de las piedras vivas o muertas.
Si bien no existe una manera general para que dos programas diferentes "lo resuelvan" y hablen, este problema se evita en su mayor parte mediante el uso de reglas chinas , de Tromp-Taylor o de la Asociación Americana de Go (AGA) en las que se requiere continuar jugando (sin penalización) hasta que no haya más desacuerdos sobre el estado de ninguna piedra en el tablero. En la práctica, como en el servidor Go de KGS, el servidor puede mediar una disputa enviando un comando GTP especial a los dos programas cliente indicando que deben continuar colocando piedras hasta que no haya dudas sobre el estado de ningún grupo en particular (se hayan capturado todas las piedras muertas). El servidor Go de CGOS generalmente ve a los programas renunciar antes de que un juego haya llegado incluso a la fase de puntuación, pero sin embargo admite una versión modificada de las reglas de Tromp-Taylor que requieren un juego completo.
Este conjunto de reglas significa que un programa que estaba en una posición ganadora al final del juego bajo las reglas japonesas (cuando ambos jugadores han pasado) teóricamente podría perder debido a un juego deficiente en la fase de resolución, pero esto es muy poco probable y se considera una parte normal del juego bajo todos los conjuntos de reglas del área.
El principal inconveniente del sistema anterior es que algunos conjuntos de reglas (como las reglas japonesas tradicionales) penalizan a los jugadores por realizar estos movimientos adicionales, lo que impide el uso de jugadas adicionales para dos computadoras. Sin embargo, la mayoría de los programas de Go modernos admiten reglas japonesas contra humanos.
Históricamente, otro método para resolver este problema era que un experto humano juzgara 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 vio.
{{cite web}}: CS1 maint: archived copy as title (link)