Comprimir jugadas de ajedrez por diversión y beneficio

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

Los esfuerzos por comprimir partidas de ajedrez mucho más allá del PGN legible por humanos generan una variedad de ideas, desde codificaciones simples de ancho fijo de casillas de origen–destino hasta esquemas sofisticados que usan motores, modelos de probabilidad, Huffman o codificación aritmética, e incluso ANS. Los comentaristas debaten los límites teóricos de bits por jugada, la practicidad de predictores basados en motores a gran escala y cómo se comparan los formatos personalizados con herramientas genéricas como gzip o zstd. Muchos concluyen que, para bases de datos grandes, el problema más difícil e importante es la indexación eficiente y la búsqueda difusa de posiciones, siendo útil la compresión sobre todo en la medida en que reduzca la E/S sin complicar demasiado las consultas.

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.