Le Fou numérique

Les notions de base de 

Stefan Meyer-Kahlen 

è

Peter Schreiner

Graphique, mise en page et illustrations repris du site du Schachclub Leinzell avec l'aimable autorisation de Klaus Schumacher

Traduit de l'Allemand par Patrick Buchmann avec l'aimable autorisation de Stefan Meyer-Kahlen


UCI Engines Ligue

Matchs et tournois entre Engines

Le Système du Suisse

Téléchargement

Les modules

Comment faire...

Les liens

Plan simplifié du site

Archives

Le Forum du Fou

 

Site search Web search

powered by FreeFind

Schachclub Leinzell

Programmation aux Échecs

de Stefan Meyer-Kahlen - Juin 2001

  

 
Beaucoup de lecteurs m'ont demandé comment procéder en fait quand on veut développer son propre programme d'échecs. J'aimerais donc aborder rapidement divers points de vue de la programmation aux échecs sans être trop technique ou aller trop loin dans les détails. Mais avant tout, un avertissement à prendre très au sérieux: la programmation aux échecs rend dépendant!
 
Après chaque étape franchie avec succès, l'enthousiaste va en croissant. Quand son propre programme effectue pour la première fois des coups légaux et que la première partie est surmontée sans crash, c'est un euphorie de succès à peine descriptible. Si de plus, quelques coups sensés en sortent, il n'y a définitivement plus d'échappatoire. Dans ce cas on accepte même avec calme quand son propre programme perd...
 

 

Langage de programmation

Comment et avec quoi doit-on commencer? D'abord, il faut se poser la question dans quel langage de programmation, on veut écrire le programme. Mon programme Shredder est écrit en C, même si je ne peux conseiller cela, aussi peu que l'assembleur ou le langage machine, à un débutant. Actuellement, il existe des possibilités bien meilleures comme par ex. Delphi, Visual Basic, C++ ou aussi Java. En principe, chacun de ces langages est bien approprié et peut être conseiller sans restriction.
 
On doit cependant prendre en compte que les outils de développement commerciaux pour ces langages sont relativement chers, car 500€ pour un petit projet échiquéen ne sont pas du goût de tout le monde. Mais pas de panique, il existe des alternatives à moindre coût voir aussi gratuites. Presque tous les éditeurs proposent des versions d'entrée de gamme nettement moins chers de leur package logiciel avec la restriction que les programmes produits ne peuvent être commercialisés, mais jusque là il reste un bon bout de chemin.
 
Souvent une version plus ancienne proposée gratuitement dans beaucoup de livres d'apprentissage fait aussi l'affaire. Si je devais me décider pour un langage, je conseillerais sûrement Java. Les programmes en Java fonctionnent souvent plus lentement, mais cela ne joue pas un rôle primordial dans nos premiers essais, et, à mon avis, les avantages de Java compensent largement cet inconvénient.

 

 

La mise en route

Mais maintenant, au boulot. En premier lieu se pose la question comment on va enregistrer l'échiquier et les pièces en interne dans le programme donc aussi dans l'ordinateur. A toutes les catégories de pièces est attribué un nombre, par ex. au pion blanc le 1, au Cavalier blanc le 2, au Fou blanc le 3, à la Tour blanche le 4, la Dame et le Roi blanc auront ainsi le 5 et le 6. Ensuite au tour des Noir en commençant par le pion avec le 7.
 
Ainsi, nous avons procédé sans le remarquer à la première optimisation: Avec cette numérotation on peut se rendre compte rapidement si une pièce est blanche ou noire, ce n'est pas sans importance car on ne peut par ex. que prendre des pièces adverses et jouer avec les siennes. Le pièces blanches sont toutes inférieures ou égales à 6 et les noirs toutes supérieures à 6, un test très simple.
 
On continue avec la représentation de l'échiquier: L'échiquier possède 64 cases sur lesquelles une pièce peut être positionnée. Il est donc évident de réserver une cellule d'enregistrement pour chaque case que nous numérotons également de 1 à 64. Case 1 devientA1, la 2 est B1, la 3 est C1 et la 64 est donc H8. Si nous voulons représenter qu'un Fou blanc est sur b1, nous devons écrire un 3 = Fou Blanc dans la cellule de sauvegarde numéro 2 = b1.
 
Il manque une petite chose: Comment indiquer qu'une case est vide? Pour cela nous utilisons simplement aussi un chiffre qui signifie "pas de pièces", le 0 se signale naturellement. Par ex. si la case a2 est vide, dans la cellule de sauvegarde numéro 9 il y aura un 0. On peut ainsi représenter toute configuration possible sur un échiquier; mais que se passe-t-il quand une pièce doit exécuter un coup?
 

 

Les règles

