Las piezas son animales de costumbres

(2ª parte aquí)

Todos estamos de acuerdo con esto. Aunque durante la partida una pieza puede alcanzar cualquier casilla, con las excepciones conocidas de peones y alfiles, cada una tiene sus propias querencias y tiende a pasar la mayor parte de su vida en unas cuantas casillas y muy pocas veces en las restantes. Si alguien me pregunta por el caballo de rey, le diré que, primero, mire en la casilla f3 y que no se moleste en mirar en la casilla a1, porque nadie recuerda haberlo visto por allí. Más difícil resulta indicar donde buscar al alfil de dama, o al peón c.

Hoy es fácil conseguir una gran cantidad de partidas entre buenos jugadores y repasar, una por una, las distintas posiciones para ver cuales son las casillas preferidas de cada pieza. Los resultados de hacerlo con 308.138 partidas (23.465.000 posiciones), donde al menos uno de los dos jugadores tenía un Elo de 2500 o más, se muestran de forma gráfica en las imágenes siguientes. Hay una imagen por cada tipo de pieza y color: rey negro, rey blanco, dama negra, dama blanca, etc. Las casillas más claras son aquellas en las que más veces se encuentra a la pieza en cuestión.

No se indica a que pieza corresponde cada imagen, porque seguro que el lector sabrá identificarlas, pero tenga en cuenta que una de las imágenes es la correspondiente a las casillas vacías, en este caso las más claras son las que más tiempo permanecen vacías. Luego, en el pie de página, puede comprobar si las acertó todas.

1	2
3	4
5	6
7	8
9	10
11	12
13

¿Sirven estas estadísticas para mejorar nuestro juego?. La respuesta es que, nunca se sabe, pero probablemente no. Entonces ¿son una simple curiosidad?. Nuevamente, la respuesta es no, estas imágenes tienen una importante utilidad para una aplicación de la informática al ajedrez: las bases de datos. La información contenida en estas imágenes permite registrar las posiciones de una partida de una forma muy compacta y con ello reducir el espacio necesario para registrar millones de partidas, o reducir el tiempo para encontrar una posición de entre varios millones. Vamos a explicarlo, pero antes haremos una introducción a la teoría de la compresión.

Los métodos de compresión de datos se dividen en dos grupos, los que trabajan sustituyendo los caracteres, que componen la secuencia a comprimir, uno a uno, por códigos más pequeños y los que sustituyen grupos de caracteres. Los archiconocidos zip son del segundo tipo. Una posición de ajedrez es una pieza de información relativamente pequeña y no es probable encontrar suficientes grupos de caracteres repetidos cuya sustitución ahorre espacio, por lo que el método de compresión más adecuado, y de hecho el más empleado, es el primero.

El campeón de los métodos de sustitución carácter a carácter es debido a Huffman que en 1952 lo publicó como una mejora al propuesto, unos años antes, por Shanon. Sólo un nuevo método, denominado de compresión aritmética, cuya aplicación práctica no ha sido posible hasta hace muy pocos años, amenaza la supremacía del viejo campeón, como veremos más adelante.

Cuando todos los caracteres que forman la secuencia a comprimir aparecen con la misma frecuencia, es decir, el mismo número de veces, poco se puede hacer para comprimir el texto inicial. Pero si esto no ocurre, y algunos símbolos aparece con mayor frecuencia, se puede diseñar un conjunto de códigos de longitud variable que permite la compresión. La clave es asignar los códigos de menor tamaño a los símbolos más frecuentes, aunque haya que usar códigos largos para los símbolos que menos veces aparecen.

Podemos codificar una posición de ajedrez formando una secuencia de caracteres. Recorremos las 64 casillas y vamos escribiendo la inicial de la pieza (en mayúsculas para las blancas y minúsculas para las negras) que ocupa cada una de ellas, o un cero si la casilla está vacía. La posición inicial daría lugar a la siguiente secuencia:

tcadractpppppppp00000000000000000000000000000000PPPPPPPPTCADRACT

Sin usar métodos de compresión se necesitan 32 octetos (el octeto, o byte, es la unidad de información que más se usa en informática) para registrar esta posición.

Salta a la vista que hay caracteres que se repiten mucho más que otros. Las casillas vacías son las que más (32 veces) y luego los peones blancos y negros (8 de cada). Por lo tanto, nos encontramos ante una situación apropiada para que el método de Huffman consiga reducciones importantes. El juego de códigos, que se considera “estándar”, para codificar posiciones de ajedrez, consigue reducir, la posición inicial, de 32 bytes, a tan sólo 21. Cuando se codifican las 23.465.000 posiciones, de las 308.138 partidas que estamos usando en este estudió, se obtiene que, por término medio, se necesitan 17,5 bytes para codificar una posición.

El método de compresión aritmética también se basa en las diferentes probabilidades de cada uno de los símbolos a codificar y es mucho más sensible a estas probabilidades que el método de Huffman. Si se utilizan las frecuencias de aparición de la piezas en la posición inicial (las que dan lugar al juego de códigos estándar de Huffman) :

El método de compresión aritmética, aplicado a la posición inicial, consigue comprimirla en 21 bytes, es decir, lo mismo que el método de Huffman. En el caso del tablero vacío (64 casillas vacías), la compresión aritmética necesita 9 bytes, uno más que Huffman que sólo emplea 8 bytes.

Pero si se usan las frecuencia medias que resultan al tratar las 23.465.000 posiciones que estamos utilizando en este estudió:

La compresión aritmética comprime la posición inicial en 22 bytes y el tablero vacío en 6 bytes. Por su parte, el método de Huffman obtiene los mismos resultados que antes: 21 bytes para la posición inicial y 8 para el tablero vacío.

