En el artículo "Registro comprimido de partidas", publicado hace algunos años propuse un método para registrar los movimientos de una partida de ajedrez con unos resultados de 8,25 bytes por movimiento, en aquel momento creí que sería muy difícil aumentar ese grado de compresión, pero hoy voy a exponer un método significativamente más económico. Este método es el que he utilizado en relación a los QR-Code y la aplicación Capta.

El método es muy simple: consiste en codificar cada movimiento mediante dos elementos:

1. El número de la pieza que mueve.
2. El número del movimiento que realiza.

Cada bando dispone de un determinado número de piezas y peones, 16 al inicio de la partida, y los numeramos empezando a contar desde la casilla a1, recorriendo las distintas filas del tablero hasta llegar a la casilla h8. Para registrar un número que puede variar del 1 al 16 se necesitan 4 bits.

Cada peón o pieza puede realizar un determinado número de movimientos, de acuerdo a las reglas del ajedrez y a la posición en cada momento. La dama  puede llegar a realizar hasta 28 movimientos distintos. Para registrar un número de 1 a 28 se necesitan 5 bits.

Según esto, necesitamos 9 bits para codificar cada movimiento. Esto es más que los 8,25 del estudio antes mencionado, pero es que los 9 bits de ahora son un valor máximo, fundamentalmente porque el número de movimientos que una pieza puede realizar es muy inferior a los 28 de la dama, incluso esta, en rarísimas ocasiones puede realizar tantos. De lo que se deduce que el número de bits necesarios para codificar el número de movimiento será muy inferior a los 5 antes mencionados. Además, el número de piezas de cada bando va disminuyendo durante la partida, de forma que en promedio se necesitarán menos de 4 bits para codificar este número.

Cuando el número de bits para codificar un elemento es variable, se necesita algún tipo de "delimitador" para separar los distintos elementos a la hora de decodificar, o la utilización de códigos tales que ninguno sea una parte de otro, como es el caso de la compresión tipo Huffman. Añadir delimitadores, o utilizar este tipo de códigos, aumenta el tamaño de la codificación, pero en nuestro caso nada de esto es necesario.

Para saber cual es el número de movimientos que puede realizar la pieza que mueve, la aplicación que va a realizar la decodificación, utilizará las reglas del ajedrez y los mismos supuestos que la aplicación usada para comprimir, de esta forma puede determinar cuantos bits utilizó la aplicación codificadora para anotarlo. Por ejemplo, si la pieza que mueve es un peón que podía avanzar un paso o capturar a derechas, sabe que habrá utilizado 1 bit, que es lo mínimo para especificar una de dos posibilidades, incluso, cuando se trata de jugadas únicas, no hay que codificar ningún bit. Lo mismo podemos decir del número de bits necesarios para especificar el otro elemento del movimiento, el número de la pieza que mueve, si al bando con el turno de juego le quedan siete piezas, se habrá utilizado 3 bits. El hecho de que la aplicación decodificadora vaya reproduciendo la partida según la decodifica es lo que permite lo anterior y además permite saber que pieza es la que mueve y que casilla ocupa, a partir del número de orden y sabiendo que debe ir contando las piezas de este bando desde la casilla a1 hasta la h8, en la forma que antes indiqué.

No he realizado un codificación masiva de partidas, siguiendo este método, por lo que no puedo dar una cifra de bits promedio para un movimiento. Los casos con los que he trabajado indican que el ahorro, respecto a los 8,25 de mis estudios previos, puede ser del 15% o más.

En el caso concreto de la aplicación Capta, el primer elemento de la codificación, el número de la pieza que mueve, está subdividido en dos campos. Un primer bit que indica si mueve un peón o una pieza y el segundo campo que es el número de peón o pieza que mueve, inicialmente 8. Esta variante no es mejor ni peor que numerar conjuntamente piezas y peones, en determinadas circunstancias es más eficiente un sistema y en otras el otro.

En el caso de partidas que empiezan desde una posición determinada, la posición inicial se codifica mediante códigos Huffman.

El resultado de la codificación se precede de tres bits. Los dos primeros permiten incluir un número del 0 al 3 con el siguiente significado:

• 0. Formato actual.

• 1, 2 y 3. Sin uso en la actualidad.

El tercer bit indica:

• 0. Partida normal desde la posición inicial clásica.

• 1. Partida con una posición inicial determinada.

Al final se añaden dos bits (es decir, un número del 0 al 3) para indicar el resultado:

• 0 = 1-0

• 1 = 0-1

• 2 = 1/2-1/2

• 3 = * (en curso)

Y un último bit con el valor 1 que hace de bit de cierre. El número de bits resultante de una codificación, no tiene porque ser múltiplo de 8 (los datos que usan los ordenadores se componen de bytes), por lo que en el último byte habrá bits superfluos, que se ponen expresamente a 0. El bit de terminación permite saber donde empiezan los superfluos.

Para incluir las partidas codificadas en los QR-Code se transforma la corriente de bits en dígitos decimales. El procedimiento es tomar bloques de 13 bits y pasarlos a bloques de 4 dígitos decimales. Es decir, cada 13 bits (números de 0 a 8191)  se transforman en cuatro dígitos decimales. Esta sucesión de números decimales es la que se incluye en el QR-Code.

A continuación se muestra un ejemplo del proceso para codificar la combinación final de la partida Anderssen Dufresne jugada en 1852:

Corriente de bits (226 bits ocupando 29 bytes):

00111101000111010111111000000101101101110010101110010110110011110100000000000000111
10001100011010001010010011000100100110101000100011100001111100111000000001000
100011100000101001101101000111000010110110111010010110111110001001000000

En la que se han marcado los distintos elementos:

00 Formato

1 Partida con una posición inicial determinada.

11101000111010111111000000101101101110010101110010110110011110100000000000000111
10001100011010001010010011000100100110101000100011100001111100111000000001000   Posición inicial codificada Huffman.

100011100000101001101101000111000010110110111010010110111110001 Secuencia de movimientos.

00 Resultado 1-0

1 bit terminador

000000 bits superfluos

La corriente de bits se transforma en la secuencia de dígitos decimales:

1955562407314793348640961932334848823396361517924380066722733514294018

Con la que se genera el QR-Code: