Min-max et alpha-bêta
Choisir un coup dans un jeu à deux joueurs à somme nulle : arbre de jeu, fonction d'évaluation, profondeur limitée, remontée min-max, élagage alpha-bêta et effet de l'ordre des coups.
- 22 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
Quelques cartes du deck
Algorithme min-max : de quoi s'agit-il ?
Voir la réponse
Algorithme qui choisit le coup en supposant que l'adversaire répond toujours au mieux pour lui : on remonte le maximum aux nœuds du joueur et le minimum aux nœuds de l'adversaire.
Racine MAX avec trois nœuds MIN de feuilles (3, 5), (2, 9) et (0, 7) : les nœuds MIN valent 3, 2 et 0, la racine vaut 3, et on joue le premier coup.
La racine est un nœud MAX avec trois fils MIN, de feuilles (4, 7, 6), (5, 1) et (8, 9, 2). Quel coup min-max désigne-t-il ?
- Le premier, de valeur 4
- Le troisième, car il contient la feuille 9
- Le deuxième, car sa première feuille vaut 5
- Le troisième, de valeur 8, sa première feuille
Voir la réponse
Le premier, de valeur 4
Chaque nœud MIN prend son minimum : 4, 1 et 2. La racine MAX prend le plus grand de ces minima, 4, donc le premier coup. Regarder la plus belle feuille oublie que l'adversaire choisit.
Alpha-bêta coupe le plus quand les … sont examinés en premier ; dans le meilleur cas, il n'évalue que de l'ordre de la … du nombre de feuilles de min-max.
Voir la réponse
Alpha-bêta coupe le plus quand les meilleurs coups sont examinés en premier ; dans le meilleur cas, il n'évalue que de l'ordre de la racine carrée du nombre de feuilles de min-max.
Un bon ordre fixe vite de bonnes bornes. Dans le meilleur cas, environ b puissance d/2 feuilles au lieu de b puissance d, ce qui permet de chercher environ deux fois plus profond dans le même temps.
Élagage alpha-bêta : de quoi s'agit-il ?
Voir la réponse
Amélioration du min-max qui abandonne l'examen d'une branche dès qu'elle ne peut plus changer la valeur de la racine ; le résultat est identique, avec moins de feuilles évaluées.
On tient deux bornes : alpha, le meilleur gain déjà garanti à MAX, et bêta, le meilleur déjà garanti à MIN. Dès que bêta ≤ alpha, le reste de la branche est inutile.