5- Apprentissage et jeux

Le cours d'ITC présente de manière assez rapide plusieurs concepts d'apprentissage et de jeux. Les détails des algorithmes ne sont pas au programme.

I. Apprentissage

a) Apprentissage supervisé : les k plus proches voisins

Définition : jeu de données

On appelle jeu de données étiqueté un ensemble d'objets, associés à des classes.

En général, les objets sont ramenés à des éléments de , et les classes à des entiers de .

Définition : apprentissage supervisé

Un algorithme d'apprentissage supervisé prend en entrée un jeu de données, et l'utilise pour classifier de nouveaux objets inconnus.

Première idée : on a des points de rangés dans des classes (c'est-à-dire des catégories). On veut ranger un nouveau point de dans ces classes.

On peut simplement regarder la classe de l'objet le plus proche (ou des objets les plus proches) et classifier notre objet en conséquence ! C'est l'algorithme des plus proches voisins (aussi appelé k-NN).

Dans l'exemple ci-dessous, les points colorés sont les données étiquetées (trois classes). Cliquez n'importe où pour placer un nouveau point, et faites varier :

k = 3 Colorer le plan selon la classe prédite

Votes des 3 plus proches voisins : 1 rose, 1 bleu, 1 jaune → le nouveau point (carré) est classé rose. Cliquez pour déplacer le nouveau point.

b) Test et validation

Si on utilise tous nos exemples pour l'algorithme, comment évaluer ses performances ? On ne peut pas le tester sur un objet qu'on lui a fourni à l'entraînement, ce serait de la triche !

Définition : données de validation

Lorsqu'on a un jeu de données, on va garder (aléatoirement) un certain pourcentage d'entre elles, en général réparti uniformément entre les classes, pour la validation. Souvent, ce pourcentage est aux alentours de 1 à 10 %, mais cela va beaucoup varier en fonction des données.

On va ensuite tester notre algorithme sur ce jeu de données de validation, et mesurer les erreurs.

Définition : matrice de confusion

On peut ensuite écrire la matrice de confusion associée : il s'agit d'un tableau où, pour chaque classe, on indique le pourcentage d'objets de cette classe qui ont été placés dans chaque classe par l'algorithme.

	A	B
A	95 %	5 %
B	1 %	99 %

Ce tableau indique que, parmi les objets réellement de classe A, 95 % ont été bien classifiés et 5 % mal classifiés.

c) Apprentissage non supervisé : les k-moyennes

On a maintenant un problème différent : on dispose toujours d'un jeu de données, mais cette fois il n'est pas étiqueté, c'est-à-dire qu'on ne connaît pas la classification des objets.

On aimerait automatiquement déduire une classification des objets en classes, en fonction de leur similarité.

Plus précisément, on cherche à minimiser la quantité où est le barycentre de la classe .

Pour cela, on va utiliser une méthode itérative (voir cette visualisation).

Algorithme des k-moyennes

Entrées : un ensemble de données D (des vecteurs de flottants)

un entier C le nombre de classes

Sortie : les centres u₁, ..., u_C (qui définissent une association de D à ⟦1, C⟧)

1.Placer u₁, ..., u_C des centres.

(On peut tirer les positions aléatoirement, ou bien utiliser des méthodes

pour les répartir équitablement dans D)

2.Tant que on n'a pas convergé

(en général, on s'arrête quand l'attribution ne change plus)

3.Pour i de 1 à C

4.S_i ← l'ensemble des points pour lesquels u_i est le centre le plus proche

5.Pour i de 1 à C

6.u_i ← le barycentre de S_i

7.Renvoyer u₁, ..., u_C

À vous de dérouler l'algorithme, étape par étape, sur des points du plan (choisissez le nombre de classes, puis alternez attribution et déplacement des centres) :

Nombre de classes C :

Itération 0

En relançant plusieurs fois avec des centres aléatoires différents, on n'obtient pas toujours le même résultat.

La preuve n'est pas au programme, mais l'algorithme des -moyennes converge toujours. En revanche, il peut converger vers un minimum local de la fonction de coût, ce qui peut donner des résultats absurdes.

Le placement de départ des points a une influence importante sur la qualité de la solution obtenue.

