Nim (juego)
Nim es un juego matemático de estrategia en el que dos jugadores se turnan para quitar (o "recortar") objetos de distintos montones. En cada turno, un jugador debe eliminar al menos un objeto y puede eliminar cualquier número de objetos siempre que todos provengan del mismo montón o pila. Dependiendo de la versión que se esté jugando, el objetivo del juego es evitar tomar el último objeto o tomar el último objeto.
Nim se juega típicamente como un juego de misère, en el que el jugador que toma el último objeto pierde. Nim también se puede jugar como un juego normal, juego en el que el jugador que toma el último objeto gana. Esto se llama juego normal porque el último movimiento es un movimiento ganador en la mayoría de los juegos, aunque no es la forma normal en que se juega Nim. En el juego normal o en un juego de misère, cuando el número de montones con al menos dos objetos es exactamente igual a uno, el jugador que tome el siguiente puede ganar fácilmente. Si esto elimina todos o todos menos uno de los objetos del montón que tiene dos o más, entonces ningún montón tendrá más de un objeto, por lo que los jugadores se verán obligados a alternar la eliminación de exactamente un objeto hasta que finalice el juego. Si el jugador deja un número par de montones distintos de cero (como haría el jugador en el juego normal), el jugador toma el último; si el jugador deja un número impar de montones (como haría el jugador en el juego de misère), entonces el otro jugador toma el último.
El juego normal Nim (o más precisamente el sistema de nimbers) es fundamental para el teorema de Sprague-Grundy, que esencialmente dice que en el juego normal todo juego imparcial es equivalente a un montón Nim que produce el mismo resultado cuando se juega en paralelo con otros juegos imparciales de juego normal (ver suma disyuntiva).
Si bien a todos los juegos imparciales de juego normal se les puede asignar un valor Nim, ese no es el caso según la convención de misère. Solo se pueden jugar juegos mansos usando la misma estrategia que un misère Nim.
Nim es un caso especial de un juego poset donde el poset consiste en cadenas disjuntas (los montones).
El gráfico de evolución del juego de Nim con tres montones es el mismo que tres ramas del gráfico de evolución del autómata Ulam-Warburton.
Las variantes de Nim se han jugado desde la antigüedad. Se dice que el juego se originó en China —se parece mucho al juego chino de 捡石子 jiǎn-shízi, o "recoger piedras"— pero el origen es incierto; las primeras referencias europeas a Nim son de principios del siglo XVI. Su nombre actual fue acuñado por Charles L. Bouton de la Universidad de Harvard, quien también desarrolló la teoría completa del juego en 1901, pero los orígenes del nombre nunca se explicaron completamente.
En la Feria Mundial de Nueva York de 1940, Westinghouse exhibió una máquina, la Nimatron, que jugaba a Nim. Desde el 11 de mayo de 1940 hasta el 27 de octubre de 1940, solo unas pocas personas pudieron vencer a la máquina en ese período de seis semanas; si lo hacían, se les presentaba una moneda que decía Nim Champ. También fue uno de los primeros juegos electrónicos computarizados. Ferranti construyó una computadora de juego Nim que se exhibió en el Festival de Gran Bretaña en 1951. En 1952 Herbert Koppel, Eugene Grant y Howard Bailer, ingenieros de WL Maxon Corporation, desarrollaron una máquina que pesaba 23 kilogramos (50 libras) que jugaba a Nim contra un oponente humano y ganaba regularmente. Se ha descrito una máquina de juego Nim hecha de TinkerToy.
El juego de Nim fue el tema de la columna Mathematical Games de Martin Gardner de febrero de 1958 en Scientific American. Se reproduce una versión de Nim —y tiene una importancia simbólica— en la película francesa nouvelle vague El año pasado en Marienbad (1961).
El juego normal es entre dos jugadores y se juega con tres montones de cualquier número de objetos. Los dos jugadores se alternan tomando cualquier número de objetos de cualquiera de los montones. El objetivo es ser el último en tomar un objeto. En el juego de misère, el objetivo es, en cambio, garantizar que el oponente se vea obligado a tomar el último objeto restante.
El siguiente ejemplo de un juego normal se juega entre jugadores ficticios Alice y Bob, que comienzan con montones de tres, cuatro y cinco objetos.
La estrategia práctica para ganar en el juego de Nim es que un jugador coloque al otro en una de las siguientes posiciones, y cada turno sucesivo después debería poder hacer una de las posiciones más pequeñas. Solo el último movimiento cambia entre juego misère y normal.
* Solo válido para juego normal.
** Solo válido para misere.
Para las generalizaciones, n y m puede ser cualquier valor> 0, y pueden ser el mismo.
Nim se ha resuelto matemáticamente para cualquier cantidad de montones y objetos iniciales, y hay una forma fácil de calcular para determinar qué jugador ganará y qué movimientos ganadores están disponibles para ese jugador.
La clave de la teoría del juego es la suma digital binaria de los tamaños del montón, es decir, la suma (en binario), descuidando todos los acarreos de un dígito a otro. Esta operación también se conoce como "xor bit a bit" o "suma vectorial sobre GF (2) " (módulo 2 de adición bit a bit). Dentro de la teoría de juegos combinatorios se le suele llamar nim-suma, como se llamará aquí. La nim-suma de x e y se escribe x ⊕ y para distinguirla de la suma ordinaria, x + y . Un ejemplo del cálculo con montones de tamaño 3, 4 y 5 es el siguiente:
Un procedimiento equivalente, que a menudo es más fácil de realizar mentalmente, es expresar los tamaños del montón como sumas de potencias distintas de 2, cancelar pares de potencias iguales y luego agregar lo que queda:
En el juego normal, la estrategia ganadora es terminar cada movimiento con un nim-sum de 0. Esto siempre es posible si la nim-suma no es cero antes del movimiento. Si la suma nim es cero, el siguiente jugador perderá si el otro jugador no comete un error. Para saber qué movimiento realizar, sea X la suma nim de todos los tamaños de montón. Encuentre un montón donde la suma nim de X y el tamaño del montón sea menor que el tamaño del montón; la estrategia ganadora es jugar en ese montón, reduciendo ese montón a la suma mínima de su tamaño original con X. En el ejemplo anterior, tomando la suma mínima de los tamaños es X = 3 ⊕ 4 ⊕ 5 = 2. Las nim-sumas de los tamaños de pila A = 3, B = 4 y C = 5 con X = 2 son
El único montón que se reduce es el montón A, por lo que el movimiento ganador es reducir el tamaño del montón A a 1 (eliminando dos objetos).
Como caso particular simple, si solo quedan dos montones, la estrategia es reducir la cantidad de objetos en el montón más grande para igualar los montones. Después de eso, no importa qué movimiento haga tu oponente, puedes hacer el mismo movimiento en el otro montón, garantizando que tomas el último objeto.
Cuando se juega como un juego de misère, la estrategia de Nim es diferente solo cuando el movimiento de juego normal dejaría solo montones de tamaño uno. En ese caso, el movimiento correcto es dejar un número impar de montones de tamaño uno (en el juego normal, el movimiento correcto sería dejar un número par de montones).
Estas estrategias para el juego normal y un juego de misère son las mismas hasta que el número de montones con al menos dos objetos sea exactamente igual a uno. En ese momento, el siguiente jugador elimina todos los objetos (o todos menos uno) del montón que tiene dos o más, por lo que ningún montón tendrá más de un objeto (en otras palabras, todos los demás montones tienen exactamente un objeto cada uno) , por lo que los jugadores se ven obligados a alternar la eliminación de exactamente un objeto hasta que finaliza el juego. En el juego normal, el jugador deja un número par de montones distintos de cero, por lo que el mismo jugador toma el último; en el juego de misère, el jugador deja un número impar de montones distintos de cero, por lo que el otro jugador toma el último.
En un juego misère con montones de tamaños tres, cuatro y cinco, la estrategia se aplicaría así:
La estrategia anterior para un juego de misère se puede implementar fácilmente (por ejemplo, en Python, a continuación).
C. Bouton demostró la solidez de la estrategia óptima descrita anteriormente.
Teorema: En un juego normal de Nim, el jugador que hace el primer movimiento tiene una estrategia ganadora si y solo si la suma nim de los tamaños de los montones no es cero. De lo contrario, el segundo jugador tiene una estrategia ganadora.
Prueba: Observe que la suma nim (⊕) obedece a las leyes asociativas y conmutativas habituales de la suma (+) y también satisface una propiedad adicional, x ⊕ x = 0.
Sean x1, ..., xn los tamaños de los montones antes de un movimiento, e y1, ..., yn los tamaños correspondientes después de un movimiento. Sea s = x1 ⊕ ... ⊕ xn y t = y1 ⊕ ... ⊕ yn. Si el movimiento fue en el montón k, tenemos xi = yi para todo i ≠ k , y xk > yk. Por las propiedades de ⊕ mencionadas anteriormente, tenemos
El teorema se sigue por inducción sobre la duración del juego a partir de estos dos lemas.
Lema 1: Si s = 0, entonces t ≠ 0 sin importar qué movimiento se haga.
Prueba: si no hay movimiento posible, entonces el lema es vacuo cierto (y el primer jugador pierde el juego normal por definición). De lo contrario, cualquier movimiento en el montón k producirá t = xk ⊕ yk de (*). Este número es distinto de cero, ya que xk ≠ y k.
Lema 2: Si s ≠ 0, es posible hacer un movimiento de modo que t = 0.
Prueba: Sea d la posición del bit distinto de cero más a la izquierda (más significativo) en la representación binaria de s, y elija k tal que el bit d-ésimo de xk sea también distinto de cero. (Tal k debe existir, ya que de lo contrario el d-ésimo bit de s sería 0.) Entonces, dejando yk = s ⊕ xk, afirmamos que yk < xk: todos los bits a la izquierda de d son iguales en xk y yk, el bit d disminuye de 1 a 0 (disminuyendo el valor en 2d), y cualquier cambio en los bits restantes ascenderá a 2d−1 como máximo. El primer jugador puede entonces hacer un movimiento tomando xk - yk objetos del montón k, luego
La modificación para el juego misère se demuestra al señalar que la modificación surge primero en una posición que tiene solo un montón de tamaño 2 o más. Nótese que en tal posición s ≠ 0, y por lo tanto esta situación tiene que surgir cuando es el turno del jugador que sigue la estrategia ganadora. La estrategia de juego normal es que el jugador reduzca esto al tamaño 0 o 1, dejando un número par de montones con el tamaño 1, y la estrategia de misère es hacer lo contrario. A partir de ese momento, todos los movimientos son forzados.
En otro juego que se conoce comúnmente como Nim (pero que se llama mejor juego de resta), se impone un límite superior al número de objetos que se pueden eliminar en un turno. En lugar de eliminar arbitrariamente muchos objetos, un jugador solo puede eliminar 1 o 2 o ... o k a la vez. Este juego se juega comúnmente en la práctica con un solo montón (por ejemplo, con k = 3 en el juego Thai 21 en Survivor:Tailandia, donde apareció como un desafío de inmunidad).
El análisis de Bouton se traslada fácilmente a la versión general de varios montones de este juego. La única diferencia es que, como primer paso, antes de calcular las sumas Nim debemos reducir el tamaño de los montones al módulo k + 1. Si esto hace que todos los montones de tamaño cero (en juego misère), el movimiento ganador es tomar k objetos de uno de los montones. En particular, en el juego ideal de un solo montón de n objetos, el segundo jugador puede ganar si y solo si
Esto se sigue del cálculo de la secuencia nim de S (1,2, ..., k ),
de lo cual la estrategia anterior sigue el teorema de Sprague-Grundy.
El juego "21" se juega como un juego de misère con cualquier número de jugadores que se turnan para decir un número. El primer jugador dice "1" y cada jugador a su vez aumenta el número en 1, 2 o 3, pero no puede exceder 21; el jugador obligado a decir "21" pierde. Esto se puede modelar como un juego de resta con un montón de 21– n objetos. La estrategia ganadora para la versión de dos jugadores de este juego es siempre decir un múltiplo de 4; entonces se garantiza que el otro jugador finalmente tendrá que decir 21; así que en la versión estándar, en la que el primer jugador abre con "1", comienza con una jugada perdedora.
El juego del 21 también se puede jugar con diferentes números, por ejemplo, "Suma como máximo 5; pierde con 34".
Un juego de muestra de 21 en el que el segundo jugador sigue la estrategia ganadora:
Una versión similar es el "juego 100": dos jugadores comienzan desde 0 y agregan alternativamente un número del 1 al 10 a la suma. El jugador que llega a 100 gana. La estrategia ganadora es llegar a un número en el que los dígitos son posteriores (por ejemplo, 01, 12, 23, 34, ...) y controlar el juego saltando todos los números de esta secuencia. Una vez que un jugador llega a 89, el oponente solo puede elegir números del 90 al 99, y la siguiente respuesta puede ser, en cualquier caso, 100.
En otra variación de Nim, además de eliminar cualquier número de objetos de un solo montón, se permite eliminar el mismo número de objetos de cada montón.
Otra variación más de Nim es 'Circular Nim', en la que cualquier número de objetos se colocan en un círculo y dos jugadores eliminan alternativamente uno, dos o tres objetos adyacentes. Por ejemplo, comenzando con un círculo de diez objetos,
se toman tres objetos en el primer movimiento
luego otros tres
entonces uno
pero entonces no se pueden sacar tres objetos de un solo movimiento.
En el juego de Grundy, otra variación de Nim, varios objetos se colocan en un montón inicial y dos jugadores dividen alternativamente un montón en dos montones no vacíos de diferentes tamaños. Por lo tanto, seis objetos se pueden dividir en pilas de 5 + 1 o 4 + 2, pero no 3 + 3. El juego de Grundy se puede jugar como misère o como juego normal.
Greedy Nim es una variación en la que los jugadores están restringidos a elegir piedras solo de la pila más grande. Es un juego imparcial finito. Greedy Nim Misère tiene las mismas reglas que Greedy Nim, pero aquí el último jugador capaz de hacer un movimiento pierde.
Sea m el mayor número de piedras en una pila y n el segundo número más grande de piedras en una pila . Sea p m el número de pilas que tienen m piedras y p n el número de pilas que tienen n piedras. Entonces hay un teorema de que las posiciones del juego con p m pares son posiciones P. Este teorema se puede demostrar considerando las posiciones donde p m es impar. Si p m es mayor que 1, se pueden quitar todas las piedras de esta pila para reducir p m en 1 y la nueva p será par. Si p m = 1 (es decir, el montón más grande es único), hay dos casos:
Por tanto, existe un movimiento a un estado en el que p m es par. Por el contrario, si p m es par, si cualquier movimiento es posible ( p m ≠ 0), entonces debe llevar el juego a un estado en el que p m sea impar. La posición final del juego es par ( p m = 0). Por tanto, cada posición del juego con p m par debe ser una posición P.
Una generalización de multi-heap Nim se llamó "Nim" "o" index- k "Nim de E. H. Moore, que lo analizó en 1910. En index- k Nim, en lugar de eliminar objetos de un solo montón, los jugadores pueden eliminar objetos de al menos uno pero hasta k montones diferentes El número de elementos que se pueden eliminar de cada montón puede ser arbitrario o limitado a un máximo de r elementos, como en el "juego de resta" anterior.
La estrategia ganadora es la siguiente: como en el Nim multi-montón ordinario, se considera la representación binaria de los tamaños de montón (o tamaños de montón módulo r + 1). En Nim ordinario, uno forma la suma XOR (o suma módulo 2) de cada dígito binario, y la estrategia ganadora es hacer que cada suma XOR sea cero. En la generalización a index- k Nim, uno forma la suma de cada dígito binario módulo k + 1.
Nuevamente, la estrategia ganadora es moverse de manera que esta suma sea cero para cada dígito. De hecho, el valor así calculado es cero para la posición final, y dada una configuración de montones para la cual este valor es cero, cualquier cambio de como máximo k montones hará que el valor sea distinto de cero. Por el contrario, dada una configuración con un valor distinto de cero, siempre se puede tomar de un máximo de k montones, elegidos cuidadosamente, de modo que el valor se convierta en cero.
Building Nim es una variante de Nim en la que los dos jugadores primero construyen el juego de Nim. Dadas n piedras y s pilas vacías, los jugadores, alternando turnos, colocan exactamente una piedra en una pila de su elección. Una vez que se colocan todas las piedras, comienza un juego de Nim, comenzando con el siguiente jugador que se movería. Este juego se denota BN (n, s).
n -d Nim se reproduce en un tablero , en el que se puede quitar cualquier número de piezas continuas de cualquier hiper-fila. La posición inicial suele ser la pensión completa, pero se permiten otras opciones.
El tablero de partida es un grafo desconectado, y los jugadores se turnan para eliminar los vértices adyacentes.
Candy Nim es una versión del juego normal Nim en el que los jugadores intentan lograr dos objetivos al mismo tiempo: tomar el último objeto (en este caso, dulces) y tomar la cantidad máxima de dulces al final del juego.
En inglés: