Angel "Java" Lopez : Computer Go

Computer Go y Windows HPC Server

lopez — Wed, 18 Feb 2009 08:25:56 GMT

El último año, en el PDC 2008, el equipo de Windows HPC Server presentó un cluster de computadores jugando el juego del Go. Este video muestra la estupenda interfaz Surface que montaron:

(Please visit the site to view this media)

(Si no conocen el juego del Go, visiten:

http://www.gobase.org

Hay mucha información sobre el juego y sus reglas. Hay una sección dedicada solamente a Computer Go:

http://gobase.org/information/computers/

)

David Fotland es el autor del programa original que se muestra en el video. David es un reconocido programador de computer go. Este es el email de David, explicando este programa y su trato con la gente de Windows HPC Server:

http://computer-go.org/pipermail/computer-go/2008-November/017025.html

(Esa es LA lista de correo a seguir, si queremos conocer más sobre el ploblema de Computer Go). David programó una solución tipo MonteCarlo, usando MPI y Windows HPC Cluster.

ManyFacesOfGo, el programa de Fotland, ganó el campeonato mundial de computer go, el año pasado, corriendo sobre un Windows HPC Server cluster (ver los resultados). Nota: el programa que quedó segunda también se ejecutó sobre un cluster. Hay más información sobre el programa (comercial) ManyFacesOfGo en:

http://www.smart-games.com/

2008 fue un año lleno de sorpresas en el ámbito de computer go. Actualmente, los programas no pueden ganarle a un profesional o a un amateur fuerte humano, pero algo está cambiando. Pueden leer:

Latest Advance in Artificial Intelligence: Computer Wins a Game Against a Go Master

y los últimos avances en la página de Wikipedia sobre Computer Go:

http://en.wikipedia.org/wiki/Computer_Go

Después de décadas de pobres resultados, los programas de computación comienzan a ganar a jugadores humanos, pero hay mucho por mejorar. La complejidad del juego evita el uso puro de métodos de fuerza bruto: pienso que la solución vendrá de una mezcla de fuerza bruta, clustering, Monte Carlo, y métodos más clasicos de planeamiento.

I tengo mi propio programa, AjGo para explorar algoritmos que puedan usar este juego fascinante, el "hard problem" en Inteligencia Artificial de juegos de tablero. Un ejemplo de formulario de ese programa:

Posts explicando algo del programa:

AjGo- hacia un programa que juegue al go
Computer Go y el programa AjGo

Mantengo una colección de enlaces sobre Computer Go en delicious y en mi sitio personal:

http://delicious.com/ajlopez/computergo
Computer Go links

Nos leemos!

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

AjGo: hacia un programa que juegue al go

lopez — Mon, 31 Mar 2008 00:40:43 GMT

El hacer un programa que pueda jugar al go ha sido un problema duro de roer en el ámbito de la inteligencia artificial. Para ir explorando algunas ideas, he escrito un programa que me sirve de framework para esa investigación. Pueden descargarlo desde

http://www.codeplex.com/ajgo

(esté el código fuente sin tener aún un release).

Lo comencé a programar hace unos años, y lo presenté el año pasado, en una charla que dí en el Segundo Congreso Argentino de Go, organizado por la Asociación Argentina de Go.

Este año me invitaron de nuevo a dar la charla en el Tercer Congreso (parece que no escarmentaron con la primera... ;-), y esta vez presenté más en profundidad este programa (el año pasado había estado dedicado a temas más generales, como Inteligencia Artificial, juegos y el estado del arte en Computer Go).

He dejado un post menos técnico, más dedicado al tema del juego que a la programación, en mi blog no técnico:

Computer Go y el programa AjGo

Hay otros programas mejores de Computer Go, pero siempre me gusta explorar por mí mismo algunos caminos, para comprender mejor el programa, y además, es más divertido... ;-). Pueden ver un programa más acabado, en la implementación de GNUGo

GNU Go - GNU Project - Free Software Foundation (FSF)

GNU Go - Wikipedia, the free encyclopedia

Sensei's Library- GNU Go

El AjGo

Está escrito en C# (antes lo había escrito en VBNet, pero preferí reescribirlo en C# para aprovechar algunos temas de refactoring, y con la esperanza de portarlo a otras plataformas más fácilmente, si a alguien le interesa).

La solución consta de tres proyectos:

El proyecto AjGo es una librería de clases donde está codificado el "core" del sistema.

El proyecto AjGo.Test es una serie de test automatizados usando NUnit, que me ha resultado de gran ayuda en la exploración de alternativas de programación. Cada vez que necesitaba escribir alguna funcionalidad nueva, siguiendo los preceptos de Test Driven Development, escribía primero el test, y luego el código que lo cumplía. Tengo todavía dos test en "rojo", pero que no afectan a la funcionalidad actual del programa.

El proyecto AjGo.WinForm es el que permite probar interactivamente el programa. La idea es colgar desde ese proyecto un formulario windows que me permita probar en el momento, la efectividad de algunos algoritmos y estrategias.

