Introduction à la théorie des jeux

Sommaire

1. Théorie des jeux et lien avec les graphes
2. Jeux d'accessibilité à deux joueurs
3. Modélisation par un graphe biparti
4. Positions gagnantes : l'attracteur
5. Construction des stratégies gagnantes
6. Détermination du jeu & partition des positions
7. L'algorithme Minimax avec heuristique
8. Récapitulatif

1. Théorie des jeux et lien avec les graphes

La théorie des jeux étudie les situations où plusieurs joueurs prennent des décisions qui s'influencent mutuellement, chacun cherchant à atteindre son propre objectif. On se limite ici à une famille particulièrement liée à la théorie des graphes : les jeux d'accessibilité (reachability games) à deux joueurs.

L'idée clé : la situation du jeu à un instant donné est une position (un sommet d'un graphe), et un coup consiste à se déplacer le long d'un arc vers une nouvelle position. Le déroulement d'une partie est donc un chemin dans un graphe orienté. Résoudre le jeu revient à étudier ce graphe.

2. Jeux d'accessibilité à deux joueurs

On considère deux joueurs : le Joueur 0 (appelons-le Atteignant) et le Joueur 1 (Adversaire). Le Joueur 0 cherche à atteindre un ensemble de positions cibles ; le Joueur 1 cherche à l'en empêcher (éviter indéfiniment ces positions).

Les ingrédients du jeu :

3. Modélisation par un graphe biparti

Comme les deux joueurs jouent à tour de rôle, on partitionne les positions selon le joueur qui doit jouer. On obtient une arène (graphe du jeu) :

G = (V₀ ∪ V₁, E)  avec  V₀ ∩ V₁ = ∅

