MinMax et AlphaBeta (TD)

vendredi 10 avril 2020
par  Emmanuel Adam
popularité : 7%

Exercice MinMax

Soit un jeu dans lequel deux joueurs ont le choix entre trois possibilités d’actions à chaque étape du jeu.
Il y a : le déplacement à gauche (g), le déplacement devant au centre (c), ou lr déplacement à droite (d).

Un des joueurs est IA, une machine utilisant le principe du MiniMax qui se base sur le fait q’un joueur tente de minimiser le gain maximum de l’adversaire.

A partir d’une situation donnée, un arbre des situations futures possibles est généré sur les deux coups à venir.
IA a évalué les feuilles de cet arbre.

arbre de jeu pour le TD minimax

En supposant que l’Humain joue toujours le coup parfait, c’est-à-dire le coup minimisant le gain pour l’IA, quelle est la meilleure action possible pour l’IA à partir de la situation initiale (au sommet de l’arbre ?).

solution

L’humain choisit l’action amenant au minimum de points à l’IA, donc il choisira dans le premier cas l’action g menant à 3 points, dans le second cas l’action c menant à 2 points et dans le dernier cas l’action g menant à 1 point.
L’IA sachant cela va donc effectuer l’action g garantissant un minimum de 3 points...

Exercice Alpha-Beta

Pour un jeu à somme nulle quelconque, vous utilisez l’algorithme alpha-beta pour programmer l’IA de la machine.

Supposons l’arbre des états suivant :

arbre de jeu pour le TD Alpha-Beta
  • Donnez les valeurs des nœuds (a) à (p) qui correspondent aux actions d’élagage par l’algorithme alpha-beta.
    Les valeurs sont entières, positives ou nulle.

solution

On va affecter des valeurs entières aux noeuds feuilles en commençant par 0.

  • on pose a = 0, ce qui entraîne N21 = 0, puis b = 1, ce qui entraîne N21 = 1 (car N21 est un noeud MAX).
    Il n’y a plus de feuilles dans la branche, on remonte.
  • N2 possède alors la valeur 1. Comme N2 est un noeud MIN, l’IA cherche maintenant sous N2 des valeurs plus petites que 1.
  • si c=2, l’IA reporte dans N22 la valeur 2 et ne va pas plus loin car il est inutile de chercher une valeur supérieure à 2 (N22 est un noeud MAX) vu que le noeud précédent cherche lui une valeur inférieur à 1...
    La branche menant à d est donc élaguée.
  • Il n’y a plus de branche sous N2, on remonte et N1 possède alors la valeur 1.
    Le parcours de l’arbre se poursuit en cherchant une valeur plus grande que 1.

On poursuivant cette logique, on trouve les affectations suivantes :
a=0, b=1, c=2, e=0, f=1, g=2, j=2, l=0, m=0, n=0

Les autres noeuds se pas valués. AlphaBeta permet donc un gain de calcul de 6 noeuds sur 16 dans cet exemple. En gros, 30% du calcul est économisé.

Tic-Tac-Toe (morpion)

Dans le jeu du morpion (ou Tic-Tac-Toe en anglais), deux joueurs s’affrontent à tour de rôle sur une grille de 3x3.
Une joueur place 1 croix, l’autre un cercle.
Le premier des deux qui a aligné 3 de ses jetons (en colonne, ligne ou diagonale) a gagné.

  • Supposons le cas suivant où l’IA prend les croix X et l’humain les ronds O :
X . .
O O X
X O .
  • Supposons que l’IA ne réfléchisse qu’à une profondeur de 2 (elle estime juste le coup suivant de l’adversaire pour sélectionner son action).
  • Sachant que la valuation des coups est la suivante :
    • 3 jetons alignés = +100 pour le joueur qui les a alignés et - 100 pour l’adversaire
    • 2 jetons alignés et une case vide permettant un alignement ensuite = +50 pour le joueur qui les a alignés et - 50 pour l’adversaire
    • 1 jeton seul sur une ligne,colonne ou diagonale = +10 ou - 10 selon le joueur

Générer l’arbres des futurs possibles à partir de la situation ci-dessus, estimez les feuilles, et donnez la meilleure action à réaliser pour l’IA...

Evaluation dépendante de l’état mix-max

Un évaluation plus « intelligente » devrait prendre en compte le fait que l’on soit dans un état min ou max, c’est-à-dire dans une situation où l’IA doit jouer ensuite, ou non.

Ainsi, un état proposant deux croix alignés (xx., x.x, .xx) avec un jeu à suivre pour l’IA est plus valuée qu’un état proposant deux ronds alignés dans les même conditions..
On peut réécrire les valuations ainsi :

    • 3 jetons alignés = +100 pour le joueur qui les a alignés et - 100 pour l’adversaire
    • 2 jetons alignés et une case vide permettant un alignement ensuite = +50 pour le joueur qui les a alignés et - 50 pour l’adversaire +-10 selon le jeu à venir
    • 1 jeton seul sur une ligne,colonne ou diagonale = +10 ou - 10 selon le joueur +- 5 selon le jeu à venir
  • Supposons le cas suivant où l’IA prend les croix X et l’humain les ronds O :
X . .
O O .
X . .
  • Supposons que l’IA ne réfléchisse qu’à une profondeur de 2 (elle estime juste le coup suivant de l’adversaire pour sélectionner son action).

Générer l’arbres des futurs possibles à partir de la situation ci-dessus, estimez les feuilles, et donnez la meilleure action à réaliser pour l’IA...