Saltar al contenido

The Mystery of Go, el antiguo juego que las computadoras aún no pueden ganar

julio 1, 2021


Para entender esto, piense en Go en relación con el ajedrez. Al comienzo de una partida de ajedrez, las blancas tienen veinte movimientos posibles. Después de eso, las negras también tienen veinte movimientos posibles. Una vez que ambos bandos han jugado, hay 400 posiciones posibles en el tablero. Go, por el contrario, comienza con un tablero vacío, donde las negras tienen 361 movimientos de apertura posibles, uno en cada intersección de la cuadrícula de 19 por 19. Las blancas pueden seguir con 360 movimientos. Eso hace que haya 129,960 posiciones posibles en el tablero después de solo la primera ronda de movimientos.

La velocidad a la que aumentan las posibles posiciones está directamente relacionada con el «factor de ramificación» de un juego, o el número medio de movimientos disponibles en un turno determinado. El factor de ramificación del ajedrez es 35. Go’s es 250. Los juegos con factores de ramificación altos hacen que los algoritmos de búsqueda clásicos como minimax extremadamente costoso. Minimax crea un árbol de búsqueda que evalúa los posibles movimientos simulando todos los juegos posibles que podrían seguir, y luego elige el movimiento que minimiza el mejor escenario del oponente. Mejoras en el algoritmo, como búsqueda alfa-beta y movimiento nulo – Puede podar el árbol del juego de ajedrez, identificando qué movimientos merecen más atención y facilitando búsquedas más rápidas y profundas. Pero lo que funciona para el ajedrez, y las damas y Otelo, no funciona para Go.

Veré un movimiento y me aseguraré de que sea el correcto, pero no podré decirte exactamente cómo lo sé. Solo lo veo ».

El problema es que identificar movimientos de Go que merecen atención es a menudo un proceso misterioso. «Estarás mirando el tablero y lo sabrás», me dijo Redmond, mientras estábamos parados frente a la pantalla del proyector, viendo a Crazy Stone recuperar la ventaja inicial de Nomitan. «Es algo subconsciente, que entrenas a través de años y años de juego. Veré un movimiento y me aseguraré de que sea el correcto, pero no podré decirte exactamente cómo lo sé. Simplemente lo veo».

Igualmente inescrutable es el proceso de evaluación de una configuración de placa en particular. En el ajedrez, hay algunas reglas obvias. Si, diez se mueve en la línea, a un lado le falta un caballo y al otro no, generalmente está claro quién está por delante. No es así en Go, donde no hay una manera fácil de demostrar por qué el moyo de las negras es grande pero vulnerable, y las blancas tienen ají malo. Tales cosas pueden resultar obvias para un jugador experto, pero sin una buena forma de cuantificarlas, serán invisibles para las computadoras. Y si no hay una buena manera de evaluar las posiciones intermedias del juego, un algoritmo alfa-beta que participa en búsquedas globales del tablero no tiene forma de decidir qué movimiento conduce al mejor resultado.

No es que importe: el factor de ramificación increíblemente alto de Go y el espacio de estado (la cantidad de configuraciones de placa posibles) hacen que las búsquedas alfa-beta de placa completa sean prácticamente inútiles, incluso después de implementar mejoras inteligentes. Considere la duración promedio de un juego (el ajedrez es de alrededor de 40 turnos, el Go es de 200) y el Go de la computadora comienza a parecer una tarea tonta.

Un tablero de juego tradicional de Go.

Takashi Osato / CON CABLE

En busca del salto mental

No obstante, después de Zobrist, los programadores de Go persistieron en sus esfuerzos y lograron progresar gradualmente. Pero no fue hasta 1979 que un proyecto de cinco años del científico informático Bruce Wilcox produjo un programa capaz de vencer a los aficionados de bajo nivel. Como estudiante de posgrado en la Universidad de Michigan, Wilcox y su asesor recopilaron protocolos detallados de los partidos jugados contra James Kerwin, quien poco después se iría a Japón para convertirse en el segundo jugador profesional occidental de Go.

A diferencia de los programadores de ajedrez exitosos, Wilcox se centró casi por completo en modelar la inteligencia experta, recopilando una vasta base de datos de relaciones de piedra de las partidas de Kerwin. Su programa dividió el tablero en zonas más pequeñas y manejables, y luego usó la base de datos para generar posibles movimientos, aplicando una función jerárquica para elegir el mejor entre ellos. Las búsquedas prospectivas como alfa-beta, durante mucho tiempo la piedra angular de los juegos de inteligencia artificial, estuvieron completamente ausentes de la primera encarnación del programa.

Luego, de forma algo abrupta, el progreso se estancó. Los programas habían encontrado un obstáculo que también da problemas a los jugadores humanos.

Durante el proceso de desarrollo, Wilcox se convirtió en un jugador aficionado muy fuerte, un activo indispensable para los primeros programadores de Go, dado que los programas dependían tanto de una comprensión matizada del juego. Mark Boon (Goliath), David Fotland (Many Faces of Go), Chen Zhixing (Handtalk y Goemate), los ganadores de las competiciones de Go por computadora durante los años 80 y 90, fueron todos excelentes jugadores, y fue su destreza combinada como jugadores y programadores que facilitaron mejoras constantes durante los años noventa. Luego, de forma algo abrupta, el progreso se estancó. Los programas habían encontrado un obstáculo que también da problemas a los jugadores humanos.

«Mucha gente alcanza un cierto nivel de aficionado y nunca se vuelve más fuerte», explica David Fotland. Fotland, uno de los primeros innovadores de Go en computadoras, también trabajó como ingeniero jefe del procesador PA-RISC de Hewlett Packard en los años 70 y probó el sistema con su programa Go. «Hay algún tipo de salto mental que tiene que suceder para superar ese bloqueo, y los programas se encontraron con el mismo problema. El problema es poder ver todo el tablero, no solo las peleas locales».



Source link

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *