La carotte et le bâton... et Tetris

Piste rouge 18 novembre 2013  - Ecrit par  Alain Dutech, Bruno Scherrer, Christophe Thiéry Voir les commentaires

Cet article a été écrit en partenariat avec Interstices

Cet article a été écrit en partenariat avec L’Institut Henri Poincaré

L’IHP et INRIA ont présenté un stand commun au festival Futur en Seine qui a eu lieu du 13 au 16 juin 2013 à Paris. Cet article — publié initialement ici dans la revue en ligne Interstices — détaille une des animations qui a été présentée sur ce stand. Images des maths remercie Interstices et les auteurs de l’article d’avoir permis cette reprise.

Tetris est un célèbre jeu vidéo créé en 1985 par Alexey Pajitnov. Dans ce jeu de réflexion, le joueur doit empiler des pièces de différentes formes de manière à créer un mur formé de lignes horizontales superposées. Un ordinateur est-il capable d’apprendre tout seul à jouer à ce jeu ? L’apprentissage par renforcement, un domaine de l’intelligence artificielle, propose des solutions à ce genre de problèmes.

Apprendre à jouer à Tetris... en théorie

Les êtres vivants ont naturellement la capacité d’améliorer, au fil de leurs expériences, leurs réactions à l’environnement : ainsi, face à une situation donnée, une action entraînant une sensation agréable à plus ou moins long terme sera davantage choisie dans des circonstances analogues qu’une action suivie d’une réponse moins favorable.

L’apprentissage par renforcement a pour objectifs la compréhension et la conception de systèmes informatiques possédant cette aptitude : comment, par exemple, concevoir un programme informatique qui serait capable d’apprendre de façon autonome à jouer à Tetris ? La sensation, agréable ou non, est remplacée par une récompense numérique, positive (une carotte) ou négative (un coup de bâton). Le programme va alors expérimenter les différentes actions qui s’ouvrent à lui au cours du jeu. Petit à petit, pour chaque situation, le programme devra apprendre à choisir les « bonnes » actions. Toute la difficulté réside dans la nécessité de trouver de bons compromis :

  • Faut-il explorer l’environnement, au risque d’effectuer de mauvaises actions, ou faut-il exploiter en priorité les actions déjà connues comme étant bonnes, au risque de ne jamais découvrir de meilleures actions ?
  • Est-il important d’obtenir immédiatement une récompense élevée, au risque d’avoir de nombreuses récompenses négatives plus tard ?

Modéliser Tetris comme un Processus de Décision Markovien

  1. Initialement inspiré par des travaux en psychologie et développé par la communauté de l’intelligence artificielle, l’apprentissage par renforcement est aujourd’hui reconnu comme un problème entrant dans le cadre mathématique du contrôle optimal, et peut s’appuyer sur un modèle formel qui porte le nom de « Processus de Décision Markovien » (PDM). Un PDM permet de décrire d’une façon générale un agent informatique qui prend des décisions de sorte à bien contrôler un système. À chaque instant, l’agent observe l’état du système. À partir de cet état, l’agent choisit une action. Cette action a deux effets immédiats : le système évolue vers un nouvel état et l’agent reçoit une récompense instantanée (un nombre). À l’instant suivant, l’agent se trouve dans une situation analogue, à ceci près que l’état du système peut être différent et que l’agent devra de nouveau faire le choix d’une action, qui ne sera pas forcément la même. Comme nous le verrons un peu plus loin, le but dans ce cadre est de choisir chaque action en tenant compte non seulement de la récompense instantanée mais aussi de toutes celles à venir (information qui sera contenue dans le concept de « valeur »).

Le terme « Markovien » désigne un système qui vérifie une propriété fondamentale : la propriété de Markov. Celle-ci signifie que lorsque le système est dans un état, et que l’agent effectue une certaine action, l’état suivant et la récompense obtenue ne dépendent que de l’état actuel, et pas des états précédents. En d’autres termes, le passé (la manière d’être arrivé jusqu’à l’état actuel) n’a plus d’importance, seul le présent (l’état actuel) a une influence sur le futur.

Modéliser un problème sous la forme d’un PDM revient à définir l’ensemble des états du système, l’ensemble des actions de l’agent, la dynamique du système (comment on passe d’un état à un autre), ainsi que les récompenses et les coûts. Pour nous familiariser avec les PDM, voici comment nous pourrions modéliser le jeu de Tetris. Après une courte réflexion, les choix suivants s’imposent :

  • L’état contient deux informations : la configuration actuelle du mur et la pièce courante.
  • Une action est également composée de deux informations : la colonne et l’orientation dans lesquelles on va lâcher la pièce courante.
  • La dynamique, rappelons-le, décrit comment on passe d’un état à un autre quand on choisit une action ; elle découle donc de la définition des états et des actions. Étant donné un état et une action, c’est-à-dire un mur et une pièce qu’on vient de lâcher, on obtient un nouveau mur (sans oublier l’éventuelle suppression des lignes qui pourraient se trouver complétées)... et pour avoir un nouvel état (un état contient un mur et une pièce !), il faut encore préciser comment sera choisie la prochaine pièce : on en sélectionne une aléatoirement avec une probabilité uniforme.
  • Finalement, la récompense est d’évidence le nombre de lignes qui sont complétées au moment où on pose la pièce courante.