Si lanzan el proyecto de test, pueden ejecutarlo directamente. He colocado que, aunque sea un proyecto de librería de clases, igualmente ejecute el NUnit, necesitarán el NUnit instalado en alguna parte de su entorno de ejecución. Bajarlo de

NUnit - Home

Para conseguir que ese proyecto pueda lanzarse en modo de ejecución, deben modificar las propiedades del proyecto de test:

Si lo ejecutan, lanza la interface GUI del NUnit:

Detalles de implementación

Hay varias clases interesantes de comentar incluidas en el proyecto AjGo, quisiera hoy ocuparme brevemente de algunas.

Para los que conocen el juego, verán que están implementados los conceptos de:

Color
Position
Game
Group

Desde el año pasado estoy estudiando el tema de usar, aparte de color blanco y negro, otros colores para evaluar una posición.

    public enum Color
    {
        Empty = 0,
        Black = 1,
        White = 2,
        Border = 3,
        Blue = 4,
        Red = 5,
        Green = 6,
        Yellow = 7
    }

Verán que tengo entonces una enumeración que abarca otros colores, a explicar más abajo. Está incluido también el color "vacío" y el color "borde".

La clase Point representa un lugar en el tablero:

    public class Point
    {
        public short X;
        public short Y;

La clase Move es una combinación de Color y Point:

    public class Move
    {
        public Color Color;
        public Point Point;

        public Move(short x, short y, Color c)
        {
            Color = c;
            Point = new Point(x, y);
        }
...
    }

La clase Position describe una posición de juego (la posición puede tener un ancho y alto a determinar en ejecución):

    public class Position
    {
        private short width;
        private short height;

        private Color[,] cells;

        ...
    }

La clase Game es una de las más complejas, representa una posición, distintas evaluaciones, lista de movidas, y una cuenta hasta el momento de las piedras muertas por color:

    public class Game
    {
        private Position position;
        private List<Move> moves;
        private GroupPosition groupposition;
        private Position coloredposition;
        private GroupPosition coloredgroupposition;
        private ColorCount colorcount;
        private int deadblacks;
        private int deadwhites;
        ...
    }

La clase PointSet implementa un conjunto de puntos. Como conjunto no permite la repetición de puntos. Para comparar por igualdad instancias de Point se reimplementó el Equals y GetHashCode en esa clase. Hay métodos de clase para calcular intersección, unión y diferencia de conjuntos de puntos:

    public class PointSet
    {
        protected List<Point> points = new List<Point>();

        public static PointSet Union(PointSet ps1, PointSet ps2)
        {
            return new PointSet(ps1, ps2);
        }

        public static PointSet Intersect(PointSet ps1, PointSet ps2)
        {
            PointSet ps = new PointSet();

            foreach (Point pt in ps1.Points)
                if (ps2.Points.Contains(pt))
                    ps.Add(pt);

            return ps;
        }

        public static PointSet Difference(PointSet ps1, PointSet ps2)
        {
            PointSet ps = new PointSet();


            foreach (Point pt in ps1.Points)
                if (!ps2.Points.Contains(pt))
                    ps.Add(pt);

            return ps;
        }

        public PointSet()
        {
        }

        public PointSet(PointSet ps)
        {
            Add(ps);
        }
        ...
    }

Una extensión de PointSet es la clase Group, que además de un conjunto de puntos, tiene Color asociado:

    public class Group : PointSet
    {
        private PointSet liberties = new PointSet();
        private Color color;
        private GroupPosition groupposition;
        private GroupSet neighbours;
        ...
    }

Luego de Game, la clase más importante para la actual implementación es GroupPosition:

    public class GroupPosition
    {
        private Position position;
        private List<Group> groups;
        private Group[,] groupmap;
        private List<GroupSet> zones;

        public GroupPosition(Position pos)
        {
            position = pos;
            groups = new List<Group>();
        }
        ...
    }

Con instancias de esta clase, se calculan los grupos de piedras (cadenas de piedras conectadas), sus fronteras, vecinos, y zonas (grupos de grupos, de colores asociados, más sobre colores y zonas más adelante).

El Programa

Al ejecutar el tercer proyecto AjGo.WinForm aparece la ventana de prueba:

Con las opciones de Stone de la izquierda, se pueden ir colocando piedras de los colores blanco y negro. Una de las opciones del programa es sugerir posibles movidas, en base a patrones de jugadas que tiene en archivos de texto del directorio Matches del proyecto:

Con el botón de Colors se puede evaluar una posición "en colores":

Como explico en mi post de mi post no técnico:

Computer Go y el programa AjGo

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.

Hay más detalles relacionados con el juego en ese post.

Tengo que mejorar varios puntos. Uno importante, son los algoritmos que tengo implementados para buscar en un árbol de jugadas. Otro, son las clases que evalúan una posición en forma estática. Ambos están en directorios del proyecto AjGo. Estos son los "Agents" de búsqueda en árbol:

Trabajo futuro

Hay mucho para hacer. Me gustaría terminar de pulir la exploración de árbol, la resolución de problemas de vida y muerte, tener un planeador con objetivos, evaluadores estáticos de posición, evaluadores tácticos con exploración de árbol, parámetros variables, algoritmos genéticos.... Bueno, son muchas cosas. Hay que ir paso a paso. Creo que lo primero va a ser mejorar el tema de recorrido de árbol. Vendrán más posts con algunos detalles más finos sobre la implementación actual.

Nos leemos!

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

Computer Go en el Segundo Congreso Argentino de Go

lopez — Wed, 28 Mar 2007 12:03:34 GMT

La Asociación Argentina de Go celebra este próximo fin de semana el Segundo Congreso de Go

http://www.go.org.ar/page.php?name=congreso2007

Hay actividades desde el viernes al lunes. El viernes, habrá una charla sobre Computer Go, recuerden que el Go es el gran desafío de la Inteligencia Artificial, en juegos.

En esa charla, presentaré cuál es la historia del Computer Go, su estado actual, algoritmos intentados, probaremos algún programa, y discutiremos cuál podría ser el camino a tomar para un programa que venza finalmente a un simple humano.... :-)

