Go por computadora

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Pachi contra Leela Zero, jugando en la interfaz del programa Sabaki.

El go por computadora es el campo de la inteligencia artificial dedicado a crear programas informáticos que jueguen al go. El go ha sido un tema fértil de investigación en inteligencia artificial durante décadas, que culminó en 2017 con AlphaGo Master ganando tres de tres partidas contra Ke Jie, quien en ese momento lideraba el escalafón mundial durante dos años.[1][2]

Rendimiento[editar]

Go es un juego de mesa complejo que requiere intuición, pensamiento creativo y estratégico.[3][4]​ Durante mucho tiempo se ha considerado un desafío difícil en el campo de la inteligencia artificial y es considerablemente más difícil[5]​ de resolver que el ajedrez. Muchos en el campo de la inteligencia artificial consideran que el go requiere más elementos que imitan el pensamiento humano que el ajedrez.[6]​ matemático I.J. Good escribió en 1965:[7]

¿Go en una computadora? - Para programar una computadora para que juegue una buena partida 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,[8]​ los mejores programas de go solo lograban alcanzar el nivel de dan amateur.[9]​ En el tablero pequeño 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 vencerían a los mejores humanos en go.[10]

Primeras décadas[editar]

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

En abril de 1981, Jonathan K Millen publicó un artículo en Byte sobre Wally, un programa Go para tablero de 15x15 que encajaba en la memoria RAM de 1K del microordenador KIM-1.[12]​ Bruce F. Webster publicó un artículo en la revista en noviembre de 1984 discutiendo un programa de go que había escrito para Apple Macintosh, incluido el código fuente de MacFORTH.[13]

En 1998, los jugadores muy fuertes eran capaces de vencer a los programas de computadora mientras daban hándicaps de 25 a 30 piedras, un hándicap enorme que pocos jugadores humanos tomarían. Hubo un caso en el World Computer Go Championship de 1994 en el que el programa ganador, Go Intellect, perdió los tres juegos contra los jugadores juveniles mientras recibía una hándicap de 15 piedras.[14]​ En general, los jugadores que entendieron y explotaron las debilidades de un programa podían ganar con desventajas mucho mayores que los jugadores típicos.[15]

Siglo XXI[editar]

Los desarrollos en los árboles de búsqueda de Monte Carlo y el aprendizaje automático llevaron los mejores programas a un alto nivel de dan en el pequeño tablero de 9x9. En 2009, aparecieron los primeros programas de este tipo que también podían alcanzar y mantener rangos bajos de nivel dan en el servidor KGS Go en tablero de 19x19.

En 2010, en el European Go Congress de 2010 en Finlandia, MogoTW jugó 19x19 Go contra Cătălin Țăranu (5p). MogoTW recibió un handicap de siete piedras y ganó.[16]

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

En 2012, Zen venció a Takemiya Masaki (9p) por 11 puntos en el handicap de cinco piedras, seguido de una victoria por 20 puntos en el handicap de cuatro piedras.[18]

En 2013, Crazy Stone venció a Yoshio Ishida (9p) en un juego de 19 × 19 con cuatro piedras de handicap.[19]

El Codecentric Go Challenge 2014, un encuentro al mejor de cinco en un juego parejo de 19x19, se jugó entre Crazy Stone y Franz-Jozef Dickhut (6d). Ningún jugador más fuerte había aceptado 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.[20]

2015 en adelante: la era del aprendizaje profundo[editar]

KataGo, módulo basado en las políticas de análisis de AlphaZero, analizando una posición.

En octubre de 2015, el programa AlphaGo de DeepMind venció a Fan Hui, el campeón europeo de go, en cinco partidas en condiciones de torneo.[21]

En marzo de 2016, AlphaGo venció a Lee Sedol en las primeras tres de cinco partidas.[22]​ Esta fue la primera vez que un maestro de 9 dan jugó un encuentro profesional contra una computadora sin handicap.[23]​ Lee ganó la cuarta partida, describiendo su victoria como "invaluable".[24]​ AlphaGo ganó la partida final dos días después.[25][26]

En mayo de 2017, AlphaGo venció a Ke Jie, quien en ese momento ocupaba el primer lugar en el mundo,[27][28]​ en un encuentro a tres partidas durante la Cumbre del Futuro de Go.[29]

