L'effet d'horizon

Les recommandations : profondeurs $1$ et $2$ retiennent $A$ (valeur $8$) ; profondeurs $3$ et $4$ retiennent $B$ (valeur $4$). Les deux réponses sont opposées, et rien dans les deux premières lignes ne l'annonce.

Le mécanisme. L'heuristique est appelée sur les positions du dernier niveau exploré, et elle les juge telles quelles. Le coup $A$ mène à des positions que l'heuristique trouve excellentes — un avantage matériel, mettons — mais où l'adversaire dispose, un demi-coup plus loin, d'une réplique qui renverse tout. À profondeur $2$, cette réplique est derrière l'horizon : le programme ne la voit pas, et il compte un avantage qui n'existe pas.

Ce qu'il faut en conclure, et ce qu'il ne faut pas.

• Il ne faut pas conclure que la profondeur $3$ dit la vérité. Elle a seulement un horizon plus lointain ; une profondeur $5$ pourrait renverser à nouveau. La valeur $4$ n'est pas la valeur du jeu, c'est la valeur du jeu vu à trois demi-coups.
• Il faut en conclure que la valeur rendue n'a de sens qu'associée à sa profondeur, et qu'une comparaison entre deux profondeurs différentes n'a aucun sens.

La parade classique est la recherche de quiescence : au lieu d'appeler l'heuristique à profondeur $0$, on prolonge tant que la position est « agitée » — tant qu'il reste des prises, des échecs, des menaces immédiates — et l'on n'évalue qu'une position calme. Cela ne supprime pas l'horizon, cela le déplace là où l'heuristique est fiable.

Et la relation avec alpha-bêta. L'élagage ne crée pas cet effet et ne l'atténue pas : à profondeur fixée il rend exactement la valeur de minimax, y compris quand celle-ci est trompeuse. Il agit ailleurs — il permet d'aller plus profond dans le même temps, donc de repousser l'horizon. C'est la seule manière connue de corriger un effet d'horizon : voir plus loin.