En teoría de juegos, Tic Tac Toe se clasifica como un juego secuencial finito con información perfecta. En otras palabras, los jugadores se turnan, solo puede haber un número limitado de turnos antes de que termine el juego, y cada jugador conoce el estado completo del juego en todo momento. Dichos juegos generalmente se analizan usando un árbol de juegos, que traza todas las secuencias posibles de movimientos comenzando desde el estado inicial del juego. Esto forma un árbol, en el que cada nodo es una decisión de un jugador u otro.
Una vez mapeado el árbol, comienza en la parte inferior del árbol (todos los diferentes estados finales posibles del juego) y avanza hacia arriba desde cada estado final posible, eliminando las rutas en las que un jugador toma una decisión que lleva a ese jugador perdiendo. En la parte inferior, es obvio qué decisiones eliminar, porque conducen directamente a perder. A medida que avanzas hacia arriba a través del árbol, aún es posible saber qué decisiones eliminar, porque ya has evaluado cómo progresará el juego en cada una de las posibles rutas desde ese punto. Eventualmente, habrás abierto tu camino a través del árbol completo, de regreso al comienzo del juego, y puedes demostrar que si cada jugador juega correctamente, ningún camino desde ese punto de partida conduce a la victoria para ninguno de los jugadores.
Este enfoque es tedioso, pero está garantizado que funcionará, no solo para Tic Tac Toe sino para cualquier juego similar. Incluso el ajedrez es teóricamente solucionable por este método, pero la potencia de cómputo requerida es tan grande que incluso si convirtiera toda la materia del universo en una computadora, no sería lo suficientemente potente.
- ¿Por qué los matemáticos están fascinados por los números primos y cómo se puede compartir su fascinación con los no matemáticos?
- ¿Cómo se relacionan la topología y la programación lineal?
- Si 2 ^ x-1 es una pseudoprima de Fermat, ¿es xa pseudoprima de Fermat?
- ¿Cómo encontramos una forma cerrada en términos de [matemáticas] n [/ matemáticas] para [matemáticas] \ displaystyle \ prod_ {i = 1} ^ {n} (3i-2) [/ matemáticas]?
- Si un video se repite un número infinito de veces, reproduciéndose el doble de rápido cada vez, ¿cuánto dura?
En el caso de Tic Tac Toe, probablemente haya pruebas más elegantes disponibles. Una forma obvia de reducir el tedio del método de fuerza bruta es aprovechar la simetría: el tablero se puede girar sin cambiar el estado del juego, por lo que no tiene que evaluar por separado un tablero con XYX a lo largo de la fila superior y un tablero con XYX a lo largo de la fila lateral. Son idénticos para fines estratégicos.