Valeur et décisions optimales

Pour l’instant, nous avons simplement décrit un modèle... Comment faire maintenant pour que notre programme de Tetris prenne de bonnes décisions ? Que doit-on mettre dans notre programme pour qu’il reçoive le plus de récompenses lors de ses parties ? L’apprentissage par renforcement, qui a pour but de trouver la séquence d’actions qui maximise les récompenses, est la solution que nous allons envisager ici.

Les mathématiciens du contrôle optimal, dont notamment Richard Bellman, ont eu l’idée remarquable d’introduire le concept de valeur optimale. La valeur optimale d’un état est la somme maximale des récompenses qu’il est possible de recevoir en moyenne à partir de cet état. Les algorithmes d’apprentissage par renforcement cherchent à calculer la valeur optimale de chaque état. Si on connaît cette valeur pour chaque état, il est alors facile de choisir la meilleure action à faire dans un état donné : c’est tout simplement celle qui mène à des états dont la valeur optimale est la plus grande. On montre que lorsque la propriété de Markov est vérifiée, la valeur optimale est la solution d’une équation particulière, dite équation de Bellman. Cette équation établit une relation entre la valeur optimale d’un état et la valeur optimale des états auxquels il peut mener. Ainsi, on a une équation pour chaque état, et trouver la valeur optimale de tous les états revient à résoudre le système composé de l’ensemble de ces équations. On peut par exemple résoudre ce système par un algorithme de « programmation dynamique ».

L’équation de Bellmann et sa résolution

