En la teoría de juegos combinatorios , el argumento del robo de estrategia es un argumento general que demuestra, 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 cada jugador tiene el mismo conjunto de movimientos disponibles con los mismos resultados, de modo que el primer jugador puede "utilizar" la estrategia del segundo jugador) en el que un movimiento adicional nunca puede ser una desventaja. Una propiedad clave de un argumento de robo de estrategia es que demuestra que el primer jugador puede ganar (o posiblemente empatar) el juego sin realmente construir tal estrategia. Por lo tanto, aunque podría demostrar la existencia de una estrategia ganadora, la prueba no brinda 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 está utilizando. Pero entonces, en términos generales, después de hacer un primer movimiento arbitrario (lo 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 estrategia fue inventado por John Nash en la década de 1940 para demostrar que el juego de hexadecimal es siempre una victoria del primer jugador, ya que los empates no son posibles en este juego. [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 el 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 el 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 acuñación de Sylver , el robo de estrategia se ha utilizado para demostrar que el primer jugador puede ganar en ciertas posiciones llamadas "finalizadores". [3] En todos estos ejemplos la prueba no revela nada sobre la estrategia real.
Un argumento de robo de estrategia puede usarse 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á usando una estrategia S que garantiza una victoria. El primer jugador (P1) coloca una X en una posición arbitraria. P2 responde colocando una O de acuerdo con S. Pero si P1 ignora la primera X aleatoria , P1 ahora está 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 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. Siguiendo de esta manera, por hipótesis, S tiene la garantía de producir una posición ganadora (con una X adicional ignorada sin importancia). Pero entonces P2 ha perdido, lo que contradice la suposición de que P2 tenía una estrategia ganadora garantizada. Por lo tanto, no existe una estrategia ganadora de este tipo para P2, y el tres en raya 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 es válida para cualquier juego posicional fuerte .
Existe una clase de posiciones de ajedrez denominadas Zugzwang en las que el jugador obligado a mover preferiría "pasar" si esto se le permitiera. Debido a esto, el argumento del robo de estrategia 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 las partidas modernas de alto nivel muestran que el porcentaje de victorias de las blancas es aproximadamente un 10% [ cita requerida ] más alto que el de las negras.
En Go, se permite pasar las cartas. 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 [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 funcione.
Una estrategia elemental del juego es el " mirror go ", en el que el segundo jugador realiza movimientos diagonalmente opuestos a los de su oponente. Este enfoque puede ser derrotado utilizando 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 demuestra que el segundo jugador no puede ganar, al derivar una contradicción de cualquier estrategia ganadora hipotética para el segundo jugador. El argumento se emplea comúnmente en juegos en los que no puede haber empate, por medio de la ley del medio excluido . Sin embargo, no proporciona una estrategia explícita para el primer jugador, y debido a esto se lo ha calificado de no constructivo. [4] Esto plantea la pregunta 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 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 PSPACE-difícil en dos tipos de juegos en los que se usaron argumentos de robo de estrategia: el juego poset mínimo y el juego Maker-Maker simétrico . [7]