La idea básica de la inducción hacia atrás es comenzar con todas las posiciones finales posibles de un juego en el que el jugador X gana. Entonces, para el ajedrez, mira todas las formas en que las blancas pueden hacer jaque mate a las negras. Ahora trabaje hacia atrás a todos los movimientos / posiciones posibles que le permitirían a las blancas moverse a una de esas posiciones. Si las Blancas alguna vez se encontraran en una posición así, podrían ganar si se movían a la jugada correspondiente de verificación. Ahora trabajamos hacia atrás otro paso y así sucesivamente. Eventualmente volvemos a todos los primeros movimientos posibles que las Blancas podrían hacer. El punto es que, una vez que hayamos hecho esto, sabemos que tenemos la mejor respuesta de las blancas a cualquier movimiento que las negras hagan.
Recientemente (últimos cinco años más o menos) Checkers fue "resuelto" de esta manera. Obviamente, Noughts and Crosses (lo que los coloniales podrían llamar "Tic-Tac-Toe") se ha resuelto durante siglos. Por lo menos desde este xkcd pero presumiblemente mucho antes.
Entonces la pregunta es: ¿de qué factores depende este tipo de procedimiento? El número de posibles posiciones legales, presumiblemente. Pero también quizás el número de movimientos legales en cualquier nodo dado ... Y dado esto, ¿qué tan complejo es este tipo de problema?
Pregunta adicional: ¿cuánto tiempo antes de que una PC de $ 2000 pueda resolver damas en un día? ¿Ajedrez? ¿Vamos? (Por supuesto, para esto también debe tener en cuenta la velocidad cada vez mayor de las computadoras domésticas ...)
Agregué la etiqueta de algoritmos gráficos porque puedes representar estos juegos como árboles, pero si estoy abusando de la etiqueta, agrega algo más apropiado
Respuestas:
Como @Joe señala, el ajedrez es trivial de resolver en el tiempo usando una tabla de búsqueda. (Una implementación real de este algoritmo requeriría un universo significativamente más grande que el que vivimos, pero este es un sitio para la informática teórica . El tamaño de la constante es irrelevante).O ( 1 )
Obviamente no existe una generalización canónica del ajedrez, pero se han considerado varias variantes; su complejidad depende de cómo se generalizan las reglas sobre movimientos sin capturas y posiciones repetitivas .n × n
Si se declara un empate después de un número polinómico de movimientos libres de captura, o después de que cualquier posición repite un número polinómico de veces, entonces cualquier juego de ajedrez termina después de un número polinómico de movimientos, por lo que el problema está claramente en PSPACE. Storer demostró que esta variante es dura para PSPACE.n × n
Para la variante sin límites en posiciones repetidas o movimientos sin captura, el número de posiciones legales de ajedrez es exponencial en n , por lo que el problema está claramente en EXPTIME. Fraenkel y Lichtenstein demostraron que esta variante es EXPTIME-hard.n × n norte
fuente
O(1)
pero en realidad no hay una computadora o algoritmos para resolverlos en un tiempo humano razonable. Sería curioso saber la cantidad de este tipo de problemas para una memoria y un tiempo limitados fijos determinadosProbablemente esta no sea una respuesta terriblemente útil, pero creo que vale la pena señalar que el ajedrez tiene un número máximo de movimientos y, por lo tanto, hay un número finito de juegos posibles. La regla de cincuenta movimientos permite a cualquiera de los jugadores reclamar un empate si se realizan 50 o más movimientos sin mover un peón. Podemos suponer razonablemente que esto siempre se usa, ya que si hay alguna medida objetiva de la fuerza de las posiciones de cada jugador, entonces el más débil reclamará el empate. Además, las reglas del ajedrez requieren que cada vez que se mueva un peón avance una casilla hacia el lado del oponente del tablero (ya sea que se mueva directamente hacia adelante o en diagonal) y, por lo tanto, cada peón puede moverse como máximo 6 veces. Como hay 16 peones en total, esto pone el número máximo de movimientos en . En cada movimiento, el jugador mueve una de las 16 piezas como máximo. Para un peón hay como máximo 3 movimientos, 14 para una torre, 8 para un caballero, 14 para un alfil, 28 para una reina y 8 para un rey, para un total de 132 movimientos posibles. Esto da un límite superior de 132 4851 en el número total de partidas de ajedrez. Entonces, si bien este es un número verdaderamente enorme (aproximadamente 2 34172 ), significa que la complejidad es trivialmente O ( 1 )50 × ( 16 × 6 + 1 ) + 1 = 4851 1324851 234172 O ( 1 ) . Por otro lado, con un enfoque tan ingenuo tomaría aproximadamente cincuenta mil años para que el problema sea manejable, suponiendo que la ley de Moore continuara indefinidamente.
fuente
En realidad, aquí hay un par de preguntas diferentes: (a) ¿cuánta potencia informática se necesita para buscar juegos en el árbol y (b) cuál es la complejidad computacional de estos problemas? El mejor recurso de uso múltiple para este tipo de cosas es probablemente la página de Wikipedia sobre Game Complexity , pero para entrar en un poco más de detalle:
En la práctica, la búsqueda de árbol puro se complementa con un diccionario ascendente; por ejemplo, se conocen los resultados de todos los finales de ajedrez de 6 piezas, y se han analizado muchos finales de 7 piezas (ver http://en.wikipedia.org/wiki/Endgame_tablebase ), por lo que el resultado de una rama del juego puede ser buscó en el 'diccionario' (una gran base de datos de posiciones) una vez que la posición se ha reducido a pocas piezas suficientes, atajando una gran cantidad de búsqueda de árbol adicional que de lo contrario sería necesaria. Esto es lo que se hizo con los verificadores: se crearon bases de datos de todos los finales con suficientes piezas, luego se extendieron para agregar más piezas y más, hasta que se conocieron los resultados de todos los finales de 10 piezas; luego se utilizó la búsqueda de árboles desde la posición inicial, y esencialmente los dos se encontraron en el medio.
Sin embargo, más allá de estos enfoques prácticos, está el lado (b) de la pregunta: ¿cuál es la complejidad computacional de este tipo de problemas? En resumen, la mayoría de los problemas de este tipo tienden a caer en un par de categorías; son PSPACE-complete, lo que significa aproximadamente 'si puedes resolver esto, puedes resolver cualquier problema que requiera mucho espacio polinomial', o EXPTIME-complete (lo que significa aproximadamente 'si puedes resolver esto, puedes resolver cualquier problema eso lleva exponencialmente mucho tiempo '), dependiendo de cuánto tiempo pueda durar el juego; Una vez más, la página de Wikipedia sobre la integridad EXPTIME tiene una muy buena discusión sobre los problemas involucrados y lo que diferencia a los diferentes juegos en este frente.
fuente
Estas estimaciones son demasiado altas.
Te enfocas en ramificarte en base a movimientos legales. Esto tiene mucho sentido si está tratando de hacer una computadora de ajedrez rápida, pero no es así como escribiría un programa para "resolver" el ajedrez.
Hay <<<<< 13 ^ 64 estados de juego posibles en el ajedrez. Cada casilla solo puede contener una de las piezas de ajedrez o nada. Puede iterar a través de todos ellos y marcarlos como victorias negras o victorias blancas en no más de 2 ^ 256 más o menos operaciones.
Una suposición más realista del número de estados de juego razonablemente alcanzables es de alrededor de 2 ^ 100
fuente