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

modifier

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

modifier

Exemple désavantageant un humain

modifier
Iosif Krikheli
abcdefgh
8
Fou blanc sur case noire f8
Tour noire sur case noire a7
Fou noir sur case blanche b7
Cavalier noir sur case blanche h7
Pion noir sur case noire f6
Tour noire sur case blanche g6
Pion noir sur case blanche h5
Pion blanc sur case noire b4
Roi noir sur case noire a3
Pion blanc sur case noire c3
Tour blanche sur case noire e3
Pion noir sur case blanche a2
Cavalier blanc sur case noire b2
Cavalier blanc sur case noire a1
Roi blanc sur case noire c1
Cavalier noir sur case blanche f1
8
77
66
55
44
33
22
11
abcdefgh
Trait au Blancs : mat en 17 coups.

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].

Exemples désavantageant un ordinateur

modifier

Exemple tactique

modifier
Philippe Boulanger (B) vs. Méphisto (N)
abcdefgh
8
Tour noire sur case blanche a8
Tour noire sur case noire d8
Roi noir sur case blanche g8
Pion noir sur case noire a7
Pion noir sur case blanche b7
Pion noir sur case noire c7
Pion noir sur case blanche f7
Pion noir sur case noire g7
Pion noir sur case blanche h7
Dame blanche sur case noire e5
Cavalier noir sur case blanche h5
Tour blanche sur case blanche e4
Fou noir sur case blanche g4
Fou blanc sur case noire c3
Pion blanc sur case noire g3
Dame noire sur case blanche h3
Pion blanc sur case blanche a2
Pion blanc sur case noire b2
Pion blanc sur case blanche c2
Pion blanc sur case noire f2
Tour blanche sur case noire a1
Roi blanc sur case noire g1
8
77
66
55
44
33
22
11
abcdefgh
19. Tae1 Ff3 ??
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

modifier
Pierre Nolot
abcdefgh
8
Dame noire sur case blanche c8
Cavalier blanc sur case noire d8
Roi noir sur case noire a7
Pion noir sur case blanche d7
Pion noir sur case blanche c6
Pion blanc sur case noire d6
Pion noir sur case blanche b5
Pion blanc sur case noire c5
Fou blanc sur case noire g5
Pion noir sur case blanche a4
Pion blanc sur case noire b4
Pion blanc sur case noire a3
Roi blanc sur case noire e3
8
77
66
55
44
33
22
11
abcdefgh
Les Blancs jouent et gagnent.

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.[réf. nécessaire]

Nouvelle génération de programmes

modifier

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[réf. nécessaire].

Notes et références

modifier
  1. a b et c 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.
  2. « Stockfish 12 », sur Stockfish Blog (consulté le )

Voir aussi

modifier

Bibliographie

modifier

Articles connexes

modifier