Todos conocen el juego tic-tac-toe 3x3. Con el juego correcto, el primer movimiento de los cruces resulta en un empate. Puede crear manualmente un árbol de movimientos, donde para cualquier movimiento de ceros, hay un movimiento de cruces que conduce al mejor resultado (para cruces), es decir, a un empate o una victoria. Este árbol de movimientos agota todas las opciones, por lo que dicen que el juego está "resuelto". Hay una variedad tridimensional de tic-tac-toe 4x4x4 para la cual la respuesta a la pregunta de quién ganará el primer movimiento de los tic tacs no es obvia. Además, surge la pregunta de si es posible construir un árbol tan mínimo que resuelva este problema.
La respuesta a esta pregunta está debajo del corte.
Déjame recordarte qué es el juego tic-tac-toe 4x4x4 (también se llama Qubic).
Este es un cubo que consta de 64 campos en los que ganar, debe poner 4 cruces o ceros consecutivos, y pueden ir a lo largo de cualquier línea, incluidas las diagonales principales. En total hay 76 de estas líneas: 48 contornos y verticales, 24 diagonales y 4 diagonales principales. Dado esto, se puede observar que no todos los campos son iguales: hay 8 campos angulares y 8 centrales que controlan 7 líneas y 48 otros campos que controlan 4 líneas. Por lo tanto, tiene sentido tratar de tomar posiciones que controlen más líneas.
¿Cuál es la dificultad de construir un árbol de decisión para este juego? Aproximadamente se puede estimar como 2 en un grado de 64 opciones, que es bastante. Por supuesto, no todas estas opciones se implementan en el juego y muchas ramas del árbol se cortan lo suficientemente rápido, pero incluso en este caso, la construcción de dicho árbol por simple enumeración no es posible. ¿Cómo podemos reducir la búsqueda para resolver este problema? Puede notar que después de varios movimientos de cruces y ceros, puede surgir una situación en la que es posible crear una amenaza para el enemigo al poner tres cruces o ceros en una línea. Con tal amenaza, el enemigo se ve obligado a hacer su próximo movimiento al espacio vacío restante en esta línea, de lo contrario perderá en el siguiente movimiento. Tales movimientos con una amenaza se pueden hacer varios seguidos, si hay un número suficiente de líneas en las que solo hay dos cruces o, respectivamente, un cero. Si dicha cadena de movimientos conduce a una situación en la que hay dos líneas con tres cruces o ceros, entonces el jugador correspondiente pierde. Esto se llama una victoria forzada.
Numeramos todos los campos con números del 0 al 63 comenzando desde la cara superior y siguiendo líneas horizontales de izquierda a derecha.
Ilustramos esto con un ejemplo de un juego:
0-3-60-21-15-51-12-63 4x8x5x10x20x40x28x44x24x16x36x52x48
Aquí, las cruces hacen el primer movimiento hacia la esquina más a la izquierda en la cara superior (0), luego los ceros responden a la esquina más a la derecha en la misma cara (3). Las cruces van a la esquina cercana izquierda en el borde inferior (60), los ceros corresponden en el campo al segundo desde el borde superior, etc. Después de que el dedo del pie se mueva en 63, las cruces comienzan una secuencia de movimientos forzados: 4 - verificación. Tac-toe se ve obligado a responder a las 8, la cruz es 5 check, tac-toe se responde a las 10, etc. hasta que se formen dos líneas con tres cruces en las cruces. Tac toe perdido.
Para resolver este juego, necesitas encontrar tales secuencias para todos los movimientos posibles del tac toe. Para una solución óptima, tales secuencias deberían ser mínimas.
Excursión histórica
El primero en resolver este juego fue Patashnik a principios de los 80. Seleccionó manualmente las combinaciones iniciales, y luego buscó un movimiento ganador usando una computadora. Mostró que si los cruces van a la esquina, siempre ganan con el juego correcto. El siguiente paso fue tomado por Victor Allis. En su disertación a mediados de los 90, demostró que se puede obtener una solución completamente en una computadora. Sin embargo, no marcó todas las opciones que los cruces pueden ganar, sino solo las diez primeras, las más prometedoras. Por lo tanto, su solución no fue óptima y dejó esta tarea a otros investigadores.
Decidí resolver este problema de una manera óptima, es decir, encontrar un árbol mínimo. Obviamente, para esto es necesario utilizar la búsqueda de amplitud, en lugar de la búsqueda de profundidad de Allis. En primer lugar, se implementó la búsqueda de ganancias forzadas por una situación arbitraria. Resultó, sin embargo, que resultó ser bastante lento, ya que la búsqueda profunda de la recompensa forzada para combinaciones largas es bastante costosa. La solución se encontró agregando un repositorio de opciones ya calculadas en std :: unordered_set. Vale la pena decir que el campo de juego se codificó en forma de dos variables de 64 bits, una para cruces, otra para ceros, donde 1 significa la presencia de una cruz o un cero en el campo correspondiente. Tal almacenamiento en caché proporcionó una aceleración significativa. Sin embargo, el problema principal era una búsqueda amplia de movimientos sin fuerza. En una búsqueda normal sin optimización, el cálculo no terminó en un tiempo razonable.
Tuve que recurrir al almacenamiento en caché de nuevo. Se agregó otro byte al campo de juego calculado con el resultado de calcular el subárbol para esta opción de organizar el tic tac toe. Al mismo tiempo, la codificación del campo de juego comenzó a ocupar 17 bytes. Por lo tanto, al buscar en ancho y aumentar gradualmente la profundidad de un árbol, los subárboles ya calculados podrían descartarse. Con esto, pude calcular los árboles mínimos
para el primer movimiento de la cruz a la esquina (celda 0) y las respuestas de los ceros a todos los campos que controlan en cuatro líneas.
Surgieron dificultades si el tac toe tomó el campo que controlaba siete líneas en el primer movimiento de represalia. En este caso, el caché ocupado por el caché excedió los 32 gigabytes de RAM, y mi Linux entró en un intercambio. Era necesario buscar otra solución.
Luego me volví al hecho de que el campo de juego tiene muchos automorfismos, es decir, si encuentra una solución para una combinación de cruces y ceros, las combinaciones correspondientes a diferentes rotaciones y reflejos también tendrán una solución. Cabe señalar que gracias a estos automorfismos, el primer movimiento de los cruces solo tiene dos opciones: una en el campo 0 (controlando 7 líneas) y otra en el campo 1 (controlando 4 líneas). Por lo tanto, en mi caso, el primer movimiento que hacen las cruces siempre en el campo 0. Pero esto es cierto solo para un campo vacío.
Sin embargo, volvemos a los automorfismos para un campo de juego arbitrario. ¿Cómo encontrarlos a todos?
Utilicé el siguiente método: dado que el cubo tiene tres dimensiones, puede reorganizar las coordenadas (habrá 6 permutaciones de este tipo) y hacer reflexiones (habrá 8 de ellas). Por lo tanto, habrá 48 automorfismos espaciales en total, sin embargo, el cubo tiene dos automorfismos internos más. Uno permuta las coordenadas de los campos en el primer y segundo par en cada línea,
y el segundo deja el primer y último campo en su lugar, y reorganiza solo las coordenadas para el segundo y tercer campo. Estos dos automorfismos también se pueden aplicar simultáneamente. Por lo tanto, para cada uno de los 48 automorfismos espaciales, hay cuatro
(incluidos triviales) automorfismos internos. De lo contrario, para todo el cubo hay 192 automorfismos. Esto da esperanza para una reducción significativa en el número de campos ya calculados.
Sin embargo, aquí surge otro problema: si verifica todos los 192 automorfismos, entonces necesita transformar rápidamente el campo de juego intercambiando bits. Si esta transformación no se realiza rápidamente, entonces irá todo el tiempo, no habrá ganancia en productividad y toda la empresa con automorfismos volará hacia la tubería. Entonces comencé a buscar en Internet una forma rápida de intercambiar bits. Para ser sincero, no encontré nada adecuado. La única forma rápida aceptable de reorganizar los bits es precompilar la tabla y seleccionar una solución preparada que tenga el campo de juego actual como índice. Para mí, este método no encajaba, porque era necesario tener una matriz de 2 a la potencia de 64 palabras de sesenta bits.
Ya tenía muchas ganas de dejar esta idea, sin embargo, se me ocurrió la idea de que no es necesario tener una mesa grande, pero puede tener varias pequeñas. En principio, era posible elegir un número diferente de tales tablas, pero me decidí por 8 tablas de 256 palabras (para cada automorfismo). Por lo tanto, para intercambiar bits, tomo un byte de un campo de 64 bits y, en una tabla precalculada, selecciono una plantilla donde los bits ya están en su lugar (a menos, por supuesto, que sean cero en el campo de origen). Luego tomo el siguiente byte del campo de 64 bits y en la siguiente tabla precalculada selecciono otra plantilla y hago un "o" lógico con el primero. Y así 8 veces. Dado que estas operaciones no contienen saltos condicionales, deben realizarse lo suficientemente rápido sin violar la tubería en el procesador.
Sin embargo, todo esto parece lo suficientemente bueno como para codificar todos estos automorfismos y permutaciones rápidas de bits de forma manual y sin errores. Es bastante problemático. Por lo tanto, se creó un programa adicional que genera código C, que, a su vez,
incluido en el programa principal.
Conclusión y desarrollo posterior.
Después de crear el programa anterior, fue posible en pocos días encontrar un árbol casi óptimo para jugar 4x4x4 tic-tac-toe. ¿Por qué es "casi óptimo"? Debido a que la longitud total de los movimientos forzados no se tiene en cuenta y puede suceder que haya un árbol para movimientos no forzados de la misma profundidad, pero con una profundidad total menor de los movimientos forzados. Pero creo que este no es un gran inconveniente.
Por lo tanto, el juego de tic-tac-toe 4x4x4 está completamente calculado, los cruces siempre ganan y puedes cerrar este tema. En realidad no El hecho es que, dado que las cruces van primero, tienen una ventaja. ¿Qué pasa si intenta compensar esta ventaja de alguna manera? Propongo la siguiente idea: prohibir que las cruces pongan la cruz en el campo que controla 7 líneas con el primer movimiento, restringiéndolas a los campos que controlan solo 4 líneas. A pesar de que esto parece ser un pequeño cambio, de hecho, el resultado del juego puede cambiar significativamente y los ceros podrán reducir el juego a un empate, o tal vez ganar. Entonces, hay algo para explorar.