Juegos de Nim
Nimgames juego de mesa
| Formato | diverso |
|---|---|
| Jugador (s) | 2 |
| Edad | a partir de 5 años |
| Duración anunciada | unos 5 minutos |
| capacidad física  No
|
decisión de reflexión si
|
generador de posibilidades No
|
info. compl. y perfecto si
|
Los juegos de Nim son juegos de pura estrategia , con dos jugadores. Hay varias variaciones. Se juegan con semillas, canicas, fichas, fósforos o cualquier otro objeto de fácil manipulación.
Ejemplos de
Muchos juegos de Nim se juegan con una o más pilas de objetos (partidos, por ejemplo), cada jugador modifica una o más pilas de acuerdo con las reglas adoptadas. Expliquemos en detalle la versión utilizada en la emisión de Fort Boyard , tal juego constituye el duelo de los palos contra un maestro de las tinieblas (el montón incluye 20 cerillas). Este juego consiste en retirar 1, 2 o 3 palos en cada turno. El ganador es el que puede jugar en último lugar. Aquí hay un ejemplo de un juego: 20 -> 19 -> 16 -> 13 -> 12 -> 10 -> 8 -> 5 -> 4 -> 3 -> 0
Para este juego, la estrategia es dejar cada vez, si se puede, un número de objetos que sea múltiplo de 4: estas son las posiciones ganadoras. Entonces vemos que el oponente no podrá hacer lo mismo.
Existen otras variaciones:
- Podemos imaginar una variante de la versión de Fort Boyard donde pierde el que se lleva el último objeto, la estrategia es dejar un número de objetos congruentes a 1 módulo 4 (es decir: 1, 5, 9, 13 .. .). De hecho, volvemos al caso anterior considerando que el objeto del juego es tomar el penúltimo objeto.
- El clásico juego de Nim o el juego Marienbad se hizo famoso por una película de Alain Resnais en 1961 , El año pasado en Marienbad . Está formado por varios montones. Cada jugador elige la pila de su elección, y de esa pila, toma el número de partidos de su elección.
- El juego Grundy se juega separando uno del grupo en dos montones de diferentes tamaños, hasta que solo queden montones de uno o dos objetos.
- El juego Wythoff se juega en dos pilas. Cada jugador reduce las dos pilas al mismo tiempo por la misma cantidad de objetos, o bien reduce una sola pila por la cantidad de objetos que quiere.
Además, el juego trivial de Nim (o juego de Nim de una sola pila) consiste en una sola pila de cerillas. Cuando es su turno, cada jugador toma la cantidad de partidos que quiera. La estrategia ganadora para el primer jugador es llevarse todos los partidos. El juego es trivial y tiene interés teórico.
Historia
Los orígenes probablemente sean muy antiguos. Los primeros rastros se registran en China con el nombre de fan-tan , se conoce en África con el nombre de tiouk-tiouk . El nombre actual proviene de la palabra alemana Nimm que significa "¡tomar!" ”Pero también podría provenir de la palabra inglesa WIN (“ wins! ”), Porque al invertir gráficamente la palabra WIN se convierte en NIM . El nombre actual le fue dado al juego por el matemático inglés Charles Leonard Bouton en 1901 cuando encontró un algoritmo que permitía la recompensa.
En la Feria Mundial de Nueva York en 1940, Westinghouse Electric Corporation exhibió una máquina llamada Nimatron , que jugaba al juego de Nim. Desde el 11 de mayo de 1940 hasta el 27 de octubre de 1940, solo un pequeño número de participantes pudo vencer a la máquina; los que ganaron obtuvieron una moneda marcada "Nim Champ". En 1951 , el Nimrod , retomando el concepto de Nimatron, es una computadora que te permite jugar al juego de Nim. Sin embargo, su propósito inicial es ensalzar las habilidades de programación y diseño de computadoras de Ferranti , en lugar de entretener .
Objetivo del juego
Cada juego es jugado por turnos por dos jugadores. La casualidad no interviene. Esto suele implicar mover o recoger objetos según unas reglas que indican cómo pasar de una posición del juego a otra, evitando la repetición cíclica de las mismas posiciones. El número de posiciones se acaba y el juego termina necesariamente, el jugador ya no puede jugar siendo el perdedor (o según ciertas variantes, el ganador).
Estrategia ganadora
Los juegos de Nim son juegos de duelo de suma cero (dos jugadores, un ganador y un perdedor, sin posibilidad de empate), equivalentes a moverse de un vértice a otro de un gráfico dirigido sin circuito , los vértices del gráfico representan las diversas posiciones posibles de el juego, y los bordes las transiciones de una posición a otra. Se demuestra que existe una estrategia óptima, dividiéndose las distintas posiciones del juego en dos subconjuntos, las posiciones ganadoras y las posiciones perdedoras.
Estos se definen recursivamente de la siguiente manera, en el caso de que el jugador que ya no puede jugar haya perdido:
- Las posiciones finales (desde las que ya no se puede jugar) van ganando, ya que el jugador que llega a una impide que su oponente juegue y gana la partida.
- Una posición está perdiendo si hay un movimiento que conduce a una posición ganadora. Si un jugador alcanza una posición perdedora, su oponente puede alcanzar una posición ganadora.
- Una posición no final es ganadora si, independientemente de la jugada que se realice, se llega a una posición perdedora. Si un jugador logra una posición ganadora, su oponente tendrá que ir a una posición perdedora.
Al subir posiciones finales, podemos determinar gradualmente el estado de cada puesto. Entonces, la estrategia óptima es pasar de una posición ganadora a otra.
La determinación de las posiciones ganadoras en el caso de un gráfico complejo utiliza la noción de número de Grundy o nimber . Esto se define de la siguiente manera:
- El número de Grundy de la posición final es igual a 0.
- El número de Grundy de una posición dada es el número entero positivo o cero más pequeño que no aparece en la lista de números de Grundy de las posiciones que siguen inmediatamente a la posición dada.
Las posiciones ganadoras son aquellas con un número de Grundy cero. De hecho, a partir de esa posición, cualquiera que sea la jugada que se realice, se llega a una posición en la que el número de Grundy no es cero (posición perdedora). Por el contrario, a partir de una posición perdedora, hay al menos un movimiento que se puede jugar y que conduce a una posición en la que el número de Grundy es cero (posición ganadora).
Nim establece suma
Llamamos juegos de suma de Nim al juego de jugar varios juegos de Nim al mismo tiempo. Cada jugador, a su vez, elige qué juego de Nim quiere jugar y juega un movimiento de ese juego. El juego de suma finaliza cuando un jugador no puede jugar ninguno de los juegos de Nim individuales. Así, el clásico juego de Nim o el juego de Marienbad en n montón es la suma de n juegos de Nim trivial.
El teorema de Sprague-Grundy explica cómo determinar las posiciones ganadoras de una suma de conjuntos de Nim, conociendo las posiciones ganadoras de cada juego individual de Nim. De hecho, el número de Grundy de cualquier posición del juego de suma se obtiene desglosando los números de Grundy de las posiciones de cada juego individual en binario y luego aplicando la función OR exclusiva a los dígitos del mismo rango de todos estos números. Obtenemos un número binario cuyo valor es el número de Grundy de la suma de la posición del juego.
Este fenómeno se ilustra en el siguiente párrafo.
Juego clásico de Nim
La versión clásica del juego de Nim se juega con varios montones, cada uno compuesto por varias fichas, peones o cerillas. Cada jugador en su turno puede quitar tantos peones como desee, pero en una pila a la vez. El ganador es el que quita el último peón (la versión llamada "miseria" es donde el jugador que toma el último peón es el perdedor. Se puede deducir fácilmente de esto).
Dado que este conjunto es la suma de conjuntos Nim triviales de una pila, y el número de Grundy de cada pila individual es el número de peones en ese montón, obtenemos el número de Grundy de la posición expresando el número de peones en cada pila en binario. y haciendo que la suma sea exclusiva OR o XOR, (también anotado ⊕) de estos números. Una posición con un valor de 0 siempre gana para el que tiene éxito, una posición con un valor diferente de 0 siempre pierde.
Tomemos el ejemplo de un juego que comienza con tres pilas A, B y C, la pila A contiene 3 peones, la pila B 4 peones y la pila C 5 peones. Entonces tenemos:
0112 310 Pile A 1002 410 Pile B 1012 510 Pile C --- 0102 210 Nim-somme X des piles A, B et C: 3 ⊕ 4 ⊕ 5 = 2
La estrategia ganadora consiste en dejar a su oponente en una posición donde la Nim-sum X es igual a 0. Esto siempre es posible en el caso en que se parte de una posición donde la Nim-sum es diferente de 0, imposible cuando partimos de una posición cuya suma Nim es 0. Aquí basta con eliminar, por ejemplo, dos peones de la pila A (que ahora contiene solo un peón) para llegar a:
0012 110 Pile A 1002 410 Pile B 1012 510 Pile C --- 0002 010 Nim-somme X des piles A, B et C: 1 ⊕ 4 ⊕ 5 = 0
Para encontrar sistemáticamente la jugada a jugar, basta con construir la suma XOR de cada una de las pilas con el número X. Empecemos de nuevo, por ejemplo, de nuestras pilas A = 3 = 011 2 , B = 4 = 100 2 y C = 5 = 101 2 original y sumamos la X que encontramos (X = 2 = 010 2 ):
A ⊕ X = 3 ⊕ 2 = 1 [Char (011) ⊕ (010) = 001] B ⊕ X = 4 ⊕ 2 = 6 C ⊕ X = 5 ⊕ 2 = 7La única pila cuya cantidad disminuye es la pila A. Por lo tanto, debemos reducir A a este número, es decir, a un solo peón, así que quitar dos peones de A, que es exactamente lo que habíamos hecho.
Una de las variantes más clásicas consiste en limitar el número de peones que se pueden sacar de cada pila a un máximo de k peones. Se aplica el método anterior, siempre que el número de Grundy de cada montón se tome como el número de objetos de módulo (k + 1).
Programa
En 1977 , el manual de la calculadora programable HP-25 incluía un juego llamado Nimb . El juego comenzó con 15 partidos y cada jugador podía llevarse 1, 2 o 3 por turno. Quienquiera que se llevara el último había perdido. El programa, de 49 pasos , jugó segundo y aplicó una estrategia ganadora que no permitió ningún error en su oponente.
Notas y referencias
- Lisa Rougetet, Los múltiples ancestros del juego de Nim , Pour la Science, octubre de 2012, n ° 420, p.80-85
- J.-P. Delahaye, Estrategias mágicas en la tierra de Nim , Pour la Science, marzo de 2009, n ° 307, p 88-93
- Rudolf Flesch , The Art of Clear Thinking , Nueva York, Harper and Brothers Publishers,1951, p. 3
- " ExpoMuseum / New York World's Fair, 1939-'40 " , en www.expomuseum.com (consultado el 20 de abril de 2018 )
- " 1940: Nimatron " , en platinumpiotr.blogspot.com (consultado el 20 de abril de 2018 )
- (en) " Nimb para HP-25 "