Robo de estrategia
En la teoría de juegos, en particular la teoría de juegos combinatorios, el argumento o demostración por 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 "utilizar" la estrategia del segundo) en el que un movimiento extra nunca puede ser una desventaja.
El argumento funciona obteniendo una contradicción. Se asume que existe una estrategia ganadora para el segundo jugador, que la está usando. Pero luego, en términos generales, después de hacer su primer movimiento, que por 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 para el primer jugador, ya que los empates no son posibles en este juego.[1] Sin embargo, Nash no publicó este método, y Beck (2008)[2] 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.[3] Otros ejemplos de juegos a la que el argumento se aplica incluir juegos m,n,k como gomoku. En el juego de la acuñación de Sylver, el robo de estrategia se ha utilizado para demostrar que el primer jugador gana, en lugar de que el juego termine en un empate.[4]
Ejemplo
[editar]Se puede usar 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.[1][3] Supóngase que el segundo jugador está usando una estrategia, S, que le garantiza una victoria. El primer jugador coloca una X en una posición arbitraria, y el segundo jugador responde entonces mediante la colocación de un O de acuerdo con S. Pero si ignoran la primera X aleatoria que colocaron, el primer jugador se encuentra en la misma situación que enfrentó el segundo jugador en su primer movimiento; una sola pieza enemiga en el tablero. Por lo tanto, el primer jugador puede hacer sus movimientos de acuerdo con S, es decir, a menos que S pide que se coloque otra X donde ya está colocada la X ignorada. Pero en este caso, el jugador puede simplemente colocar su X en alguna otra posición aleatoria en el tablero, cuyo efecto neto será que una X está en la posición exigida por S, mientras que otra está en una posición aleatoria, y se convierte en el nueva pieza ignorada, dejando la situación como antes. Continuando de esta manera, S está, por hipótesis, garantizado para producir una posición ganadora (con una X ignorada adicional sin consecuencias). Pero luego el segundo jugador ha perdido, contradiciendo la suposición de que tenían una estrategia ganadora garantizada. Por lo tanto, tal estrategia ganadora para el segundo jugador no existe, y el tic-tac-toe es una victoria forzada para el primer jugador 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
[editar]
| |||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
|
|
|
|
|
|
|
|
| ||
|
|
|
|
|
|
|
|
| ||
|
|
|
|
|
|
|
| ||
|
|
|
|
|
|
|
|
| ||
|
|
|
|
|
|
|
|
| ||
|
|
|
|
|
|
|
|
| ||
|
| |||||||||
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.[5] 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 tienen un porcentaje de victorias de las blancas aproximadamente un 10% más alto que el de las negras.
Go
[editar]En go se permite pasar. 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,[6] 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 "go 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
[editar]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.[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 una búsqueda exhaustiva.[7] 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 PSPACE-completo en dos tipos de juegos en los que se utilizaron argumentos de robo de estrategia: el juego poset mínimo y el juego simétrico Maker-Maker.[8]
Referencias
[editar]- ↑ a b Beck, József (2008). Combinatorial Games: Tic-Tac-Toe Theory. Encyclopedia of Mathematics and its Applications. Cambridge University Press. ISBN 978-0-521-46100-9. Consultado el 15 de febrero de 2021.
- ↑ Hales, A. W.; Jewett, R. I. (1963). «Regularity and positional games». Transactions of the American Mathematical Society (en inglés) 106 (2): 222-229. ISSN 0002-9947. doi:10.1090/S0002-9947-1963-0143712-1. Consultado el 15 de febrero de 2021.
- ↑ a b Hales, A. W.; Jewett, R. I. (1963). «Regularity and positional games». Transactions of the American Mathematical Society (en inglés) 106 (2): 222-229. ISSN 0002-9947. doi:10.1090/S0002-9947-1963-0143712-1. Consultado el 15 de febrero de 2021.
- ↑ Sicherman, George (2002), «Theory and Practice of Sylver Coinage», Integers 2, G2.
- ↑ a b Bishop, J. M.; Nasuto, S. J.; Tanay, T.; Roesch, E. B.; Spencer, M. C. (2016), «HeX and the single anthill: Playing games with Aunt Hillary», en Müller, Vincent C., ed., Fundamental Issues of Artificial Intelligence, Synthese Library 376, Springer, pp. 369-390, doi:10.1007/978-3-319-26485-1_22.. See in particular Section 22.2.2.2, The Strategy-Stealing Argument, p. 376.
- ↑ Fairbairn, John, History of Komi, consultado el 9 de abril de 2010.
- ↑ rjlipton (2 de octubre de 2013). «Stealing Strategies». Gödel's Lost Letter and P=NP (en inglés). Consultado el 30 de noviembre de 2019.
- ↑ Bodwin, Greg; Grossman, Ofer (2019-11-15). «Strategy-Stealing is Non-Constructive». .
| Control de autoridades |
|
|---|
Datos: Q1158962