Angel "Java" Lopez en Blog

Publicado el 31 de Marzo, 2008, 1:48

El lunes 24 de marzo pasado dí una charla sobre Computer Go, acá en Buenos Aires, en el marco del Tercer Congreso Argentino de Go, organizado por la Asociación Argentina de Go. No pude participar mucho del congreso, pero me cuentan que fue un éxito.

Mi charla trató sobre un problema difícil de lo que se ha llamado Inteligencia Artificial: construir un programa de computación capaz de jugar al go a un nivel aceptable (algún dan aficionado). Quisiera escribir aquí un resumen de lo que mostré.

Para los que quieran ver más detalles técnicos del programa que presenté, visitar:

AjGo: hacia un programa que juegue al go

Luego de décadas de trabajo de programadores de todo el mundo, apenas si tenemos algún programa que juega a nivel de kyu de un dígito. Otros juegos, al pasar los años, han sido "alcanzados" por la inteligencia artificial, pero el fascinante juego del go se resiste.

La Inteligencia Artificial

La inteligencia artificial ha recibido ese nombre en una época optimista, de los años cincuenta del siglo pasado. En aquellos tiempos, se pensaba que estábamos a la vuelta de producir máquinas y programas que emularan al ser humano en actividades que involucran inteligencia. Con el tiempo, el optimismo inicial dió paso a una cautela más acorde a la magnitud de los problemas a enfrentar.

Con el tiempo, se han formado tantas ramas de la inteligencia artificial, que se ha puesto en duda que se la llame de una sola forma. Yo prefiero reconocer la diversidad de campos, pero mantener el nombre original.

El conseguir un comportamiento inteligente de un programa implica más que razonamiento: puede incluir percepción, organización de las percepciones, aprender, comunicar los estados internos, actuar. Hasta ha aparecido una rama, denominada vida artificial, que propugna la simulación de la vida antes de llegar al desarrollo de la inteligencia.

Hoy, en retrospectiva, se puede ver que el desarrollo de la inteligencia artificial, ha tomado dos caminos: tratar de simular la inteligencia humana imitando los procesos humanos, y otra que la simula siguiendo otros caminos, como la fuerza bruta y algoritmos ad hoc.

Una de las aspiraciones actuales es conseguir que un artefacto, combinación de hardware y software, pueda manejarse autónomamente en un ambiente complejo. Los ejemplos más conocidos son los robots enviados a Marte, como el Sojourner de la misión Mars Pathfinder de 1997. Desde Karol Kopec ha quedado en el imaginario popular el concepto de robot, popularizado por el "buen doctor" Asimov.

Pero hay otro ámbito interesante a investigar: en lugar de explorar un ambiente complejo, en un escenario real, se puede avanzar también investigando un ambiente más controlado, como es el de los juegos humanos.

Inteligencia Artificial y Juegos

Vimos que en otros juegos, el alcance de un nivel humano ha sido más accesible. Mencioné como ejemplos a otros juegos:

Backgammon: mi primer contacto con el trabajo de Hans Berliner (campeón mundial de ajedrez por correspondencia y especialista en inteligencia artificial), que con su grupo de investigación construyó el programa BKG que le ganó al flamante campeón mundial humano de backgammon de 1979, Luigi Villa. Recordé que en los noventa, el programa TD Gammon de Tesauro consiguió un gran nivel, en base a aprendizaje. También mencioné que durante los noventa, un programa de backgammon consiguió establecer una nueva forma de "apertura" ante una salida inicial de dados.

Ajedrez: lo más conocido es el triunfo de Deep Blue sobre Gary Kasparov, en la década pasada. A Kasparov no le gusta perder ni a las bolitas, y fue batido en buena ley por el programa desarrollado en IBM, sucesor de anterior Deep Thought. El sistema consiguió un gran nivel apelando a la fuerza bruta. Más información en

http://www.research.ibm.com/deepblue/
http://en.wikipedia.org/wiki/Deep_Blue_%28chess_computer%29

Curiosamente, uno de los principales involucrados es Feng-hsiung Hsu que ahora está trabajando el área de Research de Microsoft, en Beijing.

Pueden ver un comentario actual de su trabajo en:

http://spectrum.ieee.org/oct07/5552

Otro grupo interesado en go, del gigante de Redmond, está en Cambrigde:

http://research.microsoft.com/displayArticle.aspx?id=1062

También comenté sobre otros juegos "quemados" como el gomoku, las damas. Mencionamos al juego inventado en Argentina, el de las amazonas, en cuyo estudio estuvo involucrado uno de los miembros de la AAGo, el bueno de Pablo Coll, y sus tesistas. Recomiendo para un estudio más detallado del problema de los juegos y la inteligencia artificial, visitar el grupo de la Universidad de Alberta:

