Projet apprentissage par renforcement

Votre groupe doit mener le travail à bout, vous devez donc créer une synergie de groupe qui vous permettra d'obtenir des livrables de qualité maximale, dans une ambiance de travail agréable et productive. Le projet se déroule sur un temps plus long que le temps d'un TP, vous avez donc un peu de temps pour vous tromper mais pour parvenir à un rendu de qualité, une bonne gestion de votre temps s'impose.

Vous devez également apprendre à utiliser Git… et l'utiliser de façon efficace.

Vous devrez de plus maintenir au fil de votre projet une page web sur le site de l'ISIMA. Cette page devra proposer un lien sur votre dépôt git, des informations sur l'état du projet, et servira de support lors des deux présentations. Il est important que votre page soit tenue à jour, au minimum de façon journalière.

Attention
    - vous devez pouvoir présenter des fiches/diagrammes de répartition des tâches (prévisionnelles, effectives) à jour à tout moment,
    - chacun doit créer plusieurs commits par jour et au moins un push chaque jour,
    - les branches (git) doivent être utilisées : à chaque nouvelle fonctionnalité correspond au moins une branche.

Chacun d'entre-vous doit à la fin de ce projet avoir atteint un niveau minimal dans la qualité de son code, et en particulier, vous devrez :

1. Maîtriser la syntaxe du c,
2. Savoir utiliser à bon escient des bibliothèques standards,
3. Savoir rechercher rapidement de l'information dans le man / sur le net,
4. Comprendre l'utilisation des makefiles,
5. Savoir documenter votre code : code le plus possible auto-documenté (les noms de variable, la présentation du code sont si lumineux que d'autres explications sont superflues) qu'on pourra compléter si nécessaire par des fichiers d'explications en org mode ou markdown et potentiellement doxygen,
6. Savoir réaliser une page web présentant votre travail.

Au cours du TP vous allez réinvestir vos acquis en algorithmique ainsi qu'en structures de données. Le projet utilisera au minimum des listes, tableaux, arbres, graphes et vous demandera de les manipuler et parcourir de façon adaptée.

Le terme 'liste' est souvent utilisé dans ce document pour simplement signifier 'énumération' et n'implique pas de façon de l'implémenter.

Le projet doit vous permettre de découvrir ou d'approfondir vos connaissances dans le domaine de la programmation graphique 2D. Vous devrez notamment :

1. (Re?-)Découvrir la SDL2,
2. Créer une image par juxtaposition et superposition d'autres images,
3. Gérer la transparence dans la superposition de deux images,
4. Créer une animation simple,
5. Gérer une boucle d'évènements,
6. Gérer les entrées utilisateur.

Durant la première semaine du projet, les apprentissages sont guidés. Ils ont pour vocation à vous familiariser avec la création de graphiques, d'animations en 2D. Les premiers exercices sont individuels, afin que chacun dispose d'un socle commun, puis dans la deuxième moitié de la semaine, un premier travail de groupe est réalisé, un petit jeu d'arcade vous permettant de mettre en œuvre vos acquis.

La seconde phase vous permettra à votre groupe de créer une application plus conséquente de votre choix, respectant les contraintes ainsi que la thématique imposées.

Les exercices demandés acceptent des variations, acceptables tant qu'elles vous permettent de démontrer votre savoir-faire sur le point étudié. Le but n'est pas de plagier les exemples proposés, mais de démontrer votre savoir-faire ! Pensez cependant à faire valider vos propositions de variations par un enseignant afin :

• de ne pas vous lancer dans un travail trop chronophage par rapport à la version originale,
• de ne pas avoir manqué un point particulier que les enseignants désirent vous voir démontrer.

Afin de pouvoir travailler de la façon la plus agréable possible, il est possible d'utiliser une machine virtuelle personnelle fournie par l'ISIMA sur laquelle vous êtes administrateurs. Être administrateur vous permettra d'installer les logiciels de votre choix, et de configurer à votre guise le système d’exploitation.

Pour rappel, il est nécessaire de démarrer la machine virtuelle avant de pouvoir l'utiliser sur guacamole, ou en s'y connectant via ssh ssh -Y login@nom_machine, où à l'aide de remmina. Il peut être nécessaire de reconfigurer le password (vous pouvez mettre celui de l'ENT ici).

Vous pouvez utiliser votre ordinateur personnel, que ce soit avec une distribution Linux ou WSL pour Windows… mais dans tous les cas il vous est demandé de faire de la programmation sous Linux, et non sous Windows.

Parfois, toutes les actions ne sont pas possibles. Par exemple, si on désire simuler un système qui peut se déplacer dans les directions Nord, Sud, Est, Ouest avec certaines probabilités (ses préférences pour chacune des directions), il pourrait être nécessaire de prévoir les différentes situations : on ne peut pas aller à l'est, on ne peut aller ni au nord, ni à l'est, … ce qui va ajouter beaucoup d'états !

Une solution simple à ce problème est : on construit la table $\mathbb{P}$ sans se préoccuper de ce qui est possible, et au moment de choisir l'action, on normalise le vecteur ligne.

Maths

On s'intéresse à la situation où l'état $S_k$ est impossible, et on calcule la probabilité de transiter de l’état $s_i$ vers l'état $s_j$ (avec évidemment $k \not = j$)

$$\begin{equation} \begin{split} P\left(S_n = s_j | (S_{n-1}=s_i \wedge S_n \not = s_k)\right) &= \frac{P\left(S_n = s_j \wedge S_{n-1}=s_i \wedge S_n \not = s_k\right)}{P\left( S_{n-1}=s_i \wedge S_n \not = s_k\right)}\\ &= \frac{P\left(S_n = s_j \wedge S_n \not = s_k | S_{n-1}=s_i \right) \times P\left( S_{n-1}=s_i \right)}{P\left( S_n \not = s_k|S_{n-1}=s_i \right)\times P\left( S_{n-1}=s_i \right)}\\ &= \frac{P\left(S_n = s_j \wedge S_n \not = s_k | S_{n-1}=s_i \right)}{P\left( S_n \not = s_k|S_{n-1}=s_i \right)}\\ &= \frac{P\left(S_n = s_j | S_{n-1}=s_i \right)}{P\left( S_n \not = s_k|S_{n-1}=s_i \right)} \text{ car }s_i\text{ et }s_k \text{ sont incompatibles} \end{split} \end{equation}$$

Algo qui en découle

Entrée :
  - P la matrice des transitions
  - i et k
Sortie :
  - un entier j qui est une réalisation de la v.a. S, partant de l'état s_j et interdisant d'arriver sur l'état s_k
