2.1 Le Minimax
15
18 16 12 24 9 20 13 6 5
8
4 2
10 11 79 1 05 73 2
FIGURE 2.2 - Un arbre Minimax.
La figure 2. 1 donne un arbre Minimax évalué. La racine de l'arbre est un noeud Max.
On commence par évaluer les noeuds internes au dessus des feuilles puis on remonte les
évaluations dans l'arbre. Le score d'un noeud Min est le minimum des scores de ses fils
et le score d'un noeud Max est le maximum des scores de ses fils. Le score est ce qui
se trouve dans la partie supérieure d'un noeud. La partie inférieure montre l'évaluation
courante du noeud au fur et à mesure d'un parcours en profondeur d'abord de l'arbre en
commençant par les fils les plus à gauche.
Exercice : Quelle est la valeur de la racine de l'arbre de la figure 2.2 en utilisant
l'algorithme Minimax ? Combien de noeuds a-t-on développé et combien d'évaluations
a-t-on effectué ?
On souhaite maintenant implémenter un algorithme Minimax pour le jeu du virus vu
dans le chapitre sur les fonctions d'évaluation.
Exercice : É crire une classe Virus pour le jeu du virus qui permette d'annuler le
dernier coup joué pour arriver à la position. É crire de plus une fonction qui permette
d'évaluer une position lorsqu'il n'y a plus de coups possible pour l'un des joueurs.
Exercice
É crire
les
fonctions
maxi (int depth, Coup &
15
18 16 12 24 9 20 13 6 5
8
4 2
10 11 79 1 05 73 2
FIGURE 2.2 - Un arbre Minimax.
La figure 2. 1 donne un arbre Minimax évalué. La racine de l'arbre est un noeud Max.
On commence par évaluer les noeuds internes au dessus des feuilles puis on remonte les
évaluations dans l'arbre. Le score d'un noeud Min est le minimum des scores de ses fils
et le score d'un noeud Max est le maximum des scores de ses fils. Le score est ce qui
se trouve dans la partie supérieure d'un noeud. La partie inférieure montre l'évaluation
courante du noeud au fur et à mesure d'un parcours en profondeur d'abord de l'arbre en
commençant par les fils les plus à gauche.
Exercice : Quelle est la valeur de la racine de l'arbre de la figure 2.2 en utilisant
l'algorithme Minimax ? Combien de noeuds a-t-on développé et combien d'évaluations
a-t-on effectué ?
On souhaite maintenant implémenter un algorithme Minimax pour le jeu du virus vu
dans le chapitre sur les fonctions d'évaluation.
Exercice : É crire une classe Virus pour le jeu du virus qui permette d'annuler le
dernier coup joué pour arriver à la position. É crire de plus une fonction qui permette
d'évaluer une position lorsqu'il n'y a plus de coups possible pour l'un des joueurs.
Exercice
É crire
les
fonctions
maxi (int depth, Coup &