II. Modélisation des jeux

On va utiliser, comme premier exemple, le jeu de Chomp.

C'est un jeu à deux joueurs, qui se joue avec une tablette de chocolat. Le carré en haut à gauche est empoisonné, et donc le joueur ou la joueuse qui le mange a perdu.

Chacun leur tour, les joueurs doivent manger un rectangle de carrés en bas à droite de la tablette.

Définition : jeu de Chomp

On prend un rectangle (la tablette de chocolat) de taille . Le carré en position est empoisonné.

Chacun leur tour, les joueurs choisissent une case non mangée et mangent tous les carrés situés dans le rectangle en bas à droite de cette case (la case incluse).

Un joueur perd s'il est obligé de manger la case , et, dans ce cas, l'autre joueur gagne.

Essayez de jouer, contre l'ordinateur ou à deux :

Montrer les coups gagnants

À vous de jouer.

a) Graphe d'un jeu

On s'intéresse aux jeux à deux joueurs, J1 et J2, qui jouent chacun leur tour, et où chacun connaît toute la situation (pas de hasard, pas d'information cachée) : Chomp, les échecs, le morpion...

Définition : graphe d'un jeu

Un jeu est décrit par un graphe orienté :

les sommets sont les états (ou positions) du jeu : la situation, et le joueur qui doit jouer. Ils sont partagés en deux ensembles : les états contrôlés par J1 (c'est à J1 de jouer) et ceux contrôlés par J2 ;
les arcs sont les coups possibles : d'un état contrôlé par J1, on va vers un état contrôlé par J2, et inversement. Le graphe est donc biparti ;
certains états sont finals : la partie s'arrête, et ils sont gagnants pour J1, gagnants pour J2, ou nuls.

Un jeu d'accessibilité est un jeu où J1 cherche à atteindre un état de l'ensemble (ses états finals gagnants), et J2 à l'en empêcher.

Pour avoir un exemple plus petit que Chomp, prenons le jeu des allumettes : il y a allumettes sur la table ; chacun son tour, un joueur en retire 1, 2 ou 3 ; celui qui prend la dernière allumette a perdu. Un état est un couple (nombre d'allumettes, joueur qui doit jouer). L'état est gagnant pour J1 (c'est J2 qui a pris la dernière allumette), et est gagnant pour J2.

Voici le graphe du jeu avec 5 allumettes au plus : les états contrôlés par J1 sont des rectangles, ceux contrôlés par J2 des ellipses, et les états finals sont entourés deux fois.

b) Stratégies

Définitions : stratégie, stratégie gagnante

Une stratégie (sans mémoire) pour J1 est une fonction qui, à chaque état contrôlé par J1 (non final), associe un coup possible, c'est-à-dire un successeur.
Une stratégie est gagnante depuis un état si, en partant de , J1 atteint un état de quels que soient les coups de J2.
Un état est une position gagnante pour J1 s'il existe une stratégie gagnante pour J1 depuis cet état.

Dans le widget Chomp ci-dessus, l'option "Montrer les coups gagnants" indique les coups qui mènent à une position perdante pour l'adversaire : c'est une stratégie gagnante.

c) Calcul des attracteurs

Comment trouver les positions gagnantes ? On part des états finals gagnants, et on "remonte" le graphe. On note les états contrôlés par J1, ceux contrôlés par J2, et l'ensemble des successeurs d'un état .

Définition : attracteur

On définit par récurrence :

La suite est croissante, dans un ensemble fini : elle finit par être constante. Sa limite est l'attracteur de pour J1 : c'est exactement l'ensemble des positions gagnantes pour J1.

Intuitivement : J1 gagne depuis un état qu'il contrôle s'il peut jouer vers un état gagnant ; et depuis un état contrôlé par J2, si tous les coups de J2 mènent à des états gagnants pour J1. est l'ensemble des états d'où J1 peut gagner en au plus coups.

Calculons l'attracteur pour le jeu des allumettes (avec au plus 5 allumettes) :

;
: avec une allumette, J2 est obligé de la prendre ;
: J1 peut laisser une seule allumette à J2 ;
: quoi que fasse J2, il laisse 2, 3 ou 4 allumettes à J1 ;
: la suite est constante, l'attracteur est .

J1 gagne s'il doit jouer avec 2, 3 ou 4 allumettes, mais pas avec 1 ou 5. Plus généralement, on montre que le joueur qui doit jouer perd exactement quand est de la forme .

Construire une stratégie gagnante. Pour chaque état de l'attracteur, on note le plus petit tel que . Depuis un état de rang , par définition de , il existe un successeur de rang au plus : la stratégie consiste à jouer vers . Depuis un état de de rang , tous les successeurs sont de rang au plus . Le rang diminue donc strictement à chaque coup, et on finit par atteindre .

Par exemple, depuis , de rang 2, J1 joue vers , de rang 1 : il retire 3 allumettes.

d) Heuristique et algorithme min-max

