Juego m,n,k
Un juego m,n,k 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, y el ganador es el jugador que obtiene primero k piedras de su propio color seguidas, horizontal, vertical o diagonalmente.[1][2] Por tanto, el tres en línea es un juego 3,3,3 y el gomoku de estilo libre es un juego 15,15,5. Un juego de m,n,k también se llama juego de k en línea 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 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 extra dada a cualquiera de los jugadores en cualquier posición sólo puede mejorar las posibilidades de ese jugador. El argumento del robo de estrategia asume que el segundo jugador tiene una estrategia ganadora y demuestra una estrategia ganadora para el primer jugador. Para empezar, el primer jugador realiza un movimiento arbitrario. Después, el jugador finge que es el segundo jugador y adopta la estrategia ganadora del segundo. Puede hacerlo siempre que la estrategia no requiera colocar una piedra en la casilla "arbitraria" que ya está ocupada. Sin embargo, si esto ocurre, pueden volver a realizar un movimiento arbitrario y continuar como antes con la estrategia ganadora del segundo jugador. Como una piedra extra no puede perjudicarles, 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 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)", en el que los k consecutivos del segundo jugador no terminan el juego con una victoria del segundo jugador.
Si un juego 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 empate.
Por el contrario, si en un juego débil o normal (m, n, k) es una victoria, entonces cualquier débil mayor (m, n, k) es una victoria.
Se debe tener en cuenta que las pruebas de empates 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 declaraciones se refieren al primer jugador en el juego débil, asumiendo que ambos jugadores usan una estrategia óptima.
- Si un particular (m0, n0, k0) es un empate, entonces (m0, n0, k) con k ≥ k0 es un empate, y (m, n, k0) con m ≤ m0 y n ≤ n0 es un empate. Del mismo modo, si (m0, n0, k0) es una victoria, entonces (m0, n0, k) con k ≤ k0 es una victoria, y (m, n, k0) con m ≥ m0 y n ≥ n0 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 consiste en 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 or 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 victorias triviales, excepto para (1,1,2) and (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 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 -en-una-fila donde el tablero es un hipercubo n-dimensional con todos los bordes con longitud k, Hales y Jewett demostraron[4] que el juego es un empate si k es impar y
- k ≥ 3n - 1
o si k es par y
- k ≥ 2n+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 kn ≥ (k + 2)n.
Véase también
Referencias
- ↑ J. W. H. M. Uiterwijk and H. J van der Herik, The advantage of the initiative, Information Sciences 122 (1) (2000) 43-58.
- ↑ Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence.
- Hsu, Wei-Yuan; Ko, Chu-Ling; Hsueh, Chu-Hsuan; Wu, I.-Chen (1 de enero de 2018). «Solving 7,7,5-game and 8,8,5-game». ICGA Journal (en inglés) 40 (3): 246-257. ISSN 1389-6911. doi:10.3233/ICG-180061. Consultado el 26 de febrero de 2021.
- Berlekamp, Elwyn R; Conway, John H; Guy, Richard K; Conway, John H (1982). Winning ways for your mathematical plays Vol 1 Vol 1 (en inglés). Academic Press. ISBN 978-0-12-091101-1. OCLC 1101356712. Consultado el 26 de febrero de 2021.