Dilemmes de prisonniers et stratégies dominantes

Le 9 octobre 2019  - Ecrit par  Jordi Deolofeu Voir les commentaires (4)

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

En 2013, l’Institut Henri Poincaré et Images des Mathématiques avaient 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 édition avait été entièrement lue et corrigée par l’équipe d’Images des Mathématiques ; des préfaces et listes bibliographiques rajoutées.

En 2019, cette collection est de nouveau éditée, présentée par Étienne Ghys et distribuée par L’Obs.

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. Il sera également accompagné du sommaire du livre et d’une invitation à prolonger votre lecture.

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, 2019

Crédits image :

Image à la une - Manon Bucciarelli
img_9921 - Archives RBA

Commentaire sur l'article

Voir tous les messages - Retourner à l'article

  • 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