 |
|
PLAN Liens Contact Livres Glossaire ECO Search Outils FAQ News
ACCUEIL CLUBS BANNIÈRES 
BLOG MUSÉE VIRTUEL ARTICLES CAISSA FORUM
 | |||
 |
|
 Pratique des Échecs - MenuPrat. Échecs PrésentationGrands TournoisNouvelles InternationalesJeu à la penduleJeu par correspondanceHistoire des ÉchecsRéflexions et débatsPrat. Échecs - Forums |
|
|
3o) La Fonction d'Évaluation
Aux échecs, la fonction d'évaluation est forcément approximative, elle ne fait que traduire des principes heuristiques- il n'y a pas de méthode canonique pour calculer cette évaluation. Une simple valeur numérique est utilisée pour résumer plusieurs règles. C'est une voie par laquelle il est possible d'expliquer les principes stratégiques à l'ordinateur. En cherchant à optimiser la valeur de la position, l'ordinateur agit comme s'il comprenait les règles de stratégie. Mais bien sûr ces principes ne permettent pas de discerner la présence d'une combinaison: c'est l'algorithm min-max qui permet à la machine de trouver des combinaisons. Basiquement, la fonction d'évaluation compte le matériel (de part et d'autre) par la somme des pièces en jeu pondérée par les valeurs des types des pièces: par exemple, la Dame vaut 9 pions. Dans certains programmes la fonction attribue au Roi une valeur très, très élevée de façon à signifier que le mat est le facteur le plus important. On peut affiner cette évaluation en ajoutant à cette valeur d'autres valeurs traduisant des considérations positionnelles. Il est important de pouvoir distinguer les positions à matériel égal et dans certaines situations des aspects positionnels peuvent l'emporter sur les aspects matériels. Affiner la fonction d'évaluation est une piste fondamentale pour améliorer les performances des programmes d'échecs. Un aspect facile à calculer est la mobilité: il suffit de compter le nombre de coups générés par le générateur de coups légaux. En fait cette quantité ne reflète pas exactement ce que l'on entend par la mobilité aux échecs puisqu'elle prend en compte tous les coups possibles, y compris ceux qui sont stériles voire ceux qui sont mauvais! - mais cela en donne une approximation. On peut quantifier d'autres aspects positionnels tels que la sécurité du Roi, la domination du centre, la structure de pions, etc. On peut affiner encore cette évaluation en ajoutant ou en supprimant des points en tenant compte de diverses règles, au moyen de lignes conditionnelles du genre: "si le Roi est en échec alors retirer x points". Il est recommandé d'avoir 3 fonctions d'évaluation différentes - une pour l'ouverture, une pour le milieu de partie et une pour la finale - parce que beaucoup de règles stratégiques sont spécifiques aux phases de jeu. Par exemple, dans l'ouverture la fonction va retirer des points si la Dame s'est déplacée, ou si le pion f2/f7 s'est déplacé avant le petit roque. Dans le milieu de partie la fonction va retirer des points si le Roi n'a pas roqué, ou si les Cavaliers et les Fous n'ont jamais été déplacés. Dans la finale la fonction va retirer des points pour les pions arriérés, isolés ou doublés.
4o) L'Effet Horizon
Pour remédier à l'effet horizon il faut faire varier la profondeur en fonction de la (nature de la) position. On dispose d'un certain capital de temps d'analyse et il s'agit de le répartir de la façon la plus utile parmi toutes les positions à analyser. On peut nettement améliorer une recherche à profondeur p donnée si on effectue un algorithme à profondeur variable qui est seulement en moyenne égale à p. Si un coup paraît mauvais (par exemple en cas de perte de matériel) alors il y a de fortes chances pour que ce coup soit vraiment mauvais et il est inutile de le privilégier dans l'analyse alors que si le coup parait intéressant il y a intérêt à poursuivre pour déterminer s'il l'est vraiment, pour ne pas le jouer inconsidérément. Pour reconnaître un coup mauvais on peut utiliser l'heuristique du coup nul: si juste après avoir joué un coup on joue un second coup comme si on avait encore le trait, et si ce coup n'est pas avantageux alors le premier coup peut être considéré comme mauvais. Pour définir une profondeur en moyenne égale à p, l'algorithme Search Extension associe au départ de chaque branche la valeur 10 fois p et diminue cette valeur à la descente d'un niveau dans l'arbre d'une quantité qui est petite si le coup joué est intéressant, ainsi les coups intéressants bénéficient d'une plus grande profondeur d'analyse. La recherche en profondeur s'arrête sur chaque branche quand cette valeur est nulle (ou négative). Au-delà des coups mauvais ou bons ou intéressants, l'effet horizon est en cause dans les positions instables, i.e. celles où il y a prise, échec ou promotion. Par exemple, considérons le cas où on fait tourner l'algorithme minimax avec une profondeur de 1. Le programme va choisir un coup qui permet de gagner une pièce adverse, même si c'est en prenant avec la Dame un Cavalier protégé, parce que la riposte de l'adversaire se situera au delà de son champ d'analyse. Si on le fait tourner à une plus grande profondeur ce problème se posera encore à la frontière de l'horizon: il verra à cet endroit une prise sans voir qu'elle peut être compensée voire largement compensée. Il verra une menace illusoire dans ce qui n'est qu'un échange banal parce qu'il ne verra que la moitié de cet échange et cela va peser sur les calculs même si cela se joue dans les profondeurs des calculs de variantes. Par exemple si au terme d'une variante il voit qu'il peut prendre la Dame adverse avec sa propre Dame mais qu'il ne voit pas que sa Dame sera reprise un coup plus tard il va croire avoir réalisé une combinaison et cette variante sera surévaluée sans raison. Ce problème est spécifique aux prises: si la profondeur d'analyse est impaire l'algorithme ne tient pas compte de la riposte de l'adversaire et surévalue certains coups, tandis que lorsque la profondeur est paire il ne voit pas sa propre riposte aux coups de l'adversaire et surévalue certains coups de l'adversaire. Or le problème est qu'il faut bien s'arrêter à une profondeur déterminée (paire ou impaire). Un écueil un peu plus subtil se présente lorsque l'ordinateur est en proie à une menace inéluctable (comme la perte de sa Dame). L'effet horizon va lui donner l'illusion d'une parade: tout sacrifice permettant de retarder l'échéance de la menace inéluctable lui donnera l'illusion de le débarrasser de la menace simplement parce qu'elle la situera au-delà de son horizon, or ces sacrifices ne sont pas des réfutations et alourdissent inutilement le bilan. Or si sur cette position l'algorithme alpha-bêta est poussé plus loin, le programme perçoit le bilan global et ne joue plus les coups de retardement. La solution est donc de reconnaître ce type de position pour y investir plus de temps d'analyse. La solution est donc de poursuivre la recherche de base par une recherche d'équilibre. Pour cela on crée une deuxième fonction d'évaluation comme celle qui évalue la position, mais qui celle-ci évalue la nature de la position. Cette deuxième évaluation fournit le niveau de confiance que le programme peut avoir en l'évaluation de la position. L'ordinateur poursuit donc l'analyse dans les cas où la position n'a pas une évaluation fiable pour atteindre des positions dont l'évaluation est fiable et qui permettent de modifier l'évaluation de la position concernée. Les positions stables ont une évaluation fiable, et on n'a pas besoin de pousser loin l'analyse sur elles, tandis que les positions instables doivent être analysées en profondeur jusqu'à atteindre des positions stables qui permettent de changer l'évaluation de notre position de façon fiable. © Antoine Bruneau - Avril 2008 |
|||||
|
[Cette page a été conçue par Antoine Bruneau - All data is copyrighted by: © Antoine Bruneau & Chess-Theory] ************ Si vous aimez la musique, vous pouvez choisir maintenant une agréable Musique d'ambiance:
*** POUR NAVIGUER AGRÉABLEMENT SUR CE SITE :
*** POUR DÉCOUVRIR QUI NOUS SOMMES:
******** ©-«Chess-Theory.com»-2004-2008 ******** |
 |
«CRYSTAL PHOENIX GALLERY- 