En octubre de 2017, DeepMind reveló una nueva versión de AlphaGo, entrenada solo a través del juego personal, que había superado todas las versiones anteriores, superando a la versión que derrotó a Ke Jie en 89 de 100 juegos.[30]

Dado que los principios básicos de AlphaGo se habían publicado en la revista Nature, otros equipos pudieron producir programas de alto nivel. En 2017, tanto Zen como el proyecto Fine Art de Tencent fueron capaces de derrotar a profesionales de muy alto nivel en algunas ocasiones y se lanzó el motor Leela Zero de código abierto.

Obstáculos para el rendimiento de alto nivel[editar]

Durante mucho tiempo, fue una opinión generalizada que el go informático planteaba un problema fundamentalmente diferente del ajedrez informático. Se creía que los métodos que se basaban en una búsqueda global rápida con relativamente poco conocimiento del dominio no serían efectivos contra los expertos humanos. Por lo tanto, una gran parte del esfuerzo de desarrollo del go informático 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 pero que tenían debilidades muy pronunciadas en comparación con su manejo general del juego. Además, estos programas clásicos no obtuvieron casi nada de los aumentos en la potencia informática disponible per se, y el progreso en el campo fue en general lento.

Algunos investigadores captaron el potencial de los métodos probabilísticos y predijeron que llegarían a dominar los juegos de computadora,[31]​ pero muchos otros consideraron que un programa fuerte de go es algo que solo podría lograrse en un futuro lejano, como resultado de avances fundamentales en la tecnología de inteligencia artificial general. Incluso escribir un programa capaz de determinar automáticamente el ganador de un juego terminado no se consideraba un asunto trivial.

El advenimiento de los programas basados ​​en la búsqueda de Montecarlo (que comenzó en 2006) cambió esta situación de muchas maneras, ya que los primeros jugadores profesionales de go de 9 dan fueron derrotados en 2013 por computadoras multinúcleo, aunque con hándicap de cuatro piedras.

Tamaño del tablero[editar]

El tablero grande (19 × 19, 361 intersecciones) se considera a menudo como una de las principales razones por las que es difícil crear un programa sólido. El gran tamaño del tablero evita que un buscador alfa-beta logre una búsqueda 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, llevándose todo el tablero.[32]

Número de opciones de movimiento[editar]

Continuando 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 el 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 deben evaluarse casi todos los 361 puntos del tablero. Algunos movimientos son mucho más populares que otros y algunos casi nunca se juegan, pero todos son posibles.

Función de evaluación[editar]

Si bien una evaluación de conteo de material no es suficiente para un juego decente en ajedrez, el balance de material y varios factores posicionales como la estructura de peones son fáciles de cuantificar.

Estos tipos 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 un grupo está vivo o no, qué piedras se pueden conectar entre sí y heurísticas sobre el grado en que una posición fuerte tiene influencia, o el grado en que un débil posición puede ser atacada.

Más de un movimiento puede considerarse el mejor según la estrategia que se utilice. Para elegir un movimiento, la computadora debe evaluar diferentes resultados posibles y decidir cuál es el mejor. Esto es difícil debido a las delicadas compensaciones presentes en go. Por ejemplo, puede ser posible capturar algunas piedras enemigas a costa de fortalecer las piedras del oponente en otra parte. Si se trata de un buen intercambio o no, puede ser una decisión difícil, incluso para los jugadores humanos. La complejidad computacional también se muestra aquí, ya que un movimiento podría no ser inmediatamente importante, pero después de muchos movimientos podría volverse muy importante a medida que otras áreas del tablero toman forma.

Problemas combinatorios[editar]

A veces se menciona en este contexto que varios problemas combinatorios difíciles (de hecho, cualquier problema NP-hard) pueden convertirse en problemas tipo go en un tablero suficientemente grande; sin embargo, lo mismo es cierto para otros juegos abstractos, incluyendo 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: es dudoso que los humanos sin ayuda puedan competir exitosamente contra computadoras para resolver, por ejemplo, casos del problema de suma de subconjuntos.

Finales[editar]

Dado que el final contiene menos movimientos posibles que la apertura (fuseki) o el medio juego, uno podría suponer que es más fácil de jugar y, por lo tanto, una computadora debería poder abordarlo fácilmente. En el ajedrez, los programas de computadora generalmente funcionan bien en los finales de ajedrez, especialmente una vez que el número de piezas se reduce en la medida en que permite aprovechar las bases de tablas de finales resueltas.

