14
Minimax, Alpha-Bêta et heuristiques associées
7
4
7
7
8
4
10
8
7
11
10
5
FIGURE 2. 1 - Un exemple d'arbre Minimax évalué.
joueurs. Il concerne les jeux à somme nulle, c'est à dire dont la somme des gains des
deux joueurs est constante, et à information complète (les deux joueurs connaissent toute
la position).
On rappelle qu'une fonction d'évaluation prend en entrée une position dans un jeu et
donne en sortie une évaluation numérique pour cette position. L'évaluation est d'autant
plus élevée que la position est bonne pour le joueur.
Si une fonction d'évaluation est parfaite, il est inutile d'essayer de prévoir plusieurs
coups de suite. To utefois, pour les jeux un peu complexes comme les É checs, on ne
connaît pas de fonction d'évaluation parfaite. Un programme est amélioré si à partir d'une
bonne fonction d'évaluation il prévoit les conséquences de ses coups sur plusieurs coups
de suite.
L'hypothèse fondamentale du Minimax est que l'adversaire utilise la même fonction
d'évaluation que le programme.
Notre but est de trouver le coup qui maximise la fonction d'évaluation, alors que le but
de l'adversaire est de choisir le coup qui minimise la fonction d'évaluation. Or les deux
adversaires jouent chacun leur tour et en général c'est le joueur ami qui joue en premier
puisqu'on cherche le meilleur coup à jouer pour le joueur ami. On va donc choisir les
coups qui maximisent l'évaluation lorsque c'est au joueur ami de jouer et les coups qui
minimisent l'évaluation lorsque c'est au joueur ennemi de jouer.
On représente habituellement un arbre Minimax avec des rectangles pour les noeuds
Max et des ronds pour les noeuds Min. Les feuilles correspondent aux positions évaluées.
Minimax, Alpha-Bêta et heuristiques associées
7
4
7
7
8
4
10
8
7
11
10
5
FIGURE 2. 1 - Un exemple d'arbre Minimax évalué.
joueurs. Il concerne les jeux à somme nulle, c'est à dire dont la somme des gains des
deux joueurs est constante, et à information complète (les deux joueurs connaissent toute
la position).
On rappelle qu'une fonction d'évaluation prend en entrée une position dans un jeu et
donne en sortie une évaluation numérique pour cette position. L'évaluation est d'autant
plus élevée que la position est bonne pour le joueur.
Si une fonction d'évaluation est parfaite, il est inutile d'essayer de prévoir plusieurs
coups de suite. To utefois, pour les jeux un peu complexes comme les É checs, on ne
connaît pas de fonction d'évaluation parfaite. Un programme est amélioré si à partir d'une
bonne fonction d'évaluation il prévoit les conséquences de ses coups sur plusieurs coups
de suite.
L'hypothèse fondamentale du Minimax est que l'adversaire utilise la même fonction
d'évaluation que le programme.
Notre but est de trouver le coup qui maximise la fonction d'évaluation, alors que le but
de l'adversaire est de choisir le coup qui minimise la fonction d'évaluation. Or les deux
adversaires jouent chacun leur tour et en général c'est le joueur ami qui joue en premier
puisqu'on cherche le meilleur coup à jouer pour le joueur ami. On va donc choisir les
coups qui maximisent l'évaluation lorsque c'est au joueur ami de jouer et les coups qui
minimisent l'évaluation lorsque c'est au joueur ennemi de jouer.
On représente habituellement un arbre Minimax avec des rectangles pour les noeuds
Max et des ronds pour les noeuds Min. Les feuilles correspondent aux positions évaluées.