Chapitre 2
Minimax, Alpha-Bêta et
heuristiques associées
"La vérité est comme le meilleur coup aux échecs : elle existe, mais il faut la chercher. "
Arturo Perez-Reverte.
Dans ce chapitre nous allons voir des algorithmes de recherche en profondeur d'abord
qui permettent de prévoir le déroulement d'une partie sur plusieurs coups. Un avantage
des algorithmes de recherche en profondeur d'abord est qu' ils sont peu coûteux en mémoire. C'est un avantage important sur les algorithmes en meilleur d'abord ou en largeur
d'abord qui sont limités en pratique sur les problèmes de grande taille par la mémoire disponible. Un autre avantage important des algorithmes de recherche en profondeur d'abord
est qu'ils permettent d'évaluer une position rapidement en réutilisant les informations de
la position précédente qui n'a changé que d'un coup par rapport à la position à évaluer.
L'ordre de recherche des positions permet de connaître les informations sur la position
avant le coup qui a mené à cette position. On peut utiliser les informations de la position
précédente pour recalculer plus rapidement les informations sur la position courante, en
ne calculant que la différence avec la position précédente induite par le coup.
Ce chapitre traite du Minimax, de I' Alpha-Bêta et des heuristiques associées qui le
rendent plus efficace. L' utilisation d'une table de transposition est une optimisation très
importante pour I' Alpha-Bêta qui est traitée dans le chapitre suivant.
2.1 Le Minimax
On se place maintenant dans le cadre des jeux à deux joueurs. L'algorithme Mini max,
ses variantes et améliorations sont utilisés dans de nombreux programmes de jeux à deux
Minimax, Alpha-Bêta et
heuristiques associées
"La vérité est comme le meilleur coup aux échecs : elle existe, mais il faut la chercher. "
Arturo Perez-Reverte.
Dans ce chapitre nous allons voir des algorithmes de recherche en profondeur d'abord
qui permettent de prévoir le déroulement d'une partie sur plusieurs coups. Un avantage
des algorithmes de recherche en profondeur d'abord est qu' ils sont peu coûteux en mémoire. C'est un avantage important sur les algorithmes en meilleur d'abord ou en largeur
d'abord qui sont limités en pratique sur les problèmes de grande taille par la mémoire disponible. Un autre avantage important des algorithmes de recherche en profondeur d'abord
est qu'ils permettent d'évaluer une position rapidement en réutilisant les informations de
la position précédente qui n'a changé que d'un coup par rapport à la position à évaluer.
L'ordre de recherche des positions permet de connaître les informations sur la position
avant le coup qui a mené à cette position. On peut utiliser les informations de la position
précédente pour recalculer plus rapidement les informations sur la position courante, en
ne calculant que la différence avec la position précédente induite par le coup.
Ce chapitre traite du Minimax, de I' Alpha-Bêta et des heuristiques associées qui le
rendent plus efficace. L' utilisation d'une table de transposition est une optimisation très
importante pour I' Alpha-Bêta qui est traitée dans le chapitre suivant.
2.1 Le Minimax
On se place maintenant dans le cadre des jeux à deux joueurs. L'algorithme Mini max,
ses variantes et améliorations sont utilisés dans de nombreux programmes de jeux à deux