L'étude des jeux : attracteurs et minmax

Cours · informatique (tronc commun des prépas scientifiques), chapitre 20 · prépas scientifiques, tronc commun · le début du chapitre, la suite sur Adloun

L'algorithme minmax : un joueur maximise la valeur, l'adversaire la minimise, de bas en haut de l'arbre de jeu.

20.1 Introduction et motivation

Peut-on gagner à coup sûr ? La question hante les jeux depuis toujours — et l'informatique lui a donné un sens précis et des réponses : le morpion est un match nul si personne ne se trompe ; le puissance 4 est gagné par le premier joueur ; les dames sont nulles (calcul achevé en 2007, après dix-huit ans de machine). Derrière ces verdicts, une seule idée : un jeu à deux joueurs est un graphe — les sommets sont les positions, les arcs les coups — et « bien jouer » est un problème de parcours, justiciable de tout l'arsenal des chapitres 12 à 14.

Ce chapitre construit la théorie sur les jeux d'accessibilité : deux joueurs déplacent un jeton, l'un veut atteindre certaines positions finales, l'autre veut l'en empêcher. On y définit ce qu'est une stratégie, une stratégie gagnante, une position gagnante — et l'on calcule tout cela par l'algorithme des attracteurs, un parcours de graphe à rebours d'une élégance rare. Puis on affronte la réalité : l'arbre des échecs a plus de positions que l'univers d'atomes — quand le calcul exact est hors de portée, on explore à profondeur bornée et l'on évalue les positions frontières par une heuristique : c'est l'algorithme minmax, cœur de tous les programmes de jeu classiques, et le second visage — après l'A* du chapitre 14 — de cette idée maîtresse de l'intelligence artificielle : injecter du jugement approximatif là où le calcul exact ne passe plus.

20.2 Les jeux comme graphes

20.2.1 L'arène

Définition 20.1Jeu d'accessibilité à deux joueurs

Un jeu se modélise par un graphe orienté biparti : l'ensemble des états (positions) se partage en $S_{1}$ — les états où c'est à $J_{1}$ de jouer — et $S_{2}$ — ceux où $J_{2}$ a le trait ; les arcs sont les coups légaux (d'un état de $J_{1}$ , on va vers des états de $J_{2}$ , et réciproquement). Les états sans successeur sont les états finals, de trois types : gagnants pour $J_{1}$ , gagnants pour $J_{2}$ , ou match nul. Dans le jeu d'accessibilité, $J_{1}$ cherche à amener la partie dans l'ensemble $F_{1}$ de ses états gagnants ; $J_{2}$ s'y oppose.

Exemple 20.2La course à 10

Deux joueurs annoncent tour à tour un total, en ajoutant $1$ ou $2$ au total précédent (départ $0$ , $J_{1}$ commence) ; qui dit $10$ gagne. États : les couples (total, joueur au trait), de $(0, J_{1})$ à $(10, \cdot)$ ; coups : $(t, J_{1}) \to (t + 1, J_{2})$ et $(t + 2, J_{2})$ — et symétriquement ; états finals : $(10, J_{2})$ — c'est $J_{1}$ qui vient de dire $10$ — gagnant pour $J_{1}$ , et $(10, J_{1})$ gagnant pour $J_{2}$ . Vingt-deux états, un graphe qu'on dessine sur un coin de table — et déjà toute la structure du problème : le morpion et les échecs ont exactement cette forme, en plus grand.

20.2.2 Stratégies et positions gagnantes

Définition 20.3Stratégie, stratégie gagnante, position gagnante

Une stratégie pour $J_{1}$ est une fonction qui, à chaque état de $S_{1}$ , associe un coup — sans mémoire : le choix ne dépend que de la position courante, pas de l'historique (le programme se limite à ces stratégies, et il se trouve qu'elles suffisent pour les jeux d'accessibilité). Une stratégie de $J_{1}$ est gagnante depuis l'état $s$ si toute partie partant de $s$ où $J_{1}$ la suit — quels que soient les coups de $J_{2}$ — atteint $F_{1}$ . L'état $s$ est une position gagnante pour $J_{1}$ s'il existe une stratégie gagnante depuis $s$ .

Exercices du chapitre

Implémenter l'attracteur et résoudre les allumettes corrigé
Jouer la stratégie — et mesurer l'invincibilité corrigé
La trichotomie — gagnant, perdant, nul corrigé
Première descente minimax corrigé
Le morpion, résolu exactement corrigé
Le tournoi des profondeurs corrigé

La suite du cours · Tous les exercices du chapitre