AA2024

Jean-Jacques BOURDIN

E-mail :
jj NOSPAM @ up8.edu
(enlever le NO Spam)

Algorithmique Avancée 2024

IA

  1. Présentation
  2. Constantes et complexité
  3. De la Droite Discrète
  4. Graphes
  5. Compression
  • Modélisation, Illumination, Rendus
    1. 2D/3D
    2. Modélisation
    3. Illumination
    4. Lumière
    5. Rendus, quelques effets
    6. Rendus Expressifs
    7. IA et jeux
      1. Principes
      2. Algorithmes
    8. Projets

    Intelligence Artificielle pour les jeux


    1. Cours de M. Dupont sur les jeux

    2. Bases pour le premier TP jeux

    3. Fonctions utiles pour le premier TP jeux

    1. Quelques définitions

      2. Backtracking

      Principe de base des labyrinthes, dès qu‘on est bloqué on revient à la pris récente intersection.

      Parcours en profondeur

      void afficharbre (arbre a) {
  if (a) {
	afficharbre (a->sg);
	printf("%d %3.2f ", a->num, a->val);
	afficharbre (a->sd);
  }
}

      Parcours en largeur

      Il nécessite de gérer une file d'attente pour mettre en attente les sommets rencontrés. Tous les sommets d‘une même génération seront ensemble dans la file.

    2. Premier exemple : Grille d‘anagrammes

      On peut en trouver sur quelques journaux

      En voici un :

      Grille AnagrammesJournal

      Pour résoudre ce problème il suffit de tester toutes les combinaisons de lettres.

      Le problème est que, le plus souvent, le nombre de cas possibles est tellement grand que le temps d'attente peut être déraisonnable.

    3. Second exemple : Light-Up

      Il s'agit de placer des lumières qui éclairent orthogonalement. Quand un chiffre apparaît sur une case il donne le nomre de lumières sur les quatre cases adjacentes. Exemple de situation de départ :

      Light-upDebut

      Nous regardons les "cas obligés". Par exemple s‘il y a une case à 4 c'est que ses quetre voisins ont une lampe.

      On voit que dès la fin de l‘étape 1 la grille est presque finie.

      Light-up suiteEtape2

      Il ne reste plus qu‘à remplir les nouvelles cases obligatoires puis placer les dernières lampes (il reste si peu de cas possibles...). Light-up finEtape3

    4. Algorithmes pour jeux avec adversaires

      1. Minimax

        Si deux joueurs s'affrontent, on crée un arbre des coups possibles :
        1. la racine est le demi-coup que doit jouer le joueur IA (disons White).
        2. la première génération est la liste de tous les coups jouables par White.
        3. la seconde génération comprend tous les coups jouables par l'adversaire.
        4. la troisième génération est la liste de tous les coups jouables par White.
        5. ...

        Si, pour tous ces coups, une valeur est attibuée (par exemple en comptant le nombre de pièces restantes), il n'est pas difficile de ce rendre compte que le joueur doit choisir le coup de la ligne 2 qui a la valeur la plus grande (le Max).

        Mais son adversaire doit jouer le meilleur coup pour lui-même. Donc à la ligne 3, il choisit ce qui est le moins favorable pour White, la plus petite valeur présente (le Min).

        et ainsi de suite.

      2. Alpha-beta

        Améliore cette technique en élaguant les branches inutiles.

        Exemple

        si à la ligne 2 vous avez un 15.
        quand on trouve un 6 à la ligne 3, ce n'est pas la peine de tout calculer en-dessous de ce 6 puisque toutes les valeurs à trouver seront plus petites que 6 et que de toutes les façons on choisira le 15. C‘est une coupe Beta.

        La coupe Alpha est son pendant symétrique, les signes et la parité des ligne étant inversés.

        Attention, selon l'ordre dans lequel les sommets sont donnés dans l'arbre, cet algorithme peut très bien ne rien élager.

      3. MCTS (Monte-Carlo Tree Search)

        Un peu plus complexe à installer, il s'agit ici de tirer au hasard des parties et de choisir le chemin le plus efficace. Plus on peut lancer de parties simultanées et plus les résultats sont intéressants.

      Dernière mise à jour : 25/11/2024 (17h)