Demostrar el uso de una estrategia de robar argumento de que el jugador 1 tiene una estrategia ganadora en el juego chomp

Question

No tengo idea de lo que esta pregunta está pidiendo o cómo demostrarlo matemáticamente. Me doy cuenta de basado en la estrategia de robar la teoría de que si el jugador tiene un ganador stratagy, a continuación, el jugador puede utilizar la misma estrategia yendo primero y ya que tanto los jugadores no pueden ganar, el jugador gana. ¿Cómo puedo mostrar este matemáticamente?

El juego de Chomp es jugado por dos jugadores. En este juego, las cookies son colocados en una cuadrícula rectangular. La cookie en la parte superior izquierda de la posición es envenenado. Los dos jugadores se turnan para efectuar movimientos; en cada movimiento, se requiere que un jugador comer una galleta, junto con todas las cookies a la derecha y/o por debajo (que es todo el resto de las galletas en el rectángulo, en el que la primera cookie comido es la esquina superior izquierda). El perdedor es el jugador que no tiene más remedio que comer los envenenados cookie. Demostrar que si la mesa es cuadrada (y más de 1 × 1), a continuación, el primer jugador tiene una estrategia ganadora.

Answer 1

El juego habitual de Chomp (con su orientación) tiene el jugador de comer todas las galletas que son al menos tan lejos a la derecha y al menos tan baja como la selección de cookie, no y/o. A continuación, podemos utilizar la estrategia de robar en cualquier tablero rectangular, cuadrada o no. El juego es un simétrica perfecta información del juego, por lo que cada posición es P (ganado por el jugador anterior) o N (ganado por el jugador siguiente). Suponga que el segundo jugador puede ganar, por lo que el rectángulo es un P posición. El segundo jugador debe tener una respuesta ganadora para el primer jugador que se mueve de la parte inferior derecha de la galleta, teniendo la junta a un P posición. El primer jugador puede hacer ese movimiento (que incluyen la eliminación de la parte inferior derecha de la galleta), el logro de la P posición, a continuación, siga el ganador del segundo jugador de la estrategia. Esto es una contradicción, por lo que nuestra suposición de que el segundo jugador puede ganar es el mal.

Tenga en cuenta que esta muestra no es un ganar el primer jugador de la estrategia, pero no da ninguna ayuda en encontrar. Resulta que en algunas tablas el primer jugador sólo debe tomar la cookie, mientras que en otros se debe tomar algún otro movimiento. En la plaza de las tablas, tomando sólo una cookie premios para el primer jugador. A continuación, se puede hacer simétrica se mueve al segundo jugador y ganar.

Answer 2

Como se señaló anteriormente, no creo que la estrategia de robo argumento técnicamente se aplica aquí porque P1 primer movimiento de hecho podría ser una desventaja (no se como le puede pasar). Sin embargo, como se señala más adelante en el comentario, la prueba es esencialmente el uso de la estrategia de robo de argumento.

En términos de probar que P1 tiene una estrategia ganadora, he aquí una ruta (la prueba por contradicción) por $m \times n$ junta, que es, obviamente, una generalización de un tablero cuadrado.

Supongamos que al contrario que P1 no tiene una estrategia que garantiza la victoria. Entonces, el jugador 2 debe tener una estrategia de este tipo, ya que no hay lazos. Entonces, no importa qué P1 hace con su primer movimiento, P2 puede garantizar la victoria desde ese punto en adelante. Deje $C$ ser el conjunto de todas las posibles configuraciones en grid que puede ser el resultado de P1 primer movimiento. De cada configuración,$c \in C$, el siguiente jugador en movimiento, P2 aquí, puede garantizar la victoria para sí mismo.

Sin embargo, supongamos que P1 selecciona $(m,n)$, que es la celda inferior derecha, con su primer movimiento. Entonces, no importa lo P2 elige con su segunda opción, la configuración resultante se $c^*$ $C$ - es decir, P1 podría haber tenido con nosotros directamente a $c^*$ con su primer movimiento. Por supuesto anteriormente, para todos los $c \in C$, el siguiente jugador en movimiento, ahora P1, puede garantizar la victoria para sí mismo. Desde P1 puede garantizar la victoria siguiendo lo que se mueva P2 hace, hemos encontrado una contradicción, por lo tanto, P1 debe tener una estrategia que garantiza la victoria.

No estoy seguro de que sabemos en realidad cuál es la estrategia ganadora es en general $m \times n$, sólo que uno existe. En el caso especial en que $m=n$, la estrategia ganadora consiste en P1 selección de $(2,2)$ en la primera ronda, a continuación, la explotación de la simetría en adelante (solo copia de su oponente jugar, básicamente). Vea si usted puede convencer a sí mismo por qué!

Answer 3

La estrategia de robar la teoría no se aplica aquí porque los movimientos disponibles para ambos jugadores no son los mismos. Es posible que el primer jugador no tiene una estrategia ganadora y no importa lo que él hace en movimiento 1, jugador 2 tiene una estrategia ganadora. Por supuesto, no es muy probable, ya que el jugador 1 tiene un montón de opciones que afectan al resto del juego, pero podría ser una posible plaza donde el jugador 2 la estrategia ganadora garantiza el jugador 1 el envenenado cookie.