AjGo: hacia un programa que juegue al go

Published on Author lopez2 Comments

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:

La

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/

Leave a Reply

Your email address will not be published. Required fields are marked *