Comprimir jugadas de ajedrez por diversión y beneficio

Artículo original ↗ Discusión en Hacker News ↗

Enfoque general

  • La discusión se centra en hasta qué punto se pueden comprimir partidas de ajedrez más allá de PGN, aprovechando la estructura del juego, las distribuciones no uniformes de jugadas y las predicciones de motores.
  • Hay una tensión recurrente entre la “compresión máxima” y la “simplicidad, velocidad y capacidad de consulta”.

Compresión genérica vs específica del dominio

  • Varios sugieren probar compresores estándar (gzip, zstd, LZW, diccionarios entrenados) sobre listas de jugadas o listas de partidas ordenadas como referencia.
  • Otros argumentan que los compresores generales no pueden aprovechar la estructura específica del ajedrez (jugadas legales, estado del tablero) tan bien como las codificaciones personalizadas.
  • Algunos creen que un buen diccionario de zstd o formatos columnares sobre posiciones podría acercarse “gratis”, pero esto sigue sin probarse en el hilo.

Codificaciones a nivel de jugada y de partida

  • Muchos proponen codificaciones simples de ancho fijo:
    • 12–16 bits: casillas de origen + destino (6+6 bits), con promociones/enroques inferidos o señalados mediante destinos “imposibles” o bits extra.
    • Índice de pieza + patrón de movimiento relativo, aprovechando que cada bando tiene como máximo 16 piezas; se discuten esquemas que alcanzan ~6–9 bits/jugada.
  • Esquemas más avanzados:
    • Indexar la jugada elegida entre todas las jugadas legales en la posición actual; con ~n jugadas legales, se necesitan ~log₂(n) bits; las estimaciones prácticas son ≲6–8 bits/jugada.
    • Usar códigos de longitud variable (Huffman, codificación aritmética, ANS/rANS, CABAC) con distribuciones de probabilidad por posición.
    • Las probabilidades guiadas por motores (como Stockfish o motores más débiles) podrían, en teoría, llegar a ~3–4 bits/jugada, posiblemente menos, pero con un alto coste de CPU y una fuerte dependencia de versiones concretas del motor.
  • Un seguimiento del autor del artículo (enlazado repetidamente) informa de ~3.7 bits/jugada usando codificación aritmética y generación rápida de jugadas.

Posiciones, indexación y búsqueda

  • Varios señalan que en las bases de datos reales, el almacenamiento suele estar dominado por los índices de búsqueda, no por los datos brutos de las partidas.
  • Ideas para indexar:
    • Hashing Zobrist y estructuras al estilo de tablas de transposición.
    • Filtros Bloom o filtros Bloom particionados para comprobaciones de existencia frente a tablas hash completas para búsqueda O(1).
    • Almacenamiento columnar de estados del tablero (columnas por casilla) con compresión estándar y luego referencia a las posiciones por desplazamiento.
    • Técnicas para búsqueda de posiciones “difusa” (por ejemplo, distancia de Hamming en bitboards, ideas tipo MinHash), aunque las soluciones prácticas siguen sin estar claras.

Compromisos y preocupaciones prácticas

  • Muchos destacan que una compresión extrema puede perjudicar:
    • La velocidad de decodificación (generación completa de jugadas, llamadas al motor).
    • El acceso aleatorio y las consultas complejas (por ejemplo, exploradores de aperturas, búsqueda de patrones en finales).
    • La mantenibilidad; los esquemas muy densos e ingeniosos pueden ser difíciles de entender para desarrolladores futuros.
  • Algunos señalan que PGN es despilfarrador pero legible para humanos; en muchos casos del mundo real, la latencia de E/S y la estrategia de consulta importan más que exprimir hasta el último bit del almacenamiento de jugadas.