Comprimindo jogadas de xadrez por diversão e lucro
Foco geral
- A discussão se concentra em até que ponto é possível comprimir partidas de xadrez além do PGN, explorando a estrutura do jogo, distribuições não uniformes de jogadas e previsões de engines.
- Há uma tensão recorrente entre “compressão máxima” versus “simplicidade, velocidade e capacidade de consulta”.
Compressão genérica vs. específica de domínio
- Vários sugerem tentar compressores padrão (gzip, zstd, LZW, dicionários treinados) em listas de jogadas ou listas de partidas ordenadas como linha de base.
- Outros argumentam que compressores gerais não conseguem explorar a estrutura específica do xadrez (jogadas legais, estado do tabuleiro) tão bem quanto codificações personalizadas.
- Alguns acham que um bom dicionário zstd ou formatos colunares sobre posições poderia chegar perto “de graça”, mas isso continua sem teste no tópico.
Codificações por jogada e por partida
- Muitos propõem codificações simples de largura fixa:
- 12–16 bits: origem + destino das casas (6+6 bits), com promoções/roques inferidos ou sinalizados via destinos “impossíveis” ou bits extras.
- Índice da peça + padrão de movimento relativo, explorando que cada lado tem no máximo 16 peças; são discutidos esquemas chegando a ~6–9 bits/jogada.
- Esquemas mais avançados:
- Indexar a jogada escolhida entre todas as jogadas legais na posição atual; com ~n jogadas legais, você precisa de ~log₂(n) bits; estimativas práticas ficam em ≲6–8 bits/jogada.
- Usar códigos de comprimento variável (Huffman, codificação aritmética, ANS/rANS, CABAC) com distribuições de probabilidade por posição.
- Probabilidades guiadas por engine (como Stockfish ou engines mais fracas) poderiam, em teoria, chegar a ~3–4 bits/jogada, possivelmente menos, mas com alto custo de CPU e forte acoplamento a versões específicas da engine.
- Um acompanhamento do autor do artigo (linkado repetidamente) relata ~3,7 bits/jogada usando codificação aritmética e geração rápida de jogadas.
Posições, indexação e busca
- Vários apontam que, em bancos de dados reais, o armazenamento é frequentemente dominado por índices de busca, não pelos dados brutos das partidas.
- Ideias para indexação:
- Hashing Zobrist e estruturas no estilo de tabela de transposição.
- Bloom filters ou Bloom filters particionados para checagens de existência em vez de tabelas hash completas para busca O(1).
- Armazenamento colunar de estados do tabuleiro (colunas por casa) com compressão padrão e depois referência às posições por deslocamento.
- Técnicas para busca de posições “fuzzy” (por exemplo, distância de Hamming em bitboards, ideias parecidas com MinHash), embora soluções práticas permaneçam obscuras.
Compromissos e preocupações práticas
- Muitos enfatizam que compressão extrema pode prejudicar:
- Velocidade de decodificação (geração completa de jogadas, chamadas de engine).
- Acesso aleatório e consultas complexas (por exemplo, exploradores de abertura, busca de padrões de finais).
- Manutenibilidade; esquemas muito densos e engenhosos podem ser difíceis para desenvolvedores futuros entenderem.
- Alguns observam que o PGN é ineficiente, mas legível para humanos; em muitos casos do mundo real, a latência de I/O e a estratégia de consulta importam mais do que espremer os últimos bits do armazenamento de jogadas.