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

Version imprimable

Voir 40 message(s) de cette discussion en une page

21/04/2015, 16h42
glegat

Création d'un programme d'échecs en Free Pascal
Après une interruption de plusieurs dizaines d'années (je suis à la retraite !) je reprends goût à la programmation (j'ai débuté comme beaucoup de personnes de ma génération sur un Oric), comme je suis en même temps passionné par les échecs j'ai décidé de programmer un logiciel d'échecs.

Mon projet est dans un premier temps de réaliser un programme simple, sans interface graphique et dont le moteur ne ferait qu'une analyse sur deux demi-coups. Il faudra donc optimisé l'évaluation de la position pour obtenir des réponses cohérentes avec les principes du jeu.

Je m'inspire des programmes développés par Roland Chastain qui a présenté son travail sur ce site "conception d'un jeu d'échecs en Pascal". Je suis loin d'avoir le niveau requis pour réaliser un fort programme (je débute en Pascal), et mon but est simplement d'apprendre le Pascal en réalisant un logiciel sur un thème qui me passionne.

Au fur et à mesure des résultats obtenus, le projet évoluera et on pourra envisager de pousser l'analyse beaucoup plus loin en utilisant le principe de l'Alpha-beta bien connu des programmeurs de jeux d'échecs.

De mon ancienne passion ressuscitée je conserve des livres qui me seront utiles :
- Echecs et C de Yann Takvorian (Initiation à l'analyse et à la programmation du jeu d'échecs)
- Techniques de programmation des jeux de David Lévy
- Chess Skill in man and machine edited by Peter W. Frey
- Computer in Chess de M. Botvinnik
- The Chess computer handbook de David Levy
- Algorithmes for Games de Adelson-Velsky, Ariazarov et donskoy
On pourrait d'ailleurs commencer la discussion par les sources d'information autour de la programmation du jeu d'échecs. Je suis aussi nouveau sur ce forum et ce projet a été commencé très récemment le 15 avril 2015, donc je ne suis pas encore familiarisé avec l'ouverture d'une discussion et j'apporterai des éléments d'informations au fur et à mesure.

Merci à tous de vos contributions.

Gérard
21/04/2015, 16h58
glegat

1 pièce(s) jointe(s)

Début programmation

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:

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.
21/04/2015, 18h27
e-ric

Salut

Bon retour à la programmation et bon courage.

Commencer par un jeu d'échec est un défi, ce n'est pas ce qu'il y a de plus simple.

Cdlt
21/04/2015, 18h56
glegat

1 pièce(s) jointe(s)

Premier résultat

Citation:

Commencer par un jeu d'échec est un défi, ce n'est pas ce qu'il y a de plus simple.

Oui j'en suis conscient et j'espère arriver au bout.

Mais les premiers résultats sont encourageants et je m'amuse déjà comme un fou avec ce que mon programme peut déjà faire.

Voici l'affichage de mes tests actuels. Je saisie au clavier les coups et Kempelen Proto (c'est le nom de mon programme) affiche les coups plausibles en fonction de la position, pour les Blancs et pour les Noirs suivant le trait.

Dans la pièce jointe c'est l'écran de résultat obtenu après la séquence de coups suivante : 1 - e2e4 e7e5 2 - Cg1f3 Cb8c6 3 - Ff1b5

