Dilemmes de prisonniers et stratégies dominantes

7 mai 2013  - Ecrit par  Jordi Deolofeu Voir les commentaires (4)

Cet article a été écrit en partenariat avec L’Institut Henri Poincaré

Cet article a été écrit en partenariat avec RBA

L’Institut Henri Poincaré et Images des Mathématiques ont uni leurs efforts pour superviser la réédition de la collection Le monde est mathématique,
publiée par RBA en partenariat avec Le Monde. En 40 ouvrages, cette collection de qualité, issue
d’un projet collectif de mathématiciens espagnols, vise à présenter,
à travers une grande variété de points de vue, de multiples facettes
des sciences mathématiques, sous un aspect historique, humain, social,
technique, culturel ...

Reprise et améliorée au niveau de la forme, cette nouvelle édition a été
entièrement lue et corrigée par l’équipe d’Images des Mathématiques ;
des préfaces et listes bibliographiques ont été ajoutées. Le Monde consacre un cahier spécial au lancement de cette collection présentée par Cédric Villani, qui en a écrit la préface générale.

Chaque semaine, à l’occasion de la sortie d’un nouveau numéro de la série,
un extrait sélectionné sera présenté sur Images des Mathématiques, suivi du sommaire du livre.

Extrait du Chapitre 2 - Les jeux de stratégie et de résolution de problèmes

"Bien qu’il existe peu de choses plus divertissantes que les casse-tête, qui présentent un défi à l’ingéniosité et à la capacité de raisonner, le rôle de ces jeux ne se réduit pas aux seuls loisirs : comme l’indiquait
J.E. Littlewood, un bon casse-tête mathématique peut apporter davantage aux mathématiques qu’une douzaine d’articles médiocres."
Martin Gardner

Les jeux peuvent être classés de différentes façons, selon les critères utilisés : l’emplacement, le nombre de participants, la durée d’une partie, le niveau de difficulté, etc. Dans le domaine des mathématiques, l’intervention du hasard est l’élément qui permet de distinguer deux groupes de jeux, cette intervention pouvant apparaître de différentes manières : durant les phases initiales du jeu ou lors de la réalisation des coups possibles. Par exemple, dans la majorité des jeux de cartes, ces dernières sont distribuées aléatoirement entre les joueurs. Dans le jeu de dominos, les pièces sont aussi réparties par hasard. En revanche, la situation initiale d’un jeu d’échecs est déterminée et est toujours la même, de même que pour une partie de parcheesi, de backgammon ou de reversi. Pour ce qui est des coups possibles, il existe de nombreux jeux qui ne font pas appel au hasard et où chaque joueur décide librement du coup qu’il réalise à chaque tour parmi toutes les possibilités offertes. Dans les autres jeux, l’intervention du hasard se manifeste habituellement avec le lancer d’un ou plusieurs dés, et ce n’est qu’après avoir effectué cette action que le joueur décide d’un coup possible en fonction du résultat obtenu par les dés.

PNG - 149.2 ko
Dominos du XIXe siècle. Le jeu de dominos fait partie de cette catégorie de jeux où le hasard intervient uniquement au moment
de choisir ses pièces. La suite de la partie dépend de l’habileté des joueurs.

On appelle jeux de stratégie l’ensemble des jeux qui ne nécessitent jamais le concours du hasard et dans lesquels n’interviennent que les décisions des joueurs au moment de réaliser leurs coups.

[...]

Vers la détermination d’une stratégie

Nous allons maintenant analyser en premier lieu les jeux comportant un seul ensemble de jetons et au cours duquel il est possible de retirer un nombre variable de jetons,d’un minimum de 1 et d’un maximum de $n$. Cette situation présente deux cas concrets, dont nous proposerons ensuite une généralisation. Le plus simple de ces jeux est le suivant.

Jeu 1 (deux joueurs) : le 20e gagne
On pose 20 jetons de la même couleur sur la table et chaque joueur peut en retirer un ou deux à tour de rôle. Celui qui retire le dernier jeton remporte la partie. Lequel des deux joueurs a l’avantage ? Le premier ou le second ? Comment faut-il jouer pour gagner dans toutes les situations ? Que se passe-t-il si l’on change le nombre de jetons ? Et si l’on change le but du jeu pour que perde celui qui retire le dernier jeton ? Voilà un jeu suffisamment simple pour qu’on puisse l’analyser complètement, déterminer une stratégie gagnante et la généraliser à un nombre quelconque de jetons. Si le lecteur ne connaît pas ce jeu et avant qu’il lise la suite, il serait intéressant qu’il trouve un partenaire pour le pratiquer et tenter de répondre aux questions formulées.

