Computer Go 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 las décadas de 1980 y 1990 produjeron sólo IA que podían ser derrotadas por principiantes, y las IA de principios de la década de 2000 eran, en el mejor de los casos, de nivel intermedio. Los profesionales podrían derrotar estos programas incluso con desventajas de más de 10 piedras a favor de la IA. Muchos de los algoritmos, como alfa-beta minimax , que funcionaban 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. Crear un programa de calidad profesional humana con las técnicas y hardware de la época estaba fuera de nuestro alcance. Algunos investigadores de IA especularon que el problema no tenía solución 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 Go proporcionó una mejora notable a finales de la década de 2000 , con programas finalmente capaces de alcanzar un nivel bajo de dan : el de un aficionado avanzado. Los aficionados y profesionales de alto dan aún podían explotar las debilidades de estos programas y ganar consistentemente, 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 desventaja, que durante mucho tiempo se pensó inalcanzable, provocó un estallido de interés renovado. 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 combate sin handicap en 2016, luego derrotó a Ke Jie en 2017 , quien en ese momento ocupó continuamente el puesto número 1 del mundo durante dos años. Así como las damas cayeron en manos de 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 requería más elementos que imitaran el pensamiento humano que el ajedrez. [4] El matemático IJ Good escribió en 1965: [5]
¿Ir a una computadora? – Para programar una computadora para jugar un juego razonable de Go, en lugar de simplemente un juego 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 juicio. Así que creo que será aún más difícil programar una computadora para jugar una partida razonable de Go que de ajedrez.
Antes de 2015, los mejores programas de Go solo lograban alcanzar el nivel amateur dan . [6] [7] En el pequeño tablero de 9×9, a la computadora le fue mejor y algunos programas lograron ganar una fracción de sus juegos de 9×9 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 sobre Wally, un programa Go con una placa de 15x15 que encajaba en la RAM de 1K del microordenador KIM-1 . [10] Bruce F. Webster publicó un artículo en la revista en noviembre de 1984 sobre un programa Go que había escrito para Apple Macintosh , incluida la fuente MacFORTH . [11] Los programas para Go eran débiles; un artículo de 1983 estimó que, en el mejor de los casos, equivalían a 20 kyu , la calificación de un jugador novato ingenuo, y a menudo se restringían a tableros más pequeños. [12] Las IA que jugaban en Internet Go Server (IGS) en tableros de tamaño 19x19 tenían una fuerza de entre 20 y 15 kyu en 2003, después de mejoras sustanciales en el hardware. [13]
En 1998, jugadores muy fuertes pudieron vencer a los programas de computadora con handicaps de 25 a 30 piedras, un handicap enorme que pocos jugadores humanos aceptarían jamás. Hubo un caso en el Campeonato Mundial de Computer Go de 1994 en el que el programa ganador, Go Intellect, perdió los tres juegos contra los jugadores jóvenes mientras recibía una desventaja de 15 piedras. [14] En general, los jugadores que entendían y explotaban las debilidades de un programa podían ganar incluso a pesar de grandes desventajas. [15]
En 2006 (con un artículo publicado en 2007), Rémi Coulom produjo un nuevo algoritmo al que llamó búsqueda de árbol de Monte Carlo . [16] En él se crea, como de costumbre, un árbol de juego de futuros potenciales que se ramifican con cada movimiento. Sin embargo, las computadoras "califican" una hoja terminal del árbol mediante reproducciones aleatorias repetidas (similar a las estrategias de Monte Carlo para otros problemas). La ventaja es que estas reproducciones aleatorias se pueden realizar muy rápidamente. La objeción intuitiva - que los playouts aleatorios 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 se corrigió lo suficientemente bien como para encontrar árboles de juegos futuros razonables para explorar. Los programas basados en este método, como MoGo y Fuego, obtuvieron un mejor rendimiento que las IA clásicas anteriores. Los mejores programas funcionaban especialmente bien en la pequeña placa 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 la placa 19x19.
En 2010, en el Congreso Europeo de Go de 2010 en Finlandia, MogoTW jugó Go 19x19 contra Catalin Taranu (5p). MogoTW recibió una desventaja 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 hándicap de cinco piedras, seguido de una victoria de 20 puntos con hándicap de cuatro piedras. [19]
En 2013, Crazy Stone venció a Yoshio Ishida (9p) en una partida de 19×19 con hándicap de cuatro piedras. [20]
El Codecentric Go Challenge 2014, un partido al mejor de cinco en un juego igualado de 19x19, se jugó entre Crazy Stone y Franz-Jozef Dickhut (6d). Ningún jugador más fuerte había aceptado jamás jugar una competición seria contra un programa de go en igualdad de condiciones. Franz-Jozef Dickhut ganó, aunque Crazy Stone ganó el primer partido por 1,5 puntos. [21]
AlphaGo , desarrollado por Google DeepMind , supuso un avance significativo en la potencia informática en comparación con los programas Go anteriores. Utilizó 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 de cinco veces 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 jugó un juego profesional contra una computadora sin desventaja. [25] Lee ganó el cuarto partido y describió 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 desventajas en un tablero de tamaño completo.
En mayo de 2017, AlphaGo venció a Ke Jie , quien en ese momento ocupaba el primer lugar del mundo, [29] [30] en un partido de tres juegos durante la Cumbre Future of Go . [31]
En octubre de 2017, DeepMind reveló una nueva versión de AlphaGo, entrenada únicamente mediante el juego autónomo, 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 fueran publicados en la revista Nature , otros equipos han podido producir programas de alto nivel. Desde entonces, el trabajo en Go AI ha consistido en gran medida en emular las técnicas utilizadas para construir AlphaGo, que demostró ser mucho más potente que todo lo demás. En 2017, tanto el proyecto Fine Art de Zen como el de Tencent eran capaces de derrotar a profesionales de muy alto nivel en algunas ocasiones. También se creó el motor Leela Zero de código abierto.
Durante mucho tiempo estuvo ampliamente extendida la opinión de que el Go por ordenador planteaba un problema fundamentalmente diferente del ajedrez por ordenador . Muchos consideraban que un programa sólido de juego de Go era algo que sólo podría lograrse en un futuro lejano, como resultado de avances fundamentales en la tecnología de inteligencia artificial en general. Aquellos que pensaban que el problema era factible creían que se requeriría conocimiento del dominio para ser eficaz contra los expertos humanos. Por lo tanto, una gran parte del esfuerzo de desarrollo de Go por computadora se centró durante estos tiempos en formas de representar el conocimiento experto similar al humano y combinarlo con la búsqueda local para responder preguntas de naturaleza táctica. El resultado de esto fueron programas que manejaron bien muchas situaciones específicas pero que tenían debilidades muy pronunciadas en el manejo general del juego. Además, estos programas clásicos no ganaron casi nada con el aumento de la potencia informática disponible. Los avances en este campo fueron en general lentos.
El tablero grande (19×19, 361 intersecciones) a menudo se señala como una de las razones principales 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 anticipación profunda 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 apoderan de todo el tablero. [33]
Siguiendo con la comparación con el ajedrez, los movimientos de 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 selecció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 es necesario evaluar casi todos los 361 puntos del tablero.
Una de las tareas más básicas en un juego es evaluar la posición del tablero: ¿qué lado es favorecido y en qué medida? En el 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 simple conteo de materiales, 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 a 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 pueden conectarse entre sí y heurísticas sobre hasta qué punto una posición fuerte tiene influencia o hasta qué punto una posición débil tiene influencia. La posición 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 de la junta 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 vivos y cuáles pueden capturarse. Esta clase general de problemas se conoce como vida o muerte . Los sistemas de inteligencia artificial basados en el conocimiento a veces intentaban 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 de 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 determinado, existe un equilibrio entre la velocidad de reproducción y las capacidades de lectura de vida o muerte.
Una cuestión 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, a quién le toca y qué intersecciones son ilegales debido a la regla Ko . En general, los programas de aprendizaje automático se detienen ahí en esta forma más simple y permiten que las IA orgánicas lleguen a su propia comprensión del significado del tablero, probablemente simplemente usando playouts de Monte Carlo para "calificar" un tablero como bueno o malo para un jugador. Sin embargo, los programas de IA "clásicos" que intentaban modelar directamente la estrategia de un ser humano podrían ir más allá, como la superposición de datos como piedras que se creen 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 Go AI. Las redes neuronales comenzaron a probarse como un enfoque alternativo en la década de 2000, ya que requerían una inmensa potencia informática que en décadas anteriores era costosa o imposible de alcanzar. 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 tomar un programa es dónde colocar su próxima piedra. Sin embargo, esta decisión se ve dificultada por la amplia gama de impactos que una sola piedra puede tener en todo el tablero y las complejas interacciones que varios grupos de piedras pueden tener entre sí. Han surgido varias arquitecturas para manejar este problema. Las técnicas y filosofías de diseño populares incluyen:
Una técnica tradicional de IA para crear software de juegos es utilizar una búsqueda de árbol minimax . Esto implica realizar 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 árboles han sido muy efectivas en el ajedrez por computadora , han tenido menos éxito en los programas Computer Go. 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 de cada lado puede hacer que cada uno conduzca a un factor de ramificación alto . Esto hace que esta técnica sea muy costosa desde el punto de vista computacional. Debido a esto, muchos programas que utilizan ampliamente árboles de búsqueda sólo pueden jugar en el tablero más pequeño de 9×9, en lugar de en los completos de 19×19.
Existen varias técnicas que pueden mejorar enormemente 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 . Estos pueden reducir la cantidad de esfuerzo repetido, especialmente cuando se combinan con un enfoque de profundización iterativo . Para almacenar rápidamente un tablero 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 Go porque tiene bajas tasas de colisión y puede actualizarse de forma iterativa 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 en árboles completos en un tablero de tamaño completo siguen siendo prohibitivamente lentas. Las búsquedas se pueden acelerar mediante el uso de grandes cantidades de técnicas de poda específicas de dominio, como no considerar movimientos en los que tu 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 competencias por computadora muestran que las técnicas de coincidencia de patrones para elegir un puñado de movimientos apropiados combinadas con búsquedas tácticas localizadas rápidas (explicadas anteriormente) alguna vez fueron suficientes para producir un programa competitivo. Por ejemplo, GNU Go fue competitivo hasta 2008.
Los novatos humanos a menudo aprenden de los registros de juegos antiguos jugados por jugadores expertos. El trabajo de IA en la década de 1990 a menudo implicaba intentar "enseñar" a la IA heurísticas del 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 sólidos". [34] Propusieron dos formas: reconocer configuraciones comunes de piedras y sus posiciones y concentrarse en las batallas locales. En 2001, un artículo concluyó que "los programas Go todavía carecen de calidad y cantidad de conocimiento" y que solucionar este problema mejoraría el rendimiento de Go AI. [35]
En teoría, el uso del conocimiento experto mejoraría el software 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 de computadora 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 para 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 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 abordaban diferentes aspectos y estrategias del juego, como joseki. [35]
Algunos ejemplos de programas que se han basado en gran medida en el conocimiento de expertos 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, 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 fue la estrategia general del juego. Incluso si un sistema experto reconoce un patrón y sabe cómo librar 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 desde el punto de vista táctico individual, el programa puede ser engañado y maniobrado para ceder demasiado a cambio y encontrarse en una posición perdedora general. Como lo expresó la encuesta de 2001, "sólo un mal movimiento puede arruinar un buen juego. El rendimiento del programa durante un juego completo puede ser mucho menor que el nivel maestro". [35]
Una alternativa importante al uso de conocimientos y búsquedas 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 conocimientos 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 sea evaluado erróneamente como un buen movimiento. El resultado de esto son programas fuertes en un sentido estratégico general, pero imperfectos tácticamente. [ cita necesaria ] 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 además de la evolución aleatoria. Algunos programas que utilizan técnicas de Montecarlo son Fuego, [36] The Many Faces of Go v12, [37] Leela, [38] MoGo, [39] Crazy Stone , MyGoFriend, [40] y Zen.
En 2006, se desarrolló y aplicó a muchos programas Monte-Carlo Go 9x9 con excelentes resultados una nueva técnica de búsqueda, límites superiores de confianza aplicados a los árboles (UCT), [41] . 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 un 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 métodos UCT para 19x19 Go incluyen MoGo, Crazy Stone y Mango. [42] MoGo ganó la Olimpiada de Computación de 2007 y ganó una (de tres) partidas relámpago contra Guo Juan, 5º Dan Pro, en el mucho menos complejo 9x9 Go. The Many Faces of Go [43] ganó la Olimpíada 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 con base 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 expertos en el dominio asociado. Esta limitación ha dificultado la programación de IA verdaderamente potentes. Un camino diferente es utilizar técnicas de aprendizaje automático . En estos, lo único que los programadores necesitan programar son las reglas y algoritmos de puntuación simples sobre cómo analizar el valor de una posición. Luego, el software generará automáticamente su propio sentido de patrones, heurísticas y estrategias, en teoría.
Esto generalmente se hace 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. Luego, estos algoritmos pueden 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 a partir de varios cientos de juegos 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, tenía una capa que analizaba millones de posiciones existentes para determinar posibles movimientos a priorizar como dignos de un análisis más detallado, y otra capa que intentaba optimizar sus propias posibilidades de ganar utilizando los probables movimientos sugeridos desde la primera capa. AlphaGo utilizó la búsqueda de árboles de Monte Carlo para calificar las posiciones resultantes. Una versión posterior de AlphaGo, AlphaGoZero, evitó aprender de los juegos de Go existentes y, en cambio, aprendió solo jugando él mismo repetidamente. Otros programas anteriores que utilizan redes neuronales incluyen NeuroGo y WinHonte.
Los resultados de la investigación de Computer Go 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 combinatoria , 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 del final del juego Go. Esta idea ha sido desarrollada con más detalle por Elwyn R. Berlekamp y David Wolfe en su libro Mathematical Go . [48] Se ha demostrado que los finales de go son difíciles para PSPACE si el mejor movimiento absoluto debe calcularse en un tablero arbitrario en su mayor parte lleno. Ciertas situaciones complicadas como Triple Ko, Quadruple Ko, Molasses Ko y Moonshine Life dificultan este problema. [49] (En la práctica, los potentes algoritmos de Monte Carlo aún pueden manejar situaciones normales de finales de Go bastante bien, y es poco probable que las clases más complicadas de problemas de finales de vida o muerte surjan en un juego de alto nivel.) [50]
Varios problemas combinatorios difíciles (cualquier problema NP-difícil ) se pueden convertir en problemas tipo Go en un tablero suficientemente grande; sin embargo, lo mismo ocurre con 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, casos 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 Computación . Competiciones regulares, menos formales, entre programas solían tener lugar en el KGS Go Server [60] (mensualmente) y el Computer Go Server [61] (continuo).
Hay muchos programas disponibles que permiten que los motores Go de la computadora jueguen entre sí; casi siempre se comunican a través del protocolo Go Text (GTP).
La primera competencia de Go por computadora fue patrocinada por Acornsoft , [62] y las primeras regulares por USENIX . Se llevaron a cabo de 1984 a 1988. Estas competencias introdujeron Nemesis, el primer programa competitivo de Go de Bruce Wilcox , y G2.5 de David Fotland, que luego evolucionaría a Cosmos y The Many Faces of Go.
Uno de los primeros impulsores de la investigación del Go informático fue el Premio Ing, un premio monetario relativamente cuantioso patrocinado por el banquero taiwanés Ing Chang-ki , que se ofreció anualmente entre 1985 y 2000 en el Congreso Mundial de Go Computador (o Copa Ing). Al ganador de este torneo se le permitió desafiar a jugadores jóvenes con hándicap en un partido corto. Si la computadora ganaba el partido, se otorgaba el premio y se anunciaba un nuevo premio: un premio mayor por vencer a los jugadores con menor hándicap. La serie de premios Ing expiraría 1) en el año 2000 o 2) cuando un programa pudiera vencer a un profesional de 1-dan sin desventaja por 40.000.000 NT dólares . El último ganador fue Handtalk en 1997, reclamando 250.000 NT dólares por ganar un partido de handicap de 11 piedras contra tres aficionados de 2 a 6 dans de 11 a 13 años. Cuando el premio expiró en 2000, el premio no reclamado era de 400.000 NT dólares por ganar un partido de 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 de informática desde 1987, y el evento USENIX evolucionó hasta convertirse en el Campeonato de Computer Go de Estados Unidos y América del Norte, que se celebró anualmente entre 1988 y 2000 en el Congreso de Go de Estados Unidos.
Japón comenzó a patrocinar competiciones de Go por computadora en 1995. La Copa FOST se celebró anualmente de 1995 a 1999 en Tokio. Ese torneo fue reemplazado por el Gifu Challenge, que se celebró anualmente de 2003 a 2006 en Ogaki, Gifu. La Copa Computer Go UEC se celebra anualmente desde 2007.
Cuando dos computadoras juegan un juego de Go entre sí, lo ideal es tratar el juego de manera idéntica a como lo hacen dos humanos, evitando cualquier intervención de humanos reales. Sin embargo, esto puede resultar difícil durante la puntuación final del juego. El principal problema es que el software de reproducción Go, que normalmente se comunica mediante el protocolo de texto Go (GTP) estandarizado, no siempre coincide con respecto al estado vivo o muerto de las piedras.
Si bien no existe una forma general para que dos programas diferentes "hablen" y resuelvan el conflicto, este problema se evita en su mayor parte mediante el uso de reglas chinas , Tromp-Taylor o American Go Association (AGA) en las que el juego continúa ( sin penalización) es necesario hasta que no haya más desacuerdo sobre el estado de las piedras en el tablero. En la práctica, como en el servidor KGS Go, el servidor puede mediar en 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 cualquier grupo en particular (todas las piedras muertas). han sido capturados). El servidor CGOS Go generalmente ve que los programas abandonan antes de que un juego haya alcanzado la fase de puntuación, pero aún así admite una versión modificada de las reglas de Tromp-Taylor que requieren un desarrollo completo.
Estos conjuntos de reglas significan que un programa que estaba en una posición ganadora al final del juego según las reglas japonesas (cuando ambos jugadores han pasado) podría teóricamente perder debido a un mal juego en la fase de resolución, pero esto es muy poco probable y se considera normal. parte 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 tradicionales japonesas) penalizan a los jugadores por realizar estos movimientos adicionales, impidiendo el uso de playout adicional para dos computadoras. Sin embargo, la mayoría de los programas Go modernos apoyan las reglas japonesas contra los humanos.
Históricamente, otro método para resolver este problema era hacer que un humano experto juzgara la junta final. Sin embargo, esto introduce subjetividad en los resultados y el riesgo de que el experto se pierda algo que vio el programa.
{{cite web}}: CS1 maint: archived copy as title (link)