35 veces más rápido

Para la tesis de doctorado he escrito un programa que busca los patrones ajedrecísticos de acuerdo al lenguaje de descripción que definimos en este trabajo, y del cual he hablado ya muchas veces. El software -escrito en Delphi- permite buscar un patrón por segundo en toda una partida, en promedio. Desde luego, si es una partida de 20 movimientos la búsqueda tarda incluso menos. Si es una partida larga, 60 o más movimientos, probablemente la búsqueda del patrón se haga en un par de segundos.

Por supuesto que esta velocidad de proceso es muy lenta en términos de la velocidad de la computadora, aunque para los seres humanos usar un segundo por partida es extremadamente rápido sin considerar siquiera una remota posibilidad de poderlo hacer. De hecho, esto fue uno de los puntos en donde los revisores de mi artículo pusieron algunos peros. Tal vez los convencí indicando que el programa escrito buscaba ser una prueba del concepto investigado, es decir, el uso de patrones, y entonces terminaron por conceder que era un argumento razonable.

Pero desde luego que tardar un segundo por partida para hallar un patrón es lento. Y de hecho, llevaba ya tiempo dándole vueltas al problema. Si vemos los manejadores de partidas, como Chessbase, pueden hacer búsquedas -de posiciones, no patrones- en tiempos notables, por ejemplo, buscar una posición determinada puede llevarle unos 3 minutos en un conjunto de 7 millones de partidas. Y la pregunta es ¿cómo lo hace? Para poder acceder a estas velocidades hay que crear bases de datos de las partidas y manejarlas así. Por ejemplo, Chessbase tiene una serie de archivos de índice para esta tarea y es una de las explicaciones por las cuales sus búsquedas son más rápidas.

¿Sería la única alternativa? Decidí investigar una idea que tiene que ver con las búsquedas regulares, que además, ya he planteado antes en el blog. Entonces me di a la tarea de hacer un programa que mostrara la bondad de usar búsquedas regulares. En este caso el asunto sería de la siguiente manera: El patrón sería una cadena de caracteres, una cadena Forsyth (ver el articulo al que hice referencia para entender de lo que hablo) y cada partida sería una colección de cadenas de caracteres (posiciones) en formato Forsyth. Lo que tendría que hacer es ir recorriendo mi listado de posiciones y ver si pudiesen coincidir con la posición que define el patrón.

En las búsquedas regulares se usan "wildcards", comodines, que indican diferentes conceptos de búsqueda. Por ejemplo, el "?" significa que podemos poner cualquier caracter o símbolo en esa posición. Otro muy usado es "*", que generaliza la búsqueda a muchos caracteres o símbolos, sin importar cuáles sean estos. Por ejemplo, puedo buscar la posición: "???????k" o bien "*k". En la primera, busco siete símbolos pero el octavo debe ser una "k". En el segundo caso, puede haber un número, el que sea, de símbolos, antes de la "k". Desde luego que debe usarse cada símbolo considerando lo que tengamos en mente.

rnbqkbnr
pppppppp
11111111
11111111

11111111
11111111
PPPPPPPP  = 

rnbqkbnrpppppppp/11111111/11111111/11111111/11111111/PPPPPPPP/RNBQKBNR1111111111111111PPPPPPPPRNBQKBNR

Podemos quitar los "/" y tendremos:

rnbqkbnrpppppppp11111111111111111111111111111111PPPPPPPPRNBQKBNR

Ahora bien, supongamos que tengo el patrón del sacrificio griego:

111111r1
111111pp
111111X1
1111PX11
1111X111
111A1C11
11111111
111D1111

Esto es equivalente a la cadena de símbolos:

111111r1111111pp111111X11111PX111111X111111A1C1111111111111D1111

Las X son casillas que no deben estar ocupadas por ninguna pieza o peón en el momento de definir el patrón.

Si yo quiero buscar esta posición, lo que debo poner es:

??????k???????pp??????1?????P1??????1??????B?N?????????????Q????

Donde los escaques vacíos se ponen con "1".