Processus :
  - Définir normalisation = 0
  - Pour l = 0 à n-1
    - si l != k                      // s'il y a d'autres états interdits, il suffit de ne pas les ajouter à 'normalisation'
      - normalisation += P[i][l]   

  - Définir alpha : un réel tiré en aléatoire uniforme dans [0 ; 1[ 
  - définir n le nombre d'états possibles 
  - Définir  j = n-1                 // par défaut, le programme renvoie la dernière réalisation possible
  - Définir cumul = 0                // on construit les probabilités cumulées

  - Pour l = 0 à à n-2 :
    - cumul += P[i][l]/normalisation
    - Si alpha < cumul :
      - i = l 
      - break
  - renvoyer i

Il est possible de pousser encore un peu plus loin cette idée : si on sait par avance que deux actions sont incompatibles, alors on peut avoir la somme des éléments d'une ligne strictement supérieure à 1, à condition que la somme vaille 1 pour toute combinaison ne comportant pas d'impossibilité. Cela permet alors de modéliser assez simplement des comportements du type : si la porte est ouverte, alors j'avance, sinon je fais autre chose.

Si une action dure plusieurs dates de temps, il est alors nécessaire de la décomposer en plusieurs états. Ainsi, si on peut dormir pendant 3 ou 4 dates de temps, on définit les états :

• dormir 1
• dormir 2
• dormir 3
• dormir 4

Et on peut par exemple modifier la table du début en :

Par définition, une chaîne de Markov n'a pas de mémoire. Cela n'est pas toujours ce que l'on désire, on voudrait parfois 'ne pas revenir sur ses pas', 'tenir compte de certains éléments clés du passé', … Ceci va être possible, mais va augmenter (potentiellement de façon importante) le nombre d'états.

Imaginons que dans un certain état, on acquière un objet. On aimerait se rappeler que l'on dispose de cet objet. Cela est possible en dédoublant chacun des états $s$ en $(s,\text{ objet } = 1)$ et $(s,\text{ objet } = 0)$. Si cela est appliqué à la totalité des états, le nombre d'états a doublé, et le nombre de valeurs dans la table a quadruplé. Cependant, la plupart des valeurs sont identiques à celles que l'on avait précédemment : à moins de poser l'objet, on passe toujours d'un état $(x,1)$ à un état $(y, 1)$, et réciproquement, à moins de ramasser l'objet, on passe d'un état $(x,0)$ à un état $(y, 0)$ [il y a de plus beaucoup de chances que ces deux transitions aient la même valeur numérique]. Les seules valeurs nouvelles correspondent aux actions qui font gagner ou perdre l'objet (transitions de la forme $(x,0)$ vers $(y, 1)$ ou réciproquement). L'explosion combinatoire peut être un frein à l'utilisation de cette méthode (avec 10 drapeaux, on multiplie le nombre d'états par 1024 et la taille de la table par plus d'un million), mais il est possible de rendre cette explosion quasi négligeable, mais au prix d'une complexité accrue des codes et structures de données.

De la même façon, il est possible de se 'rappeler' de ce qui a été fait à la date précédente, en choisissant comme états non plus $S_t$ mais des couples $S_t, S_{t-1}$. Il est à noter que beaucoup de cases de la matrice $\mathbb{P}$ valent 0, car on ne peut transiter de l'état $(s_i,s_{i'})$ vers l'état $(s_j,s_{j'})$ que si $i = j'$ (ils correspondent à l'état du système à la même date). Dans la pratique, dans cette éventualité, il est certainement préférable de ne pas conserver dans $\mathbb{P}$ les cases évidement inutiles.

Dans l'exemple précédent, si on voulait modifier le comportement par "si avant de se révolter, on était en train de dormir, alors il n'y a aucune chance que l'on retourne dormir", on pourrait alors avoir comme table de transition :

La création d'une texture commence fréquemment par le chargement d'une image. Pour cela, la procédure la plus classique consiste à repasser temporairement en SDL1 :

• on crée une surface (type de données SDL1)
• on charge l'image dans la SDL_Surface,
• on transforme la surface en texture (type de données correspondant en SDL2)

Remarque

• la SDL ne fonctionne par défaut qu'avec le format bmp… Afin de pouvoir utiliser d'autres formats, il est nécessaire d'ajouter une bibliothèque #include <SDL2/SDL_image.h>. Il sera alors nécessaire de compiler avec le drapeau -lSDL2_image.

#include <SDL2/SDL_image.h>

On peut écrire une fonction qui charge une image dans une texture :

  #include <SDL2/SDL_image.h>               // Nécessaire pour la fonction IMG_Load
                                            // Penser au flag -lsdl2_image à la compilation
  //...

SDL_Texture* load_texture_from_image(char  *  file_image_name, SDL_Window *window, SDL_Renderer *renderer ){
    SDL_Surface *my_image = NULL;           // Variable de passage
    SDL_Texture* my_texture = NULL;         // La texture

    my_image = IMG_Load(file_image_name);   // Chargement de l'image dans la surface
                                            // image=SDL_LoadBMP(file_image_name); fonction standard de la SDL, 
                                            // uniquement possible si l'image est au format bmp */
    if (my_image == NULL) end_sdl(0, "Chargement de l'image impossible", window, renderer);

    my_texture = SDL_CreateTextureFromSurface(renderer, my_image); // Chargement de l'image de la surface vers la texture
    SDL_FreeSurface(my_image);                                     // la SDL_Surface ne sert que comme élément transitoire 
    if (my_texture == NULL) end_sdl(0, "Echec de la transformation de la surface en texture", window, renderer);

    return my_texture;
  }

  //...
  IMG_Quit()                                // Si on charge une librairie SDL, il faut penser à la décharger   

Remarque :

• le paramètre SDL_Window *window ne sert qu'en cas de problème à fermer la fenêtre,

On peut préférer à cette méthode 'traditionnelle' :

#include <SDL2/SDL_image.h>
// ...
  SDL_Texture *my_texture; 
  my_texture = IMG_LoadTexture(renderer,"./img/Maze.png");
  if (my_texture == NULL) end_sdl(0, "Echec du chargement de l'image dans la texture", window, renderer);
//...
  IMG_Quit() 

Dans tous les cas, il ne faut alors pas oublier la contrepartie à la création d'une texture : sa libération…

SDL_DestroyTexture(my_texture);

Une fois une texture créée, on peut désirer l'afficher, c'est la fonction SDL_RenderCopy qui va copier la texture, ou une partie de la texture à l'endroit indiqué dans le renderer.

void play_with_texture_1(SDL_Texture *my_texture, SDL_Window *window,
                         SDL_Renderer *renderer) {
  SDL_Rect 
          source = {0},                         // Rectangle définissant la zone de la texture à récupérer
          window_dimensions = {0},              // Rectangle définissant la fenêtre, on n'utilisera que largeur et hauteur
          destination = {0};                    // Rectangle définissant où la zone_source doit être déposée dans le renderer

  SDL_GetWindowSize(
      window, &window_dimensions.w,
      &window_dimensions.h);                    // Récupération des dimensions de la fenêtre
  SDL_QueryTexture(my_texture, NULL, NULL,
                   &source.w, &source.h);       // Récupération des dimensions de l'image

  destination = window_dimensions;              // On fixe les dimensions de l'affichage à  celles de la fenêtre

  /* On veut afficher la texture de façon à ce que l'image occupe la totalité de la fenêtre */

  SDL_RenderCopy(renderer, my_texture,
                 &source,
                 &destination);                 // Création de l'élément à afficher
  SDL_RenderPresent(renderer);                  // Affichage
  SDL_Delay(2000);                              // Pause en ms

  SDL_RenderClear(renderer);                    // Effacer la fenêtre
}

Remarque :

• Il ne faut pas oublier d'afficher avec SDL_RenderPresent et de mettre une pause SDL_Delay si on espère voir quelque chose.

void play_with_texture_2(SDL_Texture* my_texture,
                            SDL_Window* window,
                            SDL_Renderer* renderer) {
     SDL_Rect 
           source = {0},                      // Rectangle définissant la zone de la texture à récupérer
           window_dimensions = {0},           // Rectangle définissant la fenêtre, on n'utilisera que largeur et hauteur
           destination = {0};                 // Rectangle définissant où la zone_source doit être déposée dans le renderer

     SDL_GetWindowSize(
         window, &window_dimensions.w,
         &window_dimensions.h);               // Récupération des dimensions de la fenêtre
     SDL_QueryTexture(my_texture, NULL, NULL,
                      &source.w, &source.h);  // Récupération des dimensions de l'image

     float zoom = 1.5;                        // Facteur de zoom à appliquer    
     destination.w = source.w * zoom;         // La destination est un zoom de la source
     destination.h = source.h * zoom;         // La destination est un zoom de la source
     destination.x =
       (window_dimensions.w - destination.w) /2;     // La destination est au milieu de la largeur de la fenêtre
     destination.y =
         (window_dimensions.h - destination.h) / 2;  // La destination est au milieu de la hauteur de la fenêtre

     SDL_RenderCopy(renderer, my_texture,     // Préparation de l'affichage  
                    &source,
                    &destination);            
     SDL_RenderPresent(renderer);             
     SDL_Delay(1000);                         

     SDL_RenderClear(renderer);               // Effacer la fenêtre
   }

Remarque

• Ici, la source a pris la totalité de la texture, en modifiant les quatre paramètres du rectangle source, il aurait été possible de n'en prendre qu'une partie (obligatoirement rectangulaire).

