Argumento sobre el robo de estrategias

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 ambos jugadores tienen 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. ^{[ 1 ]} Una propiedad clave del argumento del robo de estrategia es que prueba que el primer jugador puede ganar (o posiblemente empatar) el juego sin construir realmente dicha estrategia. Por lo tanto, aunque podría probar la existencia de una estrategia ganadora, la prueba no proporciona información sobre cuál es esa estrategia.

El argumento se basa en una contradicción . Se presupone que el segundo jugador, que la utiliza, tiene una estrategia ganadora. Sin embargo, en términos generales, tras realizar un primer movimiento arbitrario —que, según las condiciones anteriores, no representa una desventaja—, el primer jugador también puede jugar siguiendo 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 hex siempre es ganado por el primer jugador, ya que los empates no son posibles en este juego. ^{[ 2 ]} 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 . ^{[ 2 ] [ 3 ]} 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 (excepto 1x1). En el juego de Sylver coinage , el robo de estrategia se ha utilizado para demostrar que el primer jugador puede ganar en ciertas posiciones llamadas "enders". ^{[ 4 ]} En todos estos ejemplos, la demostración 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. ^{[ 2 ] [ 3 ]} 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 según 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. P1 puede entonces hacer un movimiento según S , es decir, a menos que S requiera 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 requerida por S , mientras que otra esté en una posición aleatoria, y se convierta en la nueva pieza ignorada, dejando la situación como antes. Siguiendo este razonamiento, S tiene garantizada, por hipótesis, una posición ganadora (con una X adicional ignorada sin consecuencias). Pero entonces P2 pierde, 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 tres en raya resulta en una victoria forzada para P1 o en un empate. (Un análisis posterior demuestra que, de hecho, se trata de un empate).

La misma prueba es válida para cualquier juego posicional fuerte .

Existe una clase de posiciones de ajedrez llamada Zugzwang en la que el jugador obligado a mover preferiría "pasar" si esto estuviera permitido. Por esta razón, el argumento del robo de estrategia no se puede aplicar al ajedrez. ^{[ 5 ]} Actualmente se desconoce 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 que las blancas ganan con más frecuencia que las negras en partidas de alto nivel.

Si se modifican las reglas para permitir que los jugadores pasen, la simetría de la posición inicial permite utilizar un argumento de robo de estrategia para demostrar que el primer jugador tiene al menos un empate, como lo describió por primera vez Claude Shannon : si el primer jugador tiene una jugada ganadora en la posición inicial, que la juegue; de ​​lo contrario, que pase. En el turno del segundo jugador, si el primero no tenía ninguna jugada ganadora antes, el segundo tampoco la tiene ahora. Por lo tanto, el segundo jugador puede, en el mejor de los casos, empatar, y el primero al menos empatar, de modo que una partida perfecta resulta en que el primer jugador gane o empate. ^{[ 6 ]}

En Go, pasar el turno está permitido. Cuando la posición inicial es simétrica (tablero vacío, ninguno de los jugadores 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, ^{[ 7 ]} 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 es válido.

Una estrategia básica del juego es el " go espejo ", donde el segundo jugador realiza movimientos diagonalmente opuestos a los de su oponente. Esta estrategia puede ser contrarrestada mediante tácticas de escalera , combates 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 dicho jugador. Este argumento se emplea comúnmente en juegos donde no puede haber empate, debido a la ley del tercero excluido . Sin embargo, no proporciona una estrategia explícita para el primer jugador, y por ello se le ha denominado no constructivo. ^{[ 5 ]} 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 búsqueda exhaustiva. ^{[ 8 ]} Sin embargo, esto podría ser 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 utilizaron argumentos de robo de estrategia: el juego de poset mínimo y el juego simétrico Maker-Maker . ^{[ 9 ]}