El siguiente paso es poner una partida, jugada a jugada, en formato Forsyth, es decir, en este formato en donde se ve la partida, movimiento con movimiento como una cadena de caracteres. Por ejemplo, esta es una partida de ajedrez completa en formato Forsyth:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq - 0 1
rnbqkbnr/pp1ppppp/8/2p5/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 2
rnbqkbnr/pp1ppppp/8/2p5/4P3/2P5/PP1P1PPP/RNBQKBNR b KQkq - 0 2
rnbqkbnr/pp1p1ppp/8/2p1p3/4P3/2P5/PP1P1PPP/RNBQKBNR w KQkq - 0 3
rnbqkbnr/pp1p1ppp/8/2p1p3/4PP2/2P5/PP1P2PP/RNBQKBNR b KQkq - 0 3
rnbqkbnr/pp3ppp/3p4/2p1p3/4PP2/2P5/PP1P2PP/RNBQKBNR w KQkq - 0 4
rnbqkbnr/pp3ppp/3p4/2p1p3/4PP2/2P2N2/PP1P2PP/RNBQKB1R b KQkq - 1 4
rnbqkbnr/pp3ppp/3p4/2p5/4Pp2/2P2N2/PP1P2PP/RNBQKB1R w KQkq - 0 5
rnbqkbnr/pp3ppp/3p4/2p5/3PPp2/2P2N2/PP4PP/RNBQKB1R b KQkq - 0 5
rnbqkb1r/pp3ppp/3p1n2/2p5/3PPp2/2P2N2/PP4PP/RNBQKB1R w KQkq - 1 6
rnbqkb1r/pp3ppp/3p1n2/2p5/3PPp2/2PB1N2/PP4PP/RNBQK2R b KQkq - 2 6
rnbqk2r/pp2bppp/3p1n2/2p5/3PPp2/2PB1N2/PP4PP/RNBQK2R w KQkq - 3 7
rnbqk2r/pp2bppp/3p1n2/2p5/3PPB2/2PB1N2/PP4PP/RN1QK2R b KQkq - 0 7
rnbq1rk1/pp2bppp/3p1n2/2p5/3PPB2/2PB1N2/PP4PP/RN1QK2R w KQ - 1 8
rnbq1rk1/pp2bppp/3p1n2/2p5/3PPB2/2PB1N2/PP1N2PP/R2QK2R b KQ - 2 8
r1bq1rk1/pp2bppp/2np1n2/2p5/3PPB2/2PB1N2/PP1N2PP/R2QK2R w KQ - 3 9
r1bq1rk1/pp2bppp/2np1n2/2p5/3PPB2/2PB1N2/PP1N2PP/R2Q1RK1 b - - 4 9
r2q1rk1/pp2bppp/2np1n2/2p5/3PPBb1/2PB1N2/PP1N2PP/R2Q1RK1 w - - 5 10
r2q1rk1/pp2bppp/2np1n2/2p1P3/3P1Bb1/2PB1N2/PP1N2PP/R2Q1RK1 b - - 0 10
r2q1rk1/pp2bppp/2n2n2/2p1p3/3P1Bb1/2PB1N2/PP1N2PP/R2Q1RK1 w - - 0 11
r2q1rk1/pp2bppp/2n2n2/2p1P3/5Bb1/2PB1N2/PP1N2PP/R2Q1RK1 b - - 0 11
r2q1rk1/pp2bppp/2n5/2p1P2n/5Bb1/2PB1N2/PP1N2PP/R2Q1RK1 w - - 1 12
r2q1rk1/pp2bppB/2n5/2p1P2n/5Bb1/2P2N2/PP1N2PP/R2Q1RK1 b - - 0 12
r2q1r2/pp2bppk/2n5/2p1P2n/5Bb1/2P2N2/PP1N2PP/R2Q1RK1 w - - 0 13
r2q1r2/pp2bppk/2n5/2p1P1Nn/5Bb1/2P5/PP1N2PP/R2Q1RK1 b - - 1 13
r2q1r2/pp3ppk/2n5/2p1P1bn/5Bb1/2P5/PP1N2PP/R2Q1RK1 w - - 0 14
r2q1r2/pp3ppk/2n5/2p1P1bn/5BQ1/2P5/PP1N2PP/R4RK1 b - - 0 14
r2q1r2/pp3ppk/2n5/2p1P1b1/5nQ1/2P5/PP1N2PP/R4RK1 w - - 0 15
r2q1r2/pp3ppk/2n5/2p1P1b1/4NnQ1/2P5/PP4PP/R4RK1 b - - 1 15
r2q1r2/pp3ppk/2n1n3/2p1P1b1/4N1Q1/2P5/PP4PP/R4RK1 w - - 2 16
r2q1r2/pp3ppk/2n1n3/2p1P1bQ/4N3/2P5/PP4PP/R4RK1 b - - 3 16
r2q1rk1/pp3pp1/2n1n3/2p1P1bQ/4N3/2P5/PP4PP/R4RK1 w - - 4 17
r2q1rk1/pp3pp1/2n1n3/2p1P1bQ/4N3/2P5/PP4PP/3R1RK1 b - - 5 17
r4rk1/pp2qpp1/2n1n3/2p1P1bQ/4N3/2P5/PP4PP/3R1RK1 w - - 6 18
r4rk1/pp1Rqpp1/2n1n3/2p1P1bQ/4N3/2P5/PP4PP/5RK1 b - - 7 18
r4rk1/pp1q1pp1/2n1n3/2p1P1bQ/4N3/2P5/PP4PP/5RK1 w - - 0 19
r4rk1/pp1q1pp1/2n1nN2/2p1P1bQ/8/2P5/PP4PP/5RK1 b - - 1 19
r4rk1/pp1q1p2/2n1np2/2p1P1bQ/8/2P5/PP4PP/5RK1 w - - 0 20
r4rk1/pp1q1p2/2n1nR2/2p1P1bQ/8/2P5/PP4PP/6K1 b - - 0 20

