Argumento de robo de estrategia - Strategy-stealing argument
En la teoría de juegos combinatorios , el argumento del robo de estrategia es un argumento general que muestra, para muchos juegos de dos jugadores , que el segundo jugador no puede tener una estrategia ganadora garantizada . El argumento del robo de estrategia se aplica a cualquier juego simétrico (uno en el que cualquiera de los jugadores tiene el mismo conjunto de movimientos disponibles con los mismos resultados, de modo que el primer jugador puede "usar" la estrategia del segundo jugador) en el que nunca se puede realizar un movimiento adicional. una desventaja.
El argumento funciona obteniendo una contradicción . Se supone que existe una estrategia ganadora para el segundo jugador, que la está usando. Pero luego, hablando en términos generales, después de hacer un primer movimiento arbitrario, que según las condiciones anteriores no es una desventaja, el primer jugador también puede jugar de acuerdo con esta estrategia ganadora. El resultado es que ambos jugadores tienen la garantía de ganar, lo cual es absurdo, lo que contradice la suposición de que tal estrategia existe.
El robo de estrategia fue inventado por John Nash en la década de 1940 para demostrar que el juego de hex es siempre una victoria del primer jugador, ya que los empates no son posibles en este juego. Sin embargo, Nash no publicó este método, y Beck (2008) atribuye su primera publicación a Alfred W. Hales y Robert I. Jewett, en el artículo de 1963 sobre tic-tac-toe en el que también demostraron el teorema de Hales-Jewett . Otros ejemplos de juegos a la que el argumento se aplica incluir la m , n , k -Juegos como gomoku . En el juego de la acuñación de Sylver , el robo de estrategia se ha utilizado para mostrar que el primer jugador gana, en lugar de que el juego termine en un empate.
Ejemplo
Se puede utilizar un argumento de robo de estrategia en el ejemplo del juego de tic-tac-toe , para un tablero y filas ganadoras de cualquier tamaño. Suponga que el segundo jugador (P2) está usando una estrategia S que garantiza una victoria. El primer jugador (P1) coloca una X en una posición arbitraria. P2 responde mediante la colocación de un O de acuerdo con S . Pero si P1 ignora la primera X aleatoria , P1 está ahora en la misma situación que P2 en el primer movimiento de P2: una sola pieza enemiga en el tablero. Por lo tanto, P1 puede hacer un movimiento de acuerdo con S , es decir, a menos que S pida que se coloque otra X donde ya está colocada la X ignorada . Pero en este caso, P1 puede simplemente colocar una X en alguna otra posición aleatoria en el tablero, cuyo efecto neto será que una X está en la posición demandada por S , mientras que otra está en una posición aleatoria, y se convierte en la nueva. Pieza ignorada, dejando la situación como antes. Continuando de esta manera, se garantiza, por hipótesis , que S producirá una posición ganadora (con una X adicional ignorada sin consecuencias). Pero entonces P2 ha perdido, lo que contradice la suposición de que P2 tenía una estrategia ganadora garantizada. Por lo tanto, tal estrategia ganadora para P2 no existe, y el tic-tac-toe es una victoria forzada para P1 o un empate. (Un análisis más detallado muestra que, de hecho, es un empate).
La misma prueba vale para cualquier juego posicional fuerte .
Ajedrez
| a | B | C | D | mi | F | gramo | h | ||
| 8 |      |
8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | B | C | D | mi | F | gramo | h | ||
Hay una clase de posiciones de ajedrez llamadas Zugzwang en las que el jugador obligado a moverse preferiría "pasar" si esto estuviera permitido. Debido a esto, el argumento del robo de estrategias no se puede aplicar al ajedrez. Actualmente no se sabe si las blancas o las negras pueden forzar una victoria con un juego óptimo, o si ambos jugadores pueden forzar un empate. Sin embargo, prácticamente todos los estudiantes de ajedrez consideran que el primer movimiento de las blancas es una ventaja y las estadísticas de las partidas modernas de alto nivel tienen un porcentaje de victorias de las blancas aproximadamente un 10% más alto que el de las negras.
Ir
En Go se permite el paso. Cuando la posición inicial es simétrica (tablero vacío, ningún jugador tiene puntos), esto significa que el primer jugador podría robar la estrategia ganadora del segundo jugador simplemente renunciando al primer movimiento. Sin embargo, desde la década de 1930, el segundo jugador suele recibir algunos puntos de compensación , lo que hace que la posición inicial sea asimétrica, y el argumento del robo de estrategia ya no funcionará.
Una estrategia elemental en el juego es " ir espejo ", donde el segundo jugador realiza movimientos que son diagonalmente opuestos a los de este oponente. Este enfoque puede ser derrotado usando tácticas de escalera , peleas de ko o compitiendo con éxito por el control del punto central del tablero.
Constructividad
El argumento del robo de estrategia muestra que el segundo jugador no puede ganar, derivando una contradicción de cualquier estrategia ganadora hipotética para el segundo jugador. El argumento se emplea comúnmente en juegos donde no puede haber empate, por medio de la ley del medio excluido . Sin embargo, no proporciona una estrategia explícita para el primer jugador, por lo que se le ha llamado no constructiva. Esto plantea la cuestión de cómo calcular realmente una estrategia ganadora.
Para juegos con un número finito de posiciones alcanzables, como chomp , se puede encontrar una estrategia ganadora mediante una búsqueda exhaustiva. Sin embargo, esto puede resultar poco práctico si el número de posiciones es grande.
En 2019, Greg Bodwin y Ofer Grossman demostraron que el problema de encontrar una estrategia ganadora es difícil de PSPACE en dos tipos de juegos en los que se utilizaron argumentos de robo de estrategia: el juego de poset mínimo y el juego simétrico Maker-Maker .