Nim (juego) para niños

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 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.

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 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).

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.

* 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   011₂ 3₁₀ Montón A 100₂ 4₁₀ Montón B 101₂ 5₁₀ Montón C --- 010₂ 2₁₀ 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 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

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 010₂=2₁₀ Saco 2 de A, dejando una suma de 000, así que ganaré. 1 4 5 000₂=0₁₀ Sacas 2 de C 1 4 3 110₂=6₁₀ Tomo 2 de B 1 2 3 000₂=0₁₀ Sacas 1 de C 1 2 2 001₂=1₁₀ Tomo 1 de A 0 2 2 000₂=0₁₀ Sacas 1 de C 0 2 1 011₂=3₁₀ 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 001₂=1₁₀ 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([1], MISERE))
    misere [1] You will lose :(
    >>> print(nim([1], NORMAL))
    normal [1] (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.

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 x₁, ...,  x_n los tamaños de los montones antes de un movimiento, e y₁, ...,  y_n los tamaños correspondientes después de un movimiento. Sea s = x₁  ⊕ ... ⊕  x_n y t = y₁  ⊕ ... ⊕  y_n. Si el movimiento fue en el montón k, tenemos x_i = y_i para todo i ≠ k , y x_k > y_k. Por las propiedades de ⊕ mencionadas anteriormente, tenemos

t = 0 ⊕ t = s ⊕ s ⊕ t = s ⊕ (x₁ ⊕ ... ⊕ x_n) ⊕ (y₁ ⊕ ... ⊕ y_n) = s ⊕ (x₁ ⊕ y₁) ⊕ ... ⊕ (x_n ⊕ y_n) = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (x_k ⊕ y_k) ⊕ 0 ⊕ ... ⊕ 0 = s ⊕ x_k ⊕ y_k   (*) t = s ⊕ x_k ⊕ y_k.

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 = x_k ⊕ y_k de (*). Este número es distinto de cero, ya que x_k ≠ 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 x_k 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 y_k = s ⊕ x_k, afirmamos que y_k < x_k: todos los bits a la izquierda de d son iguales en x_k y y_k, el bit d disminuye de 1 a 0 (disminuyendo el valor en 2^d), y cualquier cambio en los bits restantes ascenderá a 2^d−1 como máximo. El primer jugador puede entonces hacer un movimiento tomando x_k - y_k objetos del montón k, luego t = s ⊕ x_k ⊕ y_k (by (*)) = s ⊕ x_k ⊕ (s ⊕ x_k) = 0.

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.

Variaciones

The subtraction game

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

n ≡ 0 (mod k + 1) (en juego normal), o

n ≡ 1 (mod k + 1) (en juego misère).

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

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: Jugador Número 1 1 2 4 1 5, 6 o 7 2 8 1 9, 10 o 11 2 12 1 13, 14 o 15 2 16 1 17, 18 o 19 2 20 1 21

El juego de los 100

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.

Regla de varios montones

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.

Circular Nim

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.

Juego de Grundy

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

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:

• Si p _n es impar, el tamaño del montón más grande se reduce an (por lo que ahora el nuevo p _m es par).
• Si p _n es par, el montón más grande se elimina por completo, dejando un número par de montones más grandes.

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.

Index-k Nim

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

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).

Nim de mayor dimensión

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.

Graph Nim

El tablero de partida es un grafo desconectado, y los jugadores se turnan para eliminar los vértices adyacentes.

Candy Nim

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.

Véase también

En inglés: Nim Facts for Kids

• Nim de Fibonacci
• Nimber
• Juego octal
• Estrella (teoría de juegos)
• Juego cero
• Notakto
• Chomp