Dilemas de prisioneros y estrategias dominantes

El 9 octubre 2019  - Escrito por  Jordi Deolofeu
El 20 febrero 2022  - Traducido por  Julio E. De Villegas, Jimena Royo-Letelier
Artículo original : Dilemmes de prisonniers et stratégies dominantes Ver los comentarios
Leer el artículo en  

El Instituto Henri Poincaré e Images des Mathématiques han unido sus esfuerzos para supervisar la reedición de la colección El mundo es matemático, publicado por RBA en convenio con Le Monde. En 40 obras, esta colección de calidad, -resultado de un proyecto colectivo de matemáticos españoles- aspira a presentar a través de una gran variedad de puntos de vista, de múltiples facetas, las ciencias matemáticas, bajo un aspecto histórico, humano, social, técnico, cultural...
Revisado y mejorado al nivel de la forma, esta nueva edición fue completamente leída y corregida por el equipo de Images des Mathématiques. Se agregó prefacios y listas bibliográficas. Le Monde consagra un suplemento especial para el lanzamiento de esta colección presentada por Cédric Villani, quien escribió el prefacio original.
Cada semana, con la salida de un nuevo número de la serie, un extracto seleccionado será presentado en Images des Mathématiques. Estará acompañado por un índice del libro y una invitación a prolongar su lectura.

Extracto del Capítulo 2 - Los juegos de estrategia y de resolución de problemas

’’Pese a que hay pocas cosas más divertidas que los rompecabezas -que presentan un desafío al ingenio y a la capacidad de razonar- el rol de esos juegos no se reduce sólo a la entretención: como lo indicó J.E. Littlewood, un buen rompecabezas matemático puede aportar más a las matemáticas que una docena de artículos mediocres.’’ Martin Gardner

Los juegos pueden clasificarse de varias formas, según los criterios utilizados: la ubicación, el número de participantes, la duración de una partida, el nivel de dificultad, etc. En el campo de las matemáticas, la intervención del azar es el elemento que permite distinguir dos grupos de juegos. Esta intervención puede aparecer de diversas maneras: durante las fases iniciales del juego o durante la realización de las posibles jugadas. Por ejemplo, en la mayoría de los juegos de cartas, éstas son distribuídas aleatoriamente entre los participantes. En el juego del dominó, las piezas también son repartidas al azar. En cambio, la situación inicial de un juego de ajedrez está determinada y siempre es la misma, igual que en una partida de backgammon, de parchís o de reversi. En cuanto a las jugadas posibles, hay numerosos juegos que no se valen del azar y donde cada jugador decide libremente la jugada que realiza en cada turno, entre todas las posibilidades ofrecidas. En otros juegos, la intervención del azar se manifiesta habitualmente con el lanzamiento de uno o más dados, y no es sino hasta después de efectuar esa acción que el jugador decide una jugada posible, en función del resultado obtenido en los dados.

PNG - 135.1 KB
Dominós del siglo XIX. El juego de dominós forma parte de esta categoría de juegos en que el azar interviene únicamente al momento de escoger las piezas. El resto de la partida depende de la habilidad de los jugadores.

Se llama juegos de estrategia al conjunto de juegos que no necesitan nunca el concurso del azar, y en los cuales sólo intervienen las decisiones de los participantes en el momento de realizar sus jugadas.

[...]

Hacia la determinación de una estrategia

Vamos ahora a analizar en primer lugar los juegos que llevan un sólo conjunto de fichas y en el curso del cual es posible retirar un número variable de fichas, con un mínimo de 1 y un máximo de $n$. Esta situación presenta dos casos concretos, de los cuales propondremos enseguida una generalización. El más simple de estos juegos es el siguiente.

Juego 1 (dos jugadores): el 20º gana.
Se coloca 20 fichas del mismo color sobre la mesa y cada jugador puede retirar una o dos por turno. El que retira la última ficha gana la partida. ¿Cuál de los dos jugadores tiene la ventaja? ¿El primero o el segundo? ¿Cómo hacer para ganar en todas las situaciones? ¿Qué ocurre si se cambia el número de fichas? ¿Y si se cambia el objetivo del juego para que pierda el que retira la última ficha? Aquí hay un juego suficientemente simple para que uno pueda analizarlo por completo, determinar una estrategia ganadora y generalizarla para un número cualquiera de fichas. Si el lector no conoce este juego, antes de que lea la continuación sería interesante que encontrara una pareja para practicarlo y tratar de responder las preguntas formuladas.