Premier constat, ce qui m'a demandé le plus de mal c'est la génération des coups de pion (à mon sens c'est la pièce la plus difficile à programmer) et encore je n'ai pas terminé la règle de la prise en passant.

Merci de votre intérêt,

Pièce jointe 175588
21/04/2015, 20h14
Alcatîz

Bonjour,

Chouette, un passionné ! :D

Citation:

Envoyé par glegat

Premier constat, ce qui m'a demandé le plus de mal c'est la génération des coups de pion (à mon sens c'est la pièce la plus difficile à programmer)

Ah tiens, voilà qui m'étonne. Quelles difficultés offre le pion par rapport aux autres pièces ?
21/04/2015, 20h48
glegat

Citation:

Ah tiens, voilà qui m'étonne. Quelles difficultés offre le pion par rapport aux autres pièces ?

Le pion est une pièce exceptionnelle dans ses déplacements par rapport aux autres pièces il présente plusieurs particularités :

1 - Il ne recule jamais
2 - Il avance d'une seule case sauf lorsqu'il est dans sa case d'origine il peut dans ce cas avancer d'une ou de deux cases d'un coup sauf s'il y a une pièce (noir ou blanche) située entre sa case départ et sa case d'arrivée.
3 - Son déplacement est modifié lorsqu'il prend une pièce, il avance tout droit mais ne peut prendre que les pièces situées sur les cases diagonales situées à sa gauche et à sa droite
4 - Lorsqu'il arrive sur la dernière rangée il peut se transformer en Dame, Cavalier, Fou, Tour, c'est la seule pièce qui offre cette particularité
5 - La prise en passant : Encore une particularité de prise, lorsqu'un pion adverse avance de deux cases en partant de sa case d'origine et passe par l'une des diagonales contrôlées par le pion il peut prendre le pion après le déplacement de celui-ci . La règle est en elle-même pas facile à expliquer.

Voici pour comparer les règles de déplacement des autres pièces :
Tour : se déplace d'une ou plusieurs cases de manière horizontale ou verticale. Pas de cas particulier
Fou : se déplace d'une ou plusieurs cases en diagonale (uniquement sur les cases de sa couleur). Pas de cas particulier
Roi : se déplace d'une seule case à la fois tout autour de lui, un cas particulier le roque.
Dame : Identique au déplacement du roi mais d'une ou plusieurs cases à la fois. Pas de cas particulier.
Cavalier : se déplace en L (deux cases devant une case sur le coté gauche ou droit ou deux cases sur le coté et une case vers l'avant ou vers l'arrière etc. Pas de cas particulier.

On le voit à l'énoncé de ces règles le pion comporte de nombreuses exceptions à sa règle de base et cela entraine dans la programmation la prise en compte de plusieurs paramètres pour vérifier la validité de toutes ces possibilités. L'autre pièce difficile est le roi à cause du cas particulier du roque.

Les pions sont l'âme des échecs disait Philidor ( compositeur et joueur d'échecs français 1726-1795).

Quelqu'un pourrait-il me conseiller un (ou plusieurs) bons livres sur la programmation en Pascal (j'utilise Free Pascal) ? Accessible pour un faux débutant mais le plus complet possible.

Gérard
21/04/2015, 22h57
yamer

Citation:

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:

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.

Je n'y connais pas grand chose aux échecs et encore moins à la programmation d'un jeu d'échec. Ma question est donc peut être idiote mais, pourquoi utiliser un tableau à une dimension pour représenter un échiquier à deux dimensions ?
21/04/2015, 23h42
glegat

Citation:

Je n'y connais pas grand chose aux échecs et encore moins à la programmation d'un jeu d'échec. Ma question est donc peut être idiote mais, pourquoi utiliser un tableau à une dimension pour représenter un échiquier à deux dimensions ?

En fait je ne maîtrise pas encore bien le Pascal et pour l'instant j'utilise des tableaux simples standards,mais il se trouve que le tableau tdoska119 convient à l'usage que j'en fait et ne pose pas de problème de manipulation pour en retirer l'information souhaitée. De plus j'ai repris l'idée sur d'autres programmes qui utilisent ce même type de tableau.

Si l'échiquier est en deux dimensions chaque case est en fait identifiée par ses coordonnées, la première case s'appelle la case a1 (a coordonnée horizontale et 1 coordonnées verticales) elle correspond à un numéro de case qui est l'indice de la variable, la variable indique quelle pièce est sur la case au cours de la partie (un fou, un pion ou rien dutout etc..) ou tout autre information si on utilise ce même type de tableau pour savoir si une case est contrôlée par l'adversaire etc..., il n'y a pas besoin d'autre forme de représentation.

Avez-vous consulté la pièce jointe représentant le tableau ? Peut-être que cela vous éclairera.

Je comprends le principe de la représentation d'un échiquier par un tableau de 120 entiers mais je ne vois pas l'avantage que ça peut avoir sur un tableau à 2 dimensions.

On peut faire des choses amusantes en pascal. Par exemple :
Code:

1 2 3 4 5 // 3 façons de représenter un échiquier TEchiquier1 = array['a'..'h', 1..8] of integer; TEchiquier2 = array[1..8, 1..8] of integer; TEchiquier3 = array[0..9, -1..10] of integer; // pour avoir des cases extérieures à l'échiquier
Et on peut faire encore bien mieux en utilisant un type énuméré à la place des entiers.

Si vous voulez un bouquin d'initiation au pascal en français et pas cher : Programmer en Turbo Pascal 7.0 de Claude Delannoy. C'est un vieux livre qu'on trouve d'occasion pour moins de 10€ sur amazon ou price minister mais vous y apprendrez à utiliser les tableaux, les types enumérés et les types structurés. Ce sont vraiment des choses à connaître pour écrire des programmes plus simples et plus lisibles. Si vous lisez l'anglais ceci aussi pourrait vous servir : http://code-sd.com/books/startprog/.

Citation:

Envoyé par yamer

Je comprends le principe de la représentation d'un échiquier par un tableau de 120 entiers mais je ne vois pas l'avantage que ça peut avoir sur un tableau à 2 dimensions.

L'un des avantages qu'on peut y voir, c'est une certaine concision dans l'écriture. Exemple d'une façon de trouver toutes les cases que peut atteindre le cavalier :
Code:

1 2 3 4 5 case damier[a] * trait of cCavalier: for i := 1 to 8 do begin b := a + mCavalier[i]; // Une simple addition suffit à obtenir la case d'arrivée
Mais peut-être pourrait-on obtenir la même chose avec un tableau à deux dimensions, en définissant un type coordonnée et en surchargeant l'opérateur + ?
Citation:
Envoyé par yamer
On peut faire des choses amusantes en pascal. Par exemple :
Code:

1 2 3 4 5 // 3 façons de représenter un échiquier TEchiquier1 = array['a'..'h', 1..8] of integer; TEchiquier2 = array[1..8, 1..8] of integer; TEchiquier3 = array[0..9, -1..10] of integer; // pour avoir des cases extérieures à l'échiquier
Et on peut faire encore bien mieux en utilisant un type énuméré à la place des entiers.
J'aime bien la première possibilité. J'avais essayé une fois de commencer un programme sur cette base mais je m'étais vite retrouvé bloqué au moment de faire certaines opérations (par exemple l'équivalent du code que j'ai donné plus haut).

22/04/2015, 07h54
glegat

Citation:

Si vous voulez un bouquin d'initiation au pascal en français et pas cher : Programmer en Turbo Pascal 7.0 de Claude Delannoy. C'est un vieux livre qu'on trouve d'occasion pour moins de 10€ sur amazon ou price minister mais vous y apprendrez à utiliser les tableaux, les types enumérés et les types structurés. Ce sont vraiment des choses à connaître pour écrire des programmes plus simples et plus lisibles. Si vous lisez l'anglais ceci aussi pourrait vous servir : http://code-sd.com/books/startprog/.

Pour la question sur le tableau Roland Chastaing a mieux répondu que je ne saurai le faire.

Merci pour les références des bouquins et notamment celui téléchargeable gratuitement qui est sans doute exactement ce que je cherchais et même si je ne maitrise pas bien l'anglais il me rendra service.
22/04/2015, 09h09
yamer
Citation:
Envoyé par Roland Chastain

L'un des avantages qu'on peut y voir, c'est une certaine concision dans l'écriture. Exemple d'une façon de trouver toutes les cases que peut atteindre le cavalier :

Code:

1 2 3 4 5 case damier[a] * trait of cCavalier: for i := 1 to 8 do begin b := a + mCavalier[i]; // Une simple addition suffit à obtenir la case d'arrivée
Dans cet exemple précis, on peut y voir un avantage. Mais cette façon de faire doit quand même nécessiter pas mal de conversions des coordonnées 2D vers le numéro de case ou du numéro de case vers les coordonnées 2D.

Et on pourrait aussi imaginer représenter les coordonnées de cases et les déplacement par un type vecteur et écrire une fonction d'addition de vecteurs.
Code:

1 2 3 4 5 6 7 8 type TVecteur = record X, Y: Integer; end; var A, B : TVecteur; begin B := AdditionVecteurs(A, mCavalier[i]); // Bien sûr mCavalier devient un tableau de TVecteur
Je ne connais pas les contraintes des la programmation d'un jeu d'échecs mais ma première impression est que le tableau à une seule dimension doit vous conduire à faire pas mal de contorsions...
22/04/2015, 10h41
Roland Chastain

Citation:

Envoyé par yamer

Dans cet exemple précis, on peut y voir un avantage. Mais cette façon de faire doit quand même nécessiter pas mal de conversions des coordonnées 2D vers le numéro de case ou du numéro de case vers les coordonnées 2D.

C'est vrai. Cela dit, en adoptant le système que j'ai expliqué dans ce message, on peut obtenir x par i div 10 et y par i mod 10, ce qui est amusant (si l'on veut). Toujours suivant le même système, un coup peut être représenté par un seul nombre, par exemple 5254 pour "e2e4", ce qui peut aussi être un avantage lorsqu'on a besoin d'économiser de la mémoire. Mais remarquez bien que je ne défends pas à tout prix ce système : ce que j'en dis, c'est seulement pour essayer de faire le tour du sujet.

Citation:

Envoyé par yamer

Et on pourrait aussi imaginer représenter les coordonnées de cases et les déplacement par un type vecteur et écrire une fonction d'addition de vecteurs.

Oui, et j'aime bien ton exemple. Dans le même esprit, j'avais pensé à surcharger l'opérateur + : je ne sais plus trop si c'est possible en Pascal, mais de toute façon ça n'apporterait pas grand chose de plus.

Pour faciliter les problèmes de conversion numéro de case vers coordonnées de la case n'est-il pas opportun de créer un tableau contenant le nom des cases, l'indice du tableau utilisé pour mémoriser l'emplacement des pièces est également utilisé pour ce tableau des coordonnées. J'utilise ce procédé dans mon programme et cela m'a simplifié les choses.
Code:

1 2 3 4 5 6 7 8 9 Const NomCase : Array[20..98] Of String = ('','a1','b1','c1','d1','e1','f1','g1','h1','', '','a2','b2','c2','d2','e2','f2','g2','h2','', '','a3','b3','c3','d3','e3','f3','g3','h3','', '','a4','b4','c4','d4','e4','f4','g4','h4','', '','a5','b5','c5','d5','e5','f5','g5','h5','', '','a6','b6','c6','d6','e6','f6','g6','h6','', '','a7','b7','c7','d7','e7','f7','g7','h7','', '','a8','b8','c8','d8','e8','f8','g8','h8');

22/04/2015, 11h48
Roland Chastain

Citation:

Envoyé par glegat

Pour faciliter les problèmes de conversion numéro de case vers coordonnées de la case n'est-il pas opportun de créer un tableau contenant le nom des cases, l'indice du tableau utilisé pour mémoriser l'emplacement des pièces est également utilisé pour ce tableau des coordonnées.

Personnellement, je dirais que c'est une bonne idée, parce que c'est plus rapide qu'une fonction. Par contre, si je peux me permettre un petit conseil, ou même deux, je donnerais au tableau de chaîne la même étendue qu'à l'échiquier, même si à première vue ça ne sert à rien, et pour les chaînes correspondant aux cases hors de l'échiquier, au lieu de les laisser vides, je mettrais par exemple '00', même si à première vue etc. Autrement il finira toujours par arriver un moment où le programme essaiera d'accéder à une chaîne qui n'existe pas, ou à un caractère qui n'existe pas, et le programme se plantera sans que vous sachiez pourquoi ; alors que si vous voyez sortir des 0 vous comprendrez tout de suite ce qui se passe.

Citation:

Envoyé par Roland Chastain

Dans le même esprit, j'avais pensé à surcharger l'opérateur + : je ne sais plus trop si c'est possible en Pascal, mais de toute façon ça n'apporterait pas grand chose de plus.

Effectivement c'est possible.

Code:

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
 
(* http://www.freepascal.org/docs-html/ref/refch15.html *)
 
(*
  Operator overloading is, in essence, v1 powerful notational tool; but it is
  also not more than that, since the same results can be obtained with regular
  function calls.
  
  La surcharge des opérateurs est une technique d'écriture très efficace ; mais
  ce n'est rien de plus, les mêmes résultats pouvant toujours être obtenus au
  moyen d'une fonction ordinaire.
*)
 
program SurchargeOperateur;
{$MODE OBJFPC}
 
type
  TVecteur = record
    x, y: integer;
  end;
 
operator + (v1, v2: TVecteur) v3: TVecteur;
begin
  v3.x := v1.x + v2.x;
  v3.y := v1.y + v2.y;
end;
 
operator = (v1, v2: TVecteur) b: Boolean;
begin
  b := (v1.x = v2.x) and (v1.y = v2.y);
end;
 
const
  a: TVecteur = (x: 1; y: 1);
  b: TVecteur = (x: 2; y: -1);
 
var
  c, d: TVecteur;
 
begin
  c := a + b;
 
  WriteLn(c.x = 3);
  WriteLn(c.y = 0);
 
  d := c;
 
  WriteLn(d = c);
 
  Write('Appuyez sur Entr'#130'e...');
  ReadLn;
end.

22/04/2015, 13h25
glegat

Citation:

je donnerais au tableau de chaîne la même étendue qu'à l'échiquier, même si à première vue ça ne sert à rien, et pour les chaînes correspondant aux cases hors de l'échiquier, au lieu de les laisser vides, je mettrais par exemple '00', même si à première vue etc. Autrement il finira toujours par arriver un moment où le programme essaiera d'accéder à une chaîne qui n'existe pas, ou à un caractère qui n'existe pas, et le programme se plantera sans que vous sachiez pourquoi ; alors que si vous voyez sortir des 0 vous comprendrez tout de suite ce qui se passe.

Bien vu ! Merci
23/04/2015, 10h30
glegat

Kempelen proto est maintenant capable de recevoir au clavier les coups d'une partie et de générer après chaque coup la liste des réponses légales de l'adversaire. Cette liste comporte tous les coups légaux, reste le cas de la prise en passant à traiter, je peux différer l'intégration de cette règle pour l'instant le plus important est de bien valider mon générateur.

En faisant de nombreux tests j'ai retrouvé des bugs très vicieux mais facile à réparer une fois trouvé (variable non remise à zéro = erreur de débutant), quand je trouve une anomalie de fonctionnement je panique, mais finalement tout est rentré dans l'ordre.

Il me semble important avant d'aller plus loin de poursuivre mes tests de manière exhaustive en imaginant tous les cas de figure possible, car il ne s'agit pas dans 15 jours de constater un bug dans le générateur, je n'aurais plus à l'esprit la manière dont j'ai travaillé et cela demandera plus de temps pour des corrections. Je veux donc valider à 101% mon générateur avant d'aller plus loin.

Concernant le roque toutes les règles sont bien validées cependant il en reste une particulière c'est la vérification que les cases de passage et d'arrivée du roi ne sont pas contrôlées par une pièce adverse (idem l'échec au roi). Je pense que je ne peux intégrer ce contrôle que lorsque j'aurai créer une procédure de repérage des cases contrôlées. Cette procédure me servira d'ailleurs pour évaluer la position (avec d'autres critères).

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. Ainsi dans la position de départ le nombre de déplacement autorisé pour les Blancs est de 20, mais le nombre de cases contrôlées est de 22, les blancs contrôlent toutes les cases de la troisième rangée, tous les pions sont contrôlés par les pièces et chaque pièce et contrôlée par une autre pièce sauf les tours qui sont les seules pièces à être en position de départ sur une cas non contrôlée par les Blancs (me trompe-je ?).

Le générateur des cases contrôlées doit tenir compte de toutes les cases sur lesquelles une pièce peut se déplacer, même si cette case est occupée par une pièce de même couleur, ou même si la prise n'est pas encore autorisée par l'absence de pièce adverse (cas de la prise en diagonale du pion), alors que le générateur de coup plausible ne retient que les cases ou les pièces au trait peuvent se déplacer d'un point de vu strictement conforme aux règles du jeu au regard de la position étudiée à l'instant t.

Ce distinguo est-il correct ou ne suis-je pas déjà en train de m'égarer ?. Je vais réfléchir à cela tout en testant mon générateur.

La suite à dans quelques jours (car aujourd'hui j'ai reçu par la poste "Programmer en Turbo Pascal 7" de Claude Delannoy) et je vais peut-être comprendre pourquoi mon programme fonctionne (pour l'instant).
23/04/2015, 13h45
e-ric

Citation:

En faisant de nombreux tests j'ai retrouvé des bugs très vicieux mais facile à réparer une fois trouvé (variable non remise à zéro = erreur de débutant), quand je trouve une anomalie de fonctionnement je panique, mais finalement tout est rentré dans l'ordre.

Pas de panique, on respire et on réfléchit;)

Citation:

Il me semble important avant d'aller plus loin de poursuivre mes tests de manière exhaustive en imaginant tous les cas de figure possible, car il ne s'agit pas dans 15 jours de constater un bug dans le générateur, je n'aurais plus à l'esprit la manière dont j'ai travaillé et cela demandera plus de temps pour des corrections. Je veux donc valider à 101% mon générateur avant d'aller plus loin.

tu devrais essayer de monter un projet de tests unitaires automatisés, c'est pratique pour vérifier l'absence de régressions, enfin comme le pensait Dijkstra, pour révéler les bugs les plus évidents... ("Testing shows the presence, not the absence of bugs")

Pour la suite, mieux vaut laisser parler des spécialistes des échecs tels Roland.

En tout cas, bonne suite.
23/04/2015, 14h47
glegat

Citation:

tu devrais essayer de monter un projet de tests unitaires automatisés, c'est pratique pour vérifier l'absence de régressions

C'est encore trop pointu pour moi ! Pour l'instant je saisie des parties d'échecs et je vérifie que les coups proposés en réponse sont légaux, c'est manuel mais pas déplaisant car chaque coup joué correctement par mon programme me donne 1 bon point (et quand j'aurais assez de bon point j'aurais droit à un cadeau j'espère). C'est la méthode ancienne mais faut dire que je suis un ancien.

Voir 40 message(s) de cette discussion en une page