L'idée ici est de déposer successivement la texture à différents endroits de l'écran, en effaçant l'écran entre chaque affichage.

void play_with_texture_3(SDL_Texture* my_texture,
                         SDL_Window* window,
                         SDL_Renderer* renderer) {
  SDL_Rect 
        source = {0},                             // Rectangle définissant la zone de la texture à récupérer
        window_dimensions = {0},                  // Rectangle définissant la fenêtre, on n'utilisera que largeur et hauteur
        destination = {0};                        // Rectangle définissant où la zone_source doit être déposée dans le renderer

  SDL_GetWindowSize(                                
      window, &window_dimensions.w,                 
      &window_dimensions.h);                      // Récupération des dimensions de la fenêtre
  SDL_QueryTexture(my_texture, NULL, NULL,         
                   &source.w,                       
                   &source.h);                    // Récupération des dimensions de l'image

  /* On décide de déplacer dans la fenêtre         cette image */
  float zoom = 0.25;                              // Facteur de zoom entre l'image source et l'image affichée

  int nb_it = 200;                                // Nombre d'images de l'animation
  destination.w = source.w * zoom;                // On applique le zoom sur la largeur
  destination.h = source.h * zoom;                // On applique le zoom sur la hauteur
  destination.x =                                   
      (window_dimensions.w - destination.w) / 2;  // On centre en largeur
  float h = window_dimensions.h - destination.h;  // hauteur du déplacement à effectuer

  for (int i = 0; i < nb_it; ++i) {
    destination.y =
        h * (1 - exp(-5.0 * i / nb_it) / 2 *
                     (1 + cos(10.0 * i / nb_it * 2 *
                              M_PI)));            // hauteur en fonction du numéro d'image

    SDL_RenderClear(renderer);                    // Effacer l'image précédente

    SDL_SetTextureAlphaMod(my_texture,(1.0-1.0*i/nb_it)*255);      // L'opacité va passer de 255 à 0 au fil de l'animation
    SDL_RenderCopy(renderer, my_texture, &source, &destination);   // Préparation de l'affichage
    SDL_RenderPresent(renderer);                  // Affichage de la nouvelle image
    SDL_Delay(30);                                // Pause en ms
  }                                                 
  SDL_RenderClear(renderer);                      // Effacer la fenêtre une fois le travail terminé
}

Remarque :

• il y a un fade-out dans cette animation : l'objet disparait petit à petit à la fin de l'animation. Pour obtenir ce résultat, SDL_SetTextureAlphaMod est utilisée. Cette fonction permet d'appliquer un coefficient de transparence à une texture (0 pour invisible, 255 pour opaque). S'il y avait un fond, il serait plus ou moins visible en fonction de la transparence choisie.

Les planches des sprites utilisées dans les animations sont construites en positionnant un objet dans ces différentes positions dans une même image (on peut appeler ces positions des vignettes). Il est important que :

• les positions soient placées intelligemment dans l'image : les vignettes sont si possible de la même taille, espacées régulièrement. L'objectif est de permettre de parcourir séquentiellement aisément les différentes vignettes qui constituent l'animation en déplaçant le rectangle source sur l'image de façon régulière,
• le fond de l'image soit transparent : sur les formats type png un point est codé par 4 valeurs (de 0 à 255) $(Rouge, Vert, Bleu, Transparence)$. Cette dernière composante est à 0 pour une parfaite transparence, et à 255 pour une parfaite opacité. Il est aisé d'incorporer des sprites dont le fond est transparent à n'importe quel décor. Dans l'éventualité où le fond du sprite serait uni, il y a plusieurs possibilités :
  • reprendre l'image avec un logiciel de dessin (gimp par exemple, présent sur la plupart des système Linux), l'outil permet même de réaliser un détourage avec un dégradé de transparence sur le bord du sujet afin qu'il se fonde au mieux dans n'importe quel décor,
  • utiliser des fonctions de la SDL qui permettent de choisir une ou plusieurs couleurs comme étant en réalité transparentes (c'est souvent ce que l'on fait avec des images au format bmp qui ne gèrent pas dans leur format la transparence),
  • utiliser un masque de transparence : on crée une image supplémentaire, en intensité de gris qui va servir, de façon totalement similaire à la 4^ième composante du png, à indiquer la transparence. Cette méthode, peut également donner des résultats intéressants pour créer des effets (par exemple une lampe torche qui se déplace en utilisant un disque avec un dégradé radial au bord que l'on déplace sur une image : sur la partie peinte à 100% du disque, on voit l'image, sur la partie peinte à 0%; on ne voit rien, et entre les deux une zone en clair obscur).

Vous pourrez par exemple utiliser vignettes libres kenney, ou celles-ci, ou rechercher par vous-même une planche sur votre moteur de recherche préféré "free tileset dungeon" (se limiter aux planches libres de droit !!).

void play_with_texture_4(SDL_Texture* my_texture,
                         SDL_Window* window,
                         SDL_Renderer* renderer) {
       SDL_Rect 
             source = {0},                    // Rectangle définissant la zone totale de la planche
             window_dimensions = {0},         // Rectangle définissant la fenêtre, on n'utilisera que largeur et hauteur
             destination = {0},               // Rectangle définissant où la zone_source doit être déposée dans le renderer
             state = {0};                     // Rectangle de la vignette en cours dans la planche 

       SDL_GetWindowSize(window,              // Récupération des dimensions de la fenêtre
                         &window_dimensions.w,
                         &window_dimensions.h);
       SDL_QueryTexture(my_texture,           // Récupération des dimensions de l'image
                        NULL, NULL,
                        &source.w, &source.h);

       /* Mais pourquoi prendre la totalité de l'image, on peut n'en afficher qu'un morceau, et changer de morceau :-) */

       int nb_images = 8;                     // Il y a 8 vignette dans la ligne de l'image qui nous intéresse
       float zoom = 2;                        // zoom, car ces images sont un peu petites
       int offset_x = source.w / nb_images,   // La largeur d'une vignette de l'image, marche car la planche est bien réglée
           offset_y = source.h / 4;           // La hauteur d'une vignette de l'image, marche car la planche est bien réglée


       state.x = 0 ;                          // La première vignette est en début de ligne
       state.y = 3 * offset_y;                // On s'intéresse à la 4ème ligne, le bonhomme qui court
       state.w = offset_x;                    // Largeur de la vignette
       state.h = offset_y;                    // Hauteur de la vignette

       destination.w = offset_x * zoom;       // Largeur du sprite à l'écran
       destination.h = offset_y * zoom;       // Hauteur du sprite à l'écran

       destination.y =                        // La course se fait en milieu d'écran (en vertical)
         (window_dimensions.h - destination.h) /2;

       int speed = 9;
       for (int x = 0; x < window_dimensions.w - destination.w; x += speed) {
         destination.x = x;                   // Position en x pour l'affichage du sprite
         state.x += offset_x;                 // On passe à la vignette suivante dans l'image
         state.x %= source.w;                 // La vignette qui suit celle de fin de ligne est
                                              // celle de début de ligne

         SDL_RenderClear(renderer);           // Effacer l'image précédente avant de dessiner la nouvelle
         SDL_RenderCopy(renderer, my_texture, // Préparation de l'affichage
                        &state,
                        &destination);  
         SDL_RenderPresent(renderer);         // Affichage
         SDL_Delay(80);                       // Pause en ms
       }
       SDL_RenderClear(renderer);             // Effacer la fenêtre avant de rendre la main
     }

Fréquemment, on désire incruster un sprite sur un décor, et non sur un fond uni. Pour afficher, cela ne pose pas de problème particulier : à la façon d'un peintre, on positionne successivement les couches, et ce qui est peint après cache ce qui a été peint précédemment (superposition des couches).

Pour ce qui est de l'effacement, on peut effacer toute l'image, puis recommencer la totalité de la peinture (peut-être après avoir sauvegardé le fond, en particulier s'il est procédural). Cette solution est utilisée en particulier sur les jeux où il y a un scrolling de l'écran, et dans le cas général lorsque le 'fond' varie sur une grande partie.

Lorsque entre chaque image peu de choses ont été modifiées, on peut préférer sauvegarder un rectangle de fond qui englobe l'endroit où sera positionné l'élément mobile, superposer au fond l'élément mobile, afficher, et avant de passer à l'image suivante recopier la sauvegarde du fond pour effacer l'élément mobile. L'avantage de cette méthode est (potentiellement) sa vitesse car on ne modifie qu'une partie de la texture à afficher et pas sa totalité. Elle est moins utilisée maintenant suite à l'évolution des performances des circuits graphiques, et on préfère souvent simplifier le code, cette optimisation n'étant plus réellement nécessaire…

  void play_with_texture_5(SDL_Texture *bg_texture,
                           SDL_Texture *my_texture,
                           SDL_Window *window,
                           SDL_Renderer *renderer) {
  SDL_Rect
    source = {0},                             // Rectangle définissant la zone de la texture à récupérer
    window_dimensions = {0},                  // Rectangle définissant la fenêtre, on  n'utilisera que largeur et hauteur
    destination = {0};                        // Rectangle définissant où la zone_source doit être déposée dans le renderer

  SDL_GetWindowSize(window,                   // Récupération des dimensions de la fenêtre
                    &window_dimensions.w, 
                    &window_dimensions.h); 
  SDL_QueryTexture(my_texture, NULL, NULL,    // Récupération des dimensions de l'image
                   &source.w, &source.h); 

  int nb_images = 40;                         //  Il y a 8 vignette dans la ligne qui nous intéresse
  int nb_images_animation = 1 * nb_images;    // 
  float zoom = 2;                             // zoom, car ces images sont un peu petites
  int offset_x = source.w / 4,                // La largeur d'une vignette de l'image
      offset_y = source.h / 5;                // La hauteur d'une vignette de l'image
  SDL_Rect state[40];                         // Tableau qui stocke les vignettes dans le bon ordre pour l'animation

  /* construction des différents rectangles autour de chacune des vignettes de la planche */
  int i = 0;                                   
  for (int y = 0; y < source.h ; y += offset_y) {
    for (int x = 0; x < source.w; x += offset_x) {
      state[i].x = x;
      state[i].y = y;
      state[i].w = offset_x;
      state[i].h = offset_y;
      ++i;
    }
  }
                                              // ivaut 20 en sortie de boucle
  state[15]  = state[14]                      // on fabrique des images 14 et 15 en reprenant la 13  
            = state[13];                      // donc state[13 à 15] ont la même image, le monstre ne bouge pas   

  for(; i< nb_images ; ++i){                  // reprise du début de l'animation en sens inverse  
    state[i] = state[39-i];                   // 20 == 19 ; 21 == 18 ; ... 39 == 0  
  }

  destination.w = offset_x * zoom;            // Largeur du sprite à l'écran
  destination.h = offset_y * zoom;            // Hauteur du sprite à l'écran
  destination.x = window_dimensions.w * 0.75; // Position en x pour l'affichage du sprite
  destination.y = window_dimensions.h * 0.7;  // Position en y pour l'affichage du sprite

  i = 0;
  for (int cpt = 0; cpt < nb_images_amination ; ++cpt) {
    play_with_texture_1_1(bg_texture,         // identique à play_with_texture_1, où on a enlevé l'affichage et la pause
                          window, renderer); 
    SDL_RenderCopy(renderer,                  // Préparation de l'affichage
                   my_texture, &state[i], &destination);
    i = (i + 1) % nb_images;                  // Passage à l'image suivante, le modulo car l'animation est cyclique 
    SDL_RenderPresent(renderer);              // Affichage
    SDL_Delay(100);                           // Pause en ms
  }
  SDL_RenderClear(renderer);                  // Effacer la fenêtre avant de rendre la main
}

Le défilement parallaxe consiste à donner une impression de profondeur en utilisant plusieurs fonds superposés les uns sur les autres (algorithme du peintre : la nouvelle couche de peinture en recouvrant l'ancienne cache ce qui était dessiné) que l'on anime à des vitesses différentes (ce qui est plus loin bouge plus lentement).

Si on imagine que l'on regarde le paysage depuis une voiture :

• le soleil et la lune, à l'infini, ne bougent pas, on les dessine en premier
• les montagnes à l'horizon ne bougent quasiment pas : on va les dessiner ensuite,
• les collines un peu plus proches se déplacent à une vitesse moyenne,
• les arbres au bord de la route se déplacent à la vitesse de la voiture, comme ils sont les plus proches on les dessine en dernier.

Pour que tout se passe bien, il ne faut pas oublier de gérer la transparence : les arbres ne doivent se dessiner que là où il y a de la matière. Dans l'image de l'arbre, ce qui n'est pas arbre doit être de couleur totalement transparente (rappel : les images au format png possèdent un canal α pour gérer la transparence).

On peut encore améliorer l'effet de profondeur en jouant sur les couleurs et la netteté :

• plus un décor est lointain, plus on en diminue la netteté (le flou créé par les l'air)
• plus un décor est lointain, plus on en diminue le contraste.

Afin de réaliser ces effets, on peut utiliser le logiciel gimp, ou tout autre logiciel de traitement d'images prenant en charge ces éléments (quasiment tous).

Si on remet les différents morceaux de code précédents bout-à-bout, et peut-être quelque modifications mineures, on obtient ./all_executables.tar.gz (télécharger, exécuter 'textures').

Il est temps de mettre en pratique ce que l'on vient de voir sur les textures, en créant une petite animation simple. Il est inutile qu'elle soit paramétrable, il ne faut pas y passer trop longtemps, faites uniquement de petites variations par rapport à ce qui a été proposé ci-avant, gardez vos idées géniales pour la suite :-).

On peut ainsi imaginer utiliser (avec plus ou moins de variations par rapport à ce qui est introduit dans ce document) cette méthode dans des situations telles que :

• apprendre à jouer au go : l'ordinateur joue avec deux programmes, lorsqu'un des programmes gagne, on favorise par le futur les coups joués dans les mêmes situations, et inversement s'il perd.
• apprendre à garer une voiture : un environnement est simulé sur ordinateur, le programme réalise des actions (tourner de x degrés à gauche le volant, accélérer, freiner), on évalue la qualité de la position de la voiture après N actions, et on améliore nos connaissances de ce qu'il faut ou il ne faut pas faire. Le pilotage peut aller jusqu'au véhicule autonome, voire même au véhicule de course.
• apprendre à jouer au casse briques : l’ordinateur peut déplacer la raquette à droite ou à gauche, s'il perd la balle, l'évaluation est négative, s'il ne la perd pas, l'évaluation est le temps moyen utilisé afin de toucher une brique (ce qui permettra de favoriser les coups les plus efficaces, et pas seulement de rattraper la balle).
• apprendre à se mouvoir : un robot dispose de différents actionneurs (par exemple : un par articulation), le but est de lui apprendre à les combiner afin qu'il puisse passer d'une position couchée à la position debout.
• …

La méthode abordée ici a pour vocation d'apprendre à un programme à prendre des décisions. Pour cela on simule un environnement analogue à celui qui sera utilisé dans l'application finale, et on génère des actions dans cet environnement (parfois on travaille directement dans l'univers réel, mais ce n'est en général pas la voie privilégiée). L'apprentissage par renforcement consiste à renforcer les comportements qui ont menés à des résultats positifs et à réfréner ceux dont les conséquences ont été néfastes.

Restriction 1

La méthode abordée nécessite de simuler l'environnement de façon suffisamment pertinente pour permettre la transposition de ce qui a été appris pendant la simulation à la réalité (cela ne pose en général pas de problème pour les jeux, mais est moins évident pour les applications agissant sur le monde physique : les capteurs physiques ne correspondent pas tout à fait aux "perceptions" de nos fonctions, les actionneurs ne font pas toujours ce que l'on demande, les roues patinent, l'arrêt n'est pas instantané, …).

Restriction 2

Afin d'obtenir un apprentissage concluant, le nombre de simulations à réaliser est souvent très important. Pour se donner une idée, la 'difficulté de l'apprentissage' est souvent proportionnelle au nombre d'états de perception possibles. Ainsi, si la perception se limite à la couleur d'un feu de signalisation, il y a 3 états, si on doit 'attraper' cette couleur sur une grille de $(L=100) \times (l = 100) \times (nbCouleurs=16)$, ce qui fait $160 000$ états. Des méthodes existent afin de limiter l'effet de l'explosion du nombre d'états existent, mais elles ne seront pas abordées dans ce document (mélange de Q-learning et de réseaux de neurones en particulier).

Dans les exemples qui suivent, un agent reçoit des stimulus (perceptions), agit, et reçoit une récompense. Vous disposez des traces de ce qui s'est produit dans le passé. Votre but est de déterminer des règles de la forme "si perception alors action" dans le but de permettre à cet agent de maximiser les récompenses futures. Vous n'avez pour l'instant pas de connaissance sur le sujet, vous n'avez que votre bagage général pour obtenir vos premiers algorithmes.

exemple 1

Deux perceptions possibles, 3 actions.

perception	action	récompense
A	1	42
B	2	-4
B	3	-2
A	1	24
A	2	36
A	1	20
B	3	2
A	3	12
A	2	21
A	1	35

Résultat (à compléter) :

SI perception	ALORS action
A	?
B	?

Quelles nouvelles expériences seraient les plus intéressantes à demander à l'agent de réaliser ?

exemple 2

L'agent va cette fois exécuter consécutivement deux actions, il y a 4 perceptions possibles et 2 actions disponibles.

• l'agent perçoit 'perception 1',
• il agit avec 'action 1',
• suite à cette action il arrive dans un nouvel état et reçoit un récompense 'récompense 1'
• il perçoit ce nouvel état par 'perception 2',
• il agit avec 'action 2',
• suite à cet action il obtient la récompense 'récompense 2'.

les perceptions possibles sont A, B, C, D les actions disponibles 1, 2.

perception 1	action 1	récompense 1	perception 2	action 2	récompense 2
A	1	1	C	1	4
A	1	1	C	2	3
A	1	-1	D	1	3
A	2	0	D	2	5
A	2	-2	D	1	2
A	2	-1	D	2	4
B	1	-1	D	1	3
B	2	0	D	2	4
B	1	2	A	1	1
B	2	3	B	2	-2

Résultat (à compléter) :

SI perception	ALORS action
A	?
B	?
C	?
D	?

Dans la plupart des algorithmes, il existe des paramètres qui doivent décroitre vers 0 au fil de l'exécution du programme.

Plusieurs types de suites, de décroissances plus ou moins lentes et de limite nulle sont classiquement utilisées, dont :

Pour limiter la vitesse de décroissance de la suite géométrique (même avec une raison de l'ordre de 0.99), on l'utilise souvent conjointement avec des paliers : la mise à jour de la valeur de $U_n$ n'est pas réalisée à chaque itération, mais uniquement toutes les 100 itérations (ou 200, ou 1000… [ce qui malheureusement va encore ajouter un paramètre à gérer]).

La décroissance logarithmique est lente, mais c'est celle qui est la plus proche de la théorie (les preuves de convergence des algorithmes sont souvent sous l'hypothèse d'une décroissance logarithmique) et a (un peu) plus de chances d'aboutir à un résultat correct (mais parfois au prix d'un temps de calcul plus long).

La plupart des algorithmes utilisent la même forme de formule de mise à jour. Cette formule, avec ses variations est $u \longleftarrow u + \xi \times \left(a-u\right)\text{ où } 0 < \xi < 1$, que l'on peut réécrire sous la forme d'une suite : $u_{n+1} = u_{n} + \xi \times\left(a-u_{n}\right)$. On s'intéresse à l'évolution de la distance entre $u_n$ et $a$. On a :

On désire étendre le résultat précédent au cas où $a$ n'est plus une constante mais une suite de réalisations d'une variable aléatoire. Pour étudier cette modification, on définit :

• la suite de variables aléatoires $(A_n)$, identiquement distribuées en fonction de $n$ et admettant une même espérance $\mathcal{A}$,
• la suite de variables aléatoires $(U_n)$ par $U_{n+1} = U_{n} + \xi \times\left(A_n-U_{n}\right)$,
• la suite des espérances des variables $U_n$ par $V_n = \mathbb{E}( U_n)$.

On s'intéresse à l'évolution de la distance entre $V_n$ et $\mathcal{A}$. On a

Attention

Il y a convergence de l'espérance, il n'y a pas convergence de la variable, et il n'y a d'ailleurs pas de raison que la variable $U_n$ converge (chaque nouvelle réalisation de $A_n$ réalise une modification dont l'amplitude ne tend pas vers 0)! Pour obtenir de façon pratique (et artificielle) cette convergence, on choisit de prendre un $\xi$ petit (il n'y a toujours pas de convergence, mais les fluctuations sont alors de faible amplitude), et/ou de faire doucement tendre $\xi$ vers 0 au fil de l'algorithme [Il y a alors convergence en valeur, mais plus $\xi$ tend rapidement vers 0, moins la convergence en espérance est garantie. Il faudra choisir comment tendre vers O, ce qui complexifie le paramétrage de l’algorithme]). Il ne faut toutefois pas oublier que la vitesse de convergence de l'espérance dépend également de $\xi$, plus $\xi$ est proche de 1, plus la convergence est rapide [car $|1-\xi|$ est plus proche de 0]. Un compromis est donc absolument nécessaire afin d'obtenir au mieux ces deux convergences !

En conclusion

En utilisant la formule proposée, on peut approcher petit à petit la valeur de l'espérance d'une variable aléatoire en coagulant les valeurs des réalisations de cette variable. Cette méthode possède le très regrettable inconvénient de nécessiter un réglage de paramètre $\xi$, qui peut être laborieux et assez dépendant du problème, mais profite des avantages suivants :

• la seule information stockée est l'estimation en cours (cela simplifie un peu les algorithmes),
• il y a une adaptation naturelle à des variations de la distribution de la variable aléatoire au fil des itérations ($A_n$ n'est plus identiquement distribuée, mais peut évoluer lentement), les valeurs les plus récentes étant les plus importantes dans le calcul de l'estimation (on peut diminuer cet effet en choisissant que $\xi \to 0$, la vitesse de décroissance permettant d'ajuster le poids du passé).

La fonction $v$ associe à un état du système sa qualité. Ainsi, un agent rationnel choisira préférentiellement de se rendre dans un état de qualité élevée plutôt que dans un état de faible qualité. La valeur de $v$ ne représente pas uniquement le bénéfice immédiat (récompense obtenue parce qu'on atteint cet état), mais également le bénéfice que l'on peut espérer obtenir à plus long terme si on transite par cet état.

Une fois les qualités de tous les états connus, leur utilisation peut suivre la boucle suivante :

• percevoir la situation ( = connaitre $s$),
• pour chaque action disponible, générer l'état qui serait (au conditionnel !!!) atteint,
• choisir parmi les actions possibles préférentiellement celle qui mène à un état de qualité maximale. Le problème de cette façon de juger de la qualité par la qualité des états vient d'apparaitre : il est nécessaire de pouvoir générer les états sans pour autant effectuer réellement les actions qui permettraient de les atteindre.

La fonction $Q(s,a)$ associe à une perception de l'agent la qualité de chacune des actions disponibles dans cet état. L'état du système est défini par les perceptions de l'agent. La fonction $Q$ prend deux arguments, $p$ (ou $s$, puisque l'état n'est connu que via les perceptions) et $a$ et renvoie la valeur de la qualité de l'action $a$ lorsque la perception du monde est $p$. On peut imaginer d'implémenter $Q$ par un tableau 2D, dont les indexes des lignes représentent les différentes perceptions possibles et les indexes des colonnes les différentes actions possibles. La valeur située en ligne $l$ et colonne $c$ indique la qualité de l'action $c$ lorsque la perception du monde est $l$.

Par exemple : un véhicule se trouve devant un feu tricolore. Sa perception de l'environnement se limite à la couleur du feu, et ses actions possibles sont : s'arrêter, rouler. On peut alors imaginer la table des qualités qui suit :

On augmentant les perceptions (ici, en tenant compte de la vitesse actuelle du véhicule), on peut améliorer la modélisation du monde (on est encore loin d'un modèle pertinent à implémenter dans un véhicule autonome…) :

Une fois cette table d'association créée, son utilisation peut suivre la boucle suivante :

• percevoir la situation,
• choisir parmi les actions possibles préférentiellement celle avec la qualité la plus élevée.

On s'intéresse dans ce paragraphe aux valeur que l'on voudrait trouver dans la table, pas à comment les fabriquer.

Suite à une observation, la qualité d'une action est la qualité de l'état atteint lorsque l'on effectue cette action. Afin de définir la qualité d'un état, voici les points qu'il faut considérer :

• La qualité n'est pas toujours une mesure immédiate : avant de savoir si le résultat d'une action est bon, il est souvent nécessaire de la juger à l'aune de ses conséquences. Dévaliser une banque peut procurer une récompense immédiate, qui après quelques temps peut ne pas être suffisante pour compenser les désagréments que cette action engendre. La qualité est un mélange entre les récompenses obtenues à court terme et les récompenses futures issues de cet état. Suivant l'adage "un tien valant mieux que deux tu l'auras !", on va généralement pondérer dans le calcul de la qualité plus fortement le futur proche que le futur lointain.
• La qualité d'un état n'est pas toujours la même, même si la situation perçue est la même. Par exemple : griller un feu rouge ne provoque pas toujours la mort. L'état du monde définit les perceptions mais les perceptions ne définissent pas l'état du monde, il peut y avoir plusieurs états du monde qui créent la même perception. La qualité est un mélange entre les différentes qualités des états qui peuvent être atteints.

La qualité d'une action dans une certaine situation peut donc être définie comme une moyenne pondérée des espérance des qualité des états qui en découlent.

Dans la première table des qualités dans l'exemple des feux de signalisation, la valeur de 5 (feu vert, rouler) correspond à un mélange entre les accidents (plus ou moins graves) possibles (même si le véhicule est passé au vert), au plaisir d'être rentré plus tôt, au plaisir de la rencontre imprévue un peu plus tard, … On ne sait pas a priori ce que cette valeur présage, elle indique uniquement que c'est une état qui dans le passé nous aurait permis d'espérer une qualité de 5.

La qualité d'un état terminal est la récompense obtenue dans cet état (trésor trouvé, mort, …). La qualité d'un état non terminal dépend des actions qui seront réalisées depuis cet état. On va se placer dans la situation où le prochain choix sera rationnel (le meilleur possible d'après les connaissances du moment) : la qualité d'un état est la qualité du meilleur état que l'on peut atteindre après une action.

La qualité d'un état $s$ est l'espérance des récompenses que l'on peut atteindre depuis l'état $s$ pour les dates de temps futures : $k = 0, 1, ...$, pondérées par un facteur $\gamma^k, \text{ avec } \gamma \in [0; 1[$

version se focalisant sur les états

En supposant que les tous les états ont leur qualité calculée comme précédemment, cette équation devient:

NB : le maximum de la formule a pour origine que le choix de l'action qui sera réalisée est rationnel : pendant l'exploitation, on choisit l'action qui possède la plus haute qualité. Dans l'éventualité où l'exploitation ferait un choix notablement différent, il pourrait être approprié de modifier ce $max$ de façon à ce qu'il corresponde à la politique d'utilisation choisie. [Les deux façons de choisir une action présentées dans la suite sont compatibles avec le $max$ utilisé ici.]

version se focalisant sur les actions

La qualité d'une action $a$ réalisée dans l'état $s$, en notant $s'$ les états résultants de $s$ après l'action $a$ est

NB : voir ci-dessus dans la version 'états'.

$\left(1-X\%\right)$ du temps, on choisit l'action de qualité maximale, et $X\%$ on tire en aléatoire uniforme l'action à exécuter parmi toutes celles possibles. Cela permet de modéliser deux comportements :

l'exploration

On ne se préoccupe pas de ce qui a déjà été appris. Cette partie exploratoire est prépondérante lorsque les connaissances sont faibles et diminue au fil de l'apprentissage, de façon à ne pas toujours perdre du temps à explorer des situations non pertinentes. Comme on ne tient pas du tout compte de ce qui a déjà été appris, il est possible de faire émerger des comportements totalement nouveaux.

l'exploitation

Une fois le modèle appris, la partie exploratoire est terminée, on utilise l'information emmagasinée en choisissant à chaque itération l'action de qualité maximale. Dans une situation où l'environnement n'est pas stable, la phase exploratoire ne disparait pas totalement, ce qui permet au programme de :

• par défaut préférer ce qui a fonctionné par le passé,
• sans supprimer la possibilité d'une innovation.

Les valeurs dans la table ne sont plus interprétées comme des qualités mais comme des préférences (et même si on préfère le chocolat au bonbons, il n'est pas impossible de temps en temps de choisir les bonbons plutôt que le chocolat, alors que pour la qualité, on choisit toujours la meilleure possible). Pour implémenter cette idée, on va utiliser la table des qualités afin de définir une loi de distribution de probabilités, qui rende plus probables les actions de qualités les plus fortes, sans pour autant supprimer la possibilités des autres. On peut utiliser la distribution de Boltzmann (ou distribution de Gibbs, selon la littérature) afin de choisir cet état.

Entrées :
  - s la situation
  - Q la méthode permettant de connaitre la qualité d'une action dans une situation donnée
  - T la 'température', c'est un réel strictement positif
Sortie :
  - une action tirée selon la distribution de Gibbs
Processus :
  - Définir L : la liste des actions possibles depuis l'état s
  - Définir N le nombre d'éléments de L
  - Pour chaque action a de L:
      - Définir E(a) : l'énergie de a est E(a) = exp(Q(s,a)/T)
  - Définir Z : la somme des énergies des éléments de L
  - Définir action = L[N-1], c'est l'indice de l'action par défaut 
  - Définir alpha : un réel tiré en aléatoire uniforme dans [0 ; 1[
  - Définir cumul = 0
  - pour a dans L :
    - cumul +=  E(a)/Z
    - si alpha <= cumul :
      - action = a
      - break
  - renvoyer action 

Pour comprendre le fonctionnement de cet algorithme, on commence par oublier le paramètre $T$. Le passage par l'exponentielle rend les énergies strictement positives. La normalisation par Z rend $\sum_{a}\frac{E(a)}{Z} = 1$, ce qui rend ces quantités conformes à des mesures de probabilités. Ainsi, les $\frac{E(a)}{Z}$ permettent de définir une distribution de probabilité que l'on utilise comme une loi tabulés (Cf. compléments algorithmiques) Le critère de "plus la qualité est élevée, plus la probabilité de réaliser l'action" est respecté (stricte croissance de l'exponentielle).

Le paramètre de température a l'effet suivant : lorsque la température $T$ est élevée, comme l'exponentielle est 'constante' au voisinage de 0, les valeurs de $\frac{E(a)}{Z}$ sont toutes les mêmes, et la distribution tend vers une distribution uniforme ; on retrouve la partie exploration de la version ε-greedy. Lorsque la température est proche de 0, les écarts entre les $E(a)$ sont amplifiés, et à l’extrême, la distribution se limite alors aux actions dont la qualité est maximale ; on retrouve la partie 'choix de la qualité maximale' de ε-greedy (piste pour s'en convaincre : on met en facteur dans $Z$ la quantité $E(a)_{max}$ qui correspond à la qualité maximale, et on obtient alors $Z = E(a)_{max} \times \left(k + o_{T\rightarrow 0}(1)\right)$, où $k$ est le nombre d'états possédant la même qualité maximale ; après la normalisation, il ne reste donc plus que les états de qualité maximale).

Au départ l'agent ne dispose d'aucune information sur la qualité des actions qu'il peut effectuer. On peut donc au choix initialiser les qualités à 0 (ou à une valeur approxiamative de l'espérance des récompenses si les récompenses ne sont pas centrées sur 0), ou à des valeurs aléatoires tirées en uniforme dans un domaine similaire à celui dans lequel les récompenses sont définies (on n'initialise pas entre -100 et 100 sir les récompenses sont entre -1 et 2, on choisit un domaine similaire).

L'agent est placé dans un état initial $s_0$, il choisit son action en utilisant pour cela sa connaissance actuelle des qualités, il atteint alors l'état $s_1$, … et ainsi de suite jusqu'à :

• atteindre un état terminal (fin de partie : la tâche a plus ou moins bien été accomplie)
• dépasser un nombre d'état jugé comme plus que suffisant (cela permettra d'éviter des boucles infinies)

Il résulte de cet enchaînement d'actions (que l'on appelle une époque, ou un 'run') les suites suivantes :

• la suite des états parcourus $s_0, s_1, s_2, ..., s_{n-1}, s_n$,
• la suite des actions réalisées $a_0, a_1, a_2, ..., a_{n-1}$ [ Attention important : $a_i$ désigne l'action réalisée au départ de l'état $s_i$]
• la suite des récompenses obtenue $r_0, r_1, r_2, ..., r_{n}$ [ Attention important : $r_i$ désigne la récompense obtenue en atteignant l'état $s_i$ c'est à dire après l'action $a_{i-1}$]

Les formules de mises à jour ont été créées en fusionnant les formules qui définissent les qualités (qualité d'un état ou d'une action) avec le préliminaire mathématique qui permet d'estimer de façon itérative une espérance.

modification immédiate

L'agent choisit une action, l'exécute, et met à jour la qualité correspondante en fonction des récompenses obtenues. Les listes présentées (les suites $s_i$, $a_i$ et $r_i$) sont limitées à leur premier terme ($s_0, a_0, r_0$). Comme la mise à jour est immédiate, si les récompenses sont principalement à long terme, l'apprentissage risque d'être extrêmement long : pour modifier $Q$ (ou $v$), il faut arriver sur un état qui a déjà été modifié, donc si au départ l'agent est dans un état assez lointain d'une récompense, il ne va rien apprendre, et tout nouvel apprentissage ne sera pleinement utilisé que dans un futur lointain, le temps qu'il influence les autres qualités pouvant être assez long. Quoi que cette méthode soit la plus simple à implémenter, elle n'est en général pas la plus efficace et elle ne sera pas développée dans la suite de ce document.

modification après un 'run'

On fait la mise à jour après avoir obtenu : soit un nombre de récompenses significatif (positives comme négatives), ou après avoir atteint un état terminal [dans le cas où le run s'est terminé par dépassement du nombre d'actions, on choisira ou non de faire la mise à jour, ou de la faire avec un coefficient $\xi$ plus petit, mais l'information à tirer de cette époque est faible]. Cette méthode est en général préférable à la précédente car il va être possible de maximiser l'utilisation de l'information obtenue dans un apprentissage aux autres apprentissages de la même époque en procédant par rétro-propagation : on effectue les mises à jour en partant de l'état $s_{n-1}$ car c'est celui qui contient le plus d'information, puis on remonte vers l'état $0$. Ainsi, lorsque l'on met à jour une qualité, on utilise le résultat des mises à jour des qualités qui viennent d'être faites.

Le synopsis du processus d'apprentissage est

1. Initialiser les qualités, les paramètres d'apprentissage,
2. Générer une instance du monde,
3. Réaliser un 'run', c'est à dire une suite d'actions menant si possible à un état terminal,
4. A partir des résultats du 'run', modifier les qualités par rétro-propagation,
5. Modifier si nécessaires les paramètres d'apprentissage,
6. Retour en 1 jusqu'à (condition à choisir de façon adéquate).

La difficulté d'utilisation de cette formule provient du calcul du maximum qui se fait sur l'ensemble des situations accessibles. Il est en général assez aisé d'énumérer les actions possibles à un instant donné, mais pour connaître les états qui en résultent… il est nécessaire d'effectuer les actions. Ainsi, on va construire pour chaque état la liste des situations qui lui sont directement accessibles. Par conséquent, afin que cette stratégie soit possible, il faudra être capable de mémoriser un état du monde afin de pouvoir y revenir par la suite [attention, ici il y a une nuance : il ne suffit pas de pouvoir sauvegarder un état (qui ne correspond qu'à une perception du monde), il est nécessaire de pouvoir sauvegarder l'état du monde afin de pouvoir reprendre la simulation là où elle en était].

Ce retour sur une situation sauvegardée n'est possible que si on a accès à tous les paramètres qui caractérisent le monde, ce qui n'est en général pas le cas si l'apprentissage se déroule dans le monde réel.

L'algorithme va consister à créer pour chaque état la liste des états auxquels il permet d'accéder en une action. Pour cela, on modifie l'algorithme de la suite des déplacements : avant de se déplacer depuis un état $s$, pour chacune des actions possibles, on vérifie que l'état qui serait atteint est bien dans la liste des états directement accessibles depuis $s$, et s'il ne l'est pas on l'ajoute à cette liste. On dispose alors d'un graphe orienté des perceptions $G$.

algorithme dans le cas d'un apprentissage après une suite d'actions concluante

Entrées :
  - s0, s1, ... sn la suites des états
  - r0, r1, ..., r(n-1) la suite des récompenses 
  - G table des fils des perceptions, G[x] est l'ensemble des états accessibles depuis l'état x
  - v la méthode permettant de connaitre la qualité d'un état
Sortie :
  - v mise à jour
Processus :
  - V(sn) += epsilon * (rn  - v(sn)) 
  - pour i = n-1 à 0 par pas de -1
    - Définir M le maximum des v(s') pour s' dans G[si] 
    - v(si) += epsilon * (ri + gamma * M - v(si)) 

En notant $s'$ l'état atteint après avoir effectué l'action $a$ en l'état $s$ :

Cette méthode n'a pas le problème de la sauvegarde de l'état du monde de la méthode précédente, mais possède le désavantage de posséder plus de valeurs de qualités à estimer que la précédente". Dans la méthode précédente, on devait estimer une qualité par état, alors que dans cette méthode, il faut estimer la qualité de chaque action effectuée dans chaque état, ce qui signifie que le nombre de qualités à estimer est multiplié par le nombre d'actions possibles. Par conséquent, il y a un risque que cette méthode nécessite plus de temps pour obtenir un résultat concluant.

algorithme dans le cas d'un apprentissage après une suite d'actions concluante

Entrées :
  - s0, s1, ... sn la suites des états
  - a0, a1, ..., a(n-1) la suite des actions réalisées
  - r0, r1, ..., r(n-1) la suite des récompenses  
  - Q la méthode permettant de connaitre la qualité d'une action dans un état
Sortie :
  - Q mise à jour
Processus :
  - Q( s(n-1), a(n-1) ) += epsilon * (rn - Q( s(n-1),a(n-1) ))
  - pour i = n-2 à 0 par pas de -1
    - Définir M le maximum des Q(s(i+1), a) pour toute action a possible
    - Q(si, ai) += epsilon * (r(i+1) + gamma * M - Q(si,ai) )

Le problème lié au maximum reste n'est pas présent dans la phase d’apprentissage de SARSA, mais existe toujours au moment du run, lors du choix de l'action à réaliser. L'influence de cette modification sera donc plus faible que dans le 'double Q-learning' mais peut tout de même améliorer les résultats.

Pour y palier, on peut encore une fois utiliser deux fonctions de qualité, afin de séparer l'estimateur sur lequel on a choisi l'action de celui que l'on apprend.

Entrées :
  - s0, s1, ... sn la suites des états
  - a0, a1, ..., a(n-1) la suite des actions réalisées
  - r0, r1, ..., r(n-1) la suite des récompenses  
  - Q1, Q2 les fonctions défiissant la  qualité d'une action dans un état
Sortie :
  - Q1 et Q2 mis à jour
Processus :
 - Définir alpha, réel aléatoire tiré en uniforme dans [0 ; 1[ 
 - Si alpha <0.5
     - Définir Q_apprentissage = Q1 et Q_estimation = Q2
 - Sinon
     - Définir Q_apprentissage = Q2 et Q_estimation = Q1

  - Q_apprentissage(s(n-1), a(n-1)) += epsilon * (r(n) - Q_apprentissage(s(n-1),a(n-1)) )

  - pour i = n-2 à 0 par pas de -1
      - Q_apprentissage(si, ai) += epsilon * (r(i+1) + gamma * Q_estimation(s(i+1), a(i+1)) - Q_apprentissage(si,ai) )

Comme vous allez vous en rendre compte, le réglage des paramètres peut être assez désagréable. Afin de pouvoir manipuler les algorithmes, les différents paramètrages sont conservés dans une structure découpée si nécessaire en unions (lorsque des paramètres son incompatibles) et structures (s'ils sont compatibles entre eux). Il est conseillé que tout soit stocké dans le même .c (ou dans un même fichier texte de configuration si vous voulez quelque chose de plus ergonomique pour faire les tests). Les paramètres Elle contient :

• paramètres de définition du monde
  • paramètres de dimensionnement
  • paramètres définissant les récompenses
  • paramètres d'initialisation
• paramètres de l'apprentissage
  • pointeurs sur les fonctions choisies : ce n'est pas obligatoire, mais cela peut rendre les modifications de code plus agréables, vous pouvez avoir différentes fonctions (par exemple learn_state, learn_Q , learn_Q_double, learn_sarsa, …) et la fonction à utiliser pendant cet apprentissage est précisée dans le fichier de config par un pointeur sur fonction… à vous de voir si cela ne vous effraie pas.
  • nombre d'époques
  • nombre maximum d'états dans une époque
  • ξ, comment ξ décroît
  • α, comment α décroît
  • γ, comment γ décroît
• paramètres sur les états
  • paramètres pour définir les états
  • paramètres pour définir les actions
  • paramètres pour l'initialisation
• paramètres de l'exploration
  • pour ε -greedy : valeur de départ, comment ε décroît,
  • pour 'preference learning base' : valeur initiale de la température, comment $T$ décroît,

Il est de plus conseillé que toutes les fonctions prennent en entrée un pointeur sur cette structure : cela ne coûte pas cher et cela simplifie l'utilisation des fonctions (on ne se pose pas de question, c'est le premier paramètre à l'appel de toutes les fonctions).

Même si vous ne travaillez pas avec un fichier de configuration, il est intéressant d'avoir une fonction qui à chaque test sauvegarde les paramètres, auxquels sont ajoutés la date et l'heure (et si possible les résultats de l'apprentissage, mais vous verrez que dans la pratique ce point est plus difficile). Cela permet de vérifier ce qui a été testé. Conserver une trace des tests réalisés et très important afin de ne pas refaire 100 fois les mêmes choses, et oublier toujours les mêmes.

Voici une liste de quelques fonctions qui peuvent vous aider à commencer à structurer votre code. N'oubliez pas que toutes ces fonctions ont également en entrée un accès à tous les paramètres.

• fonction de perception : prend l'état du monde en entrée et renvoie l'état de perception ($s$),
• fonction d'évolution : prend en entrée le monde et une action et modifie l'état du monde,
• fonction de récompense : prend le monde en entrée et renvoie la récompense associée à cet état du monde,
• fonction d'énumération des actions : prend le monde en entrée et renvoie une énumération des actions possibles,
• fonction de choix d'une action : prend en entrée une perception, le monde et renvoie l'action choisie.
• fonction principale :

- Initialiser les paramètres, les sauvegarder
- Si c'est un apprentissage de qualité d'états : initialiser dans la table des successeurs des états
- Pour époque = 0 à nb_époques-1
      - Créer le monde
      - Pour pas = 0 à nb_max_actions_dans_epoque-1
            - Récupérer la récompense sur le monde actuel, la stocker
            - Percevoir l'état, le stocker
            - Si c'est un apprentissage de qualité d'états : mettre à jour les successeurs de l'état perçu
            - Choisir l'action à réaliser, la stocker
            - Appliquer l'action choisie au monde
            - Si l'état atteint est terminal : break
      - Percevoir le monde, le stocker
      - Récupérer la récompense sur le monde actuel, la stocker 
      
      - Réaliser une phase d'apprentissage à partir des informations conservées
      - Modifier si nécessaire les paramètres
- Sauvegarder dans un fichier des qualités
- Afficher un score (ou autre) montrant à quel point l'apprentissage a été concluant 

Pendant la phase de développement, l'option -g (pour GCC et Clang au moins) permet d'intégrer dans l'exécutable de nombreuses informations utiles aux outils comme gdb et Valgrind.

Un seul appel à malloc (ou apparentés) par ligne permet d'identifier facilement l'allocation qui pose problème lorsqu'une fuite de mémoire ou une erreur de lecture/écriture est détectée.

Une seule définition de variable par ligne permet d'identifier facilement quelle variable pose problème lorsqu'une variable non initialisée est utilisée en lecture.

• La commande Linux time permet de mesurer le temps d'exécution d'une commande en ligne de commande.

time ./a.out
time ls -al

• à l'intérieur du code C, insérer des affichages du temps passé. On peut s'inspirer du code suivant (src : koor.fr)

#include <stdio.h>
#include <time.h>

int main( int argc, char * argv[] ) {

  clock_t begin = clock();

  // Do something
  // sleep( 2 );    // Wait 2 seconds, but no ticks are consumed
  int i;
  for( i=0; i<1000000000; i++ ) {

  }

  clock_t end = clock();
  unsigned long millis = (end -  begin) * 1000 / CLOCKS_PER_SEC;
  printf( "Finished in %ld ms\n", millis );  

  return 0;
}

Les profileurs permettent de mesurer le temps passé dans chaque fonction du programme. Ils ont en général pour vocation de permettre de détecter, sans faire d'étude théorique, les portions du programme qui nécessiteraient des optimisations (mémoire ou temps). Ainsi, une fonction déjà optimisée peut mériter des optimisations plus avancées, voire une remise en cause de son principe, parce qu'elle est fréquemment appelée, alors qu'une autre fonction, peu appelée pourra être laissée un peu « bâclée ».

Il est à noter que la qualité des informations apportées par les profileurs est fortement liée à la qualité et au « réalisme » des instances sur lesquelles le programme est exécuté. Le but d'une étude de profilage est souvent de se placer soit dans le pire des cas (de façon à se rapprocher expérimentalement d'un temps garanti, très important en particulier dans le 'temps réel'), soit dans les cas qui seront les plus fréquents en production (ou un subtil mélange de ces deux situations).

Il existe deux grandes sortes de profileurs :

• ceux qui mesurent le temps mis en secondes sur une certaine machine, avec toutes ses caractéristiques particulières (son processeur, sa mémoire, sa carte graphique, …, les tâches qui sont lancées en même temps, etc),
• ceux qui s’exécutent sur une machine virtuelle, et où les unités de mesure sont plutôt, le nombre d'opérations effectuées, chaque opération possédant un coût. Le défaut majeur de ce type de profileur est la lenteur (de assez lent à … très très lent), son avantage est, par construction, sa quasi indépendance au matériel (quasi, car si le coûts réels des opérations sont relatifs au matériel).

Sous Linux, la première famille est représentée par gprof et la seconde par callgrind qui est un module de valgrind (dont vous n'avez pour l'instant utilisé que le module par défaut memcheck), que l'on utilise conjointement avec le visualiseur kcachegrind.

gprof (tutoriel gprof) est d'accès beaucoup plus aisé que kcachegrind (documentation cachegrind et documentation kcachegring, je ne connais pas de tutoriel particulièrement pertinent, vous pouvez en choisir un 'au hasard', il vous permettra à tout le moins de commencer à travailler si c'est l'outil que vous choisissez).