La aplicación de números surreales al final del juego en go, un análisis general del juego iniciado por John H. Conway, ha sido desarrollado por Elwyn R. Berlekamp y David Wolfe y descrito en su libro Mathematical Go (ISBN  978-1-56881- 032-4). Si bien no es de utilidad general en la mayoría de las circunstancias de juego, es de gran ayuda para el análisis de ciertas clases de posiciones.

No obstante, aunque se ha realizado un estudio elaborado, se ha demostrado que los finales de go son PSPACE-difíciles. Hay muchas razones por las que son tan difíciles:

  • Incluso si una computadora puede jugar cada área de juego local sin problemas, no podemos concluir que sus jugadas sean impecables con respecto a todo el tablero. Las áreas adicionales de consideración en los finales incluyen las relaciones sente y gote, la priorización de diferentes finales locales, el conteo y la estimación de territorios, etc.
  • El final del juego puede involucrar muchos otros aspectos de go, incluida la 'vida y la muerte', que también se sabe que son NP-hard.[33][34]
  • Cada una de las áreas de finales locales pueden afectarse entre sí. En otras palabras, son de naturaleza dinámica aunque visualmente aisladas. Esto hace que sea difícil razonar tanto para las computadoras como para los humanos. Esta naturaleza conduce a situaciones complejas como Triple Ko,[35]​ Cuádruple Ko,[36]​ Molasses Ko,[37]​ y Vida de Moonshine.[38]

Por lo tanto, los algoritmos tradicionales de go no pueden jugar el final de go sin problemas en el sentido de calcular el mejor movimiento directamente. Los sólidos algoritmos de Monte Carlo aún pueden manejar situaciones normales de finales de go bastante bien y, en general, es poco probable que las clases más complicadas de problemas de final de juego de vida o muerte surjan en un juego de alto nivel.[39]

Orden de juego[editar]

Los motores de go basados ​​en Montecarlo tienen la reputación de estar mucho más dispuestos a jugar tenuki, se mueve a otra parte del tablero, en lugar de continuar una pelea local que los jugadores humanos. Calcular directamente cuándo se requiere una mudanza local específica puede ser difícil.[40]​ Esto a menudo se percibía como una debilidad al principio de la existencia de estos programas.[41]​ 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".[42]

Búsqueda táctica[editar]

Una de las principales preocupaciones de un jugador de go es qué grupos de piedras pueden mantenerse vivas y cuáles pueden capturarse. Esta clase general de problemas se conoce como vida o muerte. La estrategia más directa para calcular la vida y la muerte es realizar una búsqueda de árbol en 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 un equilibrio entre la velocidad de juego y las habilidades de lectura de vida o muerte.

Con el algoritmo de Benson, es posible determinar las cadenas que están incondicionalmente vivas y, por lo tanto, no necesitarían ser revisadas en el futuro por seguridad.

Diseño del sistema[editar]

Nuevos enfoques a los problemas[editar]

Históricamente, las técnicas GOFAI (Good Old Fashioned AI) se han utilizado para abordar el problema de la inteligencia artificial en el go. Más recientemente, las redes neuronales se han utilizado como un enfoque alternativo. Un ejemplo de un programa que utiliza redes neuronales es WinHonte.[43]

Estos enfoques intentan mitigar los problemas del juego de Go que tiene un factor de ramificación alto y muchas otras dificultades.

Los resultados de la investigación de la informática aplicada al go se están aplicando a otros campos similares, como la ciencia cognitiva, el reconocimiento de patrones y el aprendizaje automático.[44]​ La teoría de juegos combinatorios, una rama de las matemáticas aplicadas, es un tema relevante para el go en informática.[45]

Filosofías de diseño[editar]

La única elección que debe tomar un programa es dónde colocar la siguiente 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 los grupos de varias piedras pueden tener entre sí. Han surgido varias arquitecturas para manejar este problema. El uso más popular:

Pocos programas utilizan sólo una de estas técnicas exclusivamente; la mayoría combina porciones de cada uno en un sistema sintético.

Búsqueda de árbol Minimax[editar]