Fíjese el lector, que en el caso del tablero vacío estamos tratando una secuencia de 64 elementos y que la compresión aritmética la comprime en 6 bytes (en realidad en menos, ya que es capaz de comprimir una secuencia de 70 casillas vacías en esos mismos 6 bytes), que son 48 bits. !! Usa menos de un bit por carácter !!. Este es el gran mérito de este método que es capaz de usar "fracciones" de bit, cosa que no puede hacer el método de Huffman.

Dado que cualquier otra posición necesita valores intermedios (salvo posiciones singulares que nunca se verán en una partida real), el método aritmético es mejor que el de Huffman, tal como la teoría general indica, también para el caso de comprimir posiciones de ajedrez.

Para hacerse una idea de las diferencias que cabe esperar entre la compresión aritmética y el método de Huffman se han aplicado ambos métodos a las 117.074 posiciones existentes en 1.563 partidas jugadas por Kramnik. Los resultados fueron: 17,50 bytes para el método de Huffman (igual que para el ejercicio con 308.138 partidas) y 17,32 bytes para la compresión aritmética. Más adelante veremos como esta diferencia se hace mucho mayor al introducir las mejoras que a continuación se comentan.

Pero ahora se trata de que empleemos nuestros conocimientos de ajedrez. Sabemos que nunca encontraremos un peón, ni blanco ni negro, en la primera o en la última fila. De acuerdo con esto, podemos, separar el tablero en tres zonas y usar un juego de códigos diferente para caza zona. La zona 1 será la primera fila, la zona 2, la formada por las filas 2 a 7 y la zona 3, la fila 8. Al ser los peones piezas con alta frecuencia de aparición, el juego de códigos Huffman “estándar” les asigna uno de los de menor tamaño, sabiendo que en las filas 1 y 8 no están presentes, esté código corto se puede asignar a otra pieza y por tanto reducir el tamaño final de la posición codificada.

Si volvemos a codificar nuestros más de 23 millones de posiciones con estos tres juegos de códigos, el tamaño medio de las posiciones codificadas es de 15,6 bytes.

Siguiendo la misma línea de razonamiento, ¿porqué no usar un juego de códigos para cada línea?, durante muchas jugadas, las piezas blancas y las negras permanecerán en su propia mitad del tablero y podremos usar los códigos más cortos para las blancas en las 4 primeras filas y para las negras en las otras cuatro. El resultado de usar códigos por filas reduce a 14,4 bytes el tamaño medio de la posición codificada.

Llegados hasta aquí, el paso siguiente es evidente, usemos un juego de códigos para cada una de las 64 casillas. La información que necesitamos para asignar los códigos a las piezas es precisamente la contenida en las imágenes con las que comenzamos estas notas, pero ordenada de otra forma. En lugar de cuales son las casillas preferidas por cada pieza, lo que nos interesa es, para cada casilla, cual es el número de veces que encontramos en ella a cada una de las piezas. A continuación se muestra la distribución de piezas para algunas casillas.

casilla	r   d  t  a  c  p vac. P  C  A   T  D  R
c7
e4
f3
g1
g8

Pues bien, con este último avance, la longitud media de las posiciones comprimidas se sitúa en 13,3 bytes, es decir, 4,2 bytes menos (un 25% menos) que la compresión con un solo juego de caracteres. 

Pero antes de terminar, volvamos a considerar el método de compresión aritmética. Cuando se diferencia por casillas, las frecuencias de aparición de las distintas piezas, en cada casilla, son más dispersas (la diferencia entre la mayor frecuencia y la mínima es mucho mayor) y el método de compresión aritmética puede sacar más partido de esto, que el de Huffman. Los resultados, para los más de 23 millones de posiciones con los que se ha realizado este estudio, son que el método aritmético necesita un promedio de tan sólo 11,8 bytes por posición, un 10% menos que los 13,3 empleados por el de Huffman. Esta es una diferencia suficientemente importante, como para tomar muy en serio la compresión aritmética.

Aún se puede “afeitar un poco más el huevo” al tomar en consideración características propias de las posiciones durante una partida de ajedrez. Por ejemplo, se puede usar una nueva pieza: el “rey enrocable” corto y largo. Si el rey y las torres blancas (igual para las negras) se mantienen en sus posiciones iniciales, podemos incluir un solo código en lugar de los tres correspondientes al rey y ambas torres. Quizás se pueda sacar provecho de que ambos reyes siempre están en el tablero, o de que como máximo hay ocho peones por bando, etc.

Las ganancias de estas sutilezas deben ser menores y damos por finalizadas estas notas, sobre como estrujar las posiciones de ajedrez, sin más que añadir la tabla en la que se muestra, para cada pieza, la casilla que más frecuenta (Max), la siguiente en preferencia (SubMax) y la que menos (Min).

Alberto Bañón Serrano
alberto@interajedrez.com

La segunda parte de este artículo puede leerla aquí

Notas al texto:

Resultados para un número mayor de partidas.

Los resultados para 658.960 partidas (50.139.940 posiciones) donde al menos uno de los jugadores tiene un Elo de 2400 o más, son exactamente los mismos.

Intensidad del color en las imágenes.

En general, la diferencia entre la casilla más frecuentemente ocupada y la menos es enorme, si la intensidad del color de cada casilla se hace proporcional a la frecuencia con que es ocupada cada una de ellas, se ve una casilla blanca y todas las demás negras, si acaso alguna más gris. Para que se vean más casillas, la intensidad del color se ha hecho proporcional a la raíz cuadrada de la frecuencia de ocupación.

Gráficos de cada pieza.

1=A; 2=t; 3= p; 4= c; 5 =D; 6=C; 7=R; 8=Casillas vacías; 9=a; 10=r; 11=d; 12=T; 13=P