Création d'un programme d'échecs en Free Pascal

**Roland Chastain** · 23/04/2015, 14h47

J'aime bien le nom du programme. Je viens de faire une recherche à ce sujet et j'ai appris à qui il fait référence.

Autrement, vos observations sont, me semble-t-il, très justes. C'est de bon augure pour la suite !

Envoyé par glegat

En effet il me semble très compliqué (pas forcément impossible) d'intégrer dans le générateur de coups plausibles le repérage des cases contrôlées il me semble que cela doit se situer à part. Il y a une grande différence entre les cases autorisées et les cases contrôlées.

En effet, la génération des coups légaux nécessite la génération des coups plausibles (je reprends votre expression). Car pour savoir si un coup est légal, il faut être en mesure de détecter l'échec, ce qui se fait au moyen des coups plausibles (l'échec étant un cas particulier de la case contrôlée par l'adversaire). Le roque n'a pas sa place dans les coups plausibles, mais seulement dans les coups légaux.

Un conseil que j'ajouterais à celui d'Éric, c'est de bien séparer les fonctions du programme de son interface. Ce qui me conduit à une dernière remarque, sur l'utilité de la notation FEN, que le moteur doit pouvoir comprendre, de façon à initialiser sa représentation interne en fonction de la position sur laquelle on le consulte.

Bonne continuation ! J'ai hâte de voir la suite.

**glegat** · 23/04/2015, 15h33

Ce qui me conduit à une dernière remarque, sur l'utilité de la notation FEN, que le moteur doit pouvoir comprendre, de façon à initialiser sa représentation interne en fonction de la position sur laquelle on le consulte.

Effectivement c'est un modèle de concision cette notation FEN que je ne connaissais pas.

Merci pour tous ces conseils, mais je pense qu'irrémédiablement mon programme sera un peu à l'italienne (ceux qui aime les nouilles comprendront), car je n'ai pas la technique qui me permettrait d'optimiser mon code. Dans un premier temps je vais essayer de faire quelque chose qui fonctionne, même si le résultat pourrait être très faible pourvu que mon programme sache jouer aux échecs ce sera bien, Kempelen n'est qu'un prototype expérimental.

**joreveur** · 27/04/2015, 08h45

Envoyé par glegat

Je précise que j'ai commencé mon programme et que je viens de terminer le générateur de coups plausibles, je suis en phase de test pour valider définitivement cette procédure. Il a fallut pour cela résoudre le problème de la représentation de l'échiquier dans le programme et j'ai choisis d'utiliser un tableau de 119 cases définit ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 tDoska119             : array[0..119] of integer;

J'ai mis en pièce jointe l'échiquier avec la numérotation des cases, les coordonnées et les vecteurs de déplacement des pièces.

Bonjour,

Comme projet, c'est un projet ambitieux, mais c'est tout à ton honneur.
je m'abonne à ce sujet car j'avais réfléchi, il y longtemps, à réaliser, un petit moteur de jeu. Mais je n'avais pas assez de connaissances (pas beaucoup plus maintenant d'ailleurs) pour y parvenir.
En tous cas je testerai tes réalisations et ça me permettra de rejouer un peu aux échecs en passant (comme le pion

)

Nb ton tableau ne fait pas 119 mais 120 cases

Bien à toi.

**glegat** · 27/04/2015, 10h05

Maintenant que mon programme connaît les règles de déplacement des pièces et de manière à commencer à le faire jouer un peu, j'ai décidé de créer la bibliothèque d'ouverture.

J'ai pu récupérer quelques fichiers au format texte contenant les ouvertures sous la forme e2e4 e7e5 b1c3 b8c6 etc... Ce type de fichier présente plusieurs avantages:

Il est d'une simplicité biblique, quand on l'ouvre on comprend tout de suite comment l'utiliser.
Il est relativement facile à compléter, puisqu'il suffit de saisir à la suite les variantes sous la forme case départ case arrivée, on peut pour cela se contenter du bloc note windows.
La mise en œuvre est immédiate.
On peut même structurer le fichier, trier les variantes (dans un traitement de texte), rajouter des titres par groupe d'ouverture etc, sans altérer le contenu puisque le programme devra simplement recherche dans ces chaines de caractère une série qui correspond à une liste de coups joués provenant du programme, s'il y a des lignes supplémentaires ou des commentaires il ne les retiendra pas comme variante.

Inconvénients:

La modification du fichier est simple mais elle demande une grande rigueur car il n'y a aucun contrôle de cohérence des coups saisies, il faut donc bien préparer son travail et se relire, c'est un peu long et fastidieux pour saisir de très nombreuses variantes, on pourrait toutefois imaginer un petit utilitaire qui permettrait un plus grand confort et un contrôle automatique, mais ce serait long à développer.
On trouve très peu de fichiers de ce type sur internet et ceux qu'on trouvent contiennent assez peu de données, le plus gros que j'ai trouvé est celui du programme d'échecs open source tscp de Tom Kerrigan's écrit en C,un fichier d'environ 4000 demi-coups, ce qui est suffisant pour démarrer. J'ai utilisé ce fichier en le modifiant un peu et en rajoutant des variantes.

