Nim (juego)
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.
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.
Solo se pueden jugar juegos mansos usando la misma estrategia que un misère Nim.
[2] Se dice que el juego se originó en China —se parece mucho al juego chino de 捡石子 jiǎn-shízi, o "recoger piedras"[3]— 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,[4] pero los orígenes del nombre nunca se explicaron completamente.
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 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 siguiente ejemplo de un juego normal se juega entre jugadores ficticios Alice y Bob, que comienzan con montones de tres, cuatro y cinco objetos.
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 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).
Prueba: si no hay movimiento posible, entonces el lema es vacuo cierto (y el primer jugador pierde el juego normal por definición).
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.
A partir de ese momento, todos los movimientos son forzados.
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.
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 lo tanto, seis objetos se pueden dividir en pilas de 5 + 1 o 4 + 2, pero no 3 + 3.
Greedy Nim es una variación en la que los jugadores están restringidos a elegir piedras solo de la pila más grande.
Sea p m el número de pilas que tienen m piedras y p n el número de pilas que tienen n piedras.
Nuevamente, la estrategia ganadora es moverse de manera que esta suma sea cero para cada dígito.
La posición inicial suele ser la pensión completa, pero se permiten otras opciones.
[15] 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.