Una técnica tradicional de la inteligencia artificial 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 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 conduce al mejor tablero hipotético y el proceso se repite en cada turno. Si bien las búsquedas de árboles han sido muy efectivas en el ajedrez por computadora, han tenido menos éxito en los programas de go. Esto se debe en parte a que tradicionalmente ha sido difícil crear una función de evaluación eficaz para una tabla de go, y en parte a que la gran cantidad de movimientos posibles de cada lado puede hacer que cada uno conduzca 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 19 × 19 completos.

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 el MTD-f pueden reducir el factor de ramificación eficaz sin pérdida de fuerza. En áreas tácticas como la vida o la muerte, el go es particularmente adecuado para técnicas de almacenamiento en caché como 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 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 de Zobrist es muy popular en los programas de go porque tiene bajas tasas de colisión y puede actualizarse 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 árbol completo en un tablero de tamaño completo siguen siendo prohibitivamente lentas. Las búsquedas pueden acelerarse mediante el uso de grandes cantidades de técnicas de poda específicas de dominio, como no considerar movimientos en los que su oponente ya es fuerte, y extensiones selectivas como considerar siempre movimientos junto a grupos de piedras que están a punto de ser capturados . Sin embargo, ambas opciones presentan un riesgo significativo de no considerar un movimiento vital que hubiera cambiado el curso del juego.

Los resultados de las competencias informáticas muestran que las técnicas de emparejamiento 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.

Sistemas basados ​​en el conocimiento[editar]

Los novatos a menudo aprenden mucho de los registros de juegos antiguos jugados por jugadores expertos. Existe una fuerte hipótesis que sugiere que adquirir conocimientos de go es la clave para hacer que un programa de go sea sólido. Por ejemplo, Tim Kinger y David Mechner argumentan que "creemos que con mejores herramientas para representar y mantener el conocimiento del go, será posible desarrollar programas de go más sólidos". Proponen dos caminos: reconocer configuraciones comunes de piedras y sus posiciones y concentrarse en las batallas locales. "Los programas de go todavía carecen de calidad y cantidad de conocimientos".[46]

Después de la implementación, el uso de conocimientos expertos ha demostrado ser muy eficaz en la programación del 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 reconocimiento de patrones y coincidencia de patrones para reconocer cuándo se aplican estas reglas. También es importante tener un sistema para determinar qué hacer en caso de que se apliquen dos pautas en conflicto.

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 go. "La mayoría de los programas competitivos han requerido de 5 a 15 personas-año de esfuerzo y contienen de 50 a 100 módulos que tratan diferentes aspectos del juego".[47]

Este método ha sido hasta hace poco la técnica más exitosa para generar programas de go competitivos en un tablero de tamaño completo. 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 ha sido considerado en algún momento como el mejor programa de go en el mundo.

Sin embargo, agregar conocimientos de go a veces debilita el programa porque algunos conocimientos superficiales pueden traer errores: "los mejores programas suelen jugar buenos movimientos de nivel maestro. Sin embargo, como todo jugador sabe, un solo movimiento malo puede arruinar un buen juego. Rendimiento del programa sobre un juego completo puede ser mucho más bajo que el nivel maestro".[47]

Métodos de Montecarlo[editar]

Una alternativa importante al uso de búsquedas y conocimientos 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 se juegan 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. La ventaja de esta técnica es que requiere muy poco conocimiento de dominio o aportes de expertos, y la compensación es un aumento de los requisitos de memoria y procesador. 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 sólidos en un sentido estratégico general, pero tácticamente imperfectos.[cita requerida] Este problema se puede mitigar agregando algunos conocimientos de 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 Monte-Carlo son Fuego,[48]​ The Many Faces of Go v12,[49]​ Leela,[50]​ MoGo,[51]​ Crazy Stone, MyGoFriend,[52]​ y Zen.

En 2006, se desarrolló una nueva técnica de búsqueda, límites de confianza superiores aplicados a árboles (UCT),[53]​ y se aplicó a muchos programas de go en tablero de 9x9 basados en Monte-Carlo con excelentes resultados. La UCT utiliza los resultados de las jugadas recopiladas hasta ahora 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 para 19x19 Go incluyen MoGo, Crazy Stone y Mango.[54]​ MoGo ganó la Olimpiada informática de 2007 y ganó una (de tres) partidas relámpago contra Guo Juan, 5 dan pro, en el mucho menos complejo go de 9x9. The Many Faces of Go[55]​ ganó la Olimpiada informática de 2008 después de agregar la búsqueda UCT a su motor tradicional basado en el conocimiento.

