Juego de resta

Juego de estrategia abstracto

En la teoría de juegos combinatorios , un juego de resta es un juego de estrategia abstracto cuyo estado puede representarse mediante un número natural o un 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 el 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 especificado , y los diferentes juegos de resta varían en sus conjuntos de resta. ^[1] Estos juegos también varían en si el último jugador en moverse gana (la convención de juego normal ) o pierde ( convención de juego 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

Algunos 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 número 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 pilas cuya suma nim sea cero, y esta estrategia es central para el teorema de Sprague-Grundy de juego óptimo en juegos imparciales . Sin embargo, cuando se juega solo con una sola pila de fichas, el juego óptimo es trivial (simplemente eliminar todas las fichas en un solo movimiento). ^[3]
• Restar un cuadrado es una variante del 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]
• El nim de Fibonacci es otra variante del nim en la que los movimientos permitidos dependen de los movimientos anteriores a la misma pila de fichas. En el primer movimiento a una pila, está prohibido tomar toda la pila, y en los movimientos posteriores, la cantidad sustraída debe ser como máximo el doble de la cantidad anterior retirada de la misma pila. ^[5]
• El juego de Wythoff se juega colocando una reina de ajedrez en un tablero 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 se puede describir de manera equivalente con dos pilas de fichas, de las cuales cada movimiento puede quitar cualquier número de fichas de una o ambas pilas, quitando la misma cantidad de cada pila cuando ambas pilas se reducen. Tiene una estrategia óptima que involucra secuencias de 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 dada no depende del jugador a quien le toca mover. Para un juego de este tipo, los estados se pueden dividir en -posiciones (posiciones en las que el jugador anterior, que acaba de mover, está ganando) y -posiciones (posiciones en las que el siguiente jugador en mover está ganando), y una estrategia de juego óptima consiste en moverse a una -posición siempre que esto sea posible. Por ejemplo, con la convención de juego normal y una única pila de fichas, cada número en el conjunto de resta es una -posición, porque un jugador puede ganar desde dicho número moviéndose al cero. ^[2] ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {N}}}$

Para juegos de resta de juego normal en los que hay múltiples números, en los que cada movimiento reduce solo uno de estos números y en los que las reducciones que son posibles a partir de un número dado dependen solo de ese número y no del resto del estado del juego, se puede usar el teorema de Sprague-Grundy 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 sus valores nim. De esta manera, la estrategia óptima para el juego general se puede reducir al cálculo de valores nim para un conjunto simplificado de posiciones de juego, aquellas en las que solo hay un único número. ^[7] Los valores nim son cero para las posiciones - y no cero para las posiciones - ; según un teorema de Tom Ferguson , las posiciones de un solo número con valor nim uno son exactamente los números obtenidos al agregar el valor más pequeño en el conjunto de resta a una posición - . El resultado de Ferguson conduce a una estrategia óptima en juegos de sustracción de misère de múltiples pilas, con solo una pequeña cantidad de cambio con respecto a la estrategia de juego normal. ^[8] ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle {\mathcal {P}}}$

En un juego de resta con una única 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 como 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 conjuntos de resta infinitos que producen valores nim acotados pero una secuencia aperiódica de estos valores. ^[11] ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle x}$ ${\displaystyle 2^{x}}$

Complejidad

Para los juegos de resta con un conjunto de resta fijo (pero posiblemente infinito), como restar un cuadrado, la partición en P-posiciones y N-posiciones de los números hasta un valor dado se puede calcular en tiempo . Los valores nim de todos los números hasta se pueden calcular en tiempo donde denota el tamaño del conjunto de resta (hasta ) y denota el valor nim más grande que ocurre en este cálculo. ^[12] ${\displaystyle n}$ ${\displaystyle O(n\log ^{2}n)}$ ${\displaystyle n}$ ${\displaystyle O(\min(ns,nm\log ^{2}n))}$ ${\displaystyle s}$ ${\displaystyle n}$ ${\displaystyle m}$

Para las generalizaciones de juegos de resta, jugados en vectores de números naturales con un conjunto de resta cuyos vectores pueden tener coeficientes positivos y negativos, es un problema indecidible determinar si dos de estos juegos tienen las mismas posiciones P y N. ^[13]

Véase 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

1. Golomb (1966).
2. Berlekamp, ​​Conway y Guy (2001), "Juegos de resta", págs. 83–86.
3. Bouton (1901–1902); Golomb (1966); Berlekamp, ​​Conway y Guy (2001), "Green hackenbush, el juego del nim y los nimbers", págs. 40–42.
4. Golomb (1966); Eppstein (2018)
5. Whinihan (1963); Larsson y Rubinstein-Salzedo (2016)
6. Wythoff (1907); Coxeter (1953)
7. Golomb (1966); Berlekamp, ​​Conway y Guy (2001), "Juegos con montones", pág. 82.
8. Ferguson (1974), pág. 164; Berlekamp, ​​Conway y Guy (2001), "Propiedad de emparejamiento de Ferguson", pág. 86.
9. Golomb (1966), Teorema 4.1, pág. 451.
10. Golomb (1966), Ejemplo (a), pág. 454; Althöfer y Bültermann (1995)
11. Larsson y Fox (2015).
12. Eppstein (2018).
13. Larsson y Wästlund (2013).

Referencias

• Althöfer, Ingo ; Bültermann, Jörg (1995), "Longitudes de períodos superlineales en algunos juegos de resta", Theoretical Computer Science , 148 (1): 111–119, doi :10.1016/0304-3975(95)00019-S, MR  1347670
• Berlekamp, ​​Elwyn R. ; Conway, John H. ; Guy, Richard K. (2001), Maneras ganadoras para sus juegos matemáticos , vol. 1 (2.ª ed.), AK Peters
• Bouton, Charles L. (1901–1902), "Nim, un juego con una teoría matemática completa", Annals of Mathematics , Segunda serie, 3 (1/4): 35–39, doi :10.2307/1967631, JSTOR  1967631
• Coxeter, HSM (1953), "La sección áurea, la filotaxis y el juego de Wythoff", Scripta Mathematica , 19 : 135–143, MR  0057548
• Eppstein, David (2018), "Evaluación más rápida de juegos de resta", en Ito, Hiro; Leonardo, Stefano; Pagli, Linda ; Prencipe, Giuseppe (eds.), Proc. Novena Conferencia Internacional sobre Diversión con Algoritmos (FUN 2018) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 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 las sumas de juegos de gráficos en los que el último jugador pierde", International Journal of Game Theory , 3 (3): 159–167, doi :10.1007/BF01763255, MR  0384169
• Golomb, Solomon W. (1966), "Una investigación matemática de los juegos de "quitar"", Revista de teoría combinatoria , 1 (4): 443–458, doi : 10.1016/S0021-9800(66)80016-9 , MR  0209015
• Larsson, Urban; Fox, Nathan (2015), "Un juego de sustracción aperiódico de 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", 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 montones de cerillas a los límites de la computabilidad", Electronic Journal of Combinatorics , 20 (3): P41:1–P41:12, arXiv : 1202.0664 , doi :10.37236/2244, MR  3118949
• Whinihan, Michael J. (1963), "El problema de Fibonacci" (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