Cours 7 : Théorie des jeux

Ce cours a duré deux heures car on a commencé par faire la dernière question du précédent exercice (voir cours 6), puis on a appliqué l'algorithme de Dijkstra sur quelques exemples (voir cours 4).

Ensuite, on a parlé de Théorie des jeux.

Jeux à somme nulle

On s'intéresse uniquement aux jeux à deux joueurs, et tour à tour. On les appelle Joueur 1 et Joueur 2.

De plus, on impose que le jeu est à somme nulle. Cela signifie qu'à la fin du jeu, les joueurs ont un score opposé. Soit $u$ le score final de Joueur 1. Le Joueur 2 a donc pour score $-u$.

• Si $u>0$, Joueur 1 gagne et Joueur 2 perd.
• Si $u<0$, Joueur 2 gagne et Joueur 1 perd.
• Si $u=0$, il y a égalité.

À retenir : Le plus souvent $u$ ne prend que trois valeurs, $-1$, $0$, et $1$. Cependant, cette généralisation pour $u \in \mathbb{R}$ va nous être utile lorsqu'on va parler d'heuristique

Exemples

Le Morpion

• Joueur 1 gagne : $u=1$
• Joueur 2 gagne : $u=-1$
• Égalité : $u=0$

Le jeu des bâtonnets de Ford Boyard

• Joueur 1 gagne : $u=1$
• Joueur 2 gagne : $u=-1$

Représentation d'un tel jeu

Formellement, un jeu est défini par :

• Un état initial $s_0$
• Un ensemble d'états possibles $S$ (en particulier $s_0 \in S$)
• Les états où c'est au Joueur 1 de jouer $S_1 \subset S$
• Les états où c'est au Joueur 2 de jouer $S_2 = S \setminus S_1$
• Des transitions allant des sommets de $S_2$ vers des sommets de $S_1$
• Des transitions allant des sommets de $S_1$ vers des sommets de $S_2$

C'est éxactement ce qu'on appelle un graphe orienté biparti $G = (S_1 \cup S_2, A)$ avec un état initial $s_0 \in S$.

Enfin, les états finaux (c'est-à-dire ceux qui n'ont pas de transitions), sont annotés par le score $u$ obtenu par le Joueur 1.

Si le score est positif, cela signifie que Joueur 1 gagne, s'il est négatif Joueur 1 perd et sinon il y a match nul.

Voici par exemple le graphe du jeu des bâtonnets de Ford Boyard

Stratégie

Une stratégie pour Joueur 1 est une fonction de $S_1$ dans $S_2$ avec que des coups valides.

Une stratégie pour Joueur 1 est dite gagnante si, quelque soient les actions jouées par Joueur 2, Joueur 1 gagne.

Une stratégie pour Joueur 1 assure le nul si, quelque soient les actions jouées par Joueur 2, Joueur 1 ne perd pas.

Quelques propriétés (à utiliser sans modération)

Propriété 1 : Si il n'y a pas d'état final nul, alors :

• Soit Joueur 1 possède une stratégie gagnante
• Soit Joueur 2 possède une stratégie gagnante

Propriété 2 : Dans tous les cas :

• Soit Joueur 1 possède une stratégie qui assure le nul
• Soit Joueur 2 possède une stratégie qui assure le nul

Attracteur

Du point de vue du Joueur 1, on note:

• $A_0$ l'ensemble des sommets finaux qui donnent la victoire à Joueur 1
• $A_{n+1} = A_n \cup {e_1\in S_1\mid \exists e_2 \in A_n, e_1 \to e_2} \cup {e_2\in S_2\mid \forall e_2 \to e_1, e_1 \in A_n}$

On appelle cet ensemble $\mathcal A_1$ (attracteur pour le Joueur 1).

On peut construire similairement $\mathcal A_2$ et on a alors

Les états de $\mathcal A_1$ possèdent une stratégie gagnante pour le Joueur 1. Les états de $\mathcal A_2$ possèdent une stratégie gagnante pour le Joueur 2. Les états de $\mathcal N$ possèdent une stratégie qui assure le nul à la fois pour le Joueur 1 et pour le Joueur 2.

Algorithme Minimax

On s'interesse ici aux jeux à somme nulle :

• Soit je gagne et mon adversaire perd
• Soit je perd et mon adversaire gagne
• Soit la partie est nulle

On peut représenter n'importe que jeu fini à deux joueurs tour par tour pas un arbre orienté :

• Chaque nœud représente un état du jeu
• La racine c'est l'état initial du jeu
• Les feuilles sont les états finaux : ils valent soit $1$ (victoire) soit $0$ (partie nulle) soit $-1$ (défaite)
• Pour un nœud donné, les arrêtes sortantes sont les actions possibles que le joueur à qui c'est le tour peut prendre.

L’algorithme Minimax permet de déterminer la stratégie optimale dans un jeu à somme nulle, en supposant que l’adversaire joue également de manière optimale.

On distingue deux types de nœuds :

• Nœud MAX → c’est mon tour → je cherche à maximiser le score
• Nœud MIN → c’est le tour de l’adversaire → il cherche à minimiser mon score

Les feuilles ont une valeur :

• $1$ → victoire
• $0$ → match nul
• $-1$ → défaite

On remonte l’arbre depuis les feuilles :

• Si le nœud est MAX (Je cherche à maximiser le score) :

• Si le nœud est MIN (L'adversaire cherche à minimiser le score) :

Mais comment on fait si on ne connaît pas le score d'un des enfants ? Et bien on fait un appel récursif :

En python, l'algorithme est tout simple (soit sûre de bien le comprendre) :

def minimax(node, c_est_moi_qui_joue):
    if node.est_terminal():
        return node.valeur

    if c_est_moi_qui_joue:
        best_value = -infinity
        for child in node.enfants:
            value = minimax(child, False) # Appel récursif
            best_value = max(best_value, value)
        return best_value
    else:
        best_value = +infinity
        for child in node.enfants:
            value = minimax(child, True) # Appel récursif
            best_value = min(best_value, value)
        return best_value

ou $d$ est la profondeur de l'arbre, et b est le nombre d'actions possibles à chaque étape.

⚠️ Cela devient rapidement très coûteux (ex : échecs).

Pour les échecs, on utilise une heuristique, qui correspond à un nombre entre $-1$ et $1$ pour chaque nœud :

• Plus on est proches de $1$, plus on est sûrs de gagner
• Plus on est proches de $-1$, plus on est sûrs de perdre

Au lieu de faire des appels récursifs pour toute la profondeur de l'arbre, on s'arrête avant, grâce à l'heuristique.

Attention : c'est algorithme heuristique n'est plus optimal, c'est juste un joueur pas trop mauvais.