Aprendizaje automático[editar]

Si bien los sistemas basados ​​en el conocimiento han sido muy efectivos en go, su nivel de habilidad está estrechamente relacionado con el conocimiento de sus programadores y expertos de dominio asociados. Una forma de romper esta limitación es utilizar técnicas de aprendizaje automático para permitir que el software genere automáticamente reglas, patrones y/o estrategias de resolución de conflictos de reglas.

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. Estos algoritmos pueden utilizar estos datos como un medio para mejorar su rendimiento. AlphaGo usó esto con gran efecto. Otros programas que utilizan redes neuronales anteriormente han sido NeuroGo y WinHonte.

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 se basan principalmente en 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 clasificación Elo.[56]

AlphaGo[editar]

AlphaGo, desarrollado por Google DeepMind, logró un avance significativo al vencer a un jugador humano profesional en octubre de 2015, utilizando técnicas que combinaban el aprendizaje profundo y la búsqueda de árboles de Monte Carlo.[57]​ AlphaGo es significativamente más poderoso que otros programas anteriores de Go, y el primero en vencer a un profesional humano de 9 dan en un juego sin desventajas en un tablero de tamaño completo.

Lista de programas informáticos de Go[editar]

  • AlphaGo, el primer programa informático en ganar juegos sin hándicap contra un jugador humano profesional de go
  • AYA[58]​ de Hiroshi Yamashita
  • BaduGI de Jooyoung Lee
  • Crazy Stone de Rémi Coulom (vendido como Saikyo no Igo en Japón)
  • Darkforest de Facebook
  • Fine Art de Tencent
  • Fuego,[48]​ un programa open source basado en Monte Carlo
  • Goban,[59]​ programa para Macintosh OS X de Sen:te (requiere extensiones gratuitas Goban)[60]
  • GNU Go, programa clásico de código abierto
  • Go++[61]​ de Michael Reiss (vendido como Strongest Go o Tuyoi Igo en Japón)
  • Leela,[50]​ el primer programa de Montecarlo en venta al público
  • Leela Zero,[50]​ una reimplementación del sistema descrito en el documento de AlphaGo Zero
  • The Many Faces of Go[49]​ de David Fotland (vendido como AI Igo en Japón)
  • MyGoFriend[52]​ de Frank Karger
  • MoGo[62]​ de Sylvain Gelly; versión paralela por varios autores.[51]
  • Pachi[63]​ programa Monte Carlo de código abierto de Petr Baudiš, versión en línea Peepo[64]​ de Jonathan Chetwynd, con mapas y comentarios mientras se juega
  • Smart Go[65]​ de Anders Kierulf, inventor del formato Smart Game Format (.sgf)
  • Steenvreter[66]​de Erik van der Werf
  • Zen[67]​ de Yoji Ojima, conocido también como Yamato (vendido como Tencho no Igo en Japón), versión paralela de Hideki Kato.

Competiciones entre programas de go[editar]

Varias competiciones anuales tienen lugar entre los programas de computadora Go, siendo la más destacada los torneos de go en las Olimpiadas de Computadoras. Torneos regulares, menos formales, entre programas suelen darse en el servidor KGS GO[68]​ (mensual) y el servidor Computer Go Server[69]​ (continuo).

Entre los programas de go destacados se incluyen Crazy Stone, Zen, Aya, Mogo, The Many Faces of Go, Pachi y Fuego, todos enumerados anteriormente; y de Taiwán, Steenvreter, de Holanda, y DolBaram, de Corea.

Historia[editar]

La primera competencia de computadoras Go fue patrocinada por Acornsoft,[70]​ y las primeras regulares por USENIX. Funcionaron de 1984 a 1988. Estas competencias introdujeron Nemesis, el primer programa competitivo de Go de Bruce Wilcox, y G2.5 de David Fotland, que más tarde 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 Ing Prize, un premio en dinero relativamente grande patrocinado por el banquero taiwanés Ing Chang-ki, ofrecido anualmente entre 1985 y 2000 en el World Computer Go Congress (o Ing Cup). Al ganador de este torneo se le permitió desafiar a jugadores jóvenes con hándicap en un encuentro 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 un handicap menor. La serie de premios Ing estaba programada para expirar 1) en el año 2000 o 2) cuando un programa podía vencer a un profesional de 1 dan sin handicap por 40.000.000 de dólares NT. El último ganador fue Handtalk en 1997, reclamando 250.000 NT dólares por ganar un encuentro de handicap de 11 piedras contra tres jugadores de 11-13 años y 2-6 dan amateur. En el momento en que el premio expiró en 2000, el premio no reclamado era de 400.000 NT dólares por ganar una partida de handicap de nueve piedras.[71]

