En la teoría de juegos combinatorios , un juego de resta es un juego de estrategia abstracto cuyo estado puede ser representado por un número natural o vector de números (por ejemplo, el número de fichas de juego en pilas de fichas o las posiciones de las piezas en el tablero) y en que los movimientos permitidos reducen estos números. [1] [2] A menudo, los movimientos del juego permiten reducir cualquier número restando un valor de un conjunto de resta específico , y los diferentes juegos de resta varían en sus conjuntos de resta. [1] Estos juegos también varían en cuanto a si el último jugador que se mueve gana (la convención de juego normal ) o pierde (misère ). [2] Otra convención ganadora que también se ha utilizado es que un jugador que se mueve a una posición con todos los números cero gana, pero que cualquier otra posición sin movimientos posibles es un empate. [1]
Ejemplos de
Ejemplos de juegos de resta notables incluyen los siguientes:
- Nim es un juego cuyo estado consiste en múltiples pilas de fichas, como monedas o cerillas, y un movimiento válido elimina cualquier cantidad de fichas de una sola pila. Nim tiene una estrategia óptima bien conocida en la que el objetivo en cada movimiento es alcanzar un conjunto de montones cuya suma nim sea cero, y esta estrategia es fundamental para el teorema de Sprague-Grundy del juego óptimo en juegos imparciales . Sin embargo, cuando se juega solo con una sola pila de fichas, el juego óptimo es trivial (simplemente elimine todas las fichas en un solo movimiento). [3]
- Restar un cuadrado es una variación de nim en la que solo se pueden eliminar números cuadrados de fichas en un solo movimiento. El juego resultante tiene una estrategia no trivial incluso para una sola pila de fichas; el teorema de Furstenberg-Sárközy implica que sus posiciones ganadoras tienen densidad cero entre los números enteros. [4]
- Fibonacci nim es otra variación de nim en la que los movimientos permitidos dependen de los movimientos anteriores al mismo montón de fichas. En el primer movimiento a una pila, está prohibido tomar toda la pila, y en los siguientes movimientos, la cantidad restada debe ser como máximo el doble de la cantidad anterior eliminada de la misma pila. [5]
- El juego de Wythoff se juega colocando una reina de ajedrez en un tablero de ajedrez grande y, en cada paso, moviéndola (de la manera normal de una reina de ajedrez) hacia el lado inferior, el lado izquierdo o la esquina inferior izquierda del tablero. Este juego puede describirse de manera equivalente con dos pilas de fichas, de las cuales cada movimiento puede eliminar cualquier número de fichas de una o ambas pilas, eliminando la misma cantidad de cada pila cuando ambas pilas se reducen. Tiene una estrategia óptima que involucra secuencias Beatty y la proporción áurea . [6]
Teoría
Los juegos de resta son generalmente juegos imparciales , lo que significa que el conjunto de movimientos disponibles en una posición determinada no depende del jugador al que le toca mover. Para tal juego, los estados se pueden dividir en-posiciones (posiciones en las que el jugador anterior, que acaba de moverse, está ganando) y -posiciones (posiciones en las que gana el siguiente jugador en moverse), y una estrategia de juego óptima consiste en moverse a un -posición siempre que sea posible. Por ejemplo, con la convención de juego normal y una sola pila de fichas, cada número en el conjunto de resta es un-posición, porque un jugador puede ganar a partir de ese número moviéndose a cero. [2]
Para juegos de resta de juego normal en los que hay varios números, en los que cada movimiento reduce solo uno de estos números, y en los que las reducciones que son posibles de un número dado dependen solo de ese número y no del resto del estado del juego , el teorema de Sprague-Grundy se puede utilizar para calcular un "valor nim" de cada número, un número que representa una posición equivalente en el juego de nim, de modo que el valor del estado general del juego es la suma nim de su nim- valores. De esta manera, la estrategia óptima para el juego en general se puede reducir al cálculo de valores nim para un conjunto simplificado de posiciones de juego, aquellas en las que hay un solo número. [7] Los valores nim son cero para-posiciones y distinto de cero para -posiciones; de acuerdo con un teorema de Tom Ferguson , las posiciones de un solo número con nim-valor uno son exactamente los números obtenidos al sumar el valor más pequeño en el conjunto de resta a un-posición. El resultado de Ferguson conduce a una estrategia óptima en los juegos de resta de misère de varios montones, con solo una pequeña cantidad de cambio de la estrategia de juego normal. [8]
Para un juego de resta con una sola pila de fichas y un conjunto de resta fijo (pero posiblemente infinito), si el conjunto de resta tiene espacios arbitrariamente grandes entre sus miembros, entonces el conjunto de -posiciones del juego es necesariamente infinito. [9] Para cada juego de resta con un conjunto de resta finito, los valores nim están acotados y tanto la partición en-posiciones y -posiciones y la secuencia de valores-nim son eventualmente periódicas. El período puede ser significativamente mayor que el valor máximo. en el conjunto de resta, pero es como máximo . [10] Sin embargo, existen infinitos conjuntos de resta que producen valores nim acotados pero una secuencia aperiódica de estos valores. [11]
Complejidad
Para juegos de resta con un conjunto de resta fijo (pero posiblemente infinito), como restar un cuadrado, la partición en posiciones P y posiciones N de los números hasta un valor dado puede calcularse a tiempo . Los valores nim de todos los números hasta puede calcularse a tiempo dónde denota el tamaño del conjunto de resta (hasta ) y denota el valor nim más grande que se produce en este cálculo. [12]
Para generalizaciones de juegos de resta, jugados en vectores de números naturales con un conjunto de resta cuyos vectores pueden tener coeficientes tanto positivos como negativos, es un problema indecidible determinar si dos de tales juegos tienen las mismas posiciones P y N posiciones. [13]
Ver también
- El juego de Grundy y los juegos octales , generalizaciones de los juegos de resta en los que un movimiento puede dividir una pila de fichas en dos.
Notas
- ↑ a b c Golomb (1966) .
- ↑ a b c Berlekamp, Conway & Guy (2001) , "Juegos de resta", págs. 83–86.
- ^ Bouton (1901-1902) ; Golomb (1966) ; Berlekamp, Conway & Guy (2001) , "Green hackenbush, the game of nim, and nimbers", págs. 40-42.
- ^ Golomb (1966) ; Eppstein (2018)
- ^ Whinihan (1963) ; Larsson y Rubinstein-Salzedo (2016)
- ^ Wythoff (1907) ; Coxeter (1953)
- ^ Golomb (1966) ; Berlekamp, Conway & Guy (2001) , "Juegos con montones", p. 82.
- ^ Ferguson (1974) , p. 164; Berlekamp, Conway & Guy (2001) , "Propiedad de emparejamiento de Ferguson", p. 86.
- ^ Golomb (1966) , Teorema 4.1, p. 451.
- ^ Golomb (1966) , Ejemplo (a), p. 454; Althöfer y Bültermann (1995)
- ^ Larsson y Fox (2015) .
- ^ Eppstein (2018) .
- ^ Larsson y Wästlund (2013) .
Referencias
- Althöfer, Ingo ; Bültermann, Jörg (1995), "Longitudes de períodos superlineales en algunos juegos de resta", Informática teórica , 148 (1): 111-119, doi : 10.1016 / 0304-3975 (95) 00019-S , MR 1347670
- Berlekamp, Elwyn R .; Conway, John H .; Guy, Richard K. (2001), Winning Ways for your Mathematical Play , 1 (2da ed.), AK Peters
- Bouton, Charles L. (1901-1902), "Nim, un juego con una teoría matemática completa", Annals of Mathematics , Second Series, 3 (1/4): 35-39, doi : 10.2307 / 1967631 , JSTOR 1967631
- Coxeter, HSM (1953), "The golden section, phyllotaxis, and Wythoff's game", Scripta Mathematica , 19 : 135–143, MR 0057548
- Eppstein, David (2018), "Evaluación más rápida de juegos de resta", en Ito, Hiro; Leonardi, Stefano; Pagli, Linda ; Prencipe, Giuseppe (eds.), Proc. 9th International Conference on Fun with Algorithms (FUN 2018) , Leibniz International Proceedings in Informatics (LIPIcs), 100 , Dagstuhl, Alemania: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, págs. 20: 1–20: 12, doi : 10.4230 / lipics.fun.2018.20
- Ferguson, TS (1974), "Sobre sumas de juegos de gráficos con el último jugador perdido", International Journal of Game Theory , 3 : 159–167, doi : 10.1007 / BF01763255 , MR 0384169
- Golomb, Solomon W. (1966), "Una investigación matemática de los juegos de" comida para llevar " ", Journal of Combinatorial Theory , 1 : 443–458, doi : 10.1016 / S0021-9800 (66) 80016-9 , MR 0209015
- Larsson, Urban; Fox, Nathan (2015), "Un juego de resta aperiódico de nim-dimensión dos" (PDF) , Journal of Integer Sequences , 18 (7), Artículo 15.7.4, arXiv : 1503.05751 , MR 3370791
- Larsson, Urban; Rubinstein-Salzedo, Simon (2016), "Valores de Grundy de Fibonacci nim", International Journal of Game Theory , 45 (3): 617–625, arXiv : 1410.0332 , doi : 10.1007 / s00182-015-0473-y , MR 3538534
- Larsson, Urban; Wästlund, Johan (2013), "De un montón de coincidencias a los límites de la computabilidad" , Electronic Journal of Combinatorics , 20 (3): P41: 1 – P41: 12, arXiv : 1202.0664 , MR 3118949
- Whinihan, Michael J. (1963), "Fibonacci nim" (PDF) , Fibonacci Quarterly , 1 (4): 9-13
- Wythoff, WA (1907), "Una modificación del juego de nim" , Nieuw Archief voor Wiskunde , 7 (2): 199–202