Encontrar la estrategia ganadora de una variación del juego de Nim

Aquí hay una variante del juego Nim de la cual no pude encontrar la estrategia ganadora, la regla del juego es así:

Los juegos comienzan con 16 piedras dispuestas de la siguiente manera:

o (primera pila)

ooo (segunda pila)

ooooo (tercera pila)

ooooooo (cuarta pila)

Normas

1.Dos jugadores se turnan para quitar piedras.

2.Cada vez puedes quitar como máximo todas las piedras del mismo montón, y debes quitar al menos una piedra.

3. Pierde el jugador que quita la última piedra.

4. Si una pila se divide en dos pilas, debe retirarlas en al menos dos turnos.

Por ejemplo, se tomaron la tercera y cuarta piedras del tercer montón: ( x representa las piedras tomadas)

o

ooo

ooxxo

ooooooo

Entonces no puedes quitar todas las piedras del tercer montón en un turno. Tienes que quitarlos todos en al menos dos turnos ya que se ha dividido en dos montones:

Primer turno: oo xxo

Segundo turno: xxxx o

Y para un patrón como oxxoxoo , debes quitarlos todos en al menos 3 turnos, etc.

Las tres primeras reglas son similares al juego NIM clásico (conozco la estrategia ganadora en el clásico), sin embargo, la última regla hace que no sea aplicable. Mi pregunta es quién tiene la estrategia ganadora en este juego y cuál es la estrategia ganadora.

¿Conoces el teorema de Sprague Grundy? Eso es casi crucial para este problema. Si ya lo sabes, ¿cuáles son tus pensamientos/dónde te quedaste atascado? Si no es así, ¿dónde encontraste ese problema (por ejemplo, en una clase de programación donde solo tienes que escribir un programa para hacer los movimientos ganadores?)?
También existe la posibilidad de que conozcas el teorema sin el nombre, entonces, ¿aprendiste sobre la aplicación de "nimbers" o "valores grundy" a juegos que no sean nim?
No he aprendido eso todavía. Mis compañeros de clase jugaron este juego conmigo, pero ninguno de nosotros conoce la estrategia ganadora. Hoy echaría un vistazo al teorema.
Puedes aprender sobre estas cosas con cosas de esta lista de recursos
Una cosa más: ¿has probado a jugar como Nim contra, digamos, un oponente aleatorio, para ver qué aprendes?

Respuestas (1)

Como dices que conoces la estrategia ganadora en Nim clásico, supongo que estás familiarizado con el nim-sum ⊕ . Si juegas esta posición en el Nim clásico sin la cuarta regla, se pierde para el primer jugador en moverse, ya que 1 ⊕ 3 ⊕ 5 ⊕ 7 = 0 .

Con la cuarta regla, obtienes movimientos adicionales: si tienes una pila con X + y + k piedras, puedes quitar k piedras y dejar dos montones con X y y piedras El valor Nim resultante de estas dos pilas es X ⊕ y .

Sin embargo, es fácil demostrar que X ⊕ y ≤ X + y . Eso significa que cada vez que divides una pila en dos (¡o más!) pilas, puedes quitar piedras de la misma pila sin dividirla para obtener el mismo valor de nim.

En cambio, si divide la pila con 3 piedras en dos pilas como esta: oxo , las dos pilas tienen un valor nim 1 ⊕ 1 = 0 . Entonces obtienes el mismo valor de nim si tomas las tres piedras para eliminar toda la pila.

Entonces las respuestas son: 1) En este juego, el primer jugador en moverse pierde. 2) La estrategia ganadora es exactamente la misma que en el Nim clásico, y nunca tienes que dividir montones. Si tu oponente lo hace, siempre tienes una respuesta.

Encontrar la estrategia ganadora de una variación del juego de Nim
RespuestasAquíPolítica de privacidad1y, 0v