Muchos otros grandes torneos regionales de go ("congresos") tienen un evento de go informático adjunto. El European Go Congress ha patrocinado un torneo informático desde 1987, y el evento USENIX evolucionó hasta convertirse en el Campeonato Computer Go de Estados Unidos y América del Norte, que se celebra anualmente entre 1988 y 2000 en el Go Congress de Estados Unidos.

Japón comenzó a patrocinar competiciones de go de 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 Computer Go UEC Cup se celebra anualmente desde 2007.

Problemas de formalización de reglas en los juegos de computadora[editar]

Cuando dos computadoras juegan un juego de go entre sí, lo ideal es tratar el juego de una manera idéntica a la de dos humanos mientras se evita cualquier intervención de humanos reales. Sin embargo, esto puede resultar difícil durante la puntuación del juego final. El principal problema es que el software de juego de go, que normalmente se comunica mediante el protocolo Go Text Protocol (GTP) estandarizado, no siempre estará de acuerdo con respecto al estado vivo o muerto de las piedras.

Si bien no existe una forma general de que dos programas diferentes "hablen" y resuelvan el conflicto, este problema se evita en su mayor parte utilizando reglas chinas, reglas de Tromp-Taylor o de la American Go Association (AGA) en las que se requiere el juego continuo (sin penalización) hasta que no haya más desacuerdos 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 ningún grupo en particular (todas las piedras muertas han sido capturados). El servidor CGOS Go generalmente ve que los programas se retiran antes de que un juego haya llegado a la fase de puntuación, pero, sin embargo, admite una versión modificada de las reglas de Tromp-Taylor que requieren una ejecución completa.

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 perder debido a un mal juego en la fase de resolución, pero esto no es algo común y se considera una parte normal del juego bajo todos los conjuntos de reglas de á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 playout adicional para dos computadoras. Sin embargo, la mayoría de los programas de go modernos admiten las reglas japonesas contra los humanos y son competentes tanto en el juego como en la puntuación (Fuego, Many Faces of Go, SmartGo, etc.).

Históricamente, otro método para resolver este problema era 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.

Pruebas[editar]

Hay muchos programas disponibles que permiten que los motores de go de la computadora jueguen entre sí y casi siempre se comunican a través del Protocolo de texto Go (GTP).

GoGUI y su complemento gogui-twogtp se pueden usar para jugar dos motores uno contra el otro en un solo sistema informático.[72]​ SmartGo y Many Faces of Go también ofrecen esta función.

Para jugar con la mayor variedad posible de oponentes, el servidor KGS Go permite a dos motores jugar entre sí, así como partidas de un motor contra humanos tanto en partidas clasificadas como no clasificadas. CGOS es una computadora dedicada frente a un servidor de go por computadora.

Véase también[editar]