http://www.cs.ualberta.ca/~games/

Cómo juega un humano

En la historia del ajedrez, Kotov, fuerte jugador soviético, escribió sobre cómo es que piensa un gran maestro. Uno de sus libros, "Piense como un gran maestro", ha sido uno de mis fuentes preferidas sobre el tema. En él, explica que tanto él como otros jugadores de primer nivel de su época, exploran un árbol de jugadas de manera sistemática, en algún momento del proceso de evaluación de su próximo movimiento. También hay abundante bibliografía sobre la sicología del jugador de ajedrez. No he encontrado bibliografía sobre cómo piensa un jugador fuerte de go, pero he encontrado algunas pistas.

El año pasado, en una charla del bueno de Fernando Aguilar en la AAGo, explicó una de las partidas que ganó hace unos años en la copa Toyota, ante un 9 dan profesional. En un momento, ante un posición que resultó en un ataque de su rival, le pregunté si había calculado las variantes posibles. Contestó que no, que se tenía confianza porque había llegado a una posición equilibrada, y que cualquier cosa que hiciera el rival, él sabría cómo responderle. Fernando estuve presente en la charla que dí, y me confirmó esa postura. Otro punto que aproveché a preguntarle sobre la charla, es sobre la tendencia a formar pocos grupos. Comentó que si un jugador llega a formar 6 o 7 grupos separados, pierde. Es un punto a anotar para la evaluación de cualquier posición.

El problema del juego de go

Presenté algunas ideas de cómo poder encarar el problema. El año pasado, en el Segundo Congreso Argentino de Go, dicté otra charla sobre el tema, y ahí me explayé más sobre la inteligencia artifical en general, el tema de juegos en particular y algo de la historia de Computer Go, como el trabajo de Zobrist y el algoritmo de Benson. Pero en esta, quería presentar algo más personal, más relacionado con el go directamente, y entonces me dediqué a mostrar un programa mío, que había mostrado el año pasado, pero al pasar. Se llama AjGo (como no podría ser de otra manera... ;-). Es de código abierto. Coloqué la página del proyecto en:

http://www.ajlopez.com/ajgo

Este año, lo mejoré para la charla, y me resultó más interesante presentar código propio que discutir código de otro, como podría ser el GNUGo.

El programa está escrito en C#, y se ejecuta en Windows. No lo probé, pero debería ejecutar bajo Mono en otros sistemas operativos. Hace un año lo tenía escrito en Visual Basic.NET, pero este año lo reescribí en C#, para poder trabajar mejor con algunos temas técnicos (como "refactoring") y previendo que alguna vez pueda ser ejecutado en otros entornos.

Evaluación de la posición

Uno de los primeros intentos en las historia de Computer Go, fue imaginar que cada pieza "irradia" luz, y que cada punto vacío de alguna forma recibe "luz blanca" o "luz negra". Me parece que esa aproximación puede ser mejorada.

Mi opción preferida para evaluar si un punto "es negro o blanco" es evaluar la cantidad de caminos que tiene ese punto que lo conducen a alguna piedra blanca o negra. También hay que evaluar cuántos puntos críticos tiene ese conjunto de caminos. Dos puntos del tablero pueden estar conectados por 7 caminos, pero puede un punto es crítico, porque al ser ocupado corta 6 de los 7 caminos posibles. El cálculo de caminos está incorporado en el programa AjGo, pero aún no está siendo usado en los otros algoritmos que contiene.

Desde el año pasado, me he decantado por evaluar "con colores" una posición:

Los puntos azules corresponden a puntos bajo la influencia negra, los amarillos están bajo el dominio blanco, los rojos están en disputa, y los verdes están en principio libres.

Una cadena de piedras conectadas, en AjGo se denomina grupo. Un conjunto de piedras negras "sumergidas" en un mar de piedras azules, es una zona negra. Lo mismo con piedras blancas y puntos amarillos.

He visto que para la evaluación de territorios, ojos, vida, y otros, conviene tomar en consideración la zona más que un grupo aislado (no lo sabía cuando le puse estos nombres, pero en GNUGo se llama cadena a lo que en AjGo llamo grupo, y se llama grupo a lo que en mi programa llamo zona).

En base a los colores, se pueden plantear distintos evaluaciones y objetivos. Una zona negra que no tengan ojos posibles o reales, está sin vida "eterna". Una zona que no esté en contacto con una zona verde, está rodeada, y si no tiene perspectivas de formar ojos, está en peligro.

Extender una zona, es aumentar su tamaño.

Conectar una zona, es fusionarla con otra del mismo color.