Une fois muni d'un fichier de ce type on a envie de l'exploiter et pour cela il faut créer un module qui va lire le fichier texte pour rechercher une chaine de caractères identique à la liste des coups joués dans le programme. Chaque réponse trouvée est stockée dans un tableau, lorsqu'on arrive à la fin du fichier il suffit de relire le tableau et de choisir aléatoirement l'un des coups trouvés dans cette liste. Cette sélection aléatoire est nécessaire pour donner de la variété au programme sinon il jouera toujours la même chose dans une position donnée.

Ensuite je me suis posé la question de savoir s'il ne fallait pas créer deux fichiers de bibliothèque l'un à utiliser par le programme quand il a les Blancs et l'autre quand il a les noirs. En effet un joueur humain procède de la même manière, il connaît un certain nombre d'ouverture mais ne les joue pas lui-même en premier, il doit les connaître pour riposter, mais quand il a l'initiative il les évite car elle ne conviennent pas à son style de jeu par exemple. Je pourrais développer d'avantage cette idée en donnant des exemples concrets pour vérifier l'opportunité de cette option. Il ne serait d'ailleurs pas nécessaire de créer deux fichiers, un seul suffirait avec un indicateur au début de chaque variante B pour signifier au programme qu'il peut jouer cette variante avec les Blancs (N pour Noir) et X dans les deux cas. De cette manière on donnerait déjà un peu d'intelligence au programme dans une phase de jeu qui généralement ne fait appel qu'à la mémoire. , Je ne sais pas comment procède les forts programmes mais je pense que leur module d'ouverture est sûrement très sophistiqué.

Pour l'instant je ne vais pas me compliquer la tâche et j'utiliserai donc un seul fichier contenant des ouvertures standards ce module d'ouverture aura pour but de conduire le programme à une position équilibrée à la fin de l'ouverture.

A noter que ces quelques lignes de programme préfigure ce que sera le logiciel le plus fort de tous les temps lorsqu'on aura déterminé la suite de coups qui à partir du début de la partie mène irrémédiablement au mat. Il suffira de stocker ces coups dans la bibliothèque d'ouverture et jamais le programme n'aura besoin de réfléchir (c'est déprimant).

Moyennant quelques modifications on pourrait transformer ce petit programme pour en faire un outil d'apprentissage personnalisé des ouvertures (affichage du nom de la variante, le programme compte un point chaque fois que vous trouvez la bonne suite etc..), à vous de saisir dans le fichier les variantes que vous souhaitez mémoriser.

Voici le source réalisé pour tester mon module d'ouverture, il me reste à l'adapter pour l'intégrer à mon programme. Il fonctionne en toute autonomie avec le fichier txt que vous trouverez en pièce jointe.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
Program ReadBook;
{*** Lire un fichier d'ouverture, retenir les variantes qui correspondent
*** à la liste des coups déjà joués, mettre les coups trouvés dans un tableau
*** Choisir au hasard l'un de ses coups
*** écrit par Gérard Legat 27 avril 2015}
{$h+} {permet d utiliser des variables string > 255}
uses  Classes, sysUtils ;  { necessaire pour lire fichier}
var
   inc, i, alea : integer;
   Filename : string;
   f : Textfile;
   enreg : string;
   coupKempelen : string;
   Listecoups : string;
   longueur : shortint;
   extrait : string;
   nouveaucoup : string;
   reponseBiblio : array[1..300] of string;
 
