thumb|Fósforos dispuestos en filas para un juego de Nim. Los jugadores se turnan para elegir una fila y eliminar cualquier número de fósforos. 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. 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 nímeros) 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.
Historia 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 . 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).
Juego e ilustración
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.
Tamaños Movimientos A B C
3 4 5 Bob toma 2 de A 1 4 5 Alice toma 3 de C 1 4 2 Bob toma 1 de B 1 3 2 Alice toma 1 de B 1 2 2 Bob toma todo el montón A, dejando dos 2 0 2 2 Alice toma 1 de B 0 1 2 Bob toma 1 de C dejando dos 1. ( En el juego de misère tomaría 2 de C saliendo (0, 1, 0). ) 0 1 1 Alice toma 1 de B 0 0 1 Bob toma todo el montón de C y gana
Posiciones ganadoras 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. 2 montones3 montones4 montones1 1 *1 1 1 **1 1 1 1 *2 21 2 31 1 n n3 31 4 51 2 4 74 41 6 71 2 5 65 51 8 91 3 4 66 6 2 4 61 3 5 77 72 5 72 3 4 58 83 4 72 3 6 79 93 5 62 3 8 9n n4 8 124 5 6 74 9 134 5 8 95 8 13n n m m5 9 12n n n n
* 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.
Teoría matemática
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:
Binario Decimal
0112 310 Montón A 1002 410 Montón B 1012 510 Montón C
0102 210 La suma nim de los montones A, B, and C, 3 ⊕ 4 ⊕ 5 = 2
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:
3 = 0 + 2 + 1 = 2 1 Montón A 4 = 4 + 0 + 0 = 4 Montón B 5 = 4 + 0 + 1 = 4 1 Montón C
2 = 2 Lo que queda después de cancelar 1 y 4
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 . Las nim-sumas de los tamaños de pila A = 3, B = 4 y C = 5 con X = 2 son A ⊕ X = 3 ⊕ 2 = 1 [Dado que (011) ⊕ (010) = 001 ] B ⊕ X = 4 ⊕ 2 = 6 C ⊕ X = 5 ⊕ 2 = 7 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í:
A B C nim-suma
3 4 5 0102=210 Saco 2 de A, dejando una suma de 000, así que ganaré. 1 4 5 0002=010 Sacas 2 de C 1 4 3 1102=610 Tomo 2 de B 1 2 3 0002=010 Sacas 1 de C 1 2 2 0012=110 Tomo 1 de A 0 2 2 0002=010 Sacas 1 de C 0 2 1 0112=310 La estrategia de juego normal sería tomar 1 de B, dejando un número par (2) montones de tamaño 1. Para jugar misère, tomo todo el montón B, para dejar un número impar (1) de montones de tamaño 1. 0 0 1 0012=110 Sacas 1 de C y pierdes.
Implementación de ejemplo La estrategia anterior para un juego de misère se puede implementar fácilmente (por ejemplo, en Python, a continuación).
import functools
MISERE = 'misere' NORMAL = 'normal'
def nim(heaps, game_type): """Computes next move for Nim, for both game types normal and misere.
if there is a winning move: return tuple(heap_index, amount_to_remove) else: return "You will lose :("
- mid-game scenarios are the same for both game types
>>> print(nim([1, 2, 3], MISERE)) misere [1, 2, 3] You will lose :( >>> print(nim([1, 2, 3], NORMAL)) normal [1, 2, 3] You will lose :( >>> print(nim([1, 2, 4], MISERE)) misere [1, 2, 4] (2, 1) >>> print(nim([1, 2, 4], NORMAL)) normal [1, 2, 4] (2, 1)
- endgame scenarios change depending upon game type
>>> print(nim(, MISERE)) misere You will lose :( >>> print(nim(, NORMAL)) normal (0, 1) >>> print(nim([1, 1], MISERE)) misere [1, 1] (0, 1) >>> print(nim([1, 1], NORMAL)) normal [1, 1] You will lose :( >>> print(nim([1, 5], MISERE)) misere [1, 5] (1, 5) >>> print(nim([1, 5], NORMAL)) normal [1, 5] (1, 4) """
print(game_type, heaps, end=' ')
is_misere = game_type == MISERE
is_near_endgame = False count_non_0_1 = sum(1 for x in heaps if x > 1) is_near_endgame = (count_non_0_1 <= 1)
# nim sum will give the correct end-game move for normal play but # misere requires the last move be forced onto the opponent if is_misere and is_near_endgame: moves_left = sum(1 for x in heaps if x > 0) is_odd = (moves_left % 2 == 1) sizeof_max = max(heaps) index_of_max = heaps.index(sizeof_max)
if sizeof_max == 1 and is_odd: return "You will lose :("
# reduce the game to an odd number of 1's return index_of_max, sizeof_max - int(is_odd)
nim_sum = functools.reduce(lambda x, y: x ^ y, heaps) if nim_sum == 0: return "You will lose :("
# Calc which move to make for index, heap in enumerate(heaps): target_size = heap ^ nim_sum if target_size < heap: amount_to_remove = heap - target_size return index, amount_to_remove
if __name__ == "__main__": import doctest doctest.testmod()
Prueba de la fórmula ganadora
C. Bouton demostró la solidez de la estrategia óptima descrita anteriormente.