Codificando el tres en raya en 15 bits
Codificar un tablero de tres en raya de la forma más compacta posible se convierte en un terreno de juego para la teoría de la información, con personas explorando esquemas desde codificaciones simples en base 3 (15 bits para 9 casillas) hasta 13 bits al enumerar solo estados de partida válidos y alcanzables. Otros van más allá al codificar historiales completos de la partida en menos de 20 bits o al aprovechar la simetría y el juego óptimo para podar estados imposibles o redundantes, mientras discuten cuándo esta compresión es realmente útil y cuándo solo complica el código. En el camino, el hilo toca ideas relacionadas como tablas de búsqueda frente a codificaciones algorítmicas, algoritmos genéticos que evolucionan jugadores perfectos y analogías con juegos y rompecabezas más complejos como el ajedrez, Conecta 4 y acertijos mecánicos.
Codificación del estado del tablero y recuento de bits
- El artículo principal codifica un tablero de tres en raya en 9 dígitos en base 3 → 15 bits.
- Varios comentaristas muestran una compresión adicional:
- Contar todos los tableros legales alcanzables da 5.478 estados, así que bastan 13 bits sin simetría.
- Una implementación codifica tableros en [0, 6045] mediante combinaciones (“elegir las casillas ocupadas, luego elegir las O entre ellas”), lo que también encaja en 13 bits.
- Otros señalan que un esquema ingenuo de “10 bits para 765 estados” asume tableros deduplicados por simetría; las partidas reales necesitan bits extra para la orientación (rotación/volteo), volviendo a ~13 bits.
Simetría, legalidad y casos límite
- El manejo de la simetría es complicado: algunos tableros necesitan 3 bits para desambiguar rotación+reflexión, algunos menos y otros cero (totalmente simétricos).
- Es necesario contar solo tableros “legales y alcanzables” (respetando el orden de turnos y sin seguir jugando tras una victoria); los scripts iniciales tenían errores en la detección de victorias en diagonal, inflando ligeramente los recuentos.
- Existen estados inalcanzables (ambos jugadores con una línea ganadora, o múltiples victorias disjuntas), que deben excluirse.
Codificación de historiales completos de partida
- Varios esquemas para codificar secuencias completas de juego:
- Límite simple basado en factoriales: 9! ≈ 19 bits para todas las permutaciones de jugadas; depurar partidas inválidas ahorra solo ~1 bit.
- Un comentarista argumenta rigurosamente que 18 bits no pueden codificar todas las secuencias posibles (se necesitan ≥19 bits); otra propuesta de 18 bits muestra un uso incorrecto de patrones de bits “sobrantes”.
- Otras ideas:
- Codificaciones de longitud variable que se detienen cuando alguien gana.
- Aprovechar la simetría para reducir las opciones del primer movimiento (equivalencia entre esquina/borde/centro).
Estrategias, IA y juego humano
- Discusión sobre el juego minimax: el juego óptimo conduce al menos a un empate; algunos sostienen que, contra oponentes humanos, una estrategia no minimax de “tender trampas” puede ganar más a menudo.
- Aparecen sistemas históricos/educativos: un aprendiz por refuerzo basado en matchboxes, estrategias de lógica booleana, algoritmos genéticos sobre todos los estados del juego.
Representaciones, tablas de búsqueda y compromisos
- Debate sobre si las tablas de búsqueda son “hacer trampa”: las cadenas de condiciones y los arreglos son funcionalmente equivalentes; se sugiere juzgar las soluciones por el total de bits de datos+código.
- Algunos señalan que, incluso si existen codificaciones canónicas de 10 bits, los sistemas prácticos podrían mantener una tabla de mapeo hacia una estructura más conveniente de 13–18 bits.
- Aclaraciones sobre trits frente a bits: 9 trits caben en 15 bits binarios; no se asume hardware ternario.