La pratique du jeu permet vite de découvrir que le joueur qui laisse 3 jetons sur la table remporte la partie. C’est une bonne idée, mais elle ne permet pas de gagner, car il faut savoir comment arriver à ces 3 jetons. Néanmoins, on sait maintenant que l’on gagne la partie si l’on retire le 17e jeton, on réduit donc le nombre de pièces. En procédant à rebours, on observe que si on laisse 6 jetons sur la table, on gagne égale- ment, et de manière générale, que si on laisse sur la table un nombre de jetons égal à un multiple de trois, on remporte toujours la partie. Cela permet de formuler la stratégie gagnante : avec une position initiale de 20 jetons, le premier joueur peut toujours gagner en prenant 2 jetons au premier coup et en laissant toujours sur la table un multiple de 3 (si le second joueur prend 1 jeton, le premier en prendra 2, et vice-versa). Ainsi, ce jeu offre l’avantage au premier joueur puisque ce dernier dispose d’une stratégie gagnante.

La variation du nombre initial de jetons modifie en partie la stratégie, ainsi que le joueur qui détient l’avantage. En effet, étant donné que la stratégie gagnante consiste à laisser sur la table un multiple de 3, il suffit, pour connaître la suite de la partie, de diviser
le nombre initial de jetons par 3 et d’observer le reste de la division : si celui-ci est de 2 (comme dans le cas précédent), le premier joueur gagne en retirant 2 jetons au premier coup et en complétant les groupes de 3 (si l’adversaire prend 1 jeton, le premier joueur en prend 2 et vice-versa) ; si le reste de la division est 1 (on commence, par exemple, avec des tas de 19, 25, 100 ou 2011 jetons), le premier joueur gagne en prenant un jeton au premier coup. Enfin, si le reste est 0 (le nombre de jetons est divisible par 3), le deuxième joueur gagne en retirant deux jetons lorsque le premier en a retiré un, et vice-versa. Dans ce cas, le premier joueur sera toujours dans l’impossibilité de laisser sur la table un nombre de jetons multiple de 3. C’est ainsi que l’on généralise l’analyse du jeu pour n’importe quel nombre initial de jetons. On peut aussi pousser plus loin la généralisation si l’on change le nombre de jetons que l’on peut retirer à chaque tour.

Jeu 2 (deux joueurs) : le 100e perd
Le premier joueur écrit un nombre de 1 à 10 sur un papier. Le second joueur trouve un nombre de 1 à 10, ajoute ce nombre à celui du premier joueur et écrit le résultat de l’addition. Le jeu continue de façon à ce que tour à tour, les deux joueurs ajoutent au dernier résultat un nombre de 1 à 10. Le joueur qui après avoir additionné son nombre obtient un nombre à trois chiffres (supérieur ou égal à 100) perd la partie. Comment faut-il jouer pour gagner ? Lequel des deux joueurs a l’avantage ? Le premier ou le second ? Que se passe-t-il si l’on change le but ou les règles du jeu ?

Comme nous l’avons suggéré plus haut, il est conseillé de faire quelques parties pour découvrir la stratégie toujours gagnante pour l’un des deux joueurs et pour réfléchir à la relation entre ce jeu et le précédent. Pour une analyse du jeu qui nous permette d’arriver à la stratégie gagnante, on peut procéder de la manière suivante : si le joueur qui perd est celui qui arrive à 100, celui qui parvient à écrire 99 gagne. Quel nombre faut-il écrire au tour précédent pour être sûr d’arriver à 99 ? Il s’agit de 88, puisqu’il obligera l’adversaire à écrire un nombre compris entre 89 et 98 au tour suivant, ce qui permettra au joueur d’arriver à 99. Comme dans l’exemple précédent,si on remonte la chaîne (pour trouver les nombres 88, 77, 66... jusqu’au nombre 11), on s’apercevra qu’il est nécessaire de constituer des groupes de 11. Ainsi, il est possible d’énoncer la stratégie gagnante : le joueur qui écrit 11, puis les multiples successifs de ce nombre (si l’adversaire propose $n$, le gagnant devra proposer $11 – n$), parviendra à 99 et gagnera la partie. Étant donné que le premier joueur ne peut parvenir à 11 au premier tour alors que le deuxième joueur peut y parvenir, il existe une stratégie gagnante pour le second joueur. Comme dans le jeu précédent, si l’on change le nombre final, le premier joueur gagnera toujours si ce nombre n’est pas un multiple de 11. Dans le cas contraire, c’est le second joueur qui gagnera.

[...]

PDF - 1.5 Mo
Sommaire du livre
Post-scriptum :

L’extrait proposé est choisi par le préfacier du livre : Serge Cantat. Celui-ci répondra aux commentaires éventuels.

Partager cet article

Pour citer cet article :

Jordi Deolofeu — «Dilemmes de prisonniers et stratégies dominantes» — Images des Mathématiques, CNRS, 2013

Crédits image :

