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 de m por n , siendo el ganador el jugador que primero consigue colocar k piedras de su propio color en fila, horizontal, vertical o diagonalmente. [1] [2] Por lo tanto, el tres en raya es el juego 3,3,3 y el gomoku de estilo libre es el juego 15,15,5. Un juego m , n , k también se denomina juego k en fila en un tablero de m por n .
Un argumento estándar de robo de estrategia 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 supone que el segundo jugador tiene una estrategia ganadora y demuestra una estrategia ganadora para el primer jugador. El primer jugador realiza un movimiento arbitrario, para empezar. Después de eso, el jugador pretende ser el segundo jugador y adopta la estrategia ganadora del segundo jugador. Puede hacer esto siempre que la estrategia no requiera colocar una piedra en la casilla "arbitraria" que ya está ocupada. Sin embargo, si esto sucede, puede volver a realizar un movimiento arbitrario y continuar como antes con la estrategia ganadora del segundo jugador. Dado que una piedra adicional no puede hacerle 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 sobre si una partida en particular es un empate o una victoria para el primer jugador. Tampoco proporciona una estrategia concreta para el primer jugador.
Aplicación de resultados a distintos tamaños de placa
Un concepto útil es el de " juego débil ( m , n , k )", donde k -en-fila-del segundo jugador no termina el juego con una victoria del segundo jugador.
Si débil ( m , n , k ) es un empate, entonces disminuir m o 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.
Obsérvese que las pruebas de empate que utilizan estrategias de emparejamiento también prueban un empate 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 en el juego débil, asumiendo que ambos jugadores utilizan una estrategia óptima.
Si un determinado ( 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 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 todos los cuadrados del tablero en pares de tal manera que al jugar siempre en el par de cuadrados 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 realizar 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 k > m o k > n es un empate, también mediante una estrategia de emparejamiento en una dimensión no menor que k (o trivialmente imposible de ganar si ambas son menores)
Resultados específicos
k = 1 y k = 2 son victorias triviales, excepto para (1,1,2) y (2,1,2)
(3,3,3) es un empate (ver Tres en raya ), 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 ≥ 9 y un empate para m ≤ 8. [3]
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, [4] 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 sorteos mediante emparejamientos.
Variante multidimensional
Es posible considerar variantes jugadas en un tablero multidimensional en lugar de un tablero bidimensional.
Para el caso de k en fila, donde el tablero es un hipercubo n -dimensional con todas las aristas de longitud k , Hales y Jewett demostraron [5] 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 sucede si y sólo si
^ 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.
^ Uiterwijk, Jos WHM (20 de agosto de 2019). "Resolución de 4 en raya fuertes y débiles" (PDF) . Conferencia IEEE sobre juegos de 2019 (CoG) . IEEE. págs. 1–8. doi :10.1109/CIG.2019.8848010. ISBN.978-1-7281-1884-0.
^ 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 sus jugadas matemáticas, Volumen 3", AK Peters (2003)
