18
Minimax, Alpha-Bêta et heur ist iques associées
2.4 Mémorisation de la variation principale
La variation principale d'une recherche Alpha-Bêta est la suite des meilleurs coups
pour les deux adversaires. Elle permet de voir ce que le programme à prévu. Elle commence par le meilleur coup pour Max suivi de la meilleure réponse pour Min et ainsi de
suite jusqu'au dernier coup. Le nombre de coups de la variation principale est la profondeur de la recherche effectuée.
Exercice: Quelle est la variation principale de l'arbre 2.2 ?
Exercice: Modifier l'algorithme Alpha-Bêta pour qu'il mémorise la variation principale.
La variation principale peut être utilisée pour récupérer le meilleur coup : c'est le coup
en tête de liste.
2.5 L' Effet d' horizon et la recherche de quiescence
Il y a deux inconvénients au fait qu'on doive fixer une profondeur maximum. Le premier étant que le programme ne peut prévoir les effets d'un coup à une profondeur dépassant la profondeur maximum. Le second est que cela introduit des effets non désirés dans
les choix du programme : l'horizon étant défini comme la profondeur maximum de la
recherche, le programme fera toutes les menaces qu 'il peut et qui sont pourtant inutiles,
voire néfastes, pour repousser au-delà de son horizon un événement qui lui est défavorable. C'est ce qu'on appelle l'effet d'horizon : le programme repousse les événements
défavorables au-delà de son horizon. Par exemple aux É checs, si une dame est de toutes
façons prise mais que la prise peut être repoussée au delà de l'horizon en sacrifiant un cavalier, le programme choisira de sacrifier inutilement son cavalier pour repousser la prise
de la dame au delà de son horizon.
Une parade possible à l'effet d'horizon est d'utiliser une méta-fonction d'évaluation
qui n'évalue pas la position mais plutôt qui évalue le type de la position. Cette métafonction d'évaluation évalue si une position est stable (aux É checs, essentiellement s'il
reste des pièces en prise). Elle est utilisée pour savoir si une position est évaluable ou si
on doit continuer à la développer. Une position stable a une évaluation en laquelle on peut
avoir confiance alors qu' une position instable n'a pas une évaluation fiable.
La recherche de quiescence consiste à continuer à chercher les positions instables tant
qu'on ne trouve pas de position stable à évaluer. Lors d'une recherche de quiescence,
on restreint les coups à explorer pour éviter des recherches trop coûteuses. Les coups de
quiescence couramment utilisés dans les programmes d' É checs sont les coups de capture
et les coups de promotion (sauf quand le Roi est en échec).
Exercice : É crire une fonction list coupsQuiescence (char
Minimax, Alpha-Bêta et heur ist iques associées
2.4 Mémorisation de la variation principale
La variation principale d'une recherche Alpha-Bêta est la suite des meilleurs coups
pour les deux adversaires. Elle permet de voir ce que le programme à prévu. Elle commence par le meilleur coup pour Max suivi de la meilleure réponse pour Min et ainsi de
suite jusqu'au dernier coup. Le nombre de coups de la variation principale est la profondeur de la recherche effectuée.
Exercice: Quelle est la variation principale de l'arbre 2.2 ?
Exercice: Modifier l'algorithme Alpha-Bêta pour qu'il mémorise la variation principale.
La variation principale peut être utilisée pour récupérer le meilleur coup : c'est le coup
en tête de liste.
2.5 L' Effet d' horizon et la recherche de quiescence
Il y a deux inconvénients au fait qu'on doive fixer une profondeur maximum. Le premier étant que le programme ne peut prévoir les effets d'un coup à une profondeur dépassant la profondeur maximum. Le second est que cela introduit des effets non désirés dans
les choix du programme : l'horizon étant défini comme la profondeur maximum de la
recherche, le programme fera toutes les menaces qu 'il peut et qui sont pourtant inutiles,
voire néfastes, pour repousser au-delà de son horizon un événement qui lui est défavorable. C'est ce qu'on appelle l'effet d'horizon : le programme repousse les événements
défavorables au-delà de son horizon. Par exemple aux É checs, si une dame est de toutes
façons prise mais que la prise peut être repoussée au delà de l'horizon en sacrifiant un cavalier, le programme choisira de sacrifier inutilement son cavalier pour repousser la prise
de la dame au delà de son horizon.
Une parade possible à l'effet d'horizon est d'utiliser une méta-fonction d'évaluation
qui n'évalue pas la position mais plutôt qui évalue le type de la position. Cette métafonction d'évaluation évalue si une position est stable (aux É checs, essentiellement s'il
reste des pièces en prise). Elle est utilisée pour savoir si une position est évaluable ou si
on doit continuer à la développer. Une position stable a une évaluation en laquelle on peut
avoir confiance alors qu' une position instable n'a pas une évaluation fiable.
La recherche de quiescence consiste à continuer à chercher les positions instables tant
qu'on ne trouve pas de position stable à évaluer. Lors d'une recherche de quiescence,
on restreint les coups à explorer pour éviter des recherches trop coûteuses. Les coups de
quiescence couramment utilisés dans les programmes d' É checs sont les coups de capture
et les coups de promotion (sauf quand le Roi est en échec).
Exercice : É crire une fonction list