John Nash ' s prueba hexagonal

Question

Estoy leyendo un libro sobre la Combinatoria, la Teoría de juegos que se describe una prueba por John Nash que el Hexadecimal es un 'primer jugador gana, pero me parece que la prueba es muy confuso. Esta prueba utiliza una estrategia de robo de argumento.

En un momento dice:

Con este (primer) mover a la Izquierda se convierte en el Segundo.

¿Cómo se puede dar el primer paso hacer un Segundo?

Al final dice:

En algún momento, si esta estrategia requiere de la Izquierda para colocar una piedra en la que el extra se encuentra; entonces ella se limita a hacer otra arbitrariedad. Así, la Izquierda puede ganar en contradicción con la hipótesis.

Yo no entendía en absoluto. ¿Por qué el juego de la llamada para una colocación en "extra" si ese lugar ya está ocupado por una piedra? Alguien puede explicar esta prueba para mí de una manera que yo pueda entender?

Aquí está la prueba:

Es la prueba por contradicción. Vamos a la Izquierda de hacer el primer juego de la juego, y asumir que el Derecho tiene una estrategia ganadora. Con la Izquierda de la primera mover ella pone una piedra en cualquier celda, una colocación llamado "extra". Con este se mueva a la Izquierda se convierte en una Segunda, y ella de ahora en adelante sigue la ganadora la estrategia que está disponible a la Derecha. En algún momento, si esta estrategia pide a la Izquierda para colocar una piedra en la que el extra se encuentra; entonces ella se simplemente hacer otra arbitrariedad. Así, la Izquierda puede ganar en contradicción con la hipótesis.

Answer 1

El punto es que en el juego de la Hexagonal, nunca está de más tener una pieza extra en la junta.

Así, supongamos que hay una estrategia para el segundo jugador, pero usted está atascado con ser el primer jugador. ¿Qué debe hacer?

Bien, usted puede colocar una piedra en el tablero, y luego fingir que en su propia mente que no está ahí! En otras palabras, usted se está imaginando que el otro jugador ahora va a dar el primer paso. En su mente, usted se está imaginando que eres el segundo jugador ahora, y usted puede seguir la estrategia ganadora para el segundo jugador.

La única vez que podría tener problemas si su estrategia ganadora le dice a cabo un movimiento en la posición que están pretendiendo es vacío. Ya que no es realmente vacío, realmente no se puede hacer un movimiento allí. Pero por suerte, ya ha movido de allí, así que usted puede imaginar que usted está haciendo una movida que hay ahora-la piedra ya está ahí, así que usted puede imaginar que usted se acaba de poner lo que hay ahora. Pero, en realidad, usted todavía necesita hacer un movimiento, por lo que usted puede hacer la misma cosa que usted hizo en el principio-sólo tiene que colocar una piedra en alguna posición al azar y, a continuación, imagine que no.

El estado real del juego es siempre igual a su estado imaginado, excepto que hay un extra de piedra de los suyos en la junta, que no puede hacer las cosas peor. Limita el rival opciones, pero si usted tiene una estrategia ganadora, va a trabajar para cualquier movimiento que el adversario hace, así que esto no es un problema.

La conclusión es que, si hay una estrategia para el segundo jugador para ganar, entonces podría "robar" la estrategia como se describe anteriormente para ganar, incluso cuando usted está en el primer jugador. Esta es una contradicción, porque si hubo realmente una estrategia ganadora para el segundo jugador, entonces el primer jugador no sería capaz de garantizar una victoria. Por lo tanto, no hay de hecho ninguna estrategia para el segundo jugador para ganar.

Answer 2

El punto es que tener un "extra" de la pieza en el tablero no puede ayudar a su oponente.

Suponga que la Derecha (el segundo jugador tiene una estrategia ganadora. Una estrategia es una función de $\Phi(A, B)$ que elige lo que mueve a hacer cuando la Izquierda tiene piezas en las posiciones en las $A$ y el de la Derecha tiene las piezas en las posiciones en las $B$. Luego a la Izquierda puede robar esta estrategia de la siguiente manera. En la primera jugada, Izquierda, coloca una pieza en cualquier posición y pide que la posición $x$ ("extra"). En cada movimiento posterior, cuando la Izquierda ha de piezas de $A$ y el de la Derecha tiene piezas en $B$, la Izquierda considera que la posición $y=\Phi(B, A \setminus \{x\})$ (es decir, el mover a la Derecha habría hecho en su posición si ha ignorado la pieza extra). Si $y\neq x$, luego a la Izquierda pone un pedazo a $y$ (y sigue llamando la misma pieza "extra"). Si $y=x$, luego a la Izquierda pone una pieza en cualquier espacio vacío $x'$ y conjuntos de $x=x'$ (es decir, que los cambios que la pieza se llama "extra"). Esta es una estrategia ganadora para la Izquierda. Pero desde la Izquierda y la Derecha no tienen estrategias ganadoras, tenemos una contradicción, y a la conclusión de que nuestra hipótesis debe ser falsa: el Derecho no tiene una estrategia ganadora. Por lo tanto, la Izquierda debe tener uno.