• V₀ : positions contrôlées par le Joueur 0 (c'est à lui de jouer ; on les dessine souvent en cercles).
• V₁ : positions contrôlées par le Joueur 1 (on les dessine en carrés).
• E ⊆ V × V : les arcs (coups possibles).

Lorsque les joueurs alternent strictement (chaque arc va de V₀ vers V₁ ou de V₁ vers V₀), le graphe est biparti : aucun arc ne relie deux positions du même joueur. C'est le cadre étudié dans ce chapitre.

4. Positions gagnantes : l'attracteur

Une position est gagnante pour le Joueur 0 si, en partant de cette position, le Joueur 0 possède une manière de jouer qui force l'arrivée dans F, quoi que fasse le Joueur 1. L'ensemble de ces positions est l'attracteur de F pour le Joueur 0, noté Attr₀(F).

Construction par couches (point fixe)

On construit l'attracteur de proche en proche. On note Attr^k l'ensemble des positions à partir desquelles le Joueur 0 peut forcer l'arrivée dans F en au plus k coups.

Initialisation : Attr⁰ = F (on y est déjà).

Récurrence : on ajoute une position u à la couche suivante si :

Formellement :

Attr^k+1 = Attr^k ∪ { u ∈ V₀ : ∃ (u→v) ∈ E, v ∈ Attr^k } ∪ { u ∈ V₁ : ∀ (u→v) ∈ E, v ∈ Attr^k }

La suite (Attr^k) est croissante et bornée par V : elle se stabilise. La limite est l'attracteur :

Attr₀(F) = ⋃_{k ≥ 0} Attr^k

Algorithme (induction arrière)

On parcourt le graphe « à l'envers » depuis F. On maintient pour chaque position du Joueur 1 un compteur de successeurs restant à valider.

def attracteur(V0, V1, succ, pred, F):
    """V0, V1 : ensembles de positions ; succ[u], pred[u] : listes ;
       F : ensemble cible. Renvoie l'attracteur du Joueur 0."""
    attr = set(F)                 # Attr^0 = F
    file = list(F)                # positions à traiter
    # nb de successeurs encore hors de attr, pour les positions du Joueur 1
    reste = {u: len(succ[u]) for u in V1}
    while file:
        v = file.pop()            # v est déjà gagnant
        for u in pred[v]:         # on remonte vers les prédécesseurs
            if u in attr:
                continue
            if u in V0:           # Joueur 0 : UN successeur gagnant suffit
                attr.add(u); file.append(u)
            else:                 # Joueur 1 : il faut TOUS les successeurs
                reste[u] -= 1
                if reste[u] == 0:
                    attr.add(u); file.append(u)
    return attr

Les positions hors de Attr₀(F) sont exactement les positions gagnantes pour le Joueur 1 : à partir de là, le Joueur 1 peut éviter F pour toujours. C'est la détermination du jeu : chaque position est gagnante pour exactement l'un des deux joueurs.

5. Construction des stratégies gagnantes

Calculer Attr₀(F) ne dit pas seulement qui gagne : il fournit aussi comment gagner. On lit la stratégie directement sur les couches de l'attracteur.

Stratégie gagnante du Joueur 0

Notons rang(u) le plus petit k tel que u ∈ Attr^k (le nombre minimal de coups pour forcer F). Sur chaque position u ∈ V₀ ∩ Attr₀(F), la stratégie consiste à jouer vers un successeur de rang strictement inférieur :

σ₀(u) = un successeur v tel que rang(v) = rang(u) − 1

À chaque coup du Joueur 0, le rang diminue d'au moins 1 ; le Joueur 1, depuis une position de l'attracteur, ne peut que rester dans l'attracteur (tous ses successeurs y sont). Le rang, entier positif, décroît : la partie atteint F en au plus rang(v₀) coups. La stratégie est sans mémoire (elle ne dépend que de la position courante).

Stratégie gagnante du Joueur 1

Sur chaque position u ∈ V₁ hors de l'attracteur, le Joueur 1 dispose forcément d'au moins un successeur lui aussi hors de l'attracteur (sinon u y serait entré par la règle du ∀). Sa stratégie : toujours jouer vers une position hors de Attr₀(F). La partie ne touche alors jamais F.

6. Détermination du jeu & partition des positions

Le résultat fondamental des jeux d'accessibilité (cas fini) est le théorème de détermination :

Pour savoir qui gagne la partie : on regarde simplement si l'état initial v₀ appartient à Attr₀(F).

7. L'algorithme Minimax avec heuristique

Le calcul exact de l'attracteur suppose qu'on peut explorer tout le graphe du jeu. Pour des jeux réels (échecs, dames, Puissance 4…), ce graphe est gigantesque : on ne peut pas le construire. On utilise alors l'algorithme Minimax, qui explore l'arbre des coups sur une profondeur limitée et évalue les positions atteintes par une heuristique.

Principe

On déroule l'arbre des parties depuis la position courante. Les deux joueurs sont supposés jouer au mieux de leur intérêt, mesuré par une valeur :

• Le Joueur MAX (notre joueur) choisit le coup de valeur maximale.
• Le Joueur MIN (l'adversaire) choisit le coup de valeur minimale.

Les valeurs sont calculées au fond de l'arbre :

• sur une position terminale (victoire / défaite / nul) : un score exact (+∞, −∞, 0) ;
• sur une position de profondeur maximale non terminale : la valeur de l'heuristique h(position), une estimation rapide de « à quel point la position est bonne pour MAX ».

Pseudo-code

def minimax(position, profondeur, joueurMax):
    if profondeur == 0 or terminale(position):
        return heuristique(position)      # estimation ou score exact
    if joueurMax:                          # le joueur MAX maximise
        valeur = -infini
        for coup in coups(position):
            valeur = max(valeur, minimax(jouer(position, coup),
                                         profondeur - 1, False))
        return valeur
    else:                                  # le joueur MIN minimise
        valeur = +infini
        for coup in coups(position):
            valeur = min(valeur, minimax(jouer(position, coup),
                                         profondeur - 1, True))
        return valeur

Le coup effectivement joué par MAX à la racine est celui qui réalise le max.

Le rôle de l'heuristique

L'heuristique h estime la valeur d'une position sans explorer la suite du jeu. Elle privilégie certaines positions plutôt que d'autres. Exemples : aux échecs, la différence de matériel (somme des pièces pondérées) ; au morpion, le nombre d'alignements encore possibles. Une bonne heuristique permet de jouer correctement avec une profondeur faible, donc peu de calcul.

Élagage α-β (pour aller plus loin)

L'élagage alpha-bêta est une amélioration de Minimax qui coupe les branches dont on sait déjà qu'elles ne changeront pas la décision. Il renvoie la même valeur que Minimax mais explore beaucoup moins de positions, ce qui permet d'augmenter la profondeur à temps de calcul égal.

8. Récapitulatif

Informatique CPGE MP/PSI · Introduction à la théorie des jeux