En teoría de juegos , el teorema de Zermelo es un teorema sobre juegos finitos de dos personas de información perfecta en los que los jugadores se mueven alternativamente y en los que el azar no afecta el proceso de toma de decisiones. Dice que si el juego no puede terminar en empate, entonces uno de los dos jugadores debe tener una estrategia ganadora (es decir, forzar una victoria). Una declaración alternativa es que para un juego que cumpla con todas estas condiciones, excepto la condición de que un empate no es posible, entonces el primer jugador puede forzar una victoria, o el segundo jugador puede forzar una victoria, o ambos jugadores pueden forzar una victoria. dibujar. [1] El teorema lleva el nombre de Ernst Zermelo , un matemático y lógico alemán.
Conclusiones del teorema de Zermelo
El trabajo de Zermelo muestra que en juegos de suma cero de dos personas con información perfecta, si un jugador está en una posición ganadora, siempre puede forzar una victoria sin importar la estrategia que emplee el otro jugador. Además, y como consecuencia, si un jugador está en una posición ganadora, nunca requerirá más movimientos que posiciones en el juego (con una posición definida como posición de piezas así como el jugador siguiente en mover). [1]
Historial de publicaciones
En 1912, durante el Quinto Congreso Internacional de Matemáticos en Cambridge, Ernst Zermelo dio dos charlas. El primero cubrió los métodos axiomáticos y genéticos en la base de las disciplinas matemáticas, y el segundo discurso fue sobre el juego de ajedrez. El segundo discurso llevó a Zermelo a escribir un artículo sobre teoría de juegos. Siendo un ávido jugador de ajedrez, Zermelo estaba preocupado por la aplicación de la teoría de conjuntos al juego de ajedrez. El artículo original de Zermelo que describe el teorema, Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels , se publicó en alemán en 1913. Ulrich Schwalbe y Paul Walker tradujeron el artículo de Zermelo al inglés en 1997 y publicaron la traducción en el apéndice de Zermelo and the Early History de la teoría de juegos . [1] "Sobre una aplicación de la teoría de conjuntos a la teoría del juego del ajedrez" de Zermelo se convirtió en una novedad para la comunidad matemática y puede considerarse como el primer artículo conocido sobre teoría de juegos. [2]
Detalles
Zermelo considera la clase de juegos de dos personas sin azar, donde los jugadores tienen intereses estrictamente opuestos y donde solo son posibles un número finito de posiciones. Aunque en el juego solo son posibles un número finito de posiciones, Zermelo permite infinitas secuencias de movimientos ya que no considera las reglas de parada. Por lo tanto, permite la posibilidad de juegos infinitos. Luego aborda dos problemas:
- ¿Qué significa para un jugador estar en una posición 'ganadora' y es posible definir esto de una manera matemática objetiva?
- Si el jugador está en una posición ganadora, ¿se puede determinar el número de movimientos necesarios para forzar la victoria?
Para responder a la primera pregunta, Zermelo afirma que una condición necesaria y suficiente es la no vacuidad de un determinado conjunto, que contiene todas las posibles secuencias de movimientos de manera que un jugador gana independientemente de cómo juegue el otro jugador. Pero si este conjunto estuviera vacío, lo mejor que podría lograr un jugador sería un empate. Así que define otro conjunto que contiene todas las posibles secuencias de movimientos, de modo que un jugador puede posponer su pérdida por un número infinito de movimientos, lo que implica un empate. Este conjunto también puede estar vacío, es decir, el jugador puede evitar su pérdida por solo un número finito de movimientos si su oponente juega correctamente. Pero esto equivale a que el oponente pueda forzar una victoria. Ésta es la base de todas las versiones modernas del teorema de Zermelo.
Sobre la segunda pregunta, Zermelo afirmó que nunca se necesitarán más movimientos que posiciones en el juego. Su prueba es una prueba por contradicción : suponga que un jugador puede ganar en un número de movimientos mayor que el número de posiciones. Por supuesto, al menos una posición ganadora debe haber aparecido dos veces. Por lo tanto, el jugador podría haber jugado en la primera aparición de la misma manera que lo hace en la segunda y, por lo tanto, podría haber ganado en menos movimientos que posiciones.
En 1927, el matemático húngaro Denes Konig revisó el artículo de Zermelo y señaló algunas lagunas en el trabajo original. En primer lugar, Konig argumenta que Zermelo no probó que un jugador, por ejemplo, las blancas, que está en una posición ganadora siempre pueda forzar una victoria haciendo movimientos más pequeños que el número de posiciones en el juego. Zermelo argumentó que las blancas pueden cambiar su comportamiento a la primera posibilidad de cualquier posición ganadora relacionada y ganar sin repetición. Sin embargo, Koning sostiene que este argumento no es correcto ya que no es suficiente reducir el número de movimientos en un solo juego por debajo del número de posiciones posibles. Así, Zermelo afirmó, pero no demostró, que un jugador ganador siempre puede ganar sin repetición. El segundo objetivo de Konig es que la estrategia "hacer lo mismo en la primera aparición de una posición que en la segunda y, por lo tanto, ganar en menos movimientos" no se puede realizar si es el turno de las negras para moverse en esta posición. Sin embargo, este argumento no es correcto porque Zermelo consideró dos posiciones diferentes si las negras o las blancas hacen un movimiento. [2]
Ejemplo
El teorema de Zermelo se puede aplicar a todos los juegos de dos jugadores en etapas finitas con información completa y movimientos alternos. El juego debe satisfacer los siguientes criterios: hay dos jugadores en el juego; el juego es de información perfecta; el juego de mesa es finito; los dos jugadores pueden alternar turnos; y no hay presente ningún elemento de azar. Zermelo ha afirmado que hay muchos juegos de este tipo, sin embargo, su teorema se ha aplicado principalmente al ajedrez. [3] [4]
Cuando se aplica al ajedrez , el teorema de Zermelo establece que "las blancas pueden forzar una victoria o las negras pueden forzar una victoria, o ambos lados pueden forzar al menos un empate". [3] [4]
El algoritmo de Zarmelo es un algoritmo fundamental en la teoría de juegos, sin embargo, se puede aplicar en áreas fuera de los juegos finitos. Aparte del ajedrez, el teorema de Zermelo se ha aplicado en informática . El algoritmo de Zermelo se aplica en todas las áreas de la informática. En particular, se aplica en la verificación de modelos y la interacción de valores. [5]
Teorema de Zermelo e inducción hacia atrás
Se ha creído que Zermelo utilizó la inducción hacia atrás como método de prueba. Sin embargo, una investigación reciente sobre el teorema de Zermelo demuestra que la inducción hacia atrás no se utilizó para explicar la estrategia detrás del ajedrez. Contrariamente a la creencia popular, el ajedrez no es un juego finito. Estrictamente hablando, el ajedrez es un juego infinito, por lo tanto, la inducción hacia atrás no proporciona el teorema minmax en este juego. [6]
La inducción hacia atrás es un proceso de razonamiento hacia atrás en el tiempo. Se utiliza para analizar y resolver juegos de forma extensa de información perfecta. Este método analiza el juego empezando por el final y luego trabaja hacia atrás para llegar al principio. En el proceso, la inducción hacia atrás determina la mejor estrategia para el jugador que hizo el último movimiento. Entonces se determina la estrategia definitiva para el penúltimo jugador en movimiento del juego. El proceso se repite nuevamente determinando la mejor acción para cada punto del juego que se haya encontrado. Por lo tanto, la inducción hacia atrás determina el equilibrio de Nash de cada subjuego en el juego original. [5]
Hay varias razones por las que la inducción hacia atrás no está presente en el artículo original de Zermelo:
En primer lugar, un estudio reciente de Schwalbe y Walker (2001) demostró que el artículo de Zermelo contenía una idea básica de inducción hacia atrás, sin embargo, Zermelo no hizo una declaración formal sobre el teorema. El método original de Zermelo era la idea de no repetición. La primera mención de la inducción hacia atrás fue proporcionada por László Kalmár en 1928. Kalmar generalizó el trabajo de Zermelo y Konig en su artículo "Sobre la teoría de los juegos abstractos". Kalmar estaba preocupado por la pregunta: "Dada una posición ganadora, ¿con qué rapidez se puede forzar una victoria?". Su artículo mostró que ganar sin repetición es posible dado que un jugador es una posición ganadora. La prueba de no repetición de Kalmar fue la prueba por inducción hacia atrás. En su artículo, Kalmar introdujo el concepto de subjuego y táctica. El argumento central de Kalmar era que una posición puede ser una posición ganadora solo si un jugador puede ganar en un número finito de movimientos. Además, una posición ganadora para el jugador A es siempre una posición perdedora para el jugador B. [7]
Por último, en vista de las leyes oficiales del juego, el ajedrez es un juego infinito. Estrictamente hablando, el juego no tiene una regla o un conjunto de reglas que lo finalice después de un número finito si se han realizado movimientos. El juego no se detiene cuando el número de movimientos supera un límite determinado. En cambio, un jugador puede reclamar terminar el juego en un empate cuando hace un movimiento que lo lleva a una posición en la que los últimos 50 movimientos de dos jugadores se han realizado sin ningún peón y sin capturar la pieza del otro jugador. En segundo lugar, el juego puede terminar de manera efectiva sin que el jugador haga un reclamo en el que un jaque mate no puede ocurrir por ninguna posible serie de movimientos. Siguiendo estas reglas es posible construir un camino infinito en el juego. Es la posibilidad de infinitos caminos en el ajedrez lo que hace que el juego sea infinito. [6]
Referencias
- ↑ a b c Schwalbe, Ulrich; Walker, Paul. "Zermelo y la historia temprana de la teoría de juegos" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ a b Ebbinghaus, Heinz-Dieter (14 de octubre de 2010). Ernst Zermelo: Una aproximación a su vida y obra (2 ed.). Berlín: Springer. pag. 150. ISBN 9783642080500. Consultado el 26 de abril de 2021 .
- ^ a b MacQuarrie, John (enero de 2005). "Matemáticas y Ajedrez, Fundamentos" . Archivado desde el original el 12 de enero de 2017.
- ^ a b Aumann, RJ (1989). Conferencias sobre teoría de juegos (PDF) . Boulder, CO: Westview Press. pag. 1.
- ^ a b Wooldridge, Michael (17 de marzo de 2015). "Pensando hacia atrás con el profesor Zermelo" . Sistemas inteligentes IEEE . 30 (2): 62–67. doi : 10.1109 / MIS.2015.36 . S2CID 12397521 . Consultado el 24 de abril de 2021 .
- ^ a b Ewerhart, Christian (mayo de 2002). "Inducción hacia atrás y el análisis teórico del juego del ajedrez" . Juegos y comportamiento económico . 39 (2): 206–214. doi : 10.1006 / game.2001.0900 .
- ^ Schwalbe, Ulrich; Paul, Walker (enero de 2001). "Zermelo y la teoría de juegos de la historia temprana" . Juegos y comportamiento económico . 34 (1): 123-137. doi : 10.1006 / game.2000.0794 . Consultado el 26 de abril de 2021 .
enlaces externos
- Papel original (en alemán)
- Ulrich Schwalbe, Paul Walker, Zermelo and the Early History of Game Theory , Games and Economic Behavior, Volumen 34, 2001, 123-137, en línea