Un m, n, k -game es un juego de tablero abstracto en el que dos jugadores se turnan para colocar una piedra de su color en un tablero m × n , el ganador es el jugador que obtiene primero k piedras de su propio color seguidas. , horizontal, vertical o diagonalmente. [1] [2] Por lo tanto, tic-tac-toe es el juego 3,3,3 y el gomoku de estilo libre es el juego 15,15,5. Un juego de m, n, k también se denomina juego de k en una fila en un tablero de m × n .
Los juegos m, n, k son principalmente de interés matemático . Se busca encontrar el valor de la teoría del juego , el resultado del juego con un juego perfecto . Esto se conoce como resolver el juego.
Argumento de robo de estrategia
Un argumento de robo de estrategia estándar de la teoría de juegos combinatorios muestra que en ningún juego m, n, k puede haber una estrategia que asegure que el segundo jugador ganará (una estrategia ganadora del segundo jugador ). Esto se debe a que una piedra adicional dada a cualquier jugador en cualquier posición solo puede mejorar las posibilidades de ese jugador. El argumento de robo de estrategia asume que el segundo jugador tiene una estrategia ganadora y demuestra una estrategia ganadora para el primer jugador. El primer jugador hace un movimiento arbitrario para empezar. Después de eso, el jugador finge ser el segundo jugador y adopta la estrategia ganadora del segundo jugador. Pueden hacer esto siempre que la estrategia no requiera colocar una piedra en la casilla 'arbitraria' que ya está ocupada. Sin embargo, si esto sucede, pueden volver a realizar un movimiento arbitrario y continuar como antes con la estrategia ganadora del segundo jugador. Dado que una piedra extra no puede dañarlos, esta es una estrategia ganadora para el primer jugador. La contradicción implica que la suposición original es falsa y el segundo jugador no puede tener una estrategia ganadora.
Este argumento no dice nada sobre si un juego en particular es un empate o una victoria para el primer jugador. Además, en realidad no ofrece una estrategia para el primer jugador.
Aplicar resultados a diferentes tamaños de placa
Una noción útil es un " juego débil (m, n, k) ", donde el k-en-una-fila del segundo jugador no termina el juego con una victoria del segundo jugador.
Si débil (m, n, k) es un empate, entonces la disminución de m o n , o el aumento de k también resultará en un juego elaborado.
Por el contrario, si débil o normal (m, n, k) es una ganancia, entonces cualquier débil más grande (m, n, k) es una ganancia.
Tenga en cuenta que las pruebas de sorteos que utilizan estrategias de emparejamiento también resultan un atractivo para la versión débil y, por lo tanto, para todas las versiones más pequeñas.
Resultados generales
Las siguientes afirmaciones se refieren al primer jugador del juego débil, asumiendo que ambos jugadores utilizan una estrategia óptima.
- Si un particular ( m 0 , n 0 , k 0 ) es un empate, entonces ( m 0 , n 0 , k ) con k ≥ k 0 es un empate, y ( m , n , k 0 ) con m ≤ m 0 y n ≤ n 0 es un empate. Del mismo modo, si ( m 0 , n 0 , k 0 ) es una ganancia, entonces ( m 0 , n 0 , k ) con k ≤ k 0 es una ganancia y ( m , n , k 0 ) con m ≥ m 0 y n ≥ n 0 es una ganancia.
- k ≥ 9 es un empate: cuando k = 9 y el tablero es infinito, el segundo jugador puede dibujar mediante una "estrategia de emparejamiento". Un empate en un tablero infinito significa que el juego continuará para siempre con un juego perfecto. Una estrategia de emparejamiento implica dividir todas las casillas del tablero en parejas de tal manera que al jugar siempre en la pareja de la casilla del primer jugador, el segundo jugador se asegura de que el primer jugador no pueda obtener k en una línea. Una estrategia de emparejamiento en un tablero infinito también se puede aplicar a cualquier tablero finito: si la estrategia requiere hacer un movimiento fuera del tablero, entonces el segundo jugador realiza un movimiento arbitrario dentro del tablero.
- k ≥ 8 es un empate en un tablero infinito. No está claro si esta estrategia se aplica a cualquier tamaño de tablero finito. [2] No se sabe si el segundo jugador puede forzar un empate cuando k es 6 o 7 en un tablero infinito.
- k ≥ 3 y, o bien k> m o k> n es un empate, también por una estrategia de apareamiento en la dimensión no menor que k (o trivialmente imposible ganar si ambos son más pequeños)
Resultados específicos
- k = 1 y k = 2 son ganancias triviales, excepto para (1,1,2) y (2,1,2)
- (3,3,3) es un empate (ver Tic-tac-dedo del pie ), y ( m , n , 3) es un empate si m <3 o n <3 . ( M , n , 3) es un ganar si m ≥ 3 y n ≥ 4 o m ≥ 4 y n ≥ 3 .
- (5,5,4) es un empate, lo que significa que ( m , n , 4) es un sorteo de m ≤ 5 y n ≤ 5 , y (6,5,4) es una victoria, lo que significa que ( m , n , 4) es una ganancia para m ≥ 6 y n ≥ 5 o m ≥ 5 y n ≥ 6 . ( m , 4,4) es una victoria para m ≥ 30 (Lustenberger, 1967) y un empate para m ≤ 8 . [1] Se desconoce si ( m , 4,4) es una victoria o un empate para 9 ≤ m ≤ 29 .
- La búsqueda por computadora de Wei-Yuan Hsu y Chu-Ling Ko ha demostrado que tanto (7,7,5) como (8,8,5) son empates, [3] lo que significa que ( m , n , 5) es un empate para m ≤ 8 y n ≤ 8 . La búsqueda por computadora de L. Victor Allis ha demostrado que (15,15,5) es una victoria, incluso con una de las reglas restrictivas de Gomoku .
- (9,6,6) y (7,7,6) son ambos empates a través de emparejamientos.
Variante multidimensional
Es posible considerar variantes jugadas en un tablero multidimensional en lugar de bidimensional.
Para el caso de k -in-a-row donde el tablero es un hipercubo n- dimensional con todas las aristas con longitud k , Hales y Jewett demostraron [4] que el juego es un empate si k es impar y
- k ≥ 3 n - 1
o si k es par y
- k ≥ 2 n +1 - 2.
Conjeturan que el juego es un empate también cuando el número de celdas es al menos el doble del número de líneas, lo que ocurre si y solo si
- 2 k norte ≥ ( k + 2) norte .
Ver también
Referencias
- ^ a b J. WHM Uiterwijk y H. J van der Herik, La ventaja de la iniciativa , Ciencias de la información 122 (1) (2000) 43-58.
- ↑ a b Jaap van den Herik , Jos WHM Uiterwijk, Jack van Rijswijck (2002). "Juegos resueltos: ahora y en el futuro". Inteligencia artificial.
- ^ Hsu, Wei-Yuan; Ko, Chu-Ling; Hsueh, Chu-Hsuan; Wu, I-Chen (2018). "Resolviendo 7,7,5-juegos y 8,8,5-juegos" . Revista ICGA . 40 (3) . Consultado el 6 de noviembre de 2019 .
- ^ Elwyn R. Berlekamp, John Horton Conway, Richard K. Guy. "Formas ganadoras para sus juegos matemáticos, Volumen 3", AK Peters (2003)