Un juego m , n , k es un juego de mesa abstracto en el que dos jugadores se turnan para colocar una piedra de su color en un tablero m por n , siendo el ganador el jugador que primero obtenga k piedras de su propio color. una fila, horizontal, vertical o diagonal. [1] [2] Por lo tanto, el tres en raya es el juego de 3,3,3 y el gomoku de estilo libre es el juego de 15,15,5. Un juego de m , n , k también se denomina juego de k en fila en un tablero de m por n .
Un argumento estándar sobre el robo de estrategias 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 extra dada a cualquier jugador en cualquier posición sólo puede mejorar las posibilidades de ese jugador. El argumento del robo de estrategias supone que el segundo jugador tiene una estrategia ganadora y demuestra una estrategia ganadora para el primer jugador. Para empezar, el primer jugador hace un movimiento arbitrario. Después de eso, el jugador finge ser el segundo jugador y adopta la estrategia ganadora del segundo jugador. Pueden hacerlo siempre y cuando 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. Como una piedra extra no puede hacerles daño, 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 acerca de si un juego en particular es un empate o una victoria para el primer jugador. Además, en realidad no proporciona una estrategia para el primer jugador.
Aplicar resultados a diferentes tamaños de tablero
Una noción útil es un "juego débil ( m , n , k ) ", donde k consecutivos del segundo jugador no termina el juego con la victoria del segundo jugador.
Si débil ( m , n , k ) es un empate, entonces disminuir mo n o aumentar k también resultará en un juego empatado.
Por el contrario, si débil o normal ( m , n , k ) es una victoria, entonces cualquier débil mayor ( m , n , k ) es una victoria.
Tenga en cuenta que las pruebas de empates que utilizan estrategias de emparejamiento también demuestran un empate para la versión débil y, por tanto, para todas las versiones más pequeñas.
Resultados generales
Las siguientes afirmaciones se refieren al primer jugador del juego débil, suponiendo 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 empate. Del mismo modo, si ( m 0 , n 0 , k 0 ) es una victoria, entonces ( m 0 , n 0 , k ) con k ≤ k 0 es una victoria, y ( m , n , k 0 ) con m ≥ m 0 y n ≥ n 0 es una victoria.
k ≥ 9 es un empate: cuando k = 9 y el tablero es infinito, el segundo jugador puede empatar 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 el par de la casilla del primer jugador, el segundo jugador se asegura que el primer jugador no pueda conseguir 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 hace un movimiento arbitrario dentro del tablero.
k ≥ 8 es un empate en un tablero infinito. No está claro si esta estrategia se aplica a tamaños de tablero finitos. [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 k > mo k > n es un empate, también mediante una estrategia de emparejamiento en la dimensión no menor que k (o trivialmente imposible de ganar si ambos son más pequeños)
Resultados específicos
k = 1 y k = 2 son victorias triviales, excepto (1,1,2) y (2,1,2)
(3,3,3) es un empate (ver Tic-tac-toe ), y ( m , n ,3) es un empate si m < 3 o n < 3. ( m , n ,3) es una victoria 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 empate para m ≤ 5 y n ≤ 5, y (6,5,4) es una victoria, lo que significa que ( m , n ,4) es una victoria 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 realizada por 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 realizada por 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 empates mediante emparejamientos.
Variante multidimensional
Es posible considerar variantes jugadas en un tablero multidimensional en lugar de en un tablero bidimensional.
Para el caso de k -en una fila donde el tablero es un hipercubo de n dimensiones con todas las aristas de longitud k , Hales y Jewett demostraron [4] que el juego es un empate si k es impar y
k ≥ 3 norte - 1
o si k es par y
k ≥ 2 norte +1 - 2.
Conjeturan que el juego es 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 sólo si
^ ab JWHM Uiterwijk y H. J van der Herik, La ventaja de la iniciativa , Ciencias de la información 122 (1) (2000) 43-58.
^ ab 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). "Resolver 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 tus jugadas matemáticas, Volumen 3", AK Peters (2003)