À partir d’un état $s$, si on fait l’action $a$, si on arrive dans l’état $s'$ et si ensuite on agit optimalement, le cumul des récompenses sera :
\[\begin{array}{rcl} \text{récompense immédiate en } s & + & \text{somme des récompenses à partir de } s' \\ R(s,a,s') & + & V(s') \end{array}\]
où $R(s,a,s')$ est la récompense lorsqu’on fait l’action $a$ dans l’état $s$ et qu’on arrive dans l’état $s'$, et $V(s')$ la valeur optimale de l’état $s'$.

On ne sait pas exactement dans quel état $s'$ on va arriver car $s'$ dépend aléatoirement de l’état et de l’action, ce que l’on note $s' \sim \text{suivant}(s,a)$. Il est alors naturel de considérer le retour moyen si l’on fait l’action $a$ à partir de l’état $s$, c’est-à-dire :
\[\mathbb E_{s' \sim \text{suivant}(s,a)} [R(s,a,s') + V(s')].\]
Ce qui nous intéresse au fond, c’est le meilleur retour moyen à partir de l’état $s$ :
\[\max_a \big\{ \mathbb E_{s' \sim \text{suivant}(s,a)} [R(s,a,s') + V(s')]\big\}.\]
Ce meilleur retour est égal à la valeur en l’état $s$, ce qui nous donne pour tout $s$,
\[V(s) = \max_a \big\{ \mathbb E_{s' \sim \text{suivant}(s,a)} [R(s,a,s') + V(s')]\big\}.\]
Cette dernière équation est appelée équation de Bellman.

Pour illustrer cette équation et le calcul de sa solution, la valeur optimale, considérons un problème simple dans lequel un rat se déplace dans un labyrinthe pour y trouver un fromage.

Dans chaque case du labyrinthe, qui sont donc les états de notre Processus de Décision Markovien, on voudrait que le rat apprenne à choisir la meilleure action pour rejoindre au plus vite le fromage. Nous considérons que les 5 actions du rat sont : haut, bas, droite, gauche, rester. Après chaque action, le rat reçoit une « récompense » de -1 et une « récompense » de -4 quand il se cogne dans un mur.

Dans le cas du petit labyrinthe :

et lorsque les déplacements du rat ne sont pas bruités, l’équation de Bellman caractérisant la valeur optimale s’écrit

\[\begin{eqnarray*} V(s_1) & = & \max \{ -4+V(s_1),\, -1+V(s_3),\, -1+V(s_2),\, -4+V(s_1),\, -1+V(s_1) \} \\ V(s_2) & = & \max \{ -4+V(s_2),\, -1+V(s_4),\, -4+V(s_2),\, -1+V(s_1),\, -1+V(s_2) \} \\ V(s_3) & = & \max \{ -1+V(s_1),\, -4+V(s_3),\, -4+V(s_3),\, -4+V(s_3),\, -1+V(s_3) \} \\ V(s_4) & = & 0 \quad \text{(l'expérience termine lorsque le rat atteint le fromage)} \end{eqnarray*}\]

Pour calculer la valeur optimale de chaque case du labyrinthe dans ce contexte, on utilise un algorithme de programmation dynamique, Itérations sur les valeurs, qui à chaque étape, donne une estimation de plus en plus précise de valeur optimale d’une case.

Au début du calcul, la valeur optimale $V(s)$ estimée de chaque case $s$ est initialisée à $0$. À chaque itération de l’algorithme, on améliore l’estimation de la valeur optimale de chaque case s en utilisant l’équation de Bellman de la manière suivante :

  1. pour chaque case $s$, la nouvelle estimation de sa valeur optimale, que l’on note $NV(s)$ est celle donnée par le côté droit de l’équation de Bellman : \[\max_a \big\{ \mathbb E_{s' \sim \text{suivant}(s,a)} [R(s,a,s') + V(s')]\big\}\]
  2. pour chaque case $s$, la nouvelle estimation devient l’estimation courante de la valeur optimale : $V(s)$ devient $NV(s)$.
  3. si l’estimation de la valeur optimale n’est pas assez précise, on recommence à l’étape 1. L’erreur d’estimation est directement proportionnelle à la différence entre l’ancienne estimation $V(s)$ et la nouvelle $NV(s)$. Pendant le calcul, l’erreur courante sur la précision du calcul est affichée sur la ligne du bas de l’application.

À tout moment du calcul, les flèches indiquent pour chaque case l’action optimale à effectuer en fonction de la valeur optimale courante. S’il n’y a pas de flèche, le rat n’essaiera pas de bouger.

Plusieurs paramètres influencent le calcul de cette valeur optimale :

  • précision (réel supérieur à $0,\!0001$) : le calcul de la valeur optimale se poursuit tant que cette précision n’est pas atteinte.
  • bruit (entre 0 et 1) : ce paramètre permet de rendre le sol glissant. Ainsi, par exemple, un rat qui VEUT aller à gauche réussit son mouvement avec une probabilité de $1-bruit$, sinon sa véritable action est prise uniformément au hasard parmi les autres actions.

On peut remarquer que, quand il n’y a pas de bruit, le rat aura tendance à suivre le plus court chemin. On remarque d’ailleurs que, sans bruit, la valeur optimale d’une case est égale à « moins la longueur du chemin jusqu’au fromage ». Par contre, si on augmente le bruit, le rat s’éloignera aussi des murs par peur de glisser vers eux. On peut s’en rendre compte avec, par exemple, un niveau de bruit supérieur ou égal à $0,\!2$ dans le « grand » environnement.

Revenons à présent à Tetris. Dans ce cadre, comme la récompense est le nombre de lignes que l’on vient de compléter, optimiser la somme des récompenses revient à maximiser le nombre de lignes effectuées durant une partie, c’est-à-dire le score ! Et la valeur optimale introduite par les mathématiciens est tout simplement le meilleur score moyen à venir si dans une configuration du mur on lâche la pièce courante de telle ou telle manière. Comme précédemment, le mieux est évidemment de choisir l’endroit qui nous prédit le meilleur score ou encore la plus grande valeur optimale. On mesure ici la beauté de la théorie du contrôle optimal : si on est capable de calculer cette valeur optimale, c’est-à-dire simplement de résoudre une équation, on peut immédiatement en déduire comment jouer à Tetris de façon optimale.

Mais qu’en est-il en pratique ?

Construction pratique d’un contrôleur pour Tetris

Le jeu de Tetris comprend $10 \times 20 = 200$ cases. Chaque case du jeu peut être vide ou pleine. Comme le jeu comporte $7$ pièces, le nombre d’états est majoré par $7\times 2^{200} \simeq 10^{60}$. Même en éliminant les configurations impossibles, le nombre d’états à considérer reste de cet ordre astronomique et est trop grand pour que l’on puisse espérer résoudre l’équation de Bellman avec suffisamment de précision, ou même stocker le résultat dans un ordinateur. Même en stockant 10 milliards de valeurs dans un ordinateur, il faudrait $10^{50}$ ordinateurs pour stocker $10^{60}$ valeurs numériques ! Or, il n’y a qu’un milliard ($10^9$) d’ordinateurs dans le monde...

Résolution exacte d’un mini-Tetris

Pour commencer, considérons une version réduite du jeu de Tetris, un mini-Tetris en quelque sorte. Si, au lieu des 10×20 cases, on joue sur un jeu contenant seulement 5×5 cases, alors les calculs et le stockage des valeurs optimales deviennent possibles.

Dans ce cas, il y a un peu moins de $2^{25}$ murs possibles, et donc un peu moins de $7 \times 2^{25}$ soit environ 230 millions d’états. Avec un ordinateur de bureau actuel, un algorithme de programmation dynamique, et un peu de patience (une centaine d’heures de calculs), on peut résoudre l’équation de Bellman : on dispose alors des valeurs optimales pour toutes les situations qui pourraient survenir et on en déduit la manière optimale de jouer au mini-Tetris.

Le concept de valeur optimale est intéressant à bien des égards. En regardant la valeur calculée pour les états correspondant au début d’une partie (qui rappelons-le est égale au meilleur score que l’on peut obtenir), on peut voir que si on joue de nombreuses fois à ce mini-Tetris, on fera entre 13 et 14 lignes en moyenne par partie. On sait de plus qu’on ne peut pas faire mieux...

Voulez-vous vous mesurer à ce contrôleur optimal ?

Animation HTML5/JS réalisée par Xavier Caruso, Léo Testard et Bruno Scherrer
Accéder aux sources

Résolution approchée du jeu de Tetris original

Est-on contraint de se limiter au mini-Tetris ($5\times 5$) ? Est-il désespéré de s’attaquer au jeu de Tetris original ($10\times 20$) ? Pas tout à fait : s’il est impossible de résoudre exactement l’équation de Bellman, nous pouvons essayer de la résoudre approximativement.

Le très grand nombre d’états de ce jeu pose concrètement deux problèmes :

  • Le système d’équations que nous souhaitons résoudre contient autant d’équations qu’il y a d’états !
  • Comme nous l’avons déja mentionné, même si nous étions capables de les calculer, il serait impossible de stocker les valeurs optimales pour l’intégralité des états !

La solution conjointe à ces deux difficultés repose sur deux idées fondamentales :

  • La première idée est de laisser le programme jouer un certain nombre de parties et de considérer uniquement les états observés. On espère ici que se limiter à un sous-ensemble suffisamment représentatif des états suffira à donner une bonne approximation au système d’équations original.
  • La seconde idée consiste à utiliser une fonction paramétrée, c’est-à-dire un moyen d’estimer la valeur optimale d’un état donné à partir d’un nombre réduit de paramètres. L’astuce est qu’au lieu de stocker autant de valeurs que d’états, il suffira de stocker les paramètres de notre fonction (on a typiquement quelques dizaines ou centaines de paramètres).

Les techniques d’apprentissage par renforcement exploitent alors le déroulement de ces parties (les états visités et les récompenses obtenues) afin de régler les paramètres de l’architecture d’approximation, de sorte qu’elle fournisse des valeurs aussi proches que possible de la valeur optimale, autrement dit du score futur qu’il est possible de réaliser. Ainsi, à l’image d’un animal dans son environnement, notre programme exploite sa propre expérience afin d’améliorer son comportement.

Avec une vingtaine de paramètres, on peut ainsi construire un joueur de Tetris qui fait en moyenne de l’ordre de $30\:000$ lignes par partie. On reste encore loin des meilleurs programmes spécifiques à Tetris, comme celui de Pierre Dellacherie qui réalise plusieurs millions de lignes par partie grâce à une grande connaissance experte. Cependant, l’avantage des techniques que nous venons de décrire est qu’elles permettent à l’ordinateur d’apprendre de manière autonome. Elles sont ainsi applicables telles quelles à de nombreux autres domaines : optimisation d’une chaîne de production, pilotage acrobatique d’un hélicoptère, déploiement d’une flotte de satellites...

Références

Pour en savoir plus sur Tetris et sur l’apprentissage par renforcement, nous vous proposons quelques références en savoir plus, en anglais :

  • Un ouvrage en ligne sur le domaine de l’apprentissage par renforcement : Richard S. Sutton and Andrew G. Barto, Reinforcement Learning : An Introduction
  • La notice de Wikipédia sur Richard Bellman
  • Un site très intéressant sur le jeu de Tetris : celui de Colin Fahey
  • Un article (en anglais) sur l’état de l’art des contrôleurs pour Tetris
Post-scriptum :

Les auteurs et la rédaction d’Images des Maths remercient pour leur relecture attentive et leurs remarques constructives Nicolas Chatal, blanvill et
Robin Jamet.

Article édité par Xavier Caruso

Partager cet article

Pour citer cet article :

Alain Dutech, Bruno Scherrer, Christophe Thiéry — «La carotte et le bâton... et Tetris» — Images des Mathématiques, CNRS, 2013

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM