En la teoría de juegos combinatoria , 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 (aquel 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) en el que nunca se puede realizar un movimiento extra. una desventaja. Una propiedad clave del argumento del robo de estrategia es que demuestra que el primer jugador puede ganar (o posiblemente empatar) el juego sin tener que elaborar dicha estrategia. Entonces, aunque podría probar la existencia de una estrategia ganadora, la prueba no proporciona información sobre cuál es esa estrategia.
El argumento funciona obteniendo una contradicción . Se supone que existe una estrategia ganadora para el segundo jugador que la utiliza. Pero entonces, hablando en términos generales, después de realizar 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 garantizada la victoria, lo cual es absurdo y contradice la suposición de que tal estrategia existe.
El robo de estrategias fue inventado por John Nash en la década de 1940 para demostrar que en el juego de hexágono siempre gana el primer jugador, ya que en este juego no es posible empatar. [1] Sin embargo, Nash no publicó este método, y József Beck atribuye su primera publicación a Alfred W. Hales y Robert I. Jewett, en el artículo de 1963 sobre tres en raya en el que también demostraron el teorema de Hales-Jewett. . [1] [2] Otros ejemplos de juegos a los que se aplica el argumento incluyen los juegos m , n , k como gomoku . En el juego de Chomp, el robo de estrategia muestra que el primer jugador tiene una estrategia ganadora en cualquier tablero rectangular (que no sea 1x1). En el juego de monedas Sylver , se ha utilizado el robo de estrategias para demostrar que el primer jugador puede ganar en ciertas posiciones llamadas "enderers". [3] En todos estos ejemplos, la prueba no revela nada sobre la estrategia real.
Se puede utilizar un argumento de robo de estrategia en el ejemplo del juego de tres en raya , para un tablero y filas ganadoras de cualquier tamaño. [1] [2] Supongamos que el segundo jugador (P2) está utilizando una estrategia S que garantiza una victoria. El primer jugador (P1) coloca una X en una posición arbitraria. P2 responde colocando una O según S. Pero si P1 ignora la primera X aleatoria , P1 ahora se encuentra 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 solicite 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 del 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, por hipótesis, se garantiza que S producirá una posición ganadora (con una X adicional ignorada sin consecuencias). Pero entonces P2 perdió, contradiciendo la suposición de que P2 tenía una estrategia ganadora garantizada. Por lo tanto, tal estrategia ganadora para P2 no existe, y el tres en raya es una victoria forzada para P1 o un empate. (Un análisis más detallado muestra que, de hecho, se trata de un empate).
La misma prueba se aplica a cualquier juego posicional fuerte .
Existe una clase de posiciones de ajedrez llamadas Zugzwang en las que el jugador obligado a moverse preferiría "pasar" si esto estuviera permitido. Por esta razón, el argumento del robo de estrategias no se puede aplicar al ajedrez. [4] 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 los juegos modernos de alto nivel muestran que el porcentaje de victorias de las blancas es aproximadamente un 10% [ cita necesaria ] mayor que el de las negras.
En Go se permite adelantar. 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 simplemente renunciando al primer movimiento. Sin embargo, desde la década de 1930, [5] 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 el " ir espejo ", donde el segundo jugador realiza movimientos diagonalmente opuestos a los de su oponente. Este enfoque puede derrotarse usando tácticas de escalera , peleas de ko o compitiendo con éxito por el control del punto central del tablero.
El argumento del robo de estrategia muestra que el segundo jugador no puede ganar, al derivar una contradicción de cualquier hipotética estrategia ganadora para el segundo jugador. El argumento se emplea comúnmente en juegos donde no puede haber empate, mediante la ley del tercero excluido . Sin embargo, no proporciona una estrategia explícita para el primer jugador y por eso se le ha llamado no constructivo. [4] 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. [6] Sin embargo, esto podría 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 en 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 . [7]