Registro comprimido de partidas

Este artículo es la continuación de otro titulado "La piezas son animales de costumbres". En aquel artículo se describe como guardar en el mínimo espacio posible una posición de ajedrez y en este se trata de hacer lo mismo con el registro de una partida, es decir con la secuencia de movimientos que la forman.

Para no repetir lo ya escrito, supondré conocido el citado artículo y voy directamente al grano. En este estudio se aplicará el método de compresión aritmética para registrar la secuencia de movimientos de una partida.

Un movimiento en ajedrez consta de varios elementos: la pieza que lo realiza, la casilla de la que parte, la casilla a la que llega y si con él se captura, o no, una pieza del rival. En los primeros tratados sobre ajedrez, los movimientos eran descritos mediante el lenguaje habitual, dando lugar a largos pasajes que con independencia de su valor literario eran poco prácticos para transmitir las enseñanzas sobre el juego. Con el tiempo se fueron adoptando distintos esquemas de notación para abreviar el registro de las partidas, hasta llegar a la denominada notación algebraica corta que se usa con carácter universal en cualquier texto de ajedrez.

La notación algebraica corta, es una forma comprimida de registrar los movimiento, de las que se denominan con pérdida de información, aunque con matices. Si solo se dispone del registro del movimiento no siempre es posible establecer cual es el movimiento a ciencia cierta. En esta forma de anotar se especifica la pieza que mueve y el destino del movimiento (incluso se omite la pieza si es un peón), por ejemplo Cf3, pero no se dice de donde parte el movimiento. Se supone que el lector está reproduciendo una partida y es capaz de deducir esta información a partir de la disposición de las piezas sobre el tablero antes de ejecutarse el movimiento, cuando más de una pieza del mismo tipo puede alcanzar la casilla destino del movimiento, las reglas de anotación establecen que se añada la fila o columna donde está ubicada la pieza que mueve para deshacer la ambigüedad, por ejemplo, Cgf3. Al denominar a esta notación del tipo "con perdida de información", he añadido "con matices" porque realmente no hay tal pérdida, lo que ocurre es que la información que falta está en otra parte, está sobre el tablero. A todos nos han enseñado que "sacar factor común" es lo primero que hay que hacer para simplificar las expresiones aritméticas y esto es lo que hay que hacer cuando se quiere reducir el espacio necesario para el registro masivo de determinados hechos, como son los movimiento de una serie de partidas de ajedrez. Si parte de lo que se quiere registrar se repite sistemáticamente, o se puede deducir mediante reglas previamente conocidas, se omite al escribirlo y se restablece al leerlo.

La notación algebraica corta hace uso de esto y no cabe duda de que es una forma económica de registrar los movimientos, pero la necesidad de añadir información en los casos de ambigüedades y que el proceso para deducir la casilla de partida no es trivial, me ha llevado a adoptar un método de notación distinto. Este método es el llamado de coordenadas y se limita a registrar la casillas de inicio y fin del movimiento, este también es un registro de información incompleta ya la pieza que mueve y si se produce, o no, una captura se obtiene de la posición previa al movimiento.

A primera vista el método de coordenadas parece menos compacto que la notación algebraica corta. Mediante coordenadas, el movimiento se forma combinando dos elementos (casillas) que cada uno de ellos puede tomar un valor entre 0 y 63 (64 casillas). La notación algebraica también combina dos elementos, el segundo coincide con el de coordenadas (casilla de llegada) pero el primero, es una magnitud que sólo puede variar entre 1 y 6, que son los distintos tipos de piezas. Por contra, los tres movimientos: D(d1)e2, R(d1)e2, A(d1)e2 se anotan de la misma forma en coordenadas: d1e2. A los efectos del método de compresión que se describirá más adelante, cuanto menor sea el número de movimientos con notaciones distintas, más compacto será el registro. Dejo a otros, o para otro estudio, la demostración de que método es conceptualmente más compacto y a partir de ahora ya solo se hablará de notación mediante coordenadas, que cuanto menos es más sencillo de manejar con un ordenador.

Hemos dicho que un movimiento es la combinación de dos números que pueden variar, cada uno de ellos, entre 0 y 63. Esto da lugar a 64 x 64 = 4.096 combinaciones distintas, pero dada la forma de mover de las piezas de ajedrez hay combinaciones que no son posibles, por ejemplo, a1b8 y el número de combinaciones válidas se reduce a 1.792. En la imagen siguiente se muestra de forma gráfica cuales son estos movimientos:

El lado izquierdo del cuadrado, numerado del 0 al 63 (de arriba abajo), representa la casilla inicial del movimiento. El lado superior, numerado de 0 a 63 (de izquierda a derecha) son la casilla final del movimiento.

Un punto negro significa que no hay ningún movimiento que suponga el desplazamiento entre la casilla inicial y final representada. Por contra, los puntos más brillante son los que corresponden a desplazamientos que pueden realizarse mediante un mayor número de movimientos distintos. Antes vimos que d1e2 puede realizarse mediante tres movimientos: D(d1)e2, R(d1)e2, A(d1)e2.