Comment peut-on trouver quels coups sont légaux pour une pièce ou dit plus simplement comment une pièce fait-elle un coup? Chaque joueur d'échecs sait qu'un Fou ne se déplace qu'en diagonale, un pion qu'en avant ou un Roi dans chaque direction mais seulement d'une case. Cela doit être appris au programme. Prenons le cas de la Tour comme exemple. La Tour peut se déplacer à gauche, à droite, vers le haut ou le bas et au plus jusqu'à ce qu'elle tombe sur une autre pièce ou le bord de l'échiquier. Si l'on regarde notre échiquier interne, se déplacer d'une case à droite veut dire que le numéro de case s'incrémente exactement de 1. De la case b1 avec le numéro 2 à la case c1 avec le numéro 3 vers la droite, le pas est donc de 1. Vers la gauche les numéros de case se décrémente exactement de la même façon toujours de 1.
 
De même, on peut constater que les numéros de case vers le haut ou le bas augmentent, ou diminuent, de 8 ou-8. Si l'on se déplace de la case a1 avec le numéro 1vers le haut en a2, on constate que le la case a2 porte le numéro 9. Ainsi nous avons fait une observation importante qui nous permet de calculer tous les coups légaux d'une Tour. Pour cela nous partons de la case de la Tour respectivement dans les 4 directions possibles pour la Tour, soit 1, -1, 8, -8 en ajoutant, voir soustrayant, la direction du mouvement au numéro de case. Cela est fait dans chaque direction aussi longtemps que nous ne rencontrons pas une autre pièce ou le bord de l'échiquier.
 
Si nous rencontrons une pièce adverse cela veut dire que la Tour peut prendre cette pièce. Si nous retenons toutes les cases que nous pouvons atteindre ainsi de cette façon, nous avons déjà résolu notre problème et déterminer tous les coups légaux pour la Tour. Bon, la chose n'est pas tout à fait aussi simple, car nous devons vérifier à chaque coup si notre Roi ne se retrouve pas en échec, ces coups doivent être trier car ils seraient illégaux. Si nous sommes déjà en échec nous devons aussi vérifier si un de ces coups de Tour pare l'échec. En principe, les coups possibles de toutes les autres pièces sont déterminés de la même manière, on doit seulement déterminer les valeurs pour chaque direction correspondante et pour le Cavalier et le Roi prendre en compte qu'il ne peuvent bouger qu'à une case de distance.
 
Les pions créent ici le plus de problèmes, car ils avancent et font la prise dans des directions différentes, peuvent en certaines circonstances avancer de deux cases ou prendre en passant et se transforment en une autre pièce en arrivant sur la rangée initiale adverse, mais, avec un peu de précaution, toutes ces particularités comme le roque en tant que coup particulier du Roi peuvent être maîtrisées.
 
L'exécution effective du coup est ensuite un détail mineur. Si une Tour blanche va de a1 vers a2, nous écrivons dans la case avec le numéro 1 (a1) un 0, car la case est vide après le coup. Dans la case avec le numéro 9 (a2) un 4 est mis pour une Tour blanche qui s'y niche. Et c'est fait. De cette façon nous pouvons déterminer tous les coups légaux dans une position et les jouer dans notre échiquier interne, nous n'avons pas besoin de plus pour que notre programme puisse essayer tous les coups possibles jusqu'à une profondeur donnée ainsi que le font tous les programmes d'échecs actuels.
 

 

Évaluation

Pour savoir quel côté est finalement mieux, il faut d'abord expliquer à notre programme qu'une Dame est meilleure qu'une Tour et un Cavalier qu'un pion. Cavalier et Fou sont à peu près équivalents. Toutes les pièces se voient ainsi attribuer une valeur qui détermine si une pièce est précieuse. Les valeurs suivantes, comme pourra le confirmer chaque joueur d'échecs, sont considérées comme raisonnables. La Dame vaut 900 points, une Tour 500 points, Fou et Cavalier 300 points et un pion 100 points.
 
Pour évaluer grossièrement une position, nous faisons calculer la valeur de touts les pièces blanches et noires par notre programme. En faisant la différence, valeur totale blanche moins valeur totale noire, on obtient une valeur qui nous indique si les Blancs ou Noirs sont mieux. A 0, la position est égale. Une valeur de 100 indique par ex. que les Blancs ont un pion de plus. Ceci indique bien sûr uniquement une valeur très grossière d'une position que l'on peut encore étendre et affiner au choix .
 
Par ex., il est imaginable de punir un pion doublé par -10 et de récompenser une Tour sur une colonne ouverte par +6. Toutes ces valeurs sont additionnées et forment finalement une évaluation de position que nous rencontrons dans tous les programmes d'échecs. Pour trouver le meilleur coup dans une position, le programme essaie simplement tous les coups jusqu'à une certaine profondeur et calcule pour chaque coup une valeur comme décrit ci-dessus. Le coup avec la valeur la plus élevée est, d'après cette logique, le meilleur et finit par être choisi par le programme.
 

 

Conclusion

Si nous parvenons à ce point, nous avons un programme qui exécute déjà des coups pas totalement insensés et qui ne perd pas une pièce bêtement. A l'inverse il n'oubliera plus aucune pièce en prise et ramassera toutes les pièces qui lui sont jetés en pâture consciemment ou inconsciemment. Le chemin pour écrire un programme contre lequel on peut perdre soi-même est, sous diverses conditions, déjà tracé...

Stefan Meyer-Kahlen – www.shredderchess.dewww.shredderchess.com
 

nach oben