Así, buscar posiciones se reduce a hacer una búsqueda regular en las cadenas de caracteres. La pregunta que me hacía es qué tan rápido sería.

Los programas de mi tesis están todos escritos en Delphi, porque tengo una serie dee bibliotecas que ya me hacen la tarea de dibujar los tableros de ajedrez gráficos, el movimiento de las piezas, etcétera. Entonces, lo que estaba necesitando era una biblioteca que hiciese búsquedas regulares. Hallé una rutina que usaba los comodines "*" y "?", la cual se discutía en este sitio. La copié y la implementé.

Entonces hice mi primera prueba y encontré que el software tardaba 32 segundos analizando 1030 partidas. Esto significó buscar el patrón en aproximadamente unas 32 partidas por segundo, lo que es equivalente a 32 veces más rápido que en el software de patrones original de patrones.

Pero recordé entonces que tenían en otro paquete una biblioteca de búsquedas llamada hyperstrings, la cual estaba escrita en buena parte en ensamblador, buscando ser muy rápida. Hurgué en mi respaldo (porque dicha biblioteca ya no está accesible ahora), y entonces la puse en mi sistema. En este caso el sistema tardó ¡19 segundos!, lo que significa 54 partidas analizadas por segundo, lo que ya me gusta más y que es casi el doble que con la primera rutina en Delphi.

Tomando en cuenta esto último, si el sistema puede buscar un patrón a una velocidad de 54 partidas por segundo, en 48 horas (dos días), podría hacer la búsqueda en unas 9 millones de partidas (la Megabase 2020 contiene menos de 8.5 millones de partidas). Originalmente había pensado que este análisis me llevaría entre 3 y 6 meses sin apagar la computadora.

Cabe señalar que para poder usar mi programa de búsqueda de patrones a través de posiciones Forsyth (FEN), se necesita pasar todas las partidas del archivo PGN (portable game notation) a Forsyth. GigaChess era mi esfuerzo en software para ello, pero hay dificultades, y esto tiene que ver con el sistema operativo, el cual por la propia interfaz gráfica es demasiado lento (véase https://la-morsa.blogspot.com/2019/08/un-misterio-sin-resolver.html).

Entonces se me ocurrió que ya alguien debía haber hecho esta tarea en Internet y sí, hallé este sitio: http://chessbrigade.com/pgnviewer/pgn2fen.html, pero solamente puede hacer la transformación de partida por partida. Sería interesante poder transformar todas las partidas en un archivo PGN. La solución la encontré aquí: https://queenalice.com/topic.php?id=18185, la cual transforma muy rápidamente un archivo de partidas en formato PGN a FEN (esto lo hace desde la consola porque es un programa de DOS). Cabe decir que acabo de hallar otro que aparentemente lo hace en Windows, pero no lo he revisado aún (https://www.bluechillies.com/details/8077.html).

En resumen, si se tiene ya un archivo PGN en formato FEN, mi software puede hacer la búsqueda de patrones unas 50 veces más rápidamente que con el programa original de patrones que había escrito. Y desde luego, para que sea útil, no solamente debe decirme que halló una o varias posiciones donde se da al patrón, si no que debe indicar en qué partidas ocurrió el patrón que estamos buscando. Ahora estoy trabajando sobre eso que ya me parece algo relativamente sencillo.

Seguiremos informando. Una vez que tenga todo funcionando, pondré mi software a disposición de quien le interese.