Diferencia entre revisiones de «Go por computadora»

De Wikipedia, la enciclopedia libre
Ir a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Juscelk (discusión · contribs.)
5065 ediciones
Página creada con «{{traducción|art=Computer Go|ci=en}} {{otros usos|Go (lenguaje de programación)|para=el lenguaje de programación|este=la inteligencia artificial aplicada al go}}…»
(Sin diferencias)

Revisión del 19:58 22 ene 2021

Este artículo o sección se está traduciendo del idioma inglés a partir del artículo Computer Go. Por esta razón, puede haber lagunas de contenidos, errores sintácticos o escritos sin traducir. Puedes colaborar con Wikipedia continuando con la traducción desde el artículo original.
Este artículo trata sobre la inteligencia artificial aplicada al go. Para el lenguaje de programación, véase Go (lenguaje de programación).
No debe confundirse con Software de go.
Pachi contra Leela Zero, jugando en la interfaz del programa Sabaki.

Go en informática 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

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

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

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

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

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

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

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

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

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

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

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

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

Nuevos enfoques a los problemas

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

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

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

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

Artículo principal: Árbol de búsqueda Monte Carlo

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] ste 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

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

Artículo principal: AlphaGo

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

Artículo principal: Software de go
  • AlphaGo, el primer programa informático en ganar partidos uniformes 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

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

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

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 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

Hay muchos programas disponibles que permiten que los motores 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

Referencias

  1. ↑ «柯洁迎19岁生日 雄踞人类世界排名第一已两年» (en chino). May 2017. 
  2. ↑ «World's Go Player Ratings». 24 de mayo de 2017. 
  3. ↑ «Google's AI Wins First Game in Historic Match With Go Champion». WIRED. 9 March 2016. 
  4. ↑ https://www.koreatimes.co.kr/www/news/tech/2016/03/325_200068.html
  5. ↑ Bouzy, Bruno; Cazenave, Tristan (9 August 2001). «Computer Go: An AI oriented survey». Artificial Intelligence 132 (1): 39-103. doi:10.1016/S0004-3702(01)00127-8. 
  6. ↑ Johnson, George (29 de julio de 1997), «To Test a Powerful Computer, Play an Ancient Game», The New York Times, consultado el 16 de junio de 2008 .
  7. ↑ http://www.chilton-computing.org.uk/acl/literature/reports/p019.htm
  8. ↑ Silver, David; Huang, Aja; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis; Panneershelvam, Veda; Lanctot, Marc; Dieleman, Sander; Grewe, Dominik; Nham, John; Kalchbrenner, Nal; Sutskever, Ilya; Lillicrap, Timothy; Leach, Madeleine; Kavukcuoglu, Koray; Graepel, Thore; Hassabis, Demis (28 January 2016). «Mastering the game of Go with deep neural networks and tree search». Nature 529 (7587): 484-489. Bibcode:2016Natur.529..484S. ISSN 0028-0836. PMID 26819042. S2CID 515925. doi:10.1038/nature16961. Plantilla:Closed access
  9. ↑ Wedd, Nick. «Human-Computer Go Challenges». computer-go.info. Consultado el 28 de octubre de 2011. 
  10. ↑ «'Huge leap forward': Computer that mimics human brain beats professional at game of Go». 
  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. ↑ Millen, Jonathan K (April 1981). «Programming the Game of Go». Byte. p. 102. Consultado el 18 October 2013. 
  13. ↑ Webster, Bruce (November 1984). «A Go Board for the Macintosh». Byte. p. 125. Consultado el 23 October 2013. 
  14. ↑ «CS-TR-339 Computer Go Tech Report». Consultado el 28 January 2016. 
  15. ↑ See for instance intgofed.org (enlace roto disponible en este archivo).
  16. ↑ «EGC 2010 Tampere News». Archivado desde el original el 14 August 2009. Consultado el 28 January 2016.  Parámetro desconocido |url-status= ignorado (ayuda)
  17. ↑ «KGS Game Archives». Consultado el 28 January 2016. 
  18. ↑ «Zen computer Go program beats Takemiya Masaki with just 4 stones!». Go Game Guru. Archivado desde el original el 1 de febrero de 2016. Consultado el 28 January 2016.  Parámetro desconocido |url-status= ignorado (ayuda)
  19. ↑ «「アマ六段の力。天才かも」囲碁棋士、コンピューターに敗れる 初の公式戦». MSN Sankei News. Archivado desde el original el 24 March 2013. Consultado el 27 March 2013.  Parámetro desconocido |url-status= ignorado (ayuda)
  20. ↑ «codecentric go challenge – Just another WordPress site». Consultado el 28 January 2016. 
  21. ↑ «Google AI algorithm masters ancient game of Go». Nature News & Comment. Consultado el 28 January 2016. 
  22. ↑ «Artificial intelligence: Google's AlphaGo beats Go master Lee Se-dol». BBC News Online. 12 March 2016. Consultado el 12 March 2016. 
  23. ↑ «Google's DeepMind defeats legendary Go player Lee Se-dol in historic victory». www.theverge.com. Consultado el 9 March 2016. 
  24. ↑ «Artificial intelligence: Go master Lee Se-dol wins against AlphaGo program». BBC News Online. 13 March 2016. Consultado el 13 March 2016. 
  25. ↑ «Google's AlphaGo AI beats Lee Se-dol again to win Go series 4-1». The Verge. Consultado el 15 March 2016. 
  26. ↑ «After Win in China, AlphaGo's Designers Explore New AI». 27 de mayo de 2017. 
  27. ↑ «World's Go Player Ratings». May 2017. 
  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; Lai, Matthew; Bolton, Adrian; Chen, Yutian; Lillicrap, Timothy; Fan, Hui; Sifre, Laurent; Driessche, George van den; Graepel, Thore; Hassabis, Demis (19 October 2017). «Mastering the game of Go without human knowledge». Nature 550 (7676): 354-359. Bibcode:2017Natur.550..354S. ISSN 0028-0836. PMID 29052630. S2CID 205261034. doi:10.1038/nature24270. Plantilla:Closed access
  31. ↑ Game Tree Searching with Dynamic Stochastic Control pp. 194–195
  32. ↑ «5x5 Go is solved». Consultado el 28 January 2016. 
  33. ↑ On page 11: "Crasmaru shows that it is NP-complete to determine the status of certain restricted forms of life-and-death problems in Go." (See the following reference.) Erik D. Demaine, Robert A. Hearn (2008-04-22). «Playing Games with Algorithms: Algorithmic Combinatorial Game Theory». arXiv:cs/0106019. 
  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

Enlaces externos

En inglés:

Obtenido de «https://es.wikipedia.org/w/index.php?title=Go_por_computadora&oldid=132612890»