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?

6 comments:

Cafe 86 said...

Hola Manuel,

¿Podría por favor guiarme para ser un buen programador?

Me gustaría retomar la programación... he pensado en un lenguaje como Python, por la facilidad que (según varios foros) tiene para comprehenderse.

O por la "potencia" del lenguaje... he considerado C++.

¿Me puede por favor orientar?

A final de cuentas... mi idea es entrenarme de modo que pueda después realizar programas para celulares... he sabido de frameworks como "ionic" que permiten ejecutar código tanto en celulares de iOS y Android.

Le dejo mi correo electrónico por si tiene oportunidad de recomendarme algo: jantonioc2001@yahoo.es

Muchas gracias! Saludos,
José Antonio

Francisco Salguero said...

Estimado Manuel, sigo tu blog ya que coincidimos en muchos intereses, ajedrez, programación, tecnología.
Por lo que conozco de expresiones regulares son muy flexibles, pero de alto consumo de proceso.
Para el problema planteado, yo realizaría filtros previos para buscar con expresiones regulares sobre un grupo de partidas previamente filtradas.
Un filtro previo podría ser buscar en el texto de la partida Cf6 y Rg8 para tu ejemplo (con un simple select * from partidas where jugadas like '%Cf6%' and jugadas like '%Rg8%').
No necesariamente estarán esas piezas en la posición final pero ya es un filtro que segmentará bastante el grupo sobre el que aplicar expresiones regulares u otro algoritmo.
Espero te sirva, yo estoy trabajando en algún modelo de datos que me aporte también esa flexibilidad pero me falta unir algunos cabos.
Saludos!

Francisco Salguero

Morsa said...

Me han dicho ue elasticsearch puede hacer la tarea encomendada. Estoy viendo esa posibilidad... Pronto escribiré sobre eso. Saludos
Manuel

Carlos Eligio Ortiz said...

Yo enfocaría el problema utilizando otro "lenguaje". Va mi razonamiento, dime por favor si entendí el asunto:

1.- Forsyth, por lo que pude leer de la liga que dejaste, es decimonónico, (literalmente) y entiendo que es muy bueno para representar una partida, pero nunca fue pensado para búsquedas masivas.

2.- Bajo esa idea, y pensando que tu objetivo es mejorar la velocidad de extracción de información, me inclinaría por cambiar la representación de partidas para privilegiar la búsqueda, que ya el llenado se hará una sola vez y no importa tanto el espacio (ya es muy barato el disco duro).

3.- Puedes guardar la información en una base de datos open source. Oracle, en su versión gratuita, debe tener un límite de espacio,o al menos así es en SQL Server.

4.- Haciendo cálculos muy rápidos, se puede guardar 1 millón de partidas con 80 posiciones en cada una, en aprox. 5 GBytes si fuera texto plano. Total, que en menos de 20 GBytes tienes todo el asunto en una base de datos hecha y derecha.

5.- Para buscar si una pieza está en una posición específica se necesitarían menos de 30 lecturas físicas a disco. Una verdadera ganga.

¿Si entendí el objetivo? Yo soy malísimo en ajedrez, pero me interesó el problema desde el punto de vista de tratamiento de bases de datos de gran tamaño (me dedico a minería de datos, datawarehouse y esas rarezas, doy cursos en la DGTIC-UNAM de eso).

Ya si luego le quieres meter algo de "inteligencia" (ignoro cuál es el objetivo de tu tesis) entonces quizá la representación tendría que ajustarse, pero la idea en términos generales sería esa.

Eligio Ortiz

Mr. m said...

Porque no intenta con el arlgoritmo Boyer - Moore?
https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Boyer-Moore

Morsa said...

Carlos Eligio, quisiera comunicarme contigo... me mandas tus datos a morsa@la-morsa.com? gracias... saludos