Codificando jogo-da-velha em 15 bits
Codificar o jogo-da-velha da forma mais compacta possível vira um playground de teoria da informação, com pessoas explorando esquemas que vão desde codificações simples em base 3 (15 bits para 9 casas) até 13 bits ao enumerar apenas estados válidos e alcançáveis. Outros vão mais longe ao codificar históricos inteiros de jogo em menos de 20 bits ou ao explorar simetria e jogo ótimo para podar estados impossíveis ou redundantes, enquanto debatem quando essa compressão realmente é útil e quando só complica o código. Ao longo do caminho, a discussão toca em ideias relacionadas como tabelas de busca versus codificações algorítmicas, algoritmos genéticos que evoluem jogadores perfeitos e analogias com jogos e quebra-cabeças mais complexos, como xadrez, Connect-4 e charadas mecânicas.
Codificação do estado do tabuleiro e contagem de bits
- O artigo principal codifica um tabuleiro de jogo-da-velha em 9 dígitos em base 3 → 15 bits.
- Vários comentadores mostram compressão adicional:
- Contar todos os tabuleiros legais alcançáveis dá 5.478 estados, então 13 bits bastam sem simetria.
- Uma implementação codifica tabuleiros em [0, 6045] via combinações (“escolher as casas preenchidas, depois escolher os O entre elas”), também cabendo em 13 bits.
- Outros observam que um esquema ingênuo de “10 bits para 765 estados” assume tabuleiros sem duplicação por simetria; jogos reais precisam de bits extras para orientação (rotação/reflexão), voltando para ~13 bits.
Simetria, legalidade e casos especiais
- O tratamento de simetria é complicado: alguns tabuleiros precisam de 3 bits para desambiguar rotação + reflexão, alguns precisam de menos e alguns de zero (totalmente simétricos).
- É necessário contar apenas estados “legais e alcançáveis” (respeitando a ordem das jogadas e sem continuar após uma vitória); scripts iniciais tinham erros na detecção de vitórias diagonais, inflando ligeiramente as contagens.
- Existem estados inalcançáveis (ambos os jogadores com uma linha vencedora, ou várias vitórias disjuntas), que devem ser excluídos.
Codificando históricos completos de jogo
- Vários esquemas para codificar sequências inteiras de jogadas:
- Limite simples baseado em fatoriais: 9! ≈ 19 bits para todas as permutações de jogadas; podar jogos inválidos economiza apenas ~1 bit.
- Um comentador argumenta rigorosamente que 18 bits não podem codificar todas as sequências possíveis (é preciso ≥19 bits); outra proposta de 18 bits é mostrada como uso indevido de padrões de bits “sobrando”.
- Outras ideias:
- Codificações de comprimento variável que param quando alguém vence.
- Explorar simetria para reduzir as opções da primeira jogada (equivalência entre canto, borda e centro).
Estratégias, IA e jogo humano
- Discussão sobre minimax: jogo ótimo leva a pelo menos um empate; alguns argumentam que, contra oponentes humanos, estratégias não-minimax de “armar armadilhas” podem vencer com mais frequência.
- Aparecem sistemas históricos/educacionais: aprendiz por reforço baseado em matchboxes, estratégias de lógica booleana, algoritmos genéticos sobre todos os estados do jogo.
Representações, tabelas de busca e trade-offs
- Debate sobre se tabelas de busca são “trapaça”: cadeias de condições e arrays são funcionalmente equivalentes; sugere-se julgar soluções pelo total de bits de dados + código.
- Alguns observam que, mesmo que existam codificações canônicas de 10 bits, sistemas práticos podem manter uma tabela de mapeamento para uma estrutura mais conveniente de 13–18 bits.
- Esclarecimentos sobre trits versus bits: 9 trits cabem em 15 bits binários; não se assume hardware ternário.