Rodear a una zona, es desconectarla de zonas verdes (disminuir lo que llamo "vida verde").

El programa igualmente contempla que una zona verde que en su frontera sólo tenga puntos azules, es considerada un "ojo verde" (controlado por piedras negras). Uno de las evaluaciones que estoy probando pondera que una zona verde es tal porcentaje "blanca" y tal otro porcentaje "negra" en base a la cantidad de puntos azules, amarillos y rojos de su frontera.

El programa también tiene la posibilidad de evaluar la posición, usando distintos algoritmos: hay uno basado simplemente en la cantidad de piedras. Otro está basado en la cuenta de los colores, considerando que los puntos azules de las zonas negras son "territorio" (por supuesto, tentativo), sin incluir los puntos frontera con otras zonas. Otro pondera también los puntos en relación a su distancia de los bordes. Esto lo considero un defecto: las evaluaciones que estoy manejando son incapaces por ahora, de evaluar considerando futuras movidas. Así, ocupar un punto san san es considerado a veces más importante que ocupar el hoshi del rincón, porque para el evaluador le resulta una zona más segura. Creo que eso se debe a la falta de evaluación de dos o tres jugadas por adelantado.

Hay selectores de zona, en este caso, dos grupos blancos, incluidos en un grupo "amarillo" (no mostrado):

como puede verse en esta evaluación de color:

Se calculan valores por zona:

Una de las opciones que considero más interesantes, es la detección de jugadas posibles en base a una lista de posiciones a "matchear", que reconocen patrones que aparecen en el juego. Ante una posición, el programa puede sugerir una serie de jugadas calculadas desde esos patrones:

Esas posiciones patrones son externas al programa, residen en archivos de texto y pueden ser agregadas en cualquier momento:

En este ejemplo, - - - - indica borde, X indica piedra propia, O indica piedra enemiga, R indica jugada recomendada.

Esos patrones se pueden clasificar por "objetivo": hay patrones para conectar, para cortar, para extender un grupo o zona. El programa puede detectar también los patrones de jugadas que se pueden aplicar referidos al último movimiento del contrincante.

Para probar la capacidad de exploración de árboles de jugadas, AjGo tiene incorporados algunos algoritmos. Es un tema a mejorar: apenas algunos resuelven posiciones de sichos y getas complejas, y si bien tienen la capacidad de resolver algunos problemas de vida y muerte, aún son débiles y se pierden en la evaluación:

Trabajo futuro

Creo que el desarrollo de un programa de go debe pasar por los mismos estadíos que un jugador humano que va aprendiendo y ascendiendo en la escala de kyu. Próximos trabajos a encarar:

- Resolución ordenada de problemas de vida y muerte
- Evaluación con "lookup" hacia adelante, basado en colores
- Estudio de conectividad por trayectorias
- Evaluación de zonas con sugerencias de planes (por ejemplo, ante una zona rodeada, plantear el objetivo de aumentar su "vida verde")
- Primeros pasos en evaluación de planes

No encararía aún el tema joseki/fuseki.

Se nos terminó el tiempo. Me hubiera gustado comentar algo sobre la teoría de las dimensiones, dejo un artículo de referencia:

http://members.fortunecity.es/andrespernia/boletines/200610/boletin.htm#nota

Comentarios Post Charla

Al final, luego de la charla, recibí algunos comentarios. Una de las asistentes, Verónica, preguntó si el programa AjGo jugaba: creo que no quedó claro, el programa no juega, sólo me ha servido hasta ahora como marco de trabajo para explorar algunas ideas. Tampoco hoy por hoy tiene "intenciones", sólo tiene algoritmos (de búsqueda en árbol), de evaluación de posiciones estáticas (estoy por incorporar también la exploración dinámica de algunas ramas para evaluar una posición), y el uso de patrones (formaciones de piedras) para "conseguir" algunos objetivos, como conectar, cortar, y conseguir "vida verde". Todavía no hace jugadas con la intención de un plan, pero en principio quiero explorar hasta qué punto podemos evaluar una posición, aún sin saber la intención de las últimas jugadas. Eso es lo que describía Kotov en su libro: invitaba durante un torneo de ajedrez, por ejemplo, a Smislov, a que se acercara al tablero donde estaba jugando, digamos, Tahl. Un jugador profesional como Smislov no tenía problema en evaluar la posición, quizás intuyendo intenciones, pero sin conocerlas de seguro. Verónica agregó otro punto: Carlos Asato, un jugador argentino de origen japonés, fue su maestro. Le comentó que él veía colores en el tablero. Interesante punto, que tiene puntos de contacto con la forma en que presenté el tema de colorear la posición.