La imagen anterior es el resultado de un cálculo teórico, realizado de la siguiente forma. Se ha cogido cada una de las 5 piezas (R,D,T,A y C) blancas y negras, se la ha situado en cada una de las 64 casillas del tablero y se han anotado todos los movimientos que podía realizar, sin más piezas sobre el tablero que ella misma. Lo mismo se ha hecho para un peón blanco y otro negro, pero situándolos sólo en las casillas correspondientes a las filas 2 a 7.

Para obtener una idea más precisa de cuales son los movimientos más frecuentes se puede recurrir a la estadística de las partidas jugadas en la realidad. En la imagen siguiente, se muestra la distribución de los 23.465.000 movimientos realizados, en 308.138 partidas disputadas por jugadores donde, al menos uno, de ellos tenía un Elo de 2.500 o más.

Como curiosidad, mencionar que en estas 308.138 partidas (ocurre exactamente igual al ampliar el conjunto de partidas hasta 658.960) sólo se han producido 1.783 desplazamientos distintos, es decir, 9 de los que son teóricamente posibles nunca se han jugado. ¿Puede el lector adivinar cuales?. Además, ¿puede adivinar cual ha sido el desplazamiento que más veces se ha jugado?

Respecto a los nueve que faltan, ocho se corresponden a cuatro desplazamientos y sus simétricos (invirtiendo la casilla inicial y final). A su vez, dos parejas son simétricas entre sí (son la mismas si se gira el tablero 90 grados). Bueno, estos son los nueve desplazamiento que faltan:

Todos son diagonales, las diagonales más largas !!!

Aunque, una vez leí (no recuerdo donde) que a los jugadores les cuesta ver los desplazamientos largos, la verdadera razón de estas ausencias es que a nadie le gusta poner sus piezas en la esquinas y mucho menos para llevarlas hasta las esquinas opuestas, es el culto a la centralización.

Los cinco desplazamientos que más veces se han jugado, de más a menos, son los siguientes:

Aunque ya hemos mencionado que varios movimientos pueden dar lugar a un mismo desplazamiento, en estos cinco casos, detrás de cada desplazamiento pueden identificarse claramente un movimiento.

Pero ahora retomemos el objeto de estas notas, que es la forma de registrar los movimientos de la forma más compacta.

Para registrar un número cuyo valor está comprendido entre 0 y 63 se necesitan 6 bits, luego para las dos casillas de un movimiento codificado mediante coordenadas, el doble: 12 bits. Pero ya hemos visto que de las 4.096 combinaciones posibles, sólo 1.792 son válidas y este es un número que puede representarse por sólo 11 bits. Simplemente necesitamos una tabla de 1.792 elementos, con dos columnas que contengan las casillas correspondiente a los desplazamientos válidos. A la hora de registrar un movimiento, escribimos la fila de la tabla donde está ubicado (11 bits) en lugar del movimiento (12 bits).

Quienes hayan leído el artículo "Las piezas son animales de costumbres" ya saben cual es el camino a seguir. Una vez constatado que hay movimientos más frecuentes que otros, podemos utilizar un método de compresión carácter a carácter tipo Huffman o compresión aritmética para reducir el tamaño de los registros.

Las frecuencia de los distintos movimientos son las que se muestran en el gráfico anterior y como se ha dicho, se han obtenido analizando las más de 300 mil partidas que sirven de base a este estudio. Al tomar en consideración la tabla de frecuencias, se consigue codificar un movimiento con 9,59 bits por el método de Huffman y 9,55 por compresión aritmética.

Para mejorar estos resultados se puede utilizar un hecho evidente, al realizar el primer movimiento, de los 1.792 movimientos válidos en general, sólo son posibles 20, para la primera respuesta de las negras el número son otros tantos pero, además, todos distintos a los que podían haber realizado las blancas. Generalizando, puede decirse que la frecuencia de un movimiento está asociada al grado de desarrollo de la partida y al turno de juego (blancas o negras), además de a otras muchas circunstancias.

De la misma forma que hemos construido una tabla de frecuencias para los 1.792 movimientos a lo largo de toda la partida, se pueden ir haciendo tablas similares, pero una para blancas y otra para negras y además tablas distintas para cada número de jugada. Si la partida tiene, por ejemplo, 50 jugadas tendremos 50 tablas para blancas y 50 tablas para negras.

Utilizando estas tablas, diferenciadas por número de jugada y turno, el tamaño medio del registro de un movimiento es de 8,24 bits mediante compresión aritmética.

Con este dato finaliza este estudio sobre la compresión de datos relacionados con partidas de ajedrez: posiciones y movimientos, esperando que pueda ser de utilidad a quienes necesiten tratar el mayor número de partidas en el menor espacio posible.

Alberto Bañón Serrano
alberto@interajedrez.com