Nos leemos!

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

Computer Go: El gran problema de AI

lopez — Mon, 15 Jan 2007 01:01:00 GMT

Desde hace algunos años, estoy interesado en algunas ramas de lo que se llama Inteligencia Artificial. Convengamos que el término es algo ampuloso, y refleja el entusiasmo de fines de los años 50, cuando en una reunión de especialista se acuñó el término. La Artificial Intelligence o AI ha pasado por varias etapas y viscisitudes, ha habido de todo, desde triunfos y fracasos, hasta ramas nuevas (agentes, redes neuronales, aprendizaje automático) que han ido apareciendo. Realmente es un tema fascinante, pero tal vez demasiado amplio.

Pueden ver algunos enlaces desordenados que colecciono en

http://www.ajlopez.com/ia/

He mantenido, de alguna manera, el interés en una rama: su aplicación a los juegos. Pueden visitar el excelente sitio del grupo GAMES de la Universidad de Alberta (Canadá):

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

para encontrar mayor información, estupenda. Si Uds. investigan un poco, encontrarán que a lo largo de todos estos años, hay un juego que ha resistido las distintas aproximaciones que se han intentado para dominarlo. Pueden encontrar más información sobre el juego en el sitio de la Asociación Argentina de Go:

http://www.go.org.ar/

en especial, el ya clásico artículo del bueno de Franklin Bassarsky:

Por qué Aprender a jugar al Go
http://www.go.org.ar/actividades/porque.html

Mientras que Deep Blue el siglo pasado derrotó a Kasparov, en ajedrez, el mejor programa de go del planeta apenas si puede enfrentar a un verdadero experto en el juego. Para conocer más sobre la situación actual, visitar el interminable y subyugante

http://gobase.org/

En los últimos años, ha surgido el wiki

http://senseis.xmp.net/

donde encontrarán múltiples temas tratados, por ejemplo

http://senseis.xmp.net/?ComputerGoProgramming
http://senseis.xmp.net/?ComputerGoAlgorithms

Un clásico es el algoritmo de Benson (solo como botón de muestra de cómo apareció hace años, y luego han ido apareciendo otras ideas para explicar y acercar el Go a la AI):

http://senseis.xmp.net/?BensonsAlgorithm

También como botón de muestra de la cantidad de "papers" que mueve el tema, ver

http://erikvanderwerf.tengen.nl/publications.html

LA lista de correo sobre el tema es:

computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Se imaginaran entonces, que no puede faltar.... el AjGo. Sí, estoy pasando a .NET algunas ideas. La principal es concentrarme primero en planes, que traten de cumplir con 4 objetivos básicos:

- Aumentar el territorio propio
- Disminuir el territorio enemigo
- Asegurar la vida de las piedras propias
- Capturar piedras enemigas

Hace unos años investigué distintas formas de calcular la influencia y territorio, basado en conceptos que todos en computer go tratan alguna vez: "iluminación", "campos de fuerza".... En este nuevo intento, he visto que es más interesante simplemente separar en grupos, usando para visualizar el resultado distintos colores. Un ejemplo (una posición algo ridícula para un juego real, pero interesante para mí) es:

Podría explicar un poco más en detalle el coloreo, pero basta decir que los azules indican cercanía a piedra negra, los rojos cercanía a piedra blanca, amarillo cercanía a ambos colores, verde libre de cercanía. Los cuatro objetivos básicos los puedo expresar en deltas en esos coloreos. Me parece que el concepto de grupo coloreado, y su aumento o disminución, es un camino interesante a explorar. Por ejemplo, rodear a un grupo enemigo es, en principio, asimilable a "disminuir sus verdes", los verdes que estan en contacto con ese grupo.

Supongo que alguien ya lo habrá seguido, pero de alguna forma, con esto estoy aprendiendo sobre la dificultad del problema. Tengo que analizar la táctica a seguir para cumplir con cada plan sugerido. Igualmente, algo de algoritmo de sisho generalizado está siendo incorporado. Falta la hercúlea tarea de resolver:

- Tácticas de corte
- Tácticas de conexión
- Tácticas de vida y muerte

Espero poder postear algo interesante cuando tenga algo más armado, código incluído.

Nos leemos!

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