Image à la une - Manon Bucciarelli
img_9921 - Archives RBA

Commentaire sur l'article

  • Dilemmes de prisonniers et stratégies dominantes

    le 14 mai 2013 à 00:49, par Cronos

    Ce numéro était sans nul doute celui que j’attendais le plus impatiemment depuis le début de la collection et dont la lecture c’est avéré particulièrement enrichissante. Un petit bémol toutefois, je ne suis pas parvenu à trouver la solution du problème de « dé qui tourne » proposer à la page 58, c’est pourquoi j’en profite pour jeter cette bouteille à la mer avec l’espoir qu’un brillant esprit passant par la puisse éventuellement me fournir quelques pistes.

    Répondre à ce message
  • Dilemmes de prisonniers et stratégies dominantes

    le 13 septembre 2013 à 16:17, par Audibert

    Bonjour Cronos

    Je te propose une solution pour le joli problème du « Dé tournė »

    On pose le dé sur la table la face supérieur étant 4. Et dans ce cas c’est mon adversaire qui joue et tourne le dé.
    Si on pose sur la table le dé dont la face supérieure est 1, 2, 3, 5 ou 6 , alors c’est moi qui joue en premier et tourne le dé.

    Lorsqu’un des deux joueurs tourne le dé , il présente une face nouvelle et annonce un nombre nouveau, par exemple la face 6 qui ajoutée au total précédent donne un nouveau total , par exemple 17 . Cette situation sera notée 617.

    Pour que je puisse, à coup sûr, gagner la partie il me faut tourner le dé de telle sorte que j’obtienne une situation se trouvant dans la grille suivante :

    14. 24. 34. 35. 45. 54. 64.

    28. 39. 310. 49. 410. 58

    113. 213. 313. 314. 413. 414. 513. 613.

    217. 318. 319. 418. 419. 517.

    122. 222. 322. 323. 422. 423. 522. 622.

    226. 327. 328. 427. 428. 526.

    131. 231. 331. 431. 531. 631.

    Les faces 130. 229. 529. 630 sont interdites car elles bloquent la partie.

    Pour suivre facilement la grille il vaut mieux tracer cette grille dans un repère cartésien , les numéros des faces 1,2,3,4,5,6 étant en abscisse et le nombre annoncé allant de 1 à 31 étant en ordonnée.

    Ce joli problème n’est pas très gentil car j’ai du le chercher longtemps .

    Je n’ai pas trouvé de loi arithmétique comme dans « La course à 20 » où intervient la division avec reste ( mais tu peux chercher ; pour moi ça suffit),

    Voilà l’énoncé de « La couse à 20 » avec deux joueurs :Moi et Lui.
    Moi je dis 0 ou 1 ; Lui ajoute 1 ou 2 et annonce le total (1 , 2 ou 3) ;Moi j’ajoute 1 ou 2 à son total et j’annonce le nouveau total , et. Ainsi de suite. Le premier qui dit 20 a gagné.

    La course à 20 est citée dans ce même N°7 Dilemmes... à la page 50 ,sous le titre : Jeu 1 (deux joueurs) : le 20e gagne.

    Si la grille ci-dessus ne marche pas fait moi signe ,il y a peut-être une erreur.
    Je n’ai trouvé aucune référence sur ce problème.
    Ce serait un peu long de te narrer les pérégrinations de ma recherche,
    mais si tu veux me joindre facilement je te donne mon mail :
    geaudibert wanadoo.fr
    Amicalement Audibert

    P.S. Ce commentaire remplace tous mes commentaires du 4 au 10 septembre.

    Répondre à ce message
  • Dilemmes de prisonniers et stratégies dominantes

    le 4 octobre 2013 à 18:53, par Phénakistiscope

    J’ai un problème page 80, je passe brutalement d’un jeu de dés à un jeu télévisé avec des portes (qui se trouve plus loin dans le livre). L’impression des différents chapitres du livre est peut-être aléatoire, mais je reste sur ma faim quand au paradoxe du lancer de dés.

    Serait-il possible d’avoir la suite de l’explication ? et rectifier le tir pour la prochaine édition.

    Répondre à ce message
    • Dilemmes de prisonniers et stratégies dominantes

      le 5 octobre 2013 à 13:35, par Serge Cantat

      Cher Phénakistiscope,

      il y a effectivement eu un problème important suite à une correction mal effectuée sur ce volume. Les pages concernées sont 79-80 puis, plus loin 84-87. C’est très gênant, mais cela n’influe pas sur le reste du livre.

      Un erratum a été prévu pour expliquer le problème et présenter une correction. Je ne sais malheureusement pas s’il a déjà été inséré dans un des volumes suivants ou non.

      Cordialement,

      Serge Cantat

      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Dossiers

Cet article fait partie du dossier «Le monde est mathématique» voir le dossier

Suivre IDM