Referencias[editar]

  1. 周游 (2 de agosto de 2016). «柯洁迎19岁生日 雄踞人类世界排名第一已两年». sports.sina.com.cn. Consultado el 15 de febrero de 2021. 
  2. «Go Ratings». www.goratings.org. Consultado el 15 de febrero de 2021. 
  3. «Google's AI Wins First Game in Historic Match With Go Champion». Wired (en inglés estadounidense). ISSN 1059-1028. Consultado el 15 de febrero de 2021. 
  4. «AlphaGo victorious once again». koreatimes (en inglés). 10 de marzo de 2016. Consultado el 15 de febrero de 2021. 
  5. «Computer Go: An AI oriented survey». Artificial Intelligence (en inglés) 132 (1): 39-103. 1 de octubre de 2001. ISSN 0004-3702. doi:10.1016/S0004-3702(01)00127-8. Consultado el 15 de febrero de 2021. 
  6. Johnson, George (29 de julio de 1997). «To Test a Powerful Computer, Play an Ancient Game (Published 1997)». The New York Times (en inglés estadounidense). ISSN 0362-4331. Consultado el 15 de febrero de 2021. 
  7. «Go, Jack Good». www.chilton-computing.org.uk. Consultado el 15 de febrero de 2021. 
  8. Silver, David; Huang, Aja; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; van den Driessche, George; Schrittwieser, Julian; Antonoglou, Ioannis et al. (2016-01). «Mastering the game of Go with deep neural networks and tree search». Nature (en inglés) 529 (7587): 484-489. ISSN 1476-4687. doi:10.1038/nature16961. Consultado el 15 de febrero de 2021. 
  9. «Human-Computer Go Challenges». www.computer-go.info. Consultado el 15 de febrero de 2021. 
  10. ChoJan. 27, Adrian (27 de enero de 2016). «‘Huge leap forward’: Computer that mimics human brain beats professional at game of Go». Science | AAAS (en inglés). Consultado el 15 de febrero de 2021. 
  11. Albert Zobrist (1970), Feature Extraction and Representation for Pattern Recognition and the Game of Go. Ph.D. Thesis (152 pp.), University of Wisconsin. Also published as technical report
  12. Byte Magazine Volume 06 Number 04 - Future Computers (en inglés). 1981-04. p. 102. Consultado el 15 de febrero de 2021. 
  13. Byte Magazine Volume 09 Number 12 - New Chips (en inglés). 1984-11. p. 125. Consultado el 15 de febrero de 2021. 
  14. «CS-TR-339 Computer Go Tech Report». Consultado el 28 January 2016. 
  15. «See for instance intgofed.org». 
  16. «EGC 2010 Tampere News». web.archive.org. 14 de agosto de 2009. Consultado el 15 de febrero de 2021. 
  17. «Archivo de partidas de KGS». www.gokgs.com. Consultado el 15 de febrero de 2021. 
  18. «Zen computer Go program beats Takemiya Masaki with just 4 stones!». web.archive.org. 1 de febrero de 2016. Consultado el 15 de febrero de 2021. 
  19. «「アマ六段の力。天才かも」囲碁棋士、コンピューターに敗れる 初の公式戦 - MSN産経ニュース». web.archive.org. 24 de marzo de 2013. Consultado el 15 de febrero de 2021. 
  20. «codecentric go challenge | Just another WordPress site» (en inglés estadounidense). Consultado el 15 de febrero de 2021. 
  21. Gibney, Elizabeth (28 de enero de 2016). «Google AI algorithm masters ancient game of Go». Nature News (en inglés) 529 (7587): 445. doi:10.1038/529445a. Consultado el 15 de febrero de 2021. 
  22. «Artificial intelligence: Google's AlphaGo beats Go master Lee Se-dol». BBC News (en inglés británico). 12 de marzo de 2016. Consultado el 15 de febrero de 2021. 
  23. Byford, Sam (9 de marzo de 2016). «Google's DeepMind defeats legendary Go player Lee Se-dol». The Verge (en inglés). Consultado el 15 de febrero de 2021. 
  24. «Artificial intelligence: Go master Lee Se-dol wins against AlphaGo program». BBC News (en inglés británico). 13 de marzo de 2016. Consultado el 15 de febrero de 2021. 
  25. Byford, Sam (15 de marzo de 2016). «Google's AlphaGo AI beats Lee Se-dol again to win Go series 4-1». The Verge (en inglés). Consultado el 15 de febrero de 2021. 
  26. «After Win in China, AlphaGo's Designers Explore New AI». 27 de mayo de 2017. 
  27. «Go Ratings». www.goratings.org. Consultado el 15 de febrero de 2021. 
  28. «柯洁迎19岁生日 雄踞人类世界排名第一已两年» (en chino). May 2017. 
  29. «Google's AlphaGo Continues Dominance With Second Win in China». 25 de mayo de 2017. 
  30. Silver, David; Schrittwieser, Julian; Simonyan, Karen; Antonoglou, Ioannis; Huang, Aja; Guez, Arthur; Hubert, Thomas; Baker, Lucas et al. (2017-10). «Mastering the game of Go without human knowledge». Nature (en inglés) 550 (7676): 354-359. ISSN 1476-4687. doi:10.1038/nature24270. Consultado el 15 de febrero de 2021. 
  31. Game Tree Searching with Dynamic Stochastic Control pp. 194–195
  32. «5x5 Go is solved». erikvanderwerf.tengen.nl. Consultado el 15 de febrero de 2021. 
  33. Demaine, Erik D.; Hearn, Robert A. (22 de abril de 2008). «Playing Games with Algorithms: Algorithmic Combinatorial Game Theory». arXiv:cs/0106019. Consultado el 15 de febrero de 2021. 
  34. Marcel Crasmaru (1999). «On the complexity of Tsume-Go». Computers and Games. Lecture Notes in Computer Science 1558. London, UK: Springer-Verlag. pp. 222-231. ISBN 978-3-540-65766-8. doi:10.1007/3-540-48957-6_15. 
  35. «Triple Ko». 
  36. «Quadruple Ko». 
  37. «Molasses Ko». 
  38. «Moonshine Life». 
  39. «Computer Go Programming». 
  40. «example of weak play of a computer program». Archivado desde el original el 10 de julio de 2012. Consultado el 28 de agosto de 2010. 
  41. «Facebook trains AI to beat humans at Go board game – BBC News». BBC News (en inglés británico). Consultado el 24 de abril de 2016. 
  42. Ormerod, David (12 March 2016). «AlphaGo shows its true strength in 3rd victory against Lee Sedol». Go Game Guru. Archivado desde el original el 13 March 2016. Consultado el 12 March 2016. 
  43. «Jellyfish-Go.com». Archivado desde el original el 3 July 2007. Consultado el 28 January 2016. 
  44. Muhammad, Mohsin. Thinking games{{|date=january 28 2020 |bot=InternetArchiveBot |fix-attempted=yes }}, Artificial Intelligence 134 (2002): p150
  45. Müller, Martin. Computer GoUso incorrecto de la plantilla enlace roto (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última)., Artificial Intelligence 134 (2002): p150
  46. Müller, Martin. Computer GoUso incorrecto de la plantilla enlace roto (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última)., Artificial Intelligence 134 (2002): p151
  47. a b Müller, Martin. Computer GoUso incorrecto de la plantilla enlace roto (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última)., Artificial Intelligence 134 (2002): p148
  48. a b «Fuego». 
  49. a b David Fotland. «Dan Level Go Software – Many Faces of Go». 
  50. a b c «Sjeng – chess, audio and misc. software». 
  51. a b «Archived copy». Archivado desde el original el 10 de agosto de 2008. Consultado el 3 de junio de 2008. 
  52. a b «MyGoFriend – Gold Medal Winner 15th Computer Olympiad, Go (9x9)». Archivado desde el original el 8 de diciembre de 2010. 
  53. «UCT». 
  54. «Page not found (404)». Archivado desde el original el 3 de noviembre de 2007. 
  55. David Fotland. «Smart Games». 
  56. «Computing Elo Ratings of Move Patterns in the Game of Go». Consultado el 28 January 2016. 
  57. «Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning». Google Research Blog. 27 January 2016. 
  58. «Page ON/サービス終了のお知らせ». Archivado desde el original el 11 de diciembre de 2006. 
  59. «Goban. Play Go on Mac – Sen:te». Archivado desde el original el 19 de mayo de 2013. Consultado el 14 de junio de 2013. 
  60. «Goban Extensions – Sen:te». Archivado desde el original el 18 de mayo de 2016. Consultado el 14 de junio de 2013. 
  61. «Go++, Go playing program». Archivado desde el original el 25 de mayo de 2003. Consultado el 27 de julio de 2020. 
  62. «Archived copy». Archivado desde el original el 28 de noviembre de 2006. Consultado el 21 de febrero de 2007. 
  63. «Pachi – Board Game of Go / Weiqi / Baduk». 
  64. http://www.peepo.com (enlace roto disponible en este archivo).
  65. Anders Kierulf. «SmartGo». 
  66. «STEENVRETER». 
  67. «Zen (go program)». 
  68. «Computer Go Tournaments on KGS». 
  69. «9x9 Go Server». Archivado desde el original el 19 de enero de 2007. Consultado el 25 de marzo de 2007. 
  70. «Acorn 1984 The First Computer Go Tournament». computer-go.info. 
  71. David Fotland. «World Computer Go Championships». Consultado el 28 January 2016. 
  72. Using GoGUI to play go computers against each other (enlace roto disponible en este archivo).

Lecturas adicionales[editar]

Enlaces externos[editar]

En inglés: