name: inverse layout: true class: center, middle, inverse --- # Introduction IA - CM 2 ## Inès de Courchelle ## 2023-2024  --- layout: false # Lets go ## Objectifs - Étudier l'algorithme min max - Mettre en place l'algorithme min max --- # Min Max ## Quand ? Utilisé dans la théorie des jeux pour prendre des décisions dans des jeux à deux joueurs (echec, dames, morpions ...) ## Objectif Trouver la meilleur stratégie pour un joueur donné, en supposant que l'adversaire joue de maniere optimale. ## Comment ? Via des arbres ... --- # Min Max ## Stratégie de min max - le joueur qui commence (joueur MAX) : cherche à trouver parmi toutes les situations à sa disposition, une situation qui lui permet de maximiser ses gains - L'autre joueur (jouer MIN) : doit trouver, à partir de toutes les situations qui conduisent à la victoire du premier joueur, la situation qui minimise les gains de ce joueur --- # Min max ## Le concept - Alternative aux algorithmes exhaustifs lorsque les chemins sont potentiellement infinis (ou trop longs) - Se fixer une profondeur maximum (nombre de coups à évaluer) - Construire un arbre de jeu alterné jusqu'à cette profondeur - Évaluer la qualité des feuilles (distance à la victoire du joueur qui commence) - Remonter la valeur vers les noeuds pères - comme un Max des fils si joueur A (celui qui commence) - comme un Min des fils sinon (joueur B) - Utiliser l'arbre de jeu pour établir la stratégie du joueur A --- # Scénario idéal ## Arbre complet À partir d'une position donnée, il existe une arborescence de coups jusqu’à la victoire (V), au nul (N) ou à la défaite (D). (cercle représente le joueur MAX, carré représente le joueur MIN) <img src="img/arbreEx.png" width=400> --- # Scénario réel ## L’arbre incomplet avec une profondeur limitée - En réalité, il est impossible de développer entièrement l’arbre du jeu et de dire si une feuille correspond à une position gagnante ou à une position perdante (à cause d’une complexité combinatoire) - Dans ce cas, il est nécessaire de disposer d’une fonction d’évaluation (heuristique), capable d’estimer le plus précisément possible la qualité d’une position. - on définit alors une profondeur de recherche (horizon de l’IA) - les feuilles de l’arbre sont associées à une valeur numérique donnée par cette fonction d’évaluation. --- # MinMax ## Principe Fonction récursive sur la profondeur ## Paramètres : - nœud : configuration actuelle du plateau du jeu - profondeur : profondeur actuelle - evalMax : si vrai alors joueur MAX sinon joueur MIN ## Retour : valeur du nœud ## Conditions d’arrêt - fin de jeu (victoire, nul ou défaite) - ou profondeur = 0 (on atteint l’horizon d’IA) --- # Algo min max ## Fonction générique ```c FONCTION MinMax(noeud : PlateauJeu, profondeur : Entier, evalMax : Booleen) : Entier DEBUT SI profondeur = 0 ou victoire(noeud) ou defaite(noeud) ou nul(noeud) ALORS Retourner evaluation(noeud) SINON /* si on est sur un noeud interne */ SI evalMax Alors retourner MinMAx(f,profondeur-1,FAUX) SINON /* on évalue le joueur adverse */ Retourner MinMax(f , profondeur − 1, vrai) FinSi FinSi Fin ``` --- # Algorithme AlphaBeta ## Princpipe L'élagage Alpha-Beta est une technique couramment utilisée pour améliorer l'efficacité de Minimax. Elle permet de réduire le nombre de nœuds évalués en éliminant les branches de l'arbre qui ne sont pas pertinentes pour la décision actuelle.