Juego de resta

En la teoría de juegos combinatorios , un juego de sustracción es un juego de estrategia abstracto cuyo estado puede representarse mediante un número natural o un vector de números (por ejemplo, la cantidad de fichas en pilas de fichas o la posición 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 sustracción especificado , y los diferentes juegos de sustracción varían en sus conjuntos de sustracción. ^{[ 1 ]} Estos juegos también varían en si el último jugador en mover gana (la convención de juego normal ) o pierde ( la convención de juego misère ). ^{[ 2 ]} Otra convención de victoria 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 ]}

Algunos ejemplos de juegos de resta destacados son los siguientes:

• Nim es un juego cuyo estado consiste en múltiples pilas de fichas, como monedas o cerillas, y un movimiento válido permite retirar cualquier número de fichas de una sola pila. Nim tiene una estrategia óptima bien conocida en la que el objetivo de cada movimiento es alcanzar un conjunto de pilas cuya suma nim sea cero, y esta estrategia es fundamental para el teorema de Sprague-Grundy sobre el juego óptimo en juegos imparciales . Sin embargo, cuando se juega solo con una pila de fichas, el juego óptimo es trivial (basta con retirar todas las fichas en un solo movimiento). ^{[ 3 ]}
• El juego de restar un cuadrado es una variante de nim en la que solo se pueden eliminar cantidades cuadradas 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 enteros. ^{[ 4 ]}
• Fibonacci nim es otra variante de nim en la que los movimientos permitidos dependen de los movimientos previos 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 sustraída previamente de la misma pila. ^{[ 5 ]}
• El juego de Wythoff consiste en colocar una reina de ajedrez en un tablero grande y, en cada paso, moverla (como es habitual en una reina) hacia el lado inferior, el lado izquierdo o la esquina inferior izquierda del tablero. Este juego puede describirse de forma 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 se reducen. Posee una estrategia óptima que involucra secuencias de Beatty y la proporción áurea . ^{[ 6 ]}

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 al que le toca mover. Para tal juego, los estados se pueden dividir en${\displaystyle {\mathcal {P}}}$-posiciones (posiciones en las que el jugador anterior, que acaba de moverse, está ganando) y${\displaystyle {\mathcal {N}}}$-posiciones (posiciones en las que el siguiente jugador en moverse está ganando), y una estrategia de juego óptima consiste en moverse a una${\displaystyle {\mathcal {P}}}$-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 una${\displaystyle {\mathcal {N}}}$-posición, porque un jugador puede ganar desde ese número moviéndose a cero. ^{[ 2 ]}

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 posibles a partir 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 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 del juego, aquellas en las que solo hay un número. ^{[ 7 ]} Los valores nim son cero para${\displaystyle {\mathcal {P}}}$-posiciones y distinto de cero para${\displaystyle {\mathcal {N}}}$-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 sumar el valor más pequeño en el conjunto de resta a un${\displaystyle {\mathcal {P}}}$-posición. El resultado de Ferguson conduce a una estrategia óptima en juegos de sustracción de misère con múltiples pilas, con solo un pequeño cambio respecto a 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${\displaystyle {\mathcal {P}}}$-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${\displaystyle {\mathcal {P}}}$-posiciones y${\displaystyle {\mathcal {N}}}$Las posiciones y la secuencia de valores nim son eventualmente periódicas. El período puede ser significativamente mayor que el valor máximo.${\displaystyle x}$en el conjunto de resta, pero es como máximo${\displaystyle 2^{x}}$. ^{[ 10 ]} Sin embargo, existen conjuntos de resta infinitos que producen valores nim acotados pero una secuencia aperiódica de estos valores. ^{[ 11 ]}

Para 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${\displaystyle n}$puede calcularse en tiempo${\displaystyle O(n\log ^{2}n)}$. Los valores nim de todos los números hasta${\displaystyle n}$puede calcularse en tiempo${\displaystyle O(\min(ns,nm\log ^{2}n))}$dónde${\displaystyle s}$denota el tamaño del conjunto de resta (hasta${\displaystyle n}$) y${\displaystyle m}$denota el mayor valor nim que aparece en este cálculo. ^{[ 12 ]}

Para generalizaciones de juegos de resta, jugados sobre 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 estos juegos tienen las mismas posiciones P y N. ^{[ 13 ]}

• El juego de Grundy y los juegos octales son generalizaciones de los juegos de resta en los que un movimiento puede dividir una pila de fichas en dos.

• Althöfer, Ingo ; Bültermann, Jörg (1995), "Longitudes de período superlineales en algunos juegos de sustracción", 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), Winning Ways for your Mathematical Plays , 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 , ISBN 978-3-95977-067-5
• Ferguson, TS (1974), "Sobre sumas de juegos de grafos con el último jugador perdiendo", 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"", Journal of Combinatorial Theory , 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 nim" (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), "From heaps of matchs to the limits of computability" , Electronic Journal of Combinatorics , 20 (3): P41:1–P41:12, arXiv : 1202.0664 , doi : 10.37236/2244 , MR 3118949 
• Whinihan, Michael J. (1963), "Fibonacci nim" (PDF) , Fibonacci Quarterly , 1 (4): 9–13 , doi : 10.1080/00150517.1963.12431541
• Wythoff, WA (1907), "Una modificación del juego de nim" , Nieuw Archief voor Wiskunde , 7 (2): 199– 202