Prepa HelpJeux à deux joueurs : positions gagnantes, attracteurs et algorithme min-max, cours et exercices corrigés de prépa
Jeux d'accessibilité à deux joueurs sur un graphe, positions et coups, stratégie et position gagnante, calcul des attracteurs, arbre de jeu, algorithme min-max, fonction d'évaluation heuristique et profondeur limitée, complexités.
- 22méthodes
- 47exercices corrigés
- 3problèmes
- 23pièges
- 58figures
Dans un jeu à deux joueurs sans hasard, peut-on savoir d'avance qui gagne si chacun joue au mieux ? Le chapitre répond à cette question du programme d'informatique de deuxième année, en MP, PSI et TSI au Maroc et en MP, PC, PSI, PT, TSI et TPC en France. Il modélise un jeu par une arène, un graphe biparti dont les sommets sont les positions avec le joueur au trait, définit stratégie gagnante et position gagnante, et trouve les positions gagnantes en remontant depuis la fin, à la main et en Python, sur le jeu de cailloux où les multiples de 4 sont perdants. Il construit l'arbre de jeu, mesure son explosion sur le morpion et présente la notion d'heuristique. Pour MP, PSI, PC et PT en France et MP, PSI et TSI au Maroc, il calcule l'attracteur et en tire une stratégie, puis écrit l'algorithme min-max, exact puis avec une profondeur limitée ; ces deux algorithmes ne sont pas au programme de TSI et TPC en France, qui étudient l'heuristique sur le problème du sac à dos. Les problèmes reprennent des sujets de Mines-Ponts 2026 et 2025 et du CCINP 2024.
Ce que tu sauras faire
Au stand de la coopérative, les enfants jouent aux cailloux contre Ba Mbarek : chacun à son tour retire 1, 2 ou 3 cailloux d'une rangée, et celui qui prend le dernier gagne. Ba Mbarek gagne presque toujours. Peut-on savoir d'avance qui gagnera, si chacun joue au mieux ? Ce chapitre répond à cette question pour les jeux à deux joueurs sans hasard, puis montre comment faire jouer une machine quand le jeu est trop grand pour tout calculer.
- modéliser un jeu à deux joueurs par une arène, un graphe biparti ;
- dérouler une partie et dire qui gagne ;
- reconnaître une stratégie, une stratégie gagnante, une position gagnante ;
- trouver les positions gagnantes en remontant depuis la fin, à la main et en Python ;
- construire un arbre de jeu et estimer sa taille ;
- écrire une heuristique qui évalue une position.
- calculer un attracteur, en déduire les positions gagnantes des deux joueurs et une stratégie gagnante ;
- appliquer l'algorithme min-max, exact puis avec une heuristique et une profondeur limitée.
L'essentiel : Stratégies et positions gagnantes Extrait gratuit
- Stratégie (sans mémoire) de : en chaque position non terminale qu'il contrôle, le coup qu'il joue ; liste
coup, −1 ailleurs. - Stratégie gagnante depuis : toute partie conforme depuis est gagnée par , quels que soient les coups de l'adversaire.
- Position gagnante pour : il a une stratégie gagnante depuis elle. Ce n'est pas forcément à lui de jouer. Jamais gagnante pour les deux ; parfois pour aucun (nul).
- Perdante : aucun coup, ou tous les coups mènent à une position gagnante pour l'adversaire.
- Gagnante : au moins un coup mène à une position perdante pour l'adversaire.
- Avec des nuls : gagne si un coup mène à une position perdue pour l'adversaire ; sinon nul si un coup mène à un nul ; sinon perd.
- Jeu sans circuit : on calcule dans un ordre où les successeurs viennent avant, en .
| jeu du stand (retirer 1, 2 ou 3) | positions perdantes pour le joueur au trait | stratégie |
|---|---|---|
| celui qui prend le dernier gagne | 0, 4, 8, 12... (multiples de 4) | laisser un multiple de 4 |
| celui qui prend le dernier perd | 1, 5, 9... (nombres ) | laisser un nombre |
def gagnantes_retrait(N, coups):
g = [False] * (N + 1)
for n in range(N + 1):
for r in coups:
if r <= n and not g[n - r]:
g[n] = True
return g
Une méthode du chapitre Extrait gratuit
Questions « déterminer les positions gagnantes », « qui gagne si chacun joue au mieux », sur un petit jeu.
Pour le joueur au trait : perdante s'il n'a aucun coup ou si tous ses coups mènent à une position gagnante pour l'adversaire ; gagnante si au moins un coup mène à une position perdante pour l'adversaire ; avec des nuls, gagne si un coup mène à une position perdue pour l'adversaire, sinon nul si un coup mène à un nul, sinon perd (cours, sections 4.1 à 4.4).
- Écrire les fins de partie et leur issue pour le joueur au trait.
- Remonter dans un ordre où les successeurs sont déjà traités (nombres croissants, cases vides décroissantes).
- Appliquer la règle, position par position, dans un tableau.
- Repérer la régularité, puis la stratégie : jouer vers une position perdante pour l'adversaire.
- Traduire dans l'arène si on le demande : gagnante pour si est gagnante pour le joueur au trait.
« Devant la case 0, le joueur au trait ne peut plus jouer : 0 est perdante. Supposons les cases 0 à traitées. Si est impair, le coup de 1 mène en , case paire, donc perdante : est gagnante. Si est pair et non nul, les coups mènent en , et en si , cases impaires, donc gagnantes : est perdante. »
Pion des fiches : 0 perdante ; 1 mène à 0, gagnante ; 2 mène à 1, perdante ; 3 mène à 2 ou à 0, gagnante ; 4 mène à 3 ou à 1, perdante. Par récurrence, les cases paires sont perdantes pour le joueur au trait et les cases impaires gagnantes. Stratégie : laisser une case paire.
- Remonter depuis le début de la partie au lieu des fins.
- Échanger « il existe » et « tous » dans la règle.
- Oublier la position sans coup, qui est perdante pour le joueur au trait.
Exercices 5, 9, 11, 13 et 24.
Un exercice corrigé Extrait gratuit
On retire à tour de rôle 1 ou 2 cailloux ; celui qui prend le dernier gagne.
- Remplir à la main le tableau des positions gagnantes et perdantes pour le joueur au trait, de 0 à 12 cailloux.
- Quelles sont les positions perdantes ? Énoncer une stratégie gagnante pour le joueur qui commence devant une position gagnante.
- Contrôler par programme avec
gagnantes_retrait.
- Méthode 5 : on remonte depuis la fin, 0 caillou d'abord.
- Une position est gagnante pour le joueur au trait si un coup mène à une position perdante ; perdante si tous ses coups mènent à des positions gagnantes, ou s'il n'a aucun coup.
Devant 0 caillou, le joueur au trait ne peut plus jouer : l'autre a pris le dernier, il a perdu. On remplit ensuite le tableau de gauche à droite : pour chaque , on regarde les deux positions et , déjà connues.
Question 1. G pour gagnante, P pour perdante (pour le joueur au trait).
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| issue | P | G | G | P | G | G | P | G | G | P | G | G | P |
Devant 1 ou 2, on prend tout. Devant 3, les deux coups laissent 2 ou 1, gagnantes pour l'adversaire : 3 est perdante. Devant 4 ou 5, on laisse 3. Et ainsi de suite.
Question 2. Les positions perdantes sont les multiples de 3. Stratégie : devant cailloux, non multiple de 3, retirer le reste de dans la division par 3 (1 ou 2), pour laisser un multiple de 3 ; l'adversaire laisse alors un nombre qui n'en est pas un, et l'on recommence jusqu'à 0.
Question 3.
g = gagnantes_retrait(12, [1, 2])
print([n for n in range(13) if not g[n]])
Le programme affiche :
[0, 3, 6, 9, 12]
On remonte depuis la fin : la position sans coup est perdante pour le joueur au trait, puis chaque position se déduit des précédentes. Avec des retraits de 1 à , les positions perdantes sont les multiples de . Voir la méthode 5.
Le cours détaillé, toute la fiche « L'essentiel », 22 méthodes, 23 pièges corrigés, la carte mentale, 47 exercices corrigés, 3 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Ce chapitre est offert : il s’ouvre en entier avec un compte d’essai gratuit.
Ouvrir l'essai gratuitVoir les offresPlan du cours
- 1. Jeux à deux joueurs
- 1.1 Au stand de la coopérative
- 1.2 Les jeux étudiés
- 1.3 Position, coup, joueur au trait
- 1.4 Fins de partie
- 1.5 Le Python employé dans ce chapitre
- 2. L'arène : le jeu comme un graphe
- 2.1 Rappel : graphes orientés
- 2.2 Graphe biparti
- 2.3 L'arène d'un jeu
- 2.4 L'arène en Python
- 2.5 Partie
- 2.6 Jeu d'accessibilité
- 3. Stratégies et positions gagnantes
- 3.1 Stratégie
- 3.2 Stratégie gagnante
- 3.3 Position gagnante
- 3.4 Vérifier qu'une stratégie gagne
- 4. Trouver les positions gagnantes
- 4.1 Remonter depuis la fin, à la main
- 4.2 Du joueur au trait à l'arène
- 4.3 La remontée en Python
- 4.4 Avec des nuls
- 4.5 L'attracteur, couche par couche
- 4.6 Rang et stratégie gagnante
- 4.7 Les positions gagnantes des deux joueurs
- 4.8 Calcul par point fixe
- 4.9 Propagation arrière
- 4.10 La stratégie en Python
- 5. L'arbre de jeu
- 5.1 De l'arène à l'arbre
- 5.2 Le morpion en Python
- 5.3 Compter
- 5.4 L'explosion
- 5.5 Le coût d'une exploration complète
- 6. La notion d'heuristique
- 6.1 Quand on ne peut pas tout essayer
- 6.2 Évaluer une position sans aller au bout
- 6.3 Jouer avec l'évaluation seule
- 7. L'algorithme min-max
- 7.1 La valeur d'une position
- 7.2 Remonter à la main
- 7.3 Sur le jeu de cailloux
- 7.4 Le code
- 7.5 Terminaison, correction, complexité
- 7.6 Ne pas réévaluer une position : la mémoïsation
- 7.7 Une autre écriture : le negamax
- 8. Min-max avec une heuristique
- 8.1 Le min-max quand l'arbre est trop grand
- 8.2 Le code
- 8.3 Une trace
- 8.4 Coût et qualité
- 8.5 Pour aller plus loin
- 9. Bilan
- 9.1 Quelle méthode pour quelle question
- 9.2 Les complexités
- 9.3 Vers le chapitre suivant
- 7. Une heuristique sur le sac à dos
- 7.1 Le panier de dattes du stand
- 7.2 Tout essayer
- 7.3 L'heuristique gloutonne
- 7.4 Rapide, sans garantie
- 7.5 Ce qu'est une heuristique
- 8. Bilan
- 8.1 Quelle méthode pour quelle question
- 8.2 Les complexités
- 8.3 Vers le chapitre suivant
Les méthodes du chapitre
Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.
- Modéliser un jeu
- Construire l'arène et vérifier qu'elle est bipartie
- Dérouler une partie et dire qui gagne
- Représenter une stratégie et vérifier qu'elle est gagnante
- Trouver les positions gagnantes à la main en remontant depuis la fin
- Programmer la remontée pour un jeu sans circuit
- Programmer un plateau : coups possibles, vainqueur, jouer un coup sans modifier la position
- Construire un arbre de jeu, compter ses nœuds, distinguer positions et parties
- Estimer la taille d'une exploration et conclure sur sa faisabilité
- Écrire et tester une fonction d'évaluation heuristique
- Justifier qu'un programme de jeu termine et compter ses appels
- Calculer un attracteur à la main, couche par couche, avec les rangs
- Déduire les positions gagnantes des deux joueurs et les nuls
- Construire une stratégie gagnante à partir du rang
- Programmer l'attracteur et justifier terminaison, correction et complexité
- Remonter les valeurs min-max à la main et choisir le coup
- Écrire le min-max récursif
- Limiter la profondeur avec une heuristique, et discuter coût et qualité
- Ne pas réévaluer une position : la mémoïsation
- Présenter une heuristique gloutonne sur le sac à dos
- Énumérer tous les choix d'un petit sac à dos et compter le coût
- Montrer qu'une heuristique n'est pas exacte
Les exercices corrigés
Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.
Application directe (18)
- Six cailloux
- Biparti ou non
- L'arène des allumettes
- Qui gagne cette partie ?
- Retirer 1 ou 2
- Cette stratégie gagne-t-elle ?
- L'arbre des allumettes
- Ordres de grandeur
- Une fin de morpion
- Évaluer des positions
- Un attracteur à la main
- Trouver l'erreur dans une définition
- Du rang à la stratégie
- Remonter un arbre de profondeur 3
- Une arène avec des nuls
- Les mots du programme
- Le panier à la main
- Trois critères gloutons
Entraînement (22)
- Celui qui prend le dernier perd
- Retirer 1, 3 ou 4
- La tablette de dattes
- L'arène d'un jeu de retrait
- Vérifier une stratégie
- Le morpion en Python
- Compter le morpion
- Une heuristique pour un jeu d'alignement
- Le pion sur un graphe
- Le coup de l'évaluation seule
- Quixo : alignements et vainqueur
- Le point fixe
- La propagation arrière
- Jouer avec la stratégie
- Min-max sur le jeu de cailloux
- Le meilleur coup au morpion
- Profondeur limitée sur une petite grille
- Mémoïser le morpion
- Meilleur et pire cas du calcul de l'attracteur
- Le glouton sans tri
- Tout essayer
- Le glouton à l'épreuve
Approfondissement (7)
- Juniper Green
- Le morpion à symétrie près
- Pourquoi la remontée est juste
- La propagation arrière est juste
- Hors de l'attracteur, J2 tient
- Profondeur et qualité
- Moins de la moitié
Les problèmes de concours
Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.
- Le Quixo contre l'ordinateur
- L'awalé contre l'ordinateur
- Le sac à dos, de la force brute à l'heuristique
Questions fréquentes
Comment trouver les positions gagnantes d'un jeu de cailloux ?
On raisonne pour le joueur qui doit jouer, en remontant depuis la fin de la partie. Une position est perdante pour lui s'il n'a aucun coup, ou si tous ses coups mènent à une position gagnante pour l'adversaire. Elle est gagnante si au moins un de ses coups mène à une position perdante pour l'adversaire. Dans le jeu où chacun retire à son tour 1, 2 ou 3 cailloux et où celui qui prend le dernier gagne, 0 caillou est perdant, puisque le joueur ne peut plus jouer. Les positions 1, 2 et 3 sont gagnantes : on prend tout. La position 4 est perdante : tout coup laisse 3, 2 ou 1 caillou à l'adversaire. Les positions perdantes sont donc les multiples de 4, et la stratégie gagnante consiste à laisser un multiple de 4. En Python, une liste de booléens remplie de 0 à N donne ce résultat en un temps proportionnel au nombre de positions et de coups. Si celui qui prend le dernier perd, les positions perdantes deviennent 1, 5, 9, de la forme 4k + 1.
Qu'est-ce que l'arène d'un jeu, et pourquoi est-elle un graphe biparti ?
L'arène est le graphe orienté dont les sommets sont les positions du jeu et les arcs les coups. Une position contient l'état du jeu et le joueur qui doit jouer : avec 4 cailloux sur la table, il y a deux positions, selon que c'est au premier ou au second joueur de jouer, et elles n'ont pas la même issue pour lui. Chaque coup fait passer la main : il va d'une position où joue le premier joueur à une position où joue le second, ou l'inverse. En partageant les sommets entre les positions de chaque joueur, aucun arc ne relie deux sommets du même ensemble : le graphe est biparti. Si l'on oublie le joueur au trait et que l'on prend pour sommets les seuls nombres de cailloux, le graphe n'est pas biparti, car les arcs de 2 vers 1, de 1 vers 0 et de 2 vers 0 forment un triangle. Une partie est un chemin de l'arène qui part de l'état initial ; une partie infinie, possible si l'arène a un circuit, est comptée nulle dans le cours.
Comment calcule-t-on l'attracteur d'un joueur ?
L'attracteur est au programme de MP, PSI, PC et PT en France et de MP, PSI et TSI au Maroc, pas de TSI et TPC en France. L'attracteur de la cible du premier joueur se construit par couches cumulées. La couche 0 est la cible. On ajoute ensuite les positions du premier joueur qui ont au moins un coup vers les couches précédentes, et les positions de l'adversaire qui ont au moins un coup et dont tous les coups y mènent. On recommence tant qu'une position entre. La condition « au moins un coup » écarte une position de l'adversaire sans successeur, que la seule règle « tous ses coups » ferait entrer à tort. Le rang d'une position est le numéro de la couche où elle entre. Quand les cibles sont des fins de partie, les positions gagnantes du premier joueur sont exactement celles de l'attracteur, et la stratégie gagnante joue vers un rang strictement plus petit. La propagation arrière calcule l'attracteur en un temps linéaire.
Comment fonctionne l'algorithme min-max ?
L'algorithme min-max est au programme de MP, PSI, PC et PT en France et de MP, PSI et TSI au Maroc, pas de TSI et TPC en France. Le jeu est à somme nulle : une seule valeur, vue du premier joueur, appelé MAX, suffit. Une fin de partie vaut +1 si MAX a gagné, -1 si l'adversaire, MIN, a gagné, 0 en cas de nul. Une position où MAX doit jouer vaut le maximum des valeurs de ses fils ; une position où MIN doit jouer vaut le minimum. On remonte des feuilles vers la racine, et le bon coup mène au fils qui porte la valeur de la racine, pas vers la meilleure feuille. Écrit récursivement, le min-max fait un appel par nœud de l'arbre : 549 946 appels pour le morpion depuis la grille vide, dont la valeur est 0, ce qui veut dire que la partie est nulle si les deux joueurs jouent au mieux. En gardant dans un dictionnaire la valeur de chaque grille déjà évaluée, on n'évalue plus que 5 478 positions.
Qu'est-ce qu'une heuristique, et que fait le min-max à profondeur limitée ?
Une heuristique est une méthode qui donne vite une solution acceptable, sans garantie que ce soit la meilleure. Dans un jeu, elle prend la forme d'une fonction d'évaluation, qui estime une position sans jouer la partie jusqu'au bout : au morpion, on peut compter les lignes encore ouvertes pour le premier joueur et retrancher celles de l'adversaire, avec des valeurs extrêmes pour une grille déjà gagnée. Toutes les classes étudient cette notion. Le min-max à profondeur limitée, au programme de MP, PSI, PC et PT en France et de MP, PSI et TSI au Maroc, explore l'arbre de jeu seulement jusqu'à une profondeur fixée et évalue les nœuds de cette profondeur par l'heuristique. Le test de fin de partie et de profondeur vient avant tout appel récursif. Le coût est de l'ordre de b puissance p appels pour b coups par position et une profondeur p. Plus la profondeur est grande, meilleur est le coup en général, sans garantie. En TSI et TPC en France, l'heuristique est présentée sur le problème du sac à dos, avec un algorithme glouton.
Pourquoi ne peut-on pas explorer tout l'arbre d'un grand jeu ?
L'arbre de jeu d'une position a pour racine cette position, pour fils les positions atteintes en un coup, et pour feuilles les fins de partie. Si chaque position offre b coups, l'arbre a b nœuds à la profondeur 1, b au carré à la profondeur 2 et b puissance p à la profondeur p : le nombre de nœuds croît exponentiellement. Pour un jeu d'alignement à 7 colonnes, six coups d'avance font déjà 117 649 nœuds ; avec 30 coups par position, la profondeur 6 en compte 729 millions. Même le petit morpion a 549 946 nœuds et 255 168 parties, pour seulement 5 478 positions différentes : une même grille est atteinte par plusieurs ordres de coups, et il ne faut pas confondre le nombre de positions et le nombre de parties. Une exploration complète fait un appel par nœud, si bien que l'arbre complet d'un grand jeu est hors de portée. On explore alors une petite profondeur et l'on estime le reste par une heuristique.
Comment y accéder
Ce chapitre fait partie des chapitres offerts : il s'ouvre en entier avec un compte d'essai gratuit pour les filières dont il est l'un des premiers chapitres. Créer un compte d'essai ou se connecter. Pour l'accès complet et les tarifs, vois les offres.