Effet Horizon - Horizon effect
L' effet d'horizon , également connu sous le nom de problème d'horizon , est un problème en intelligence artificielle dans lequel, dans de nombreux jeux, le nombre d'états ou de positions possibles est immense et les ordinateurs ne peuvent en rechercher qu'une petite partie, généralement quelques couches dans le arbre de jeu . Ainsi, pour un ordinateur ne cherchant que cinq plis, il est possible qu'il fasse un mouvement préjudiciable, mais l'effet n'est pas visible car l'ordinateur ne recherche pas jusqu'à la profondeur de l'erreur ( c'est -à- dire au-delà de son «horizon»).
Lors de l'évaluation d'un grand arbre de jeu à l' aide de techniques telles que minimax avec élagage alpha-bêta , la profondeur de recherche est limitée pour des raisons de faisabilité. Cependant, l'évaluation d'un arbre partiel peut donner un résultat trompeur. Lorsqu'un changement significatif existe juste au-dessus de l'horizon de la profondeur de recherche, le dispositif de calcul est victime de l'effet d'horizon.
En 1973, Hans Berliner a nommé ce phénomène, que lui et d'autres chercheurs avaient observé, l '«effet d'horizon». Il a divisé l'effet en deux: l'Effet d'Horizon Négatif "a pour résultat de créer des détournements qui retardent inefficacement une conséquence inévitable ou font apparaître une conséquence irréalisable". Pour l'effet d'horizon positif «largement négligé», «le programme s'attaque beaucoup trop tôt à une conséquence qui peut être imposée à un adversaire à loisir, souvent sous une forme plus efficace».
Les algorithmes gourmands ont tendance à souffrir de l'effet d'horizon.
L'effet d'horizon peut être atténué en étendant l'algorithme de recherche avec une recherche de quiescence . Cela donne à l'algorithme de recherche la capacité de regarder au-delà de son horizon pour une certaine classe de coups d'une importance majeure pour l'état du jeu, comme les captures aux échecs .
La réécriture de la fonction d'évaluation pour les nœuds feuilles et / ou l'analyse de plusieurs nœuds résoudront de nombreux problèmes d'effet d'horizon.
Exemple
Par exemple, aux échecs , supposons une situation dans laquelle l'ordinateur ne recherche dans l'arbre de jeu que six plis et à partir de la position actuelle détermine que la reine est perdue dans le sixième pli; et supposons qu'il y ait un mouvement dans la profondeur de recherche où il peut sacrifier une tour, et la perte de la reine est poussée au huitième pli. C'est, bien sûr, un geste pire que de sacrifier la reine car cela conduit à perdre à la fois une reine et une tour. Cependant, comme la perte de la reine a été repoussée à l'horizon de la recherche, elle n'est pas découverte et évaluée par la recherche. Perdre la tour semble être mieux que de perdre la reine, donc le sacrifice est retourné comme la meilleure option alors que retarder le sacrifice de la reine a en fait affaibli la position de l'ordinateur.
Voir également
Les références
- Russell, Stuart J .; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2e éd.), Upper Saddle River, New Jersey: Prentice Hall, p. 174, ISBN 0-13-790395-2
Liens externes
- Effet d'horizon à la programmation d'échecs WIKI (CPW)