MODULE 2 • SÉANCE 3
Jouer contre un adversaire
Quand l'autre joue aussi
Dans un problème de trajet, rien ne vous répond. Dans un jeu, si : chaque coup de l'adversaire change la situation. Il faut donc raisonner « si je joue ceci, il peut répondre cela ». On traite ici le cas le plus net : deux joueurs, tout est visible, pas de hasard.
À la fin de cette séance, vous saurez
- dessiner l'arbre d'un petit jeu ;
- remonter les valeurs avec la méthode minimax ;
- expliquer pourquoi on estime au lieu de tout calculer.
Un jeu minuscule : les allumettes
Un tas d'allumettes. À tour de rôle, chacun en retire 1 ou 2. Qui prend la dernière gagne. Appelons Max le joueur qui veut une valeur élevée et Min celui qui la veut basse : +1 si Max gagne, −1 si Min gagne.
Arbre pour 4 allumettes, Max commençant. Chaque nœud indique ce qu'il reste et à qui c'est le tour.
- 4 · tour de Max
- retire 1 → 3 · tour de Min
- retire 1 → 2 · tour de Max
- retire 2 : Max prend la dernière · +1
- retire 1 → 1 · Min prend la dernière · −1
Valeur = max(+1, −1) = +1
- retire 2 → 1 · tour de Max
- retire 1 : Max prend la dernière · +1
Valeur = +1
Min choisit le plus petit : min(+1, +1) = +1
- retire 1 → 2 · tour de Max
- retire 2 → 2 · tour de Min
- retire 2 : Min prend la dernière · −1
- retire 1 → 1 · Max prend la dernière · +1
Min choisit le plus petit : min(−1, +1) = −1
Max choisit le plus grand : max(+1, −1) = +1
- retire 1 → 3 · tour de Min
À la racine, +1 : avec 4 allumettes, Max gagne s'il retire 1 pour en laisser 3. Ce chiffre est la valeur du jeu : le résultat quand les deux camps jouent au mieux.
La méthode minimax
- Noter les fins de partie : +1 si Max gagne, −1 si Min gagne, 0 pour un nul.
- Remonter : à un nœud de Max, garder la plus grande valeur des enfants ; à un nœud de Min, la plus petite.
- Jouer vers l'enfant de meilleure valeur pour soi.
La méthode est optimale pour les jeux à deux joueurs, sans hasard, où tout est visible et où ce que gagne l'un, l'autre le perd. Avec des dés ou des cartes cachées, il faut raisonner autrement (module 3).
Le mur de l'explosion combinatoire
Si chaque position offre b coups, regarder p coups à l'avance revient à examiner environ bp positions. Quelques valeurs :
| Coups d'avance | 10 coups possibles | 20 coups possibles |
|---|---|---|
| 2 | 100 | 400 |
| 3 | 1 000 | 8 000 |
| 4 | 10 000 | 160 000 |
| 6 | 1 000 000 | 64 000 000 |
Un jeu de société classique offre souvent plusieurs dizaines de coups par position, certains jeux plusieurs centaines : explorer l'arbre jusqu'au bout est hors de portée de toute machine.
Ce que minimax ne sait pas faire
Dans la réalité, l'issue d'une action n'est pas toujours certaine, et on ignore une partie des informations. Une recherche « parfaite » sur un monde imparfait donne de mauvais résultats : il faut mesurer l'incertitude. Rendez-vous au module 3.
Atelier : affrontez minimax
La machine joue avec minimax et ne se trompe jamais. Si la position est gagnante pour elle, elle gagnera. À vous de découvrir la stratégie, ou d'activer l'aide pour voir ses valeurs.