La práctica del juego permite descubrir rápidamente que el jugador que deja tres fichas sobre la mesa gana la partida. Es una buena idea, pero no permite ganar, ya que hace falta saber cómo llegar a esas tres fichas. Sin embargo, se sabe ahora que uno gana la partida si retira la 17ª ficha, por lo tanto se reduce el número de piezas. Procediendo hacia atrás, se observa que si se deja 6 fichas sobre la mesa también se gana y, de manera general, si se deja sobre la mesa un número de fichas igual a un múltiplo de tres, entonces se gana siempre la partida. Esto permite formular la estrategia ganadora: con una posición inicial de 20 fichas, el primer jugador puede siempre ganar tomando dos fichas en la primera jugada y dejando siempre sobre la mesa un múltiplo de 3 (si el segundo jugador toma 1 ficha, el primero tomará 2, y viceversa). De ese modo, el juego ofrece la ventaja al primer jugador ya que éste dispone de una estrategia ganadora.

La variación del número inicial de fichas modifica en parte la estrategia, así como el jugador que lleva la ventaja. En efecto, dado que la estrategia ganadora consiste en dejar sobre la mesa un múltiplo de 3, para conocer la continuación de la partida basta con dividir el número inicial de fichas por 3 y observar el resto de la división: si ésta es 2 (como en el caso anterior) el primer jugador gana al retirar 2 fichas en la primera jugada y completando los grupos de 3 (si el adversario toma 1 ficha, el primer jugador toma 2 y viceversa). Si el resto de la división es 1 (se comienza, por ejemplo, con una pila de 19, 25, 100 o 2011 fichas), el primer jugador gana tomando una ficha en la primera jugada. Finalmente, si el resto es 0 (el número de fichas es divisible por 3), el segundo jugador gana al retirar 2 fichas cuando el primero sacó 1, y viceversa. En ese caso, el primer jugador estará siempre en la imposibilidad de dejar sobre la mesa un número de fichas múltiplo de 3. Es así como se generaliza el análisis del juego para cualquier número inicial de fichas. Se puede también llevar la generalización más lejos si se cambia el número de fichas que se puede retirar por cada turno.

Juego 2 (dos jugadores): el 100º pierde
El primer jugador escribe un número de 1 a 10 en un papel. El segundo jugador encuentra un número de 1 a 10, agrega su número al del primer jugador y escribe el resultado de la suma. El juego continúa de manera que, por turno, los dos jugadores añaden al último resultado un número del 1 al 10. El jugador que después de haber sumado su número obtiene un número de tres cifras (mayor o igual a 100) pierde la partida. ¿Cómo hay que jugar para ganar? ¿Cuál de los los jugadores tiene la ventaja? ¿El primero o el segundo? ¿Qué sucede si se cambia el objetivo o las reglas del juego?

Como lo sugerimos más arriba, se aconseja hacer algunas partidas para descubrir la estrategia siempre ganadora para uno de los dos jugadores, y para reflexionar sobre la relación entre este juego y el anterior. Para un análisis del juego que nos permita llegar a la estrategia ganadora, se puede proceder de la siguiente manera: si el jugador que pierde es el que llega a 100, aquél que alcanza a escribir 99 gana. ¿Qué número hay que escribir en el turno anterior para estar seguro de llegar a 99? Se trata del 88, ya que obligará al adversario a escribir un número entre 89 y 98 en la vuelta siguiente, lo que permitirá al jugador llegar a 99. Como en el ejemplo anterior, si se remonta la cadena (para encontrar los números 8, 77, 66 ... hasta el número 11) uno se dará cuenta de que es necesario constituir grupos de 11. Así, es posible enunciar la estrategia ganadora: el jugador que escribe 11, luego los múltiplos sucesivos de ese número (si el adversario propone $n$, el ganador deberá proponer $11 – n$), llegará a 99 y ganará la partida. Ya que el primer jugador no puede llegar a 11 en su primer turno y que, por tanto, el segundo jugador puede lograrlo, hay una estrategia ganadora para el segundo jugador. Como en el juego anterior, si se cambia el número final, el primer jugador ganará siempre si ese número no es múltiplo de 11. En caso contrario, es el segundo jugador quien ganará.

[...]

PDF - 1.5 MB
Sommaire du livre
Post-scriptum :

El extracto propuesto fue elegido por el autor del prefacio del libro Serge Cantat. Él contestará los eventuales comentarios.

Comparte este artículo

Para citar este artículo:

Julio E. De Villegas, Jimena Royo-Letelier — «Dilemas de prisioneros y estrategias dominantes» — Images des Mathématiques, CNRS, 2022

Créditos de las imágenes:

Imagen de portada - Manon Bucciarelli
img_9921 - Archives RBA

Comentario sobre el artículo

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexióninscribirse¿contraseña olvidada?

Registros

Este artículo es parte del registro «El mundo es matemático» consulte el registro
La traducción del sitio del francés al castellano se realiza gracias al apoyo de diversas instituciones de matemáticas de América Latina.