Effet d'horizon
En informatique, et plus précisément en intelligence artificielle, l'effet d'horizon est un phénomène se produisant dans l'exploration d'arbres de décision lorsque ceux-ci, comme c'est le cas pour de nombreux jeux tels que les échecs ou le go, sont trop vastes pour être parcourus en entier par la méthode dite de « force brute ».
Description
Aux échecs, les méthodes usuelles d'exploration de arbres de décision par les programmes d'échecs définissent une profondeur maximale (qui peut être variable, mais est le plus souvent bien inférieure à la profondeur de l'arbre entier), et produisent des résultats médiocres, voire catastrophiques, s'il se cache un phénomène important au-delà du dernier choix exploré par l'algorithme, et remettant en question celui-ci.
Un équivalent humain de ce phénomène serait un joueur d'échecs médiocre qui n'envisagerait pas que son adversaire puisse sacrifier une pièce importante, les conséquences positionnelles plus lointaines de cette manœuvre lui demandant de calculer trop de coups à l'avance.
L'« effet d'horizon » peut être atténué en étendant la profondeur de recherche tant que la position n'est pas « tranquille », c-à -d., aux échecs, tant que subsiste une possibilité de capture immédiate de pièce. Mais, comme le montre l'exemple plus bas, cette stratégie de recherche n'est pas toujours efficace ; pour des jeux tels que le go, elle est même totalement vouée à l'échec, le nombre de combinaisons de coups intermédiaires possibles à tout instant (les menaces de ko) étant astronomique.
Exemples aux Ă©checs
Exemple désavantageant un humain
| a | b | c | d | e | f | g | h | ||
| 8 |              | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
La position suivante est un problème de mat en 17 coups (qui sont tous des échecs au roi). Un bon logiciel d'échecs (par exemple Stockfish) en trouve la solution en moins d'une seconde alors qu'un joueur humain même fort éprouvera beaucoup de difficulté à la trouver.
En effet il y a peu de possibilités à chaque coup qui sont des échecs, donc un logiciel peut facilement tous les essayer à une profondeur élevée, mais un humain aura du mal à se représenter les conséquences de chacun de ses coups[1].
Exemple tactique
| a | b | c | d | e | f | g | h | ||
| 8 |      | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
20. De8+! Txe8
21. Txe8+ Txe8
22. Txe8 mat.
Si aux échecs, un ordinateur, n'explorant qu'une profondeur de six coups, détermine que la dame est perdue au sixième coup et qu'il a la possibilité de sacrifier un cavalier, ce sacrifice fait que la perte de la dame n'aura lieu qu'au huitième coup ; le programme ne se « rend pas compte » qu'il n'a fait que repousser le problème, et qu'en jouant ainsi sa perte est plus grande encore : l'effet d'horizon amène ainsi une dégradation de la position qui peut devenir très grave si la perte initiale était supportable, mais que les sacrifices intermédiaires, chacun de moindre valeur, sont nombreux.
Un exemple est fourni par la partie suivante, jouée en 1982 entre le physicien Philippe Boulanger (blanc) et le logiciel Mephisto (noir).
La position des Blancs est très désavantageuse (Les Blancs ont un cavalier et un pion de moins, et leur roi est exposé à une menace de mat en deux coups, parée uniquement en donnant du matériel), et jouent Tae1 en désespoir de cause. Les noirs répondent alors Ff3 qui semble menacer d'un mat imparable au coup suivant par Dg2. Le logiciel n'a en fait pas vu l'enchaînement par les Blancs des deux sacrifices consécutifs de la dame et de la tour en e8 (De8! puis Txe8 deux fois de suite), qui lui permettent de remporter la partie grâce à un mat du couloir.
Le logiciel (limité en 1982 par son hardware par rapport aux versions plus modernes), n'ayant pas vu au-delà des deux sacrifices, n'a donc pas défendu[1].
Exemple stratégique
| a | b | c | d | e | f | g | h | ||
| 8 | | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
Dans la position suivante, les Blancs peuvent gagner en capturant le pion noir en d7 avec leur cavalier, puis en avançant leur propre pion d6 pour l'emmener à la promotion.
Pour cela il faut amener le roi blanc en e7 (sans intercepter la diagonale du fou), puis amener le fou en f8 pour empêcher la sortie de la dame après le départ du cavalier de d8. Le cavalier peut alors aller prendre le pion d7 et les blancs peuvent assurer la promotion du pion « d ».
Un joueur d'échecs de club trouve la solution relativement facilement, tandis qu'un logiciel comme Stockfish configuré par défaut avec une profondeur de calcul restreinte en est incapable, car l'avantage positionnel n'apparaît qu'après plus de 10 coups, sans qu'aucun ne lui paraisse meilleur qu'un autre dans l'intervalle. Un humain entraîné est quant à lui capable de concevoir un plan à long terme et de sélectionner les coups en conséquence[1].
En 2020, les programmes d'échecs comme Stockfish 12 sont développés avec des algorithmes nouveaux ainsi que l'apprentissage profond (deep learning), combiné à une méthode appelée Monte-Carlo (comme le programme AlphaZero)[2] ; ainsi, la position ci-contre est estimée gagnante au 40e demi-coup et annoncée mat en 31 coups au 86e demi-coup.
Nouvelle génération de programmes
Le programme AlphaZero conçu par la société DeepMind fonctionne grâce à d'autres algorithmes que l'exploration d'un arbre de coups et utilise en particulier l'apprentissage profond combiné à une méthode de Monte-Carlo. Cette différence de conception lui permet de résoudre des situations pour lesquels des logiciels tels que Stockfish sont incapables de trouver le bon coup.
Notes et références
- Pierre Nolot, « Les échecs électroniques : histoire d’une confrontation entre l’humain et la machine », sur Interstices, (consulté le ). L'article présente également la solution du problème.
- « Stockfish 12 », sur Stockfish Blog (consulté le )
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Horizon effect » (voir la liste des auteurs).
Voir aussi
Bibliographie
- Stuart Russell et Peter Norvig, Intelligence artificielle, Pearson Éducation, , page 174.
Articles connexes
- Profondeur (Ă©checs)
- Brouillard de guerre
- Recherche arborescente Monte-Carlo
- Anti-computer tactics (en)