Pour les vrais jeux, le graphe est beaucoup trop grand pour calculer les attracteurs (environ positions aux échecs). On se contente de regarder quelques coups à l'avance.

Définition : heuristique

Une heuristique est une fonction qui donne une estimation de la valeur d'une position : un grand nombre si elle semble favorable à J1, un petit (négatif) si elle semble favorable à J2. Elle ne donne pas la vraie valeur, mais doit être rapide à calculer.

Par exemple, au morpion (J1 joue les X, J2 les O), on peut prendre comme heuristique le nombre de lignes encore possibles pour X (qui ne contiennent aucun O), moins le nombre de lignes encore possibles pour O.

Algorithme min-max (à profondeur

) La valeur d'un état est :

si est final : (en pratique, une grande valeur) s'il est gagnant pour J1, s'il est gagnant pour J2, s'il est nul ;
si : , l'heuristique de ;
si : ;
si : .

J1 joue alors le coup qui mène au successeur de valeur maximale.

J1 suppose que J2 joue au mieux pour lui, c'est-à-dire qu'il minimise la valeur. Voici un exemple à profondeur 2 : J1 a trois coups possibles, puis J2 en a trois. Les feuilles sont évaluées par l'heuristique ; on remonte les valeurs en prenant le minimum aux niveaux de J2 (ellipses), puis le maximum au niveau de J1 (rectangle).

Le coup c mène à une position d'heuristique 14, la meilleure de toutes... mais J2 y répondra par le coup qui ne vaut que 2. Min-max choisit le coup a, qui garantit une valeur d'au moins 3, quoi que fasse J2.

Le morpion est assez petit pour être exploré entièrement (profondeur 9, sans heuristique) : si les deux joueurs jouent parfaitement, la partie est nulle.

Exercices

Exercice 1

Dans le jeu des allumettes, on autorise maintenant à retirer seulement 1 ou 2 allumettes. Calculer les ensembles pour au plus 5 allumettes, et en déduire les positions gagnantes pour le joueur qui doit jouer.

, , , , (J1 retire 1 allumette et laisse 4 à J2), puis la suite est constante. Le joueur qui doit jouer perd exactement quand est de la forme .

Exercice 2

Au Chomp, montrer que le premier joueur a une stratégie gagnante sur une tablette carrée (avec ).

J1 mange le carré : il reste une ligne et une colonne de même longueur, en "L". Ensuite, J1 joue toujours le coup symétrique de celui de J2 (si J2 mange carrés de la ligne, J1 mange carrés de la colonne, et inversement). C'est donc toujours J2 qui se retrouve face au seul carré empoisonné.

Exercice 3

Dans l'arbre min-max ci-dessus, on remplace la feuille 3 par 1. Quel coup choisit J1 ? Et si on remplace la feuille 5 par 20 ?

Les valeurs des nœuds de J2 deviennent 1, 2, 2 : J1 choisit le coup b (ou c), de valeur 2.
Le troisième nœud de J2 vaut toujours : rien ne change, J1 choisit le coup a.

Exercice 4

Proposer une autre heuristique pour le morpion, qui tienne compte des lignes où un joueur a déjà placé deux symboles.

Par exemple : pour chaque ligne encore possible pour X, compter 1 point si elle contient un X et 10 points si elle en contient deux ; de même (en négatif) pour O. Une ligne où X a déjà deux symboles est une menace immédiate, qui vaut donc beaucoup plus.