begin
 
     FileName := 'c:\users\glegat\documents\bibliokempelenv1.txt';
     if not FileExists(Filename) then
                    begin
                    writeln('fichier non trouve : ',FileName);
                    readln;
                    halt;
                    end;
     randomize;
     nouveaucoup := '';
     listecoups :='';
     while nouveaucoup <> 'fin' do
     begin
     writeln;
     {writeln(listecoups);}
     write('    Votre coup : ');
     readln(nouveaucoup);
     listecoups := listecoups + nouveaucoup  + ' ';
     longueur := length(listecoups);
     for i := 1 to 300 do reponsebiblio[i] := '';
 
           begin
               assignFile(F,FileName);
               Reset(F);
               inc := 1;
               While not Eof(F) do
                  begin
                      {on lit l'enregistrement}
                      readln(F,enreg);
 
                     {on extrait la portion de chaine qui correspond à la longueur de la chaine a chercher}
                     extrait := copy(enreg,1,longueur);
                     {on compare l'extrait avec la suite de coup de la partie}
                            if extrait = listecoups then
                                begin
                                {on enregistre toutes les reponses de la bibliotheque};
                                   reponsebiblio[inc] := copy(enreg,longueur+1,4);
                                   inc := inc +1;
                               end;
                 end;
                 CloseFile(F);
            end;
            nouveaucoup := 'fin';
            alea := random(inc);
            if alea = 0 then alea := 1;
            coupKempelen := reponsebiblio[alea];
 
            if coupKempelen = ''
               then
                   writeln('fin bibliotheque')
               else
               begin
               write('                      Kempelen joue : ',coupKempelen);
               nouveaucoup :='';
               listecoups := listecoups + coupKempelen +' ';
               end;
    end;
    writeln('Le programme doit maintenant reflechir pour trouver un coup');
    readln;
end.

Que ceux qui auront la curiosité de l'essayer n'hésitent pas à me faire part de leurs remarques et suggestions.

Vous trouverez en pièce jointe un fichier compressé contenant :
BiblioKempelenv1.txt (bibliothèque d'ouverture)
ReadBook.pas le source
ReadBook.exe l'exécutable (pour ceux qui ne pourrait pas compiler).

Si vous souhaitez faire jouer la bibliothèque du point de vue des noirs le premier de vos coups sera un demi-coup par exemple e2e4, si vous souhaitez faire jouer la bibliothèque du point de vue des Blancs, jouez un coup complet par exemple e2e4 e7e5 (un espace entre les deux demi-coups).

Attention : n'oubliez pas de changer le chemin d'accès au fichier BiblioKempelen si vous recompilez le source, et si vous utilisez l'exécutable vous devrez créer les répertoires prévus dans mon exemple.

**glegat** · 27/04/2015, 10h52

Nb ton tableau ne fait pas 119 mais 120 cases

Bien vu ! Mais heureusement c'est sans incidence, ce n'est que le nom de la variable, j'ai utilisé aussi Doska qui veut dire échiquier en russe, c'est aussi court que Board et ça change de l'anglais.

**Roland Chastain** · 27/04/2015, 18h49

Bonjour ! Deux ou trois petites suggestions.

1° Vous pouvez remplacer ces deux lignes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
  alea := random(inc);
  if alea = 0 then alea := 1;

par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

alea := random(inc) + 1;

Autrement le dernier coup n'a aucune chance d'être choisi.

D'ailleurs la variable alea ne sert trop à rien. Autant ne pas multiplier inutilement les variables. Vous pourriez écrire directement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

coupKempelen := reponsebiblio[random(inc) + 1];

2° Une seule chaîne suffirait pour contenir les coups trouvés. La longueur de la chaîne divisée par quatre vous donnerait instantanément le nombre de coups.

3° Vous pourriez mettre tout le code des lignes 40 à 65 dans une fonction, qui recevrait comme argument la valeur de la variable listecoups et qui renverrait une chaîne contenant les coups trouvés (en supposant que vous reteniez ma seconde suggestion). La fonction pourrait ressembler à ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
function ReponseBiblio(aListeCoup: string): string; 
var
  resultat: string;
begin
  resultat := '';
  ...
  ReponseBiblio := resultat;
end;

Et vous pourriez l'appeler ainsi depuis le programme principal :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

coupKempelen := ReponseBiblio(listecoups);

Bonne continuation !

**glegat** · 27/04/2015, 19h01

Bonjour ! Deux ou trois petites suggestions.

Merci pour toutes ces suggestions, je vais certainement les retenir !

**glegat** · 29/04/2015, 19h54

Voici l'état d'avancement de mon projet à ce jour :

Mon programme (Kempelen) commence à jouer. Il connait les règles de déplacement des pièces, il peut répondre aux coups théoriques del 'ouverture grâce à sa bibliothèque (dans laquelle je rajoute de nouvelles variantes chaque jour, et lorsque je rencontre des lacunes). Il me reste maintenant à lui donner un peu d'intelligence pour choisir le meilleur coup une fois qu'il a quitté sa bibliothèque, c'est la partie la plus difficile évidemment, mais aussi la plus passionnante. Aujourd'hui j'ai crée une procédure qui permet d'alimenter deux tableaux, l'un pour les noirs l'autre pour les blanc, ce tableau contient l'information suivante*:

Pour chaque case de l'échiquier ces tableaux me renseigne sur les cases contrôlées, ainsi pour la case e4 par exemple je trouverais la valeur 0 si la case n'est pas contrôlée et une valeur positive de 1 à 9 qui indique combien de fois cette case est contrôlée par les blancs (même chose pour les noirs). Je pense que cette procédure que j'ai crée initialement pour vérifier si les cases autour du roi sont contrôlées, si le roque est possible etc... me sera très utile par la suite dans mon système d'évaluation.

Donc maintenant je commence à réfléchir à l'évaluation de la position, je peux mettre en œuvre très rapidement le critère matériel et le critère mobilité/Cases contrôlées, mais je me pose la question de savoir si je dois commencer maintenant l'écriture du module d'analyse en profondeur ou si je dois encore travailler sur l'évaluation du premier coup de la racine, autrement dit pour l'instant mon programme joue sur un demi-coup de profondeur (autrement pas de profondeur du tout) (je rappelle mon objectif de départ faire un programme simple sans interface graphique qui analyse sur deux demi-coups seulement dans un premier temps, je n'en suis donc pas très éloigné), mais par quoi dois-je continuer ?, maintenant que j'obtiens une liste de coups potentiellement jouables ? J'aurais tendance à penser qu'il me faut le faire jouer le mieux possible à ce niveau avant de faire l'analyse en profondeur mais j'hésite et comment trouver des critères d'évaluation sans analyser la moindre réponse de l'adversaire*? (même si l'information sur les cases contrôlées est déjà une première approche de l'analyse en profondeur).

**virtualsim** · 02/05/2015, 11h04

Personnellement, je me méfierais de l'usage des tableaux à 2 dimensions, coté complexité d'une recherche en profondeur. La double indexation T[i][j] est très coûteuse. Il est préférable de mettre pour chaque case une liste de liste de pointeurs sur les cases possibles. Ainsi, n'importe quelle case de l'échiquier serait une structure avec la pièce qu'elle contient (ou pas), la couleur de la pièce, la note noire, la note blanche (calcul stratégique), le numéro de la zone (zone d'attaque ou de défense), et la liste des coups possibles pour chaque pièce. Donc, un vecteur de vecteurs (ie: p[0] = liste des cases accessibles pour la pièce 0, soit le pion, p[1], pour le cavalier, etc.)
La représentation n'est pas visuelle. Les cases sont également chaînées entre elles par quatre ou 8 pointeurs (pour aller de A1 en B1 ou B2).
Les algorithmes doivent utiliser ces chaînages pour les recherches en profondeurs et la notation globale (chaque case est notée, pondérée par les zones, puis l'échiquier à l'instant T est noté, et ensuite, on élague ou non l'arbre de recherche, etc.)
C'est comme cela que je le referai.
Après, faut peaufiner les algos et mettre un peu de stratégie et quelques grandes règles: un ordinateur doit chercher à réduire le nombre de pièces par des échanges, pour augmenter la recherche en profondeur exponentielle au nombre de pièces; l'humain contre l'ordinateur doit au contraire, refuser les échanges et maintenir le maximum de pièces sur l'échiquier, surtout en blitz).

**glegat** · 02/05/2015, 18h53

Personnellement, je me méfierais de l'usage des tableaux à 2 dimensions

Merci pour votre contribution. Dans mon programme, pour l'instant je n'utilise pas de tableaux à deux dimensions, mon niveau en programmation m'incite à faire le plus simple possible, même si en voulant faire simple on se complique parfois encore plus. Mais je découvre en même temps plein de choses et j'avance tout doucement, aujourd'hui, après avoir intégré 3 critères d'évaluations (matériel, cases contrôlées et incitation au roque) j'ai pu faire faire quelques parties test à Kempelen proto qui réagit correctement pour l'instant par rapport à ces critères. J'en dirais plus dans les prochains jours.

**joreveur** · 02/05/2015, 21h30

Bonjour
juste un essai en ayant compiler sous linux. (revu le chemin car sous Linux) et ça fontionne

Votre coup : e2e4
Kempelen joue : e7e6
Votre coup : d2d4
Kempelen joue : d7d5
Votre coup : b1c3
Kempelen joue : f8b4
Votre coup : a2a4
fin bibliotheque
Le programme doit maintenant reflechir pour trouver un coup

et quand ce n'est pas dans la bibliothèque d'ouverture (comme a2a4) , il y aura un algo qui va chercher un 1/2 coup correct, je suppose ?

sinon, l'unité Classes n'a pas l'air d'être utile,
tu peux peut-être regrouper les variables par type (mais chacun sa méhode)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

coupKempelen, enreg, Listecoups: string;

Bonne continuation

**glegat** · 03/05/2015, 00h23

l'unité Classes n'a pas l'air d'être utile,

Effectivement dans ce petit essai seule Sysutils est nécessaire pour les instructions liées à la lecture du ficher txt.

il y aura un algo qui va chercher un 1/2 coup correct, je suppose ?

Oui j'ai terminé aujourd'hui une recherche sur un 1/2 coup après la sortie de la bibliothèque. Kempelen peut maintenant faire des parties complètes, mais je ne met pas encore le source ni l'exécutable en ligne car le programme est truffée de writeln pour que je puisse vérifier tous mes paramètres et mes variables. Il y a encore du boulot pour le rendre un peu présentable. Pour l'instant kempelen scrute tous les coups issus du générateur de coups plausibles et évalue le coup en fonction de trois critères :

Eval 1 = (Cases contrôlées par kempelen - cases contrôlées par l'adversaire) / 45

Je divise par 45 pour obtenir une évaluation en avantage équivalent pion, c'est un coef provisoire.

Eval 2 = Si le coup est un roque je rajoute 0,20 dans la variable d'évaluation (c'est provisoire aussi), si je ne fais pas ça kempelen privilégie l'évaluation des cases contrôlées et trouve toujours autre chose à faire que le roque qui est souvent essentiel en début de partie.

Eval 3 = Si la case d'arrivée du coup analysé contient une pièce ou un pion de l'adversaire et que cette case est contrôlée par l'adversaire alors j'évalue la balance matérielle : Valeur de la pièce dans la case d'arrivée - Valeur de la pièce de la case départ, en revanche si la case n'est pas protégée la balance matérielle est un gain net de la valeur de la pièce d'arrivée. D'autre part si la case d'arrivée est vide et que cette case est contrôlée la balance matérielle est en faveur de l'adversaire de la valeur de la pièce qui arrive, par ces artifices et sans faire d'analyse en profondeur mais en restant au 1/2 coup kempelen produit un jeu de débutant très étourdi mais il peut tenir un certain temps avant de se faire mater contre un très faible joueur.

Maintenant je dois réfléchir à mon algorithme d'analyse sur plusieurs demi-coups afin de rendre efficace l'évaluation du matériel. Suivra l'intégration d'autres critères d'évaluation, le contrôle du centre, la structure des pions, la sécurité du roi etc...

Voici l'une des premières parties entières jouées par kempelen.

Premier résultat de mon programme une nulle contre un programme correctement programmé au niveau recherche en profondeur mais
dont la fonction d'évaluation est inefficace à faible profondeur, kempelen en analysant sur un demi coup fait nulle contre ce programme paramétré pour limiter son analyse sur deux demi-coups. Mais il y a des gaffes monumentales des deux cotés et surtout du coté Kempelen.

[Date "2015.05.02"]

[White "Schach depth 2"]
[Black "Kempelen proto depth 1"]
[Result "1/2-1/2"]
[ECO "C20"]
[PlyCount "47"]

1. e4 e5 2. Bb5 Qf6 3. d4 exd4 4. h4 Bb4+ 5. c3 Ne7?? 6. cxb4 O-O 7. Nh3 Qxh4 8. Qxd4 Qh5 9. Bxd7
Bxd7 10. Bg5 Bxh3 11. Bxe7 Bxg2 ?? 12. Rxh5 Nc6 13. Qd3 Nxe7 14. e5 Bc6 15. Nc3
{Schach ne voit pas le mat en 1 pour voir un mat en 1 coup il faut faire une
analyse sur trois demi coups.} b6 16. a3 Rab8 17. f4 Ra8 18. Kf2 Rab8 19. Rg1
Ra8 20. b3 Rab8 21. Rh3 Ra8 22. Rh5 Rab8 23. Rh3 Ra8 24. Rh5 1/2-1/2

**Roland Chastain** · 03/05/2015, 00h53

Bonsoir ! J'ai visionné rapidement la partie dans Arena. C'est vraiment pas mal pour un début ! J'aime bien votre approche, simple et claire. Ça me donne envie de m'y remettre.

**yamer** · 03/05/2015, 10h54

Envoyé par virtualsim

Personnellement, je me méfierais de l'usage des tableaux à 2 dimensions, coté complexité d'une recherche en profondeur. La double indexation T[i][j] est très coûteuse. Il est préférable de mettre pour chaque case une liste de liste de pointeurs sur les cases possibles. Ainsi, n'importe quelle case de l'échiquier serait une structure avec la pièce qu'elle contient (ou pas), la couleur de la pièce, la note noire, la note blanche (calcul stratégique), le numéro de la zone (zone d'attaque ou de défense), et la liste des coups possibles pour chaque pièce. Donc, un vecteur de vecteurs (ie: p[0] = liste des cases accessibles pour la pièce 0, soit le pion, p[1], pour le cavalier, etc.)
La représentation n'est pas visuelle. Les cases sont également chaînées entre elles par quatre ou 8 pointeurs (pour aller de A1 en B1 ou B2).
Les algorithmes doivent utiliser ces chaînages pour les recherches en profondeurs et la notation globale (chaque case est notée, pondérée par les zones, puis l'échiquier à l'instant T est noté, et ensuite, on élague ou non l'arbre de recherche, etc.)
C'est comme cela que je le referai.
Après, faut peaufiner les algos et mettre un peu de stratégie et quelques grandes règles: un ordinateur doit chercher à réduire le nombre de pièces par des échanges, pour augmenter la recherche en profondeur exponentielle au nombre de pièces; l'humain contre l'ordinateur doit au contraire, refuser les échanges et maintenir le maximum de pièces sur l'échiquier, surtout en blitz).

Accéder à un tableau à 2 dimensions n'est pas plus coûteux qu'accéder à un tableau à une dimension qui simule un tableau 2D. C'est la même chose sauf que dans un cas le compilateur se charge du boulot et, qu'accessoirement, ça donne un programme plus lisible.

En ce qui concerne la comparaison avec un système basé sur des listes chaînées j'ai de gros doutes. Mais comme je ne connais pas les échecs ...

**glegat** · 05/05/2015, 09h22

Vous l'aurez deviné je suis plus joueur d'échecs que programmeur et je montre plus volontiers ce que produit mon programme plutôt que la manière dont il le produit. Si je dévoile peu mon code dans ce groupe de discussion (mais cela viendra), c'est que je n'en suis pas spécialement fier et qu'il ne peut en aucun cas servir d'exemple. Je me rends compte que je suis parti bille en tête dans ce projet sans faire d'analyse préalable sérieuse , il en résulte que mon programme commence à être redondant, il frise l'embonpoint (1300 lignes) et il ne s'appelle pas Kempelen pour rien, on s'imagine que derrière la machine se trouve un module logique d'analyse mais en fait il y a un humain (le programmeur) qui transpose son raisonnement d'humain (fait d'intuition plus que de logique) par le biais des rouages de la machine. Pour l'instant donc il est plus agréable de constater ce qu'il ressort de la machine plutôt que ce qu'il y a à l'intérieur. Par exemple j'ai tendance à utiliser beaucoup de variables générales plutôt que des variables locales quand c'est possible, je fais cela par commodité mais je ne sais pas si cela peut avoir une incidence sur la vitesse d'exécution*? D'autres part je n'ai pas crée de Unit, tous mon code est dans le programme principal, je n'ai même pas essayé d'en faire une pour l'instant, cela aussi a t-il une incidence sur la vitesse d'exécution*? Avec tout ça, je suis conscient que si je laisse mon projet pendant plusieurs jours ou semaines sans y travailler j'aurai bien du mal à m'y retrouver ensuite.

Voici donc une nouvelle partie de Kempelen proto 29 qui joue avec les noirs contre le programme Schach dont j'ai bridé l'analyse à 3 demi-coups car kempelen lui ne joue qu'à 1 demi-coup de profondeur! Donc lorsque Schach analyse 7 000 à 10 000 coups, Kempelen n'en examine que 30 à 35. Bien évidemment j'utilise des heuristiques (je ne sais pas si c'est le nom) qui permettent de simuler une recherche en profondeur, mais Kempelen n'envisage aucune réponse de l'adversaire il se content de scruter l'état de l'échiquier pour chaque coup qu'il envisage et essaie d'en tirer toutes les informations possibles pour évaluer son coup suivant un raisonnement basé uniquement sur les forces en présence à l'instant t sur l'échiquier. Ce type de construction ne pourra pas aboutir à un fort programme qui doit obligatoirement analyser en profondeur sur un minimum de 6 à 8 demi-coups pour produire un jeu correct. Mais pour l'instant cette façon de faire m'amuse beaucoup. Ensuite lorsque j'aurai intégré tous les critères d'évaluation auxquels je pense, j'obtiendrais donc une liste de coups candidats triés dans l'ordre décroissant de leur force et je ferais une recherche en profondeur avec pour seul critère le matériel et je ne changerais mon coup choisi au départ que si l'analyse en profondeur me démontre qu'il perd du matériel, enfin d'ici là j'aurai peut-être changé d'avis ou abandonné le projet comme j'ai pensé le faire il n'y a pas longtemps devant la complexité de la tâche et la nécessité d'y consacrer beaucoup de temps.

J'ai passé un peu de temps à déboguer aujourd'hui pour finalement faire la partie suivante:

[Date "2015.05.04"]
[White "Schach Depth 3"]
[Black "Kempelen proto 29 Depth 1"]
[Result "0-1"]
[PlyCount "56"]

1. e4 {Premier mat de Kempelen face à un adversaire réglé
pour limiter sa recherche à une profondeur de 3 demi-coups (l'élagage Alpha
Beta lui permet d'analyse 7 000 à 20 000 positions au lieu de 25 000 à 40 000
s'il s'agissait d'une recherche exhaustive). Kempelen lui, n'analyse que sur
un demi-coup de profondeur donc environ 30 à 35 coups analysés, mais il
compense par des algorithmes positionnels qui s'avère étonnamment efficaces
même s'il rate plusieurs fois le mat et qu'il se laisse prendre facilement des
pièces.} c5 2. Bb5 Qc7 3. d3 Nf6 4. Bg5 Qd6 5. e5 $4 Qxe5+ 6. Be3 Qxb2 7. Bxd7+
{Le meilleur coup sinon le fou est pris par la Dame Noire.} Bxd7 8. Nd2 Nc6 9.
Bxc5 O-O-O 10. h4 Qe5+ 11. Ne4 Nxe4 12. dxe4 Qxc5 13. a4 Be6 14. Qb1 Kc7 15. a5
h5 16. Ra4 Qc3+ 17. Ke2 g6 18. Ra1 Bg7 {Kempelen Rate le mat en un coup par Fc4} 19.
Ra4 Qc5 20. c4 Bc3 21. Qb3 Bg4+ {Rate un mat en deux coups par Td2 mais
c'est impossible à voir par kempelen à son niveau d'analyse.} 22. f3 Be6 23.
Qxc3 a6 24. Qb3 Qe5 25. Qb6+ Kb8 26. f4 {Je ne comprends pas comment ce coup
est possible avec une analyse sur 3 demi-coups (Bug ?)} Qxf4 {
Kempelen ne se pose pas de question et prend tout ce qu'on lui donne} 27. g3
Qxg3 28. Ra2 Bxc4# {Cette fois le fou est attiré par le pion et il se
trouve qu'en plus cela fait mat...} 0-1 MAT !!! annonce fièrement kempelen qui maintenant sait détecter le mat mais seulement après avoir joué le coup fatidique ! Autrement dit il sait résoudre des problèmes de Mat en zéro coup, étonnant non ?

En fait je pense que le programme Schach n'est pas fait pour jouer à une profondeur réduite car son sytème d'évaluation privilégie avant tout le matériel et donc ce n'est que sur une analyse de 5 à 6 demi-coups que cette manière de faire devient intéressante, donc Schach à tendance à attaquer des pièces avec ses pions (plus la pièce à de valeur plus il est incité à le faire ex : un pion qui attaque la Dame) même si au coup suivant le pion est pris, Schach compte sur l'analyse en profondeur pour corriger le tir, et son apparente gaffe pourrait devenir un judicieux sacrifice de pion !, mais comme je lui coupe cette perspective en le limitant à 3 demi-coups il conserve ce type de coup en tête d'évaluation et ne produit pas le meilleur de ce qu'il peut faire.

Evidemment je ne tire pas de gloire de cette partie, elle est émaillée d'horreurs échiquéennes, mais cela m'amuse beaucoup du point de vue du joueur d'échecs que je suis. On a parfois l'impression que Kempelen sait ce qu'il fait et puis Boum une horreur ! Comme un humain quoi ...

Je vais maintenant trouver d'autres adversaires à opposer à Kempelen (en les réglant pour être complaisants) et voir ce que cela donne avant d'intégrer d'autres critères d'évaluations qui devraient corriger sa tendance à ne pas trop s'occuper de ces pièces en prises!

A bientôt sur ce forum pour suivre les aventures de kempelen Proto qui rêve de s'appeler un jour Kempelen v 1.0 ...

**Roland Chastain** · 05/05/2015, 10h34

Bonjour !

Je trouve vos explications intéressantes et agréables à lire. Vous paraissez quand même maîtriser assez bien votre sujet. Franchement, ce serait dommage d'abandonner par découragement. Personnellement je me suis frotté assez longtemps au problème que vous décrivez (une évaluation des coups sans profondeur) : je n'ai jamais réussi à obtenir quelque chose de convenable et je trouve très étonnant que votre programme arrive à aller jusqu'au mat (même si l'adversaire est faible). Comme je le disais dans mon précédent message, ça me donne envie de reprendre mes recherches sur le sujet, que j'ai en fait abandonnées du moment où j'ai commencé à utiliser le programme de Jürgen Schlottke. Je n'ai jamais réussi à faire moi-même, à partir de rien, un programme qui joue correctement. J'ai passé un temps fou à travailler sur des interfaces graphiques qui m'ont diverti de mon sujet initial.

J'aimerais bien prendre part à vos recherches, par exemple en vous proposant des adversaires. Ce pourrait être intéressant, non ? Mais comment faites-vous, pour le moment, pour faire s'affronter vos programmes ? J'imagine que vous entrez les coups à la main et que vous reportez peut-être le résultat dans un programme comme Arena, qui vous donne ensuite la partie au format PGN, c'est ça ? Il y aurait moyen d'automatiser ce processus. Est-ce que ça vous intéresse ?

La première chose à faire serait une fonction qui initialise l'échiquier interne de votre programme à partir d'une chaîne FEN. De cette façon, le programme n'a pas besoin de garder en mémoire toute la partie. On lui communique simplement une position, il renvoie son coup, son travail est fini. Ce n'est même pas à lui de dire, par exemple, s'il y a un mat. C'est la fonction d'un autre programme. A mon avis, vous auriez intérêt à bien séparer les rôles, plutôt que d'avoir un programme qui fait le joueur et l'arbitre à la fois. Si cette approche vous intéresse, je pourrai vous fournir la fonction qui lit la chaîne FEN. J'aurai seulement besoin de voir la partie de votre code dans laquelle votre échiquier est déclaré et initialisé.

Bonne continuation !

**Roland Chastain** · 05/05/2015, 11h16

Je reviens à la charge... La façon peut-être la plus simple de faire s'affronter deux programmes serait d'en faire des unités. Le programme principal (que je peux fournir et qui est déjà fonctionnel à 100 %) ressemblerait à ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
program Organisateur;
 
uses
  Arbitre, Kempelen, AdversaireDeKempelen;
 
var
  Jeu: Echecs;
 
begin
  Jeu.Commence;
 
  while not Jeu.fini do
  begin
    if Jeu.trait = BLANC then
      Jeu.Enregistre(Kempelen.Coup(Jeu.Position))
    else
      Jeu.Enregistre(AdversaireDeKempelen.Coup(Jeu.Position));
    ...
  end;
 
  Jeu.VoirLaPartie;
end.

Et Kempelen ressemblerait à ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
unit Kempelen;
 
interface
 
function Coup(Position: string): string;
 
implementation
 
function Coup(Position: string): string;
begin
  ...
end;
 
...
 
end.

Il y aurait d'autres approches : deux exécutables recevant la position courante par la ligne de commande, deux librairies dynamiques, deux exécutables utilisant le protocole UCI (c'est la meilleure solution mais elle est plus technique que les précédentes).

**glegat** · 05/05/2015, 12h06

Mais comment faites-vous, pour le moment, pour faire s'affronter vos programmes ?

Effectivement je joue les coups à la console en fonction de ce que m'indique l'adversaire de Kempelen et je saisie la réponse de Kempelen dans Arena, j'utilise aussi Fritz pour enregistrer les parties. C'est donc du 100% manuel mais j'aime ça quand même.

J'aimerais bien prendre part à vos recherches, par exemple en vous proposant des adversaires. Ce pourrait être intéressant, non ? Mais comment faites-vous, pour le moment, pour faire s'affronter vos programmes ? J'imagine que vous entrez les coups à la main et que vous reportez peut-être le résultat dans un programme comme Arena, qui vous donne ensuite la partie au format PGN, c'est ça ? Il y aurait moyen d'automatiser ce processus. Est-ce que ça vous intéresse ?

Oui avec grand plaisir ! Ce serait l'idéal de transformer Kempelen en Chess Engine et de pouvoir le faire jouer en tournoi contre d'autres adversaires de manière automatique, je dois dire que sur ce plan là en programmation je suis à des années lumières de savoir ce qu'il faut faire, mais cela m'intéresse bigrement. Toutefois pour l'instant je ne veux pas me disperser ni vous faire travailler pour rien. Je retiens donc votre proposition et vous en reparlerais bientôt je l'espère. Pour l'instant j'introduit mes critères d'évaluation. IL y a autre chose aussi, j'ai encore une dernière règle de déplacement à introduire c'est la prise en passant, tant que cette règle n'est pas connue de Kempelen inutile de le faire jouer automatiquement contre d'autres programmes il ferait planter l'interface, et comme je ne l'ai pas fait au début je vais peut-être avoir plus de mal à le faire maintenant sans casser des oeufs , enfin j'en sais trop rien, et puis je voudrais faire un peu de ménage dans mon code avant de le présenter.

**glegat** · 05/05/2015, 12h17

je trouve très étonnant que votre programme arrive à aller jusqu'au mat (même si l'adversaire est faible)

Effectivement, moi aussi, mais je pense qu'il y eu dans cette partie une part de hasard propice à sa conclusion. Toutefois le hasard aux échecs est infime, les probalités de conduire à une position de mat par hasard sont quasi nulles, 1 chance sur le nombre d'atome dans l'univers ? (cf Claude Shannon), il est donc agréable de constater qu'un minimum de raisonnement programmé conduise dans des directions où le hasard n'est plus le maître.

**joreveur** · 06/05/2015, 07h45

Bonjour

C'est super votre idée de créer un jeu d'échecs.
Oui on attend "Kempelen v 1.0" ! et j'y crois !
je veux bien jouer quelques parties contre Kempelen et vous noter les coups.
Comme mon niveau est débutant, il devrait me battre assez rapidement. ça vous permettrait peut-être d'améliorer le code.

à vous de me dire et bon courage !

Bonne journée

Création d'un programme d'échecs en Free Pascal

Free Pascal

Discussions similaires

Partager

Partager