 |
|
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 |
|
|
1o) Algorithmes utilisés en programmation de jeux d'échecs
L'arbre de jeu est l'arbre de tous les coups possibles contenant toutes les lignes de jeu possibles depuis la position initiale. Chaque nœud de cet arbre représente une position et toutes les branches issues d'un nœud représentent tous les coups possibles depuis cette position. Il est construit récursivement, avec une profondeur limitée à cause des limites des machines. L'algorithme min-max évalue d'abord la position de chaque feuille de l'arbre. Le principe de base est de chercher le meilleur coup lorsqu'on a le trait en supposant que l'adversaire agira de même. Donc on cherchera toujours le coup qui correspond au maximum des évaluations et on supposera que l' adversaire choisira le coup qui minimise cette évaluation. Supposons que ce soit aux Blancs de jouer. L'algorithme procède des feuilles à la racine, il remonte aux nœuds au-dessus des feuilles et associe le minimum des valeurs des feuilles qui en dépendent si au niveau des feuilles le trait est aux Noirs, ou le maximum si au niveau des feuilles le trait est aux Blancs. On remonte ensuite un étage plus haut de l'arbre et on réitère le même procédé appliqué à l'arbre diminué d'une unité en profondeur dont les feuilles sont ce qui était les nœuds à l'étape précédente. On alterne ainsi, prenant le minimum des valeurs des nœuds, puis le maximum, etc. jusqu'à la racine. L'algorithme alpha-bêta fonctionne comme l'algorithme min-max mais s'abstient d'évaluer certains nœuds lorsque ce n'est pas nécessaire. Il évite de continuer l'analyse d'un nœud si ce nœud s'avère (strictement) moins intéressant qu'un nœud déjà analysé. Pour être précis, supposons que c'est aux Blancs de jouer et que les feuilles de l'arbre correspondent à des coups blancs. On doit donc associer à chaque nœud le maximum des valeurs des feuilles qui en dépendent. Si dans l'évaluation d'un nœud à partir des feuilles on trouve une feuille dont la valeur est supérieure à la valeur d'un nœud déjà évalué, alors calculer le minimum des maxima ne requiert pas d'évaluer les feuilles restantes du nœud puisque quelles que soient leurs valeurs, la valeur du nœud sera toujours supérieure à celle du nœud de référence. Ce principe est appliqué à tout l'arbre, depuis la racine.
2o) Le générateur de coups légaux
Pour implémenter cette fonction, on parcourt les pièces en jeu et on calcule pour chaque pièce tous ses déplacements possibles en tenant compte du mode de déplacement du type de pièce concernée. Un mouvement élémentaire est représenté par un vecteur, par exemple le vecteur (1,2) est l'un des 8 déplacements possibles du Cavalier. On doit également tenir compte du fait que certaines pièces sont à longue portée (la Dame, la Tour et le Fou) et pas les autres, i.e. leurs déplacements élémentaires peuvent être réitérés dans chaque direction autorisée au cours du même coup. Chaque type de pièce est défini par le tableau de ses directions de déplacement (représentées par des vecteurs) et par une variable qui spécifie si la pièce est à longue portée ou pas. Bien sûr, les pions nécessitent un traitement particulier (pour le fait que le sens de déplacement dépend de la couleur, pour la poussée, la prise en passant, le fait que le déplacement et la prise ne s'effectuent pas de la même façon, la promotion).
«Computer Art - Image generated Une solution simple serait pour chaque coup déjà engendré de tester si après avoir joué ce coup le Roi est en échec, et le cas échéant de supprimer ce coup de la liste. Le problème de cette approche est que la fonction qui teste la mise en échec est assez coûteuse, et sera utilisée un grand nombre de fois. Une méthode plus économe est de limiter l'emploi de cette fonction de test aux situations où le Roi est déjà en échec (ce cas est relativement rare, et dans ce cas cette approche systématique est quasiment incoutournable), et de veiller à empêcher un déplacement qui placerait le Roi en échec. Lorsque le Roi n'est pas en échec la seule façon de l'exposer à un échec, en dehors du fait de déplacer le Roi lui-même, est de bouger une pièce clouée (et cela peut dépendre de la direction). Donc il suffit de faire précéder l'analyse par l'appel d'une fonction qui part de la position du Roi et parcourt toutes les directions pour vérifier s'il y a une pièce clouée et dans ce cas indiquer aux variables de la pièce la direction dans laquelle elle est clouée. Cette analyse se fait en amont de la recherche des coups légaux effectuée au départ. Le grand avantage de cette approche est que cette fonction de test est utilisée une fois pour toutes. Bien sûr si la liste est vide au sortir de cette fonction cela signifie que le Roi est mat, ou pat. © 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 ******** |
 |
«Images taken from the Thinking Machine 4 - 