Alguien mencionó al pasar que un programa no hace más que lo que el programador le pone. Bueno, una posición similar expone el beato Mario Bunge, pero es un tema que le discutiría al viejo. Actualmente hay varias estrategias de aprendizaje automático en inteligencia artificial. Siempre recuerdo el caso del Eurisko, el programa de Douglas Lenat, que conocí a mediados de los ochenta. Se le daban "reglas" de un dominio a estudiar, ya sea la aritmética, o un juego tipo batalla naval, y comenzaba a estudiar distintas estrategias. Basado en reglas heurísticas, investigaba, por ejemplo, los casos extremos. Por ejemplo, al darle las reglas de la aritmética, pudo distinguir números que tenían muchos divisores y otros que tenían pocos. Investigó los dos grupos. El segundo es el de los números primos. Y llegó a "conjeturar" que eran infinitos (no encontró el mayor que cumpliera con la propiedad de no tener divisores propios). Lamentablemente, en mi opinión, Lenat siguió luego otros caminos de investigación.

A la salida de la charla, me encontré con Fernando Aguilar, que me comentó que lo importante durante el desarrollo de un juego es el mantenimiento del equilibrio. Yo había mencionado que había juegos donde se notaba "la sangre", en el espíritu de lucha y en la muerte de grupos. Fernando afirmó que aún en esos juegos, hay un equilibrio durante el desarrollo.

Uno de los que no asistieron a la charla, Lucas Galfasso, me comentó que para él era muy difícil conseguir un programa que jugara a nivel de dan humano (supongo que se refería a amateur), porque no veía forma de programar conceptos como el tewari. Creo que tengo explorar el tema: en principio, la evalución de una posición puede ser estática, como le mencioné a Verónica. Tengo que estudiar la historia del tewari. Justamente, en el artículo que menciono más arriba sobre la teoría de las dimensiones, aparece el tema tewari. También sería interesante ver de implementar la estrategia amashi. Ver

http://www.msoworld.com/mindzine/news/orient/go/history/dosaku1.html

Enlaces y Recursos

He coleccionado algunos enlaces sobre Computer Go en

http://del.icio.us/ajlopez/computergo (los más actualizados)
http://www.ajlopez.net/Tema.php?Id=64 (actualizados hasta cerca de 2004)

En mi blog técnico en español, escribo sobre el tema en

http://msmvps.com/blogs/lopez/archive/tags/Computer+Go/default.aspx

La página del proyecto AjGo es:

http://www.ajlopez.com/ajgo

El código está publicado en

http://www.codeplez.com/ajgo

con una licencia de código abierto BSD.

Para explorar más sobre Computer Go en general, recomiendo comenzar por las páginas

Mick s Computer Go Page
Computer Go Info
Computer Go Mailing List
Computer Go Group of University of Alberta
Computer Go Bibliography
The Computer Go Ladder
Machine Learning in Games
Database of Go-playing programs

Sobre el juego de Go en general:

http://del.icio.us/ajlopez/go

Sobre Inteligencia Artificial

http://del.icio.us/ajlopez/ai
http://www.ajlopez.com/ia/

Como siempre, una gran fuente de información es el wiki de la Sensei's Library

http://senseis.xmp.net/?search=computer+go

Ahí hoy encuentro:

Computer Go Programming
Computer Go Server
Computer Go
Computer Go Musings
Use of SGF editors and Computer Go programs during games
Some Philosophical Questions about Computers and Go
Blue Wyverns Computer Go Corner
Computer Go Algorithms
Tamsin's Paper Go Computer
Computer Go Language Question
Computer Go Programming - Papers
Essay on computer go by David Fotland
Get Strong At Computer Go
Holigor's research in computer go
List Of Components A Computer Go Program Must Have
Writing A Computer Go Engine

Chrisd/ComputerGo
Computer Go Musings/ Discussion
Chrisd/Computer Go Improvements
Writing A Computer Go Engine / Skeleton Engine
DieterVerhofstadt/Thoughts on computer go
Writing A Computer Go Engine / Graphical Interfaces

Más ahí sobre el tema tewari y otros a investigar:

http://senseis.xmp.net/?Tewari
http://senseis.xmp.net/?Amashi
http://senseis.xmp.net/?Moyo
http://senseis.xmp.net/?Shinogi

Presentaciones que usé el año pasado y este año:

Computer Go 2007
Computer Go 2008

Agradezco a Hugo Scolnik, que fue el primero en confiar en mí para dar este tipo de charla el año pasado, y a Jorge Santkovsky, presidente de la asociación, que insistió en que las diera y se ocupó de organizarlas, junto con toda la gente que lo acompaña en la AAGo. Un gracias especial a Santiago, que facilitó un proyector para esta charla.

Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com/

Por ajlopez, en: Go