Showing posts with label gigachess. Show all posts
Showing posts with label gigachess. Show all posts

Friday, August 02, 2019

Un misterio sin resolver...



Crear software siempre parece ser una labor intrigante porque de hecho, si lo pensamos, las instrucciones que escribimos suponen que la computadora tendrá un comportamiento que esperamos. Cuando algo sale mal, entonces vemos nuestra lógica y notamos algún detalle que hace que ocurra un comportamiento inesperado, un resultado falso evidente, lo que nos hace "debugear", es decir depurar el código. Eventualmente obtendremos lo que queremos.

Pues bien, uno de los programas que estoy escribiendo para el doctorado, es el de tratar de "sacar una 'foto' a cada posición que se produce en una partida de ajedrez". Esta "foto" es una expresión Forsyth (o algo muy parecido), en donde se expresa en una cadena de letras la posición que estoy "fotografiando". Por ejemplo, la posición inicial sería:

tcadractpppppppp11111111111111111111111111111111PPPPPPPPTCADRACT

Esto se lee de izquierda a derecha, de 8 en 8 letras. Cuando se termina una secuencia de 8 letras, se pasa a la siguiente línea. Las piezas negras se representan con las minúsculas y las blancas con las iniciales mayúsculas. Esto podría entonces verse así:

tcadract
pppppppp
11111111
11111111
11111111
11111111
PPPPPPPP
TCADRACT

Que representa la posición inicial del tablero, leída desde la esquina superior izquierda hasta la esquina inferior derecha.

Mi software permite entonces leer una partida de ajedrez, en formato PGN, y tomar una instantánea de la posición, salvándola en un archivo. Aparte de la posición se dan detalles como si es posible el enroque y quién juega. Pero eso para el misterio que tengo no ti3ne importancia.

El software ya lo describí en este enlace. Mi programa funciona pero es muy lento. Una partida puede quizás procesarla en 10 a 15 segundos, quizás más. Y etso hace que requiera mucha "galleta" computacional o que pula mi código para que trabaje mejor.

Una primera aproximación fue la de quitar todos los "application.processmessages" de mi código cuando éste se encuentra procesando una posición. En Delphi se tiene este comportamiento: si se entra en un loop, en un ciclo, Delphi rabiosamente hará el ciclo sin interrupciones, a menos que se use, dentro del loop, una instrucción application.processmessages, que hace que el sistema vea las interrupciones y les haga caso cuando está ejecutando el loop.

Por ejemplo, si estamos procesando una imagen para pasarla de color a tonos de gris, y no le ponemos dentro del loop un application.processmessages, el sistema cambiará todos los pixeles a tonos de gris y de pronto, en un pantallazo final, desplegará el resultado. Pero si ponemos esta instrucción dentro del loop, hallaremos que el sisteam despliega cada pixel que va pasando a tonos de gris. Así, si le quitaba todos los processmessages a mi código, no tendría que ver cada cosa que va pasando en el tablero para ir viendo qué posición está fotografiando.

Hice los cambios, compilé el software y lo corrí en la máquina con Windows 7. El resultado de procesar una minibase de partidas fue rapidísimo... El video en este enlace. En cambio, en una máquina con Windows 10, el resultado fue lamentablemente lento. este es el enlace al video.

Cabe decir que es el mismo programa compilado con las "optimizaciones" mencionadas corriendo en las dos versiones diferentes del sistema operativo de Microsoft. La máquina Windows 10 es de hecho más poderosa que la Windows 7. He aquí lo que dice cada uno de los sistemas:

Windows 10: 

Windows 7:



¿Por qué uno es tan lento y el otro no? ¿Qué tiene Windows 10 que lo hace tan lento? ¿Por qué no funcionan las optimizaciones, que funcionaron en Windows 7, pero no en Windows 10? ¿Alguna idea?





Monday, August 27, 2018

Gigachess: bases de datos y búsquedas regulares



El software que he escrito para parte del desarrollo de mi tesis de doctorado no es lo rápido que quisiera y en ocasiones me he puesto a pensar si es el  enfoque correcto. La idea va así: de mi base de partidas de ajedrez, estoy tomando 1 millón de ellas y las estoy procesando de forma que cada una contenga dos campos: el encabezado de la partida: quién contra quién jugó y en qué torneo (incluyendo fecha). Los demás datos como rating no me interesan realmente. El segundo campo contiene una imagen de cada posición que se dio en cada partida. La posición la represento como una línea de caracteres Forsyth, que es un formato en modo texto para representar posiciones de ajedrez. Por ejemplo, la posición:



se representa como: "4t1r1/p1p2pp1/1d1p3p/1P3P2/1P6 /2c1D3/PA4PP/4T1R1/". La posición en modo texto se representa leyendo el tablero de izquierda a derecha y de arriba a abajo. Las piezas blancas se representan con sus iniciales en mayúsculas y las negras con minúsculas. Así, "4t1r1" significa que en la octava fila (la primera del negro), hay 4 casillas vacías, una torre negra, otra casilla vacía, un rey negro y una casilla vacía más. Las diagonales "/" simplemente sirven para denotar que pasamos a la siguiente fila, pero pueden omitirse. Si se omiten tengo exactamente 64 letras o números máximo. Obviamente puedo poner "4t1r1" como "1111t1r1", pero poniendo la cifra de casillas vacías me ahorro espacios.

Imaginemos que tenemos ya una base de datos armada así y que quiero buscar si en alguna posición se tuvo un caballo  blanco en f6 y un rey negro en g8. Mi busqueda buscaría esta posición: "6r1/8/5C2/8/8/8/8/8". Evidentemente ignoro (o debería ignorar) si hay otras piezas en donde yo estoy diciendo que hay casillas vacías. Debo -pienso- definir si es vacía o no con alg{un símbolo en la búsqueda. Se me ocurre entonces que si busco que exista un caballo blanco en f6 y cualquier pieza en g8, debería poder buscar algo así: "6?1/*/5C??/...", donde el símbolo "?" es un comodín que sustituye al símbolo "?" por cualquier pieza o casilla vacía en el tablero. Esto, de hecho, no es un invento mío, sino que se ha definido hace muchos años en cómputo. Hablamos de las búsquedas regulares, las cuales buscan "patrones" en cadenas de caracteres. Es un sistema que es muy versátil y pienso que podría ser muy útil en lo que estoy trabajando.

Mi problema básicamente es que si proceso un millón de partidas tendré aproximadamente 80 millones de posiciones. ¿Cómo puedo buscar sobre una base de datos con expresiones regulares que sea muy rápido? La idea de generar todas las posiciones que es las búsquedas sean muy rápidas. Por ejemplo, Chessbase permite buscar posiciones, pero el sistema lee cada partida y hace la búsqueda sobre la base de datos de referencia que se le dé y esto puede llevarle minutos. No es mucho, lo sé, pero pienso que mi enfoque podría hacer que con búsquedas de expresiones regulares, en mucho menos tiempo que Chessbase, debería saber en qué partida ocurrió una posición determinada.

Hay que decir que tampoco etoy pidiendo algo imposible, porque por ejemplo, si se le piude a Google que busque "regular search", entrega el siguiente resultado:

Cerca de 1,260,000,000 resultados (0.45 segundos) 

Es decir, en su gigantesca base de datos halla 1,260 millones de resultados en menos de medio segundo. Sí, sé que Google usa cómputo distribuido y que tiene montones de algoritmos refinados para sus complejas bases de datos, por lo que me queda claro que lo que quiero hacer tampoco pretende ser algo del otro mundo.

Hay un sistema RegEx, que permite hacer más fácil el asunto de definir las búsquedas de expresiones regulares y hay muchas aplicaciones que permiten crear estas búsquedas casi visualmente.


Entiendo que Oracle permite hacer búsquedas de expresiones regulares en sus bases de datos, pero no tengo más información y no tengo idea de cómo hacerlo en esa plataforma de base de datos. ¿Alguna idea de mis cuatro lectores?

Wednesday, August 22, 2018

GigaChess: una base de datos de posiciones de ajedrez


Llevo tres años trabajando en el doctorado y parece ser que ya las cosas se están aclarando. Tengo un lenguaje de descripción de patrones y ahora el plan -entre otros- es hallar los patrones comunes en la base de partidas que hoy en día tiene más de 7 millones de estas.

Una idea que llevaba hace tiempo trabajando era la de buscar patrones en una base de datos de posiciones, lo cual debe ser mucho más rápido que el tener que buscar el patrón jugando cada partida. Además, si cambio de patrón, tendría que volver a "jugar" partida tras partida para ver si el patrón que busco existe.

Por otra parte, pienso que si guardo cada partida como "fotografías" de cada posición que se dio, puedo hacer las búsquedas más rápidamente. La primera pregunta es cuánto espacio necesito. Hagamos uns imple cálculo: 7 millones de partidas por 80 posiciones (asumiendo que en promedio una partida tiene 40 jugadas, 80 movimientos de blancas y negras). Esto da: 560,000,000 posiciones en total. Si necesito un registro de al menos 64 casillas para guardar una posición (en formato Forsyth), esto nos dará 35,840,000,000 bytes, es decir, unos 35 gigabytes de almacenamiento. Hay que guardar, desde luego, el encabezado de cada partida y hacer el sistema que buisque los patrones. Vamos, hay trabajo por hacer.

35 Gigabytes no parece mucho espacio hoy en día, en donde tenemos discos con 1 o 2 terabytes de almacenamiento.


Así pues, el primer problema es generar las posiciones y ya escribí hace tiempo un programa que hace esta tarea. Cada partida, en la máquina que tengo, se procesa en promedio, en 5 segundos (veces menos).  Eso da, para 7 millones de partidas un total de 35,000,000 segundos, lo cual en días es equivalente a 405 días, como un año y tres meses...

Denasiado tiempo. Así que he reeducido a un millón de partidas, quizás menos. Por otra parte, AMD me donó una computadora mucho más rápida que la que uso normalmente y espero que esto baje el tiempo de procesamiento aún más. Con un millón de partidas, más o menos tardaré: 57 días, unos 2 meses...

Pronto seguiré dando avances sobre esta idea, la cual -después de mucho pensarlo- me parece más útil para la cuestión de programación de computadoras que para el ajedrecista que usa programas para apoyar su estudio.