Una variante del juego Nim

Question

Sabemos cómo ganar el clásico Nim regular (dos jugadores) Reglas clásicas: Cualquier número de judías en cualquier número de montones separados En cada movimiento, el jugador al que le toca, debe elegir un montón de judías y eliminar desde una judía hasta todas las judías de un solo montón El jugador que saque la última judía pierde (como ejemplo).

Estoy buscando la estrategia correcta para la siguiente variación: Las mismas reglas que en el clásico Nim regular EXCEPTO QUE sólo una vez en el juego, un jugador, y sólo uno, PUEDE PASAR su turno.

He encontrado algunas posiciones ganadoras 2 1,1 1,N,N (con N>1) 2,3,5 4,5,8, 6,7,3

y creo que, antes de utilizar el Pase, hay que utilizar una pila "virtual" con un frijol pero no he podido encontrar una estrategia general.

Answer 1

En un juego de dos jugadores de suma cero con información perfecta, un posición perdedora es aquella en la que cualquier movimiento legal conduce a una posición ganadora y, a posición ganadora es aquella desde la que se puede alcanzar una posición perdedora en exactamente una jugada legal, y todas las posiciones en las que no es posible ninguna jugada legal son posiciones perdedoras. El Nim, visto a la luz de la definición recursiva anterior, implica que ambos jugadores intenten forzar al otro jugador a una posición perdedora para que, independientemente de la jugada que realice, le devuelva a una posición ganadora.

Actualización : Después de que Jean-Pierre aclarara su pregunta (exactamente un movimiento de PASS disponible para ambos jugadores, es decir, después de que uno utilice el PASS, nadie más puede hacerlo durante el resto de la partida)

Conclusión: El primer jugador (P1) tiene garantizada la victoria siempre que no esté en una posición ganadora desde la que no se pueda alcanzar otra posición ganadora.

Estrategia: Si P1 está en una posición perdedora, se limitará a pasar, asegurando la victoria de P1. Si P1 está en una posición ganadora, jugará de forma subóptima para dar a P2 otra posición ganadora. Si P2 pasa ahora, entonces P1 puede ganar la partida jugando de forma óptima. Si P2 elige jugar de forma óptima, entonces P1 puede pasar y ganar como en el caso de que P1 esté en una posición perdedora.

Si la suposición anterior no se cumple, es decir, si la posición ganadora en la que se encuentra P1 es una desde la que sólo se pueden alcanzar otras posiciones ganadoras, entonces P2 ganará robando la estrategia de